akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

using Int = ll;

Int getLength(ll n) {
    Int len = 0;
    ll fb = 0, f = 0, b = 0;
    for (ll m = 1, d = 1; m <= n; m *= 10, ++d) {
        if (m * 10 - 1 <= n) {
            ll fbnext = (m * 10 - 1) / 15, fnext = (m * 10 - 1) / 3 - fbnext, bnext = (m * 10 - 1) / 5 - fbnext;
            len += (Int)8 * (fbnext - fb)
                + (Int)4 * (fnext - f)
                + (Int)4 * (bnext - b)
                + (Int)d * (9 * m - (fbnext - fb) - (fnext - f) - (bnext - b));

            fb = fbnext;
            f = fnext;
            b = bnext;
        }
        else {
            ll fbnext = n / 15, fnext = n / 3 - fbnext, bnext = n / 5 - fbnext;
            len += (Int)8 * (fbnext - fb)
                + (Int)4 * (fnext - f)
                + (Int)4 * (bnext - b)
                + (Int)d * (n - m + 1 - (fbnext - fb) - (fnext - f) - (bnext - b));
        }
    }

    return len;
}

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

    ll low = 0, high = 1e17;
    while (high - low > 1) {
        ll mid = (low + high) / 2;
        Int l = getLength(mid);

        if (l < s) low = mid;
        else high = mid;
    }

    string S;
    for (ll i = low + 1; i < low + 20; ++i) {
        S += i % 15 ? i % 5 ? i % 3 ? to_string(i) : "Fizz" : "Buzz" : "FizzBuzz";
    }

    cout << S.substr(s - getLength(low) - 1, 20) << endl;
}


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

namespace AtCorder
{
	public class Program
	{
		static void Main(string[] args)
		{
			Scanner cin = new Scanner();
			long a = cin.Long();
			long b = cin.Long();

			var ap = GetPrimeFactor(a);
			var bp = GetPrimeFactor(b);

			var set = new HashSet<long>();
			foreach (long app in ap) {
				if (bp.Contains(app)) {
					set.Add(app);
				}
			}

			Console.WriteLine(set.Count() + 1);
		}

		public static HashSet<long> GetPrimeFactor(long value)
		{
			long temp = value;
			long max = (long)Math.Ceiling(Math.Sqrt(temp));
			var factors = new HashSet<long>();
			for (int i = 2; i <= max; ++i) {
				if (temp % i == 0) {
					factors.Add(i);
					while (temp % i == 0) {
						temp /= i;
					}
				}
			}

			if (temp != 1) {
				factors.Add(temp);
			}

			return factors;
		}
	}

	public class Scanner
	{
		private readonly char[] delimiter_ = new char[] { ' ' };
		private string[] buf_;
		private int index_;

		public Scanner()
		{
			buf_ = new string[0];
			index_ = 0;
		}

		public string Next()
		{
			if (index_ < buf_.Length) {
				return buf_[index_++];
			}

			string st = Console.ReadLine();
			while (st == "") {
				st = Console.ReadLine();
			}

			buf_ = st.Split(delimiter_, StringSplitOptions.RemoveEmptyEntries);
			if (buf_.Length == 0) {
				return Next();
			}

			index_ = 0;
			return buf_[index_++];
		}

		public int Int() => int.Parse(Next());
		public long Long() => long.Parse(Next());
		public double Double() => double.Parse(Next());

		public int[] ArrayInt(int N, int add = 0)
		{
			int[] Array = new int[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Int() + add;
			}
			return Array;
		}

		public long[] ArrayLong(int N, long add = 0)
		{
			long[] Array = new long[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Long() + add;
			}
			return Array;
		}

		public double[] ArrayDouble(int N, double add = 0)
		{
			double[] Array = new double[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Double() + add;
			}
			return Array;
		}
	}
}

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

int main() {
  int x,a,b;
  cin >> x >> a >> b;
  if (abs(x-a)>=abs(x-b)) {
    cout<< "B" << endl;/* code */
  }
  else{
    cout<< "A" << endl;
  }  
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

class UnionFind {
    int n;
    vector<int> uni;
public:
    explicit UnionFind(int n) : uni(static_cast<u32>(n), -1) , n(n){};

    int root(int a){
        if (uni[a] < 0) return a;
        else return (uni[a] = root(uni[a]));
    }

    bool unite(int a, int b) {
        a = root(a);
        b = root(b);
        if(a == b) return false;
        if(uni[a] > uni[b]) swap(a, b);
        uni[a] += uni[b];
        uni[b] = a;
        return true;
    }
    
    int size(int i){ return -uni[root(i)]; }
    bool same(int a, int b) { return root(a) == root(b); }
};

int main() {
   int n;
   cin >> n;
   UnionFind uf(100001);
   vector<vector<int>> v(100001), u(100001);
   
    for (int i = 0; i < n; ++i) {
        int x, y;
        scanf("%d %d", &x, &y);
        v[x].emplace_back(y);
        u[y].emplace_back(x);
    }
    vector<int> dp(100001);
    for (int i = 1; i <= 100000; ++i) {
        for (int j = 0; j+1 < u[i].size(); ++j) {
            uf.unite(u[i][j], u[i][j+1]);
        }
    }
    for (int i = 1; i <= 100000; ++i) {
        int j = uf.root(i);
        if(i != j){
            for (auto &&k : v[i]) {
                v[j].emplace_back(k);
            }
        }
    }
    ll ans = -n;
    for (int i = 1; i <= 100000; ++i) {
        if(i == uf.root(i)){
            sort(v[i].begin(), v[i].end());
            v[i].erase(unique(v[i].begin(), v[i].end()), v[i].end());
            ans += (ll)v[i].size()*uf.size(i);
        }
    }
    cout << ans << "\n";

   return 0;
}

Measured memory_bytes: 9472
import bisect
N = int(input())
A = [int(input()) for _ in range(N)]
b = []
for a in A[::-1]:
  idx = bisect.bisect_right(b, a)
  if len(b) <= idx:
    b.append(a)
  else:
    b[idx] = a

print(len(b))


Measured memory_bytes: 56152
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<utility>

using namespace std;

#define int long long
#define endl "\n"

constexpr long long INF = (long long)1e18;
constexpr long long MOD = 1'000'000'007; 

struct fast_io {
	fast_io(){
		std::cin.tie(nullptr);
		std::ios::sync_with_stdio(false);
	};
} fio;

signed main(){
	cout<<fixed<<setprecision(10);
	
	vector<vector<int>> table;
	vector<vector<vector<int>>> dp;
	int R, C, K;
	
	cin>>R>>C>>K;
	
	table.resize(R, vector<int>(C));
	dp.resize(4, vector<vector<int>>(R+1, vector<int>(C+1)));
	
	for(int i = 0; i < K; i++){
		int r, c, v;
		
		cin>>r>>c>>v;
		
		r--, c--;
		
		table[r][c] = v;
	}
	
	for(int i = 0; i < R; i++){
		for(int j = 0; j < C; j++){
			for(int k = 0; k <= 3; k++){
				dp[0][i+1][j] = max(dp[0][i+1][j], dp[k][i][j]);
				dp[k][i][j+1] = max(dp[k][i][j+1], dp[k][i][j]);
				
				if(k <= 2 && table[i][j]) {
					dp[0][i+1][j] = max(dp[0][i+1][j], dp[k][i][j] + table[i][j]);
					dp[k+1][i][j+1] = max(dp[k+1][i][j+1], dp[k][i][j] + table[i][j]);
				}
			}
		}
	}
	
	cout<<max(max(dp[0][R][C-1],dp[1][R][C-1]),max(dp[2][R][C-1],dp[3][R][C-1]))<<endl;
	
	return 0;
}

Measured memory_bytes: 425652
#include <stdio.h>

int main(void)
{	
	int build[4][3][10]= {0};
	int i, j, p;
	for( i = 0;i < 4; i++)
	{
		for( j = 0;j < 3; j++)
		{
			for ( p = 0;p < 10; p++)
			{
				build[4][3][10];
				if (p >= 9)
				{
					build[i][j][p] = 0;
				}					
			}
		}
	}
	
	int n = 0;
	scanf("%d", &n);
	while(n--)
	{
		int b, f, r, v;
		scanf("%d %d %d %d", &b, &f, &r, &v);
		build[b-1][f-1][r-1]+=v;
	}
	
	for( i = 0;i < 4; i++)
	{
		for( j = 0;j < 3; j++)
		{
			for ( p = 0;p < 10; p++)
			{
				
					printf(" %d", build[i][j][p]);
			}
			printf("\n");
		}
		if (i != 3)
		{
			printf("####################\n");
		}
	}		
	return 0;
 } 



Measured memory_bytes: 2732
import java.io.BufferedReader;
import java.io.*;
import java.util.*;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Collections;
import java.util.Arrays;

public class Main {
	public static void main(final String[] args){
    
    Scanner sc = new Scanner(System.in);
    
    int t = sc.nextInt();
    int x = sc.nextInt();

    System.out.println((double)t/x);








    

    
    

    


    
    


    


    
    


    
	}
}

Measured memory_bytes: 35892
#include "bits/stdc++.h"
using namespace std;
int main(){
  string s, str;
  cin >> s;
  int count = 0;
  if(s.length()%2==1){
    str = s.substr(0,s.length()/2);
    s = s.substr(s.length()/2+1,s.length());
  }
  else {
    str = s.substr(0,s.length()/2);
    s = s.substr(s.length()/2,s.length());
  }
  
  //cout << str << " " << s << endl;
  
  reverse(str.begin(),str.end());
  
  //cout << str << " " << s << endl;
  
  for(int i = 0;i<str.length();i++){
    if(str.substr(i,i+1) != s.substr(i,i+1)){
      
      if(s.substr(i,i+1).length() != 1){
        if(s.substr(i,i+1).substr(0,1) != str.substr(i,i+1).substr(0,1)){
          count++;
        }
        continue;
      }
      
      //cout << str.substr(i,i+1) << " " << s.substr(i,i+1) << " i " << i << endl;
      
      count++;
      //cout << endl << str.substr(i,i+1) << endl <<  s.substr(i,i+1) << endl;
    }
  }
  cout << count;
}

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

using namespace std;

#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL 9223372036854775
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define MOD 1000000007
#define MOD9 998244353
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double

#define int long long

using II = pair<int, int>;

int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }
int extgcd(int a, int b, int &x, int &y) { int g = a; x = 1; y = 0; if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x; return g; }

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(a)  begin((a)), end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

const int MAX_N = 100005;
int N, K;
vector<int> edges[MAX_N];

int solve(int pos, int kk, int pre = -1) 
{
  int ret = 1;
  int k = 1;
  if(kk <= 0) return 0;
  
  for(int next : edges[pos]) {
    if(next == pre) continue;
    ret *= solve(next, K-2, pos); ret %= MOD;
    k *= kk; kk--; k %= MOD;
  }

  return (ret * k) % MOD;
}

signed main()
{
  cin >> N >> K;
  if(N == 1) {
    cout << K << endl;
    return 0;
  } else if(N == 2) {
    cout << K*(K-1)%MOD << endl;
    return 0;
  }
  REP(n,N-1) {
    int a, b; cin >> a >> b; a--; b--;
    edges[a].push_back(b);
    edges[b].push_back(a);
  }

  cout << (solve(0, K-1, 0) * K) % MOD << endl;

  return 0;
}


Measured memory_bytes: 11520
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <queue>
using ll = long long;
using graph = std::vector<std::vector<ll>>;

using namespace std;

int main() {
    ll K;
    cin >> K;
    ll A[K];
    for(ll i = 0; i < K; i++){
        cin >> A[i];
    }
    ll m = 2;
    ll M = 2;
    for(ll i = K - 1; i >= 0; i--){
        m = ceil((double)m / (double)A[i]) * A[i];
        M = floor((double)M / (double)A[i]) * A[i] +  (A[i] - 1);
        if(ceil((double)M / (double)A[i]) == floor((double)m / (double)A[i])){
            cout << "-1" << endl;
            return 0;
        }
    }

    cout << m <<" " << M << endl;
}


Measured memory_bytes: 1024
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <regex>
#define rep(i,n) for(int i = 0; i < n; i++)
#define reps(i,j,n) for(int i = j; i < n; i++)
#define rrep(i,j,n) for(int i = j-1; i >= n; i--)
#define prec(n) fixed << setprecision(n)
#define print_array(v) rep(__k, v.size()) { cout << v[__k]; if(__k != v.size()-1) cout << " "; else cout << endl; }
#define YesorNo(a) printf(a?"Yes\n":"No\n")
#define fi first
#define se second
#define endl "\n"
using namespace std;

//constexpr int inf = 2147483647;
//constexpr int64_t inf64 = 9223372036854775807;
//constexpr int mod = 1e9+7;

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

  int64_t x, y;
  cin >> x >> y;

  int res = 0;
  while (true) {
    if (x > y) {
      cout <<  res << endl;
      return 0;
    }
    res++;
    x *= 2;
  }
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,ans,a[200001],e[200001],nt[200001],hd[200001],tot;
void build(int t,int k){
	tot++;
	e[tot]=k;
	nt[tot]=hd[t];hd[t]=tot;
}
int dfs(int x,int dep){
	int i,mx=dep;
	for(i=hd[x];i;i=nt[i])mx=max(mx,dfs(e[i],dep+1));
	if(a[x]!=1&&mx-dep==m-1)ans++,mx=0;
	return mx;
}
int main(){
	int i;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	if(a[1]!=1)ans=a[1]=1;
	for(i=2;i<=n;i++)build(a[i],i);
	dfs(1,0);
	printf("%d",ans);
}

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

using ll = long long;
using pii = pair<int, int>;

#define vt          vector
#define sz(x)       (int)(x).size()
#define all(x)      (x).begin(), (x).end()
#define rall(x)     (x).rbegin(), (x).rend()
#define fi          first
#define se          second

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

    int n, m;
    cin >> n >> m;
    cout << n * (n - 1) / 2 + m * (m - 1) / 2;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define REP(i,n) for(long long i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
const double PI = acos(-1);
const double EPS = 1e-15;
long long INF=(long long)1E17;
#define i_7 (long long)(1E9+7)
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
using namespace std;
long long po(long a, long b){
    if(b==0){
        return 1;
    }
    
    long long z = po(a,b/2);
    z = mod(z*z);
    if(b%2!=0){
        z = mod(a*z);
    }
    return z;
}

int main(){
  string l;
  cin>>l;
  long long n=l.size();
  long long ans=0;
  long long temp=0;
  REP(i,n){
    if(l[i]=='1'){
      ans = mod(ans + mod(po(3,n-i-1)*po(2,temp)));
      temp++;
    }else{
      continue;
    }
  }
  ans = mod(ans + po(2,temp));
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 512
k = int(input())
if k % 2 == 0 or k % 5 == 0:
  print(-1)
else:
  t = 7
  for i in range(1, k+1):
    if t % k == 0:
      print(i)
      break
    t += 7 * pow(10, i, k)
    t %= k
  else:
    print(-1)

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

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

  int count = 0;
  unsigned int i = 0;

  char c = 0;
  c = s[i];
  while(i < s.length()){
    if(s[i] != c) {count++; c = s[i];}
    i++;
  }
  std::cout << count << std::endl;
}


Measured memory_bytes: 512
import sys
import numpy as np

n = int(sys.stdin.readline().rstrip())
res = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(n, 2)

def main():
  for i in range(n - 1):
    res[i+1] *= ((res[i] + res[i+1] - 1) // res[i+1]).max()
  print(res[n-1].sum())
  
if __name__ ==  '__main__':
  main()

Measured memory_bytes: 13828
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;
using ll = long long;

#define EPS (1e-7)

int main() {
  ll H, W;
  cin >> H >> W;
  if (H == 1 || W == 1) {
    cout << 1 << endl;
    return 0;
  }
  ll ans = H * W / 2;
  if ((H % 2 != 0) && (W % 2 != 0)) {
    ans++;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i,a,b) for (ll i=(a);i<(ll)b; i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define INF 1LL << 60
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll,ll> p;
const long long MOD=1000000007;

// vector<p> cut(M); vector<vector<ll> > v(4);
// cut[i].second
// cut[i].first;
// REP(i,M){
//     int a,b;cin>>a>>b;
//     cut[i] = make_pair(b,a);//last first の順番
// }
// for(int i=0; i<N;i++){
// }
// sort(cut.begin(),cut.end()), sort(v.rbegin(), v.rend()); //sort
// char '' str ""
int main(void)
{
    int a,b,c;cin>>a>>b>>c;
    int cnt = c -(a-b);
    cnt = max(cnt, 0);
    cout<<cnt<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

struct Point {
	int x, y;
	bool operator < (const Point & b) const{
		return x < b.x;
	}
};
Point ab[110];
Point cd[110];
bool use[110];
int main()
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> ab[i].x >> ab[i].y;
	}
	for (int i = 0; i < N; i++) {
		cin >> cd[i].x >> cd[i].y;
	}
	sort(cd, cd + N);
	int ans = 0;
	for (int i = 0; i < N; i++) {
		int num = -1;
		int point = -1;
		for (int j = 0; j < N; j++) {
			if (!use[j]) {
				if (ab[j].x < cd[i].x && ab[j].y < cd[i].y) {
					if (ab[j].y > num) {
						num = ab[j].y;
						point = j;
					}
				}
			}
		}
		if (point != -1) {
			use[point] = true;
			ans++;
		}
	}
	cout << ans << endl;
}


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

using ll = long long;
using P = pair<int, int>;

const int INF = 1e9;
const int MOD = 1e9 + 7;

ll dp[1010][1010];
char c[1010][1010];

int main() {
  int H, W;
  cin >> H >> W;
  for (int i = 1; i <= H; i++) for (int j = 1; j <= W; j++) cin >> c[i][j];

  dp[1][1] = 1;
  for (int i = 1; i <= H; i++) {
    for (int j = 1; j <= W; j++) {
      if (i == 1 && j == 1) continue;
      if (c[i][j] == '#') continue;
      dp[i][j] = dp[i-1][j] + dp[i][j-1];
      dp[i][j] %= MOD;
    }
  }

  cout << dp[H][W] << endl;
  return 0;
}


Measured memory_bytes: 9088
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i, n) FOR(i,0,n)

int main(void){
    ll A,B,N;
    cin >> A >> B >> N;
    ll ans = min(N,B-1);
    ans = floor(ans * A / B) - A * floor(ans/B);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3644
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
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;}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
typedef pair<ll,ll> l_l;
typedef pair<int,int> i_i;
const ll mod=1e9+7;
const int inf=1<<30;

ll dp[100005][105][2];

int main() {
  int D; string s;
  cin >> s >> D;
  int n=s.size();
  dp[0][0][0]=1ll;
  rep(i,n)rep(j,D)rep(k,2){
    int nd=s[i]-'0';
    rep(d,10){
      int ni=i+1,nj=j,nk=k;
      nj=(nj+d)%D;
      if(k==0){
        if(d>nd) continue;
        if(d<nd) nk=1;
      }
      dp[ni][nj][nk]+=dp[i][j][k];
      dp[ni][nj][nk]%=mod;
    }
  }
  ll ans=(dp[n][0][0]+dp[n][0][1])%mod;
  ans--;
  if(ans<0) ans+=mod;
  cout << ans << endl;
}


Measured memory_bytes: 18688
#include <iostream>
#include <queue>
#include <set>
#include <vector>
using namespace std;
vector<int> array;
void solve(int n, int m) {
	if (n == 0) {
		vector<int>::iterator it = array.begin();
		int init = 1;
		while (it != array.end()) {
			if (init) {
				init = 0;
			} else {
				cout << " ";
			}
			cout << *it;
			it++;
		}
		cout << endl;
		return;
	}
	for (int i = 0; i < m; i++) {
		if (n - m + i >= 0) {
			array.push_back(m - i);
			solve(n - m + i, m - i);
			array.pop_back();
		}
	}
}
int main() {
	int n;
	while (cin >> n,n) {
		array.clear();
		solve(n, n);
	}
	return 0;
}

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

int main() {
    ll n,a,b,ans = 10000000,an,bn;
    cin >> n;
    for(ll i=1;;i++){
        an = 0;
        bn = 0;
        a = i;
        b = n / a;
        if(a>b)break;
        if(n != a*b)continue;
        while(a>0){
            a/=10;
            an++;
        }
        while(b>0){
            b/=10;
            bn++;
        }
        ll hoge = max(an,bn);
        ans = min(hoge,ans);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define MAXN 100005
#define INF 1000000000
#define MOD 1000000007
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int n,k,a[MAXN];
int gcd(int a,int b)
{
	if(b==0) return a;
	return gcd(b,a%b);
}
int main()
{
	scanf("%d",&n);
	if(n==3)
	{
		puts("2 5 63");
		return 0;
	}
	set<int> s;
	s.insert(2);
	s.insert(3);
	s.insert(4);
	s.insert(9);
	n-=4;
	if(n>14998)
	{
		for(int i=15;i<=29997;i+=12)
		{
			if(n<=14998) break;
			s.insert(i);
			s.insert(i+6);
			n-=2;
		}
	}
	if(n>5000)
	{
		for(int i=8;i<=29996;i+=6)
		{
			s.insert(i);
			s.insert(i+2);
			n-=2;
			if(n<=5000) break;
		}
	}
	for(int i=6;i<=30000;i+=6)
	{
		if(n==0) break;
		s.insert(i);
		n--;
	}
	for(auto it=s.begin();it!=s.end();it++)
		printf("%d ",*it);
	puts("");
	return 0;
}

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

int main() {
  int n;
  cin >> n;
  vector<int> t(n);
  rep(i, n) cin >> t[i];
  int m;
  cin >> m;
  vector<pair<int, int>> v(m);
  rep(i, m) {
    cin >> v[i].first >> v[i].second;
    v[i].first--;
  }
  rep(i, m) {
    int sum = 0;
    rep(j, n) {
      if (v[i].first == j) {
        sum += v[i].second;
      }
      else {
        sum += t[j];
      }
    }
    cout << sum << endl;
  }
  return 0;
}

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

typedef pair<int,int> P;

int N, a[200005];
vector<P> A; // firstの値がsecond個

void push(int x){ // a[i-1] < a[i]
  
  if( (int)A.size() != 0 && A[(int)A.size()-1].first == 1 ){
    A[(int)A.size()-1].second += x;
    return;
  }
  
  A.push_back( P( 1, x ) );
  
}

void pop(int x){ // a[i-1] > a[i]
  
  while(x){
    
    if( A[(int)A.size()-1].second <= x ){
      x -= A[(int)A.size()-1].second;
      A.pop_back();
    }
    else{
      A[(int)A.size()-1].second -= x;
      x = 0;
    }
    
  }
  
}

bool add(int x){ // a[i-1] = a[i]
  
  if( A.size() == 1 && A[0].first == x ) return false;  
  
  if( A[(int)A.size()-1].first == x ){
    
    int cnt = A[(int)A.size()-1].second;
    
    A.pop_back();
    
    int num = A[(int)A.size()-1].first;
    int cnt2 = A[(int)A.size()-1].second - 1;
    
    A.pop_back();
    
    if( cnt2 ) A.push_back( P( num, cnt2 ) );
    
    if( cnt2 == 0 && A.size() != 0 && A[(int)A.size()-1].first == num + 1 ){
      A[(int)A.size()-1].second++;
    }
    else A.push_back( P( num + 1, 1 ) );
    
    A.push_back( P( 1, cnt ) );
    
  }
  else{
    
    int num = A[(int)A.size()-1].first;
    int cnt = A[(int)A.size()-1].second - 1;
    
    A.pop_back();
    
    if( cnt ) A.push_back( P( num, cnt ) );
    
    if( cnt == 0 && (int)A.size() != 0 && A[(int)A.size()-1].first == num + 1 ){
      A[(int)A.size()-1].second++;
    }
    else A.push_back( P( num + 1, 1 ) );
    
  }
  
  return true;
}

bool check(int x){
  
  int pre = 0;
  
  for(int i=0;i<N;i++){
    
    if( pre < a[i] ) push( a[i] - pre );
    if( pre >= a[i] ){
      pop( pre - a[i] );
      if( add( x ) == false ) return false;
    }
    
    pre = a[i];
        
  }
  
  return true;
}

void solve(){
  
  if( check( 1 ) == true ){
    cout<<1<<endl;
    return;
  }
  
  int l = 1, r = 3e5;
  
  while( l + 1 < r ){
    
    int m = ( l + r ) / 2;
    
    A.clear();
    
    if( check( m ) == false ) l = m;
    else r = m;
    
  }
  
  cout<<r<<endl;
  
}

signed main(){
  
  cin>>N;
  
  for(int i=0;i<N;i++) cin>>a[i];
  
  solve();
  
  return 0;
}


Measured memory_bytes: 1792
A, B, C, X, Y = map(int, input().split())

ans = 10 ** 9
for i in range(10 ** 5 + 1):
    tmp = 2 * i * C + max(X - i, 0) * A + max(Y - i, 0) * B
    ans = min(ans, tmp)

print(ans)


Measured memory_bytes: 2940
#include <stdio.h>
#include <stdbool.h>
#include <string.h>

int max(int a[], int n) {
  int i, m = 1;
  for(i = 2; i < n; i ++) {
    if(a[m] < a[i]) { m = i; }
  }

  return m;
}

int main() {
  int n;
  int mon[1000], day[1000], hou[1000], min[1000];
  char IO[1000][2];
  int id[1000];
  int time[2][1000];
  int total[1000];

  while(true) {
    scanf("%d", &n);
    if(n == 0) break;

    int i, j;
    for(i = 0; i < n; i ++) {
      scanf("%d/%d %d:%d %c %d", &mon[i], &day[i], &hou[i], &min[i], IO[i], &id[i]);
    }
    for(i = 0; i < 1000; i ++) {
      time[0][i] = 0;
      time[1][i] = 0;
      total[i] = 0;
    }

    bool god_flg = false;
    int in_flg[1000] = {0};
    for(i = 0; i < n; i ++) {
      if(id[i] == 0 && IO[i][0] == 'I') {
	god_flg = true;
	for(j = 0; j < 1000; j ++) {
	  time[0][j] = hou[i]*60 + min[i];
	}
      }
      else if(id[i] == 0 && IO[i][0] == 'O') {
	god_flg = false;
	for(j = 0; j < 1000; j ++) {
	  total[j] += in_flg[j]*(hou[i]*60 + min[i] - time[0][j]);
	}
      }
      else if(god_flg && IO[i][0] == 'I') {
	time[0][id[i]] = hou[i]*60 + min[i];
	in_flg[id[i]] = 1;
      }
      else if(god_flg && IO[i][0] == 'O') {
	time[1][id[i]] = hou[i]*60 + min[i];
	total[id[i]] += time[1][id[i]] - time[0][id[i]];

	in_flg[id[i]] = 0;
      }
      else if(!god_flg && IO[i][0] == 'I') {
	in_flg[id[i]] = 1;
      }
      else if(!god_flg && IO[i][0] == 'O') {
	in_flg[id[i]] = 0;
      }
    }
    printf("%d\n", total[max(total, 1000)]);
  }
    return 0;
}

Measured memory_bytes: 1064
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;
public class Main {
	int N;
	char[] ch;
	int[][] dp;
	
	public int isCat(int m,int w){
		if(m >= w)return 1;
		if(dp[m][w] != -1)return dp[m][w];
		
		if(ch[m] == 'm' && ch[w] == 'w'){
			
			for(int e = m + 1;e < w;e++){
				
				if(ch[e] == 'e'){
					
					if(isCat(m + 1,e - 1) == 1 && isCat(e + 1,w - 1) == 1){
						return dp[m][w] = 1;
					}
					
				}
				
			}
			
		}
		return dp[m][w] = 0;
	}
	
    public void solve() {
		ch = next().toCharArray();
		N = ch.length;
		dp = new int[N][N];
		for(int i = 0;i < N;i++){
			for(int j = 0;j < N;j++){
				dp[i][j] = -1;
			}
		}
		if(isCat(0,N - 1) == 1){
			out.println("Cat");
		}else{
			out.println("Rabbit");
		}
    }
 
	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}
		/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

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

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

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

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

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

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

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

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

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

n, q = map(int, input().split())
s = str(input())
ac = [0] * n
for i in range(1, n):
    ac[i] = ac[i-1]
    if(s[i-1] == "A" and s[i] == "C"):
        ac[i] += 1
for i in range(q):
    l, r = map(int, input().split())
    print(ac[r-1] - ac[l-1])

Measured memory_bytes: 52824
#ifdef ConanYu
#include "E:\yuzining\code\local.hpp"
#else
#pragma GCC optimize("-O3")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(...) do { } while(false)
void Main();
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie();
  Main();
  return 0;
}
#endif

void Main() {
  ll n, k; cin >> n >> k;
  ll t = n % k;
  t = min(t, k - t);
  cout << t << '\n';
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <complex>
#include <vector>
#include<limits>
#include<iomanip>

using namespace std;

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

const long double pi = 3.141592653589793;

#define debug(x) cout << #x << " = " << (x) << endl;
#define rep(i, n) for(int i = 0;i < n;i++)
#define repi(i, j, n) for(int i = j;i < n;i++)
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define F first
#define S second

// #define COMMENT

/*

const int NN = 200090;
ll fact[NN];
ll finv[NN];
ll inv[NN];

void inverse_modulao() {
  fact[0] = fact[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;

  for(int i = 2;i < NN;i++) {
    fact[i] = fact[i-1]*i%mod;
    inv[i] = mod-mod/i*inv[mod%i]%mod;
    finv[i] = finv[i-1]*inv[i]%mod;
  }
}

ll nCr(int n, int r) {
  return fact[n]*finv[r]%mod*finv[n-r]%mod;
}

*/

int A[200], x, n, num;

int main() {

 // freopen("input.in","r",stdin);
 // freopen("output.out","w",stdout);


  cin>>x>>n;
  rep(i,n) {cin>>num;A[num]=1;}
  int ans = 0;
  rep(i,102) {if(A[i]==0 && abs(i-x) < abs(ans-x)) ans = i;}
  cout<<ans;
  return 0;
}


Measured memory_bytes: 3632
s = list(input())

while "B" in s : #Bが存在する間実行
    b = s.index('B') #最初のBのインデックスを取得
    if b != 0: # Bが先頭でないとき
        del s[b-1:b+1] # Bの1個前とBを消す
    elif b == 0: # Bが先頭の時
        del s[b]

s = ''.join(s) #この区切り文字でリストを連結
print(s)

Measured memory_bytes: 2940
#include<bits/stdc++.h>
#define taskname "A"
#define pb push_back
#define mp make_pair
#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 long double ld;
typedef pair<int,int> ii;
const int maxn = 1e5 + 5;

string s;
ll k;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
        freopen(taskname".INP","r",stdin);
        freopen(taskname".OUT","w",stdout);
    }
    cin >> s >> k;
    if(*max_element(s.begin(),s.end()) == *min_element(s.begin(),s.end()))
        return cout << (s.size() * k) / 2 , 0;
    ll res = 0;
    int pre = 0;
    int cnt = 0;
    for(int i = 0 ; i < s.size() ; ++i){
        if(pre == s[i]){
            cnt++;
        }else{
            res += cnt / 2;
            cnt = 1;
            pre = s[i];
        }
    }
    res += cnt / 2;
    if(s.back() == s[0]){
        cnt = 0;int cnt1 = 0;
        for(int i = 0 ; i < s.size() ; ++i){
            if(s[i] == s[0])cnt++;
            else break;
        }
        cnt1 = cnt;
        for(int i = s.size() - 1 ; i >= 0 ; --i){
            if(s[i] == s[0])cnt++;
            else break;
        }
        res -= cnt1 / 2 + (cnt - cnt1) / 2;
//        cout << cnt1  << " " << cnt << endl;
        res *= k;
        res += cnt1 / 2 + (cnt - cnt1) / 2;
        res += (cnt / 2) * (k - 1);
    }else res *= k;
    cout << res;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define MAXN 200005
#define eps 1e-10
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
	res = 0;T f = 1;char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		res = res * 10 + c - '0';
		c = getchar();
	}
	res *= f;
}
template<class T>
void out(T x) {
	if(x < 0) {x = -x;putchar('-');}
	if(x >= 10) {
		out(x / 10);
	}
	putchar('0' + x % 10);
}
int N,M;
map<int,int> zz;
void Solve() {
	read(N);int a;
	for(int i = 1 ; i <= N ; ++i) {
		read(a);zz[a]++;
	}
	read(M);
	for(int i = 1 ; i <= M ; ++i) {
		read(a);
		if(zz[a]) {
			zz[a]--;
		}
		else {puts("NO");return;}
	}
	puts("YES");
}
int main() {
#ifdef ivorysi
	freopen("f1.in","r",stdin);
#endif
	Solve();
}


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

using namespace std;

#define MP make_pair
#define PB push_back
#define F first
#define S second
#define FOR(i, a, b) for(int i = a; i <= (b); i++)
#define all(x) x.begin(), x.end()

typedef pair<int, int> pi;
typedef long long ll;
const int INF = 2000000000;

vector<int> health;
int N, A, B;

bool valid(int exp)
{
  vector<int> tmp(health);
  FOR(i, 0, N - 1)
  {
      if (exp >= (double)tmp[i] / B)
      {
          tmp[i] = -1;
      }
      else
      {
          tmp[i] -= exp * B;
      }
  }

  ll necessary = 0;
  FOR(i, 0, N - 1)
  {
      if (tmp[i] > 0)
        necessary += (int) ceil((double)tmp[i] / (A - B));
  }

  return necessary <= (long long)exp;
}

int main()
{
  cin >> N >> A >> B;
  health.resize(N);
  FOR(i, 0, N - 1)
    cin >> health[i];

  int x = -1;
  for (int b = 1e9; b >= 1; b /= 2)
  {
	while (!valid(x + b))
      x += b;
  }
  int ans = x + 1;

  cout << ans;

  return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <algorithm>

using namespace std;

int main(){
	int H,W;
	while(true){
		scanf("%d %d",&H,&W);
		if(H == 0 && W == 0) break;
		for(int i = 0; i < H; i++){
			for(int j = 0; j < W; j++){
				printf("#");
			}
			printf("\n");
		}
		printf("\n");
	}
}


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

ll solve(vector<ll>& a){
    int lv = a[0], rv = a[0];
    int l = 1, r = a.size() - 1;
    int side = 0;
    ll ret = 0;
    while(l <= r){
        if(side == 0){
            ret += abs(lv - a[r]);
            lv = a[r];
            r--;
            if(l <= r){
                ret += abs(lv - a[l]);
                lv = a[l];
                l++;
            }
        }else{
            ret += abs(rv - a[r]);
            rv = a[r];
            r--;
            if(l <= r){
                ret += abs(rv - a[l]);
                rv = a[l];
                l++;
            }
        }
        side = side ^ 1;
    }
    return ret;
}

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

    vector<ll> A(N);
    for(int i=0;i<N;i++){
        cin >> A[i];
    }
    sort(A.begin(), A.end());
    ll ans = solve(A);
    reverse(A.begin(), A.end());
    ans = max(ans, solve(A));
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1024
//long long -> ll
//http://web.mit.edu/~ecprice/acm/acm08/notebook.html#file12
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include<bits/stdc++.h>
typedef long long ll;
#define x first
#define y second
#define REP(i,sss,eee) for(long long i=sss;i<=eee;++i)
#define pb push_back
#define pii pair<long long,long long>
#define vi vector<long long>
#define speed ios_base::sync_with_stdio(0);cin.tie(0);
#define N 1000000007
using namespace __gnu_pbds;
using namespace std;
template <class T>
T MAX(T a, T b){return ((a>b)?a:b);}
template <class T>
T MIN(T a, T b){return ((a<b)?a:b);}
template <class T>
T MOD(T a){return ((a>=0)?a:(-1*a));}
template <class T>
void SWAP(T &a,T &b){T temp=a;a=b;b=temp;}
typedef tree<
long long,
null_type,
less<long long>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
long long ex(long long a, long long b){
	if(b==0||a==1){return 1;}
	if(a==0||b==1){return a;}
	long long tmp=ex(a,(b/2));
	if(b%2){return ((((tmp*tmp)%N)*a)%N);}
	else{return ((tmp*tmp)%N);}
}
long long inv(long long k){
	if(k==1){return 1;}
	else{return ex(k,N-2);}
}
/*****************default********************/
std::vector<std::vector<long long>> dp;
std::vector<pii> inp;
long long f(long long n,long long w)
{
	if(n<0||w<0){return 0;}
	if(dp[n][w]!=-1){return dp[n][w];}
	if(n==0)
	{
		if(w>=inp[0].x){dp[n][w] = inp[0].y;}
		else{dp[n][w] = 0;}
		return dp[n][w];
	}

	dp[n][w]=MAX(f(n-1,w),((w>=inp[n].x)?(f(n-1,(w-inp[n].x))+inp[n].y):0));
	return dp[n][w];
}
int main(){
	long long n,w;cin>>n>>w;
	inp.resize(n);
	dp.resize(n,std::vector<long long>(w+1,-1));
	REP(i,0,n-1){cin>>inp[i].x>>inp[i].y;}
	cout<<f(n-1,w)<<"\n";
}

Measured memory_bytes: 79360
#include <iostream>
using namespace std;
typedef long long ll;

int main()
{
    ll n;
    cin >> n;
    ll ans = 1000000000000000;
    for(ll i = 1; i * i <= n; i++){
        if(n % i == 0) ans = min(ans, i + n / i - 2);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)n;++i)

using namespace std;

typedef pair<int,int>P;

const int MAX_N = 1002;

int n,m;
vector<int> G[MAX_N];
vector<int> rG[MAX_N];
vector<int> vs; //??°?????????????????????
bool used[MAX_N]; //?????§????????????????????????
int cmp[MAX_N];	//?±????????????£????????????????????????????????????
vector<int> GG[MAX_N];
vector<int> rGG[MAX_N];
bool flag[MAX_N];
vector<ll> ts;
ll dp[MAX_N];

void add_edge(int from,int to)
{
	G[from].push_back(to);
	rG[to].push_back(from);
}

void dfs(int v)
{
	used[v] = true;
	for(int i=0;i<G[v].size();i++){
		if(!used[G[v][i]]){
			dfs(G[v][i]);
		}
	}
	vs.push_back(v);
}

void rdfs(int v,int k)
{
	used[v] = true;
	cmp[v] = k;
	for(int i=0;i<rG[v].size();i++){
		if(!used[rG[v][i]]){
			rdfs(rG[v][i],k);
		}
	}
}

int scc(int n,int m)	//?????£??????????????°?????????
{
	fill(used,used+n,0);
	vs.clear();
	for(int v=0;v<n;v++){
		if(!used[v]){
			dfs(v);
		}
	}
	fill(used,used+n,0);
	int k=0;
	for(int i=vs.size()-1;i>=0;i--){
		if(!used[vs[i]]){
			rdfs(vs[i],k++);
		}
	}
	return k;
}

void rdfsdp(int u)
{
    flag[u] = true;
    if(rGG[u].size() == 0){
        dp[u] = 1;
        return;
    }
    ll hoge = 1;
    rep(i,rGG[u].size()){
        rdfsdp(rGG[u][i]);
        hoge = (hoge*(dp[rGG[u][i]]+1)) % MOD;
    }
    dp[u] = hoge;
    return;
}

int main()
{
	scanf("%d%d",&n,&m);
	rep(i,m){
		int a,b;
        scanf("%d%d",&a,&b);
        add_edge(a-1,b-1);
	}
    int cnt = scc(n,m);
    rep(i,n){
        rep(j,G[i].size()){
            if(cmp[i] != cmp[G[i][j]]){
                GG[cmp[i]].push_back(cmp[G[i][j]]);
                rGG[cmp[G[i][j]]].push_back(cmp[i]);
            }
        }
    }
    rep(i,cnt){
        flag[i] = false;
    }
    rep(i,cnt){
        if(!flag[i] && GG[i].size() == 0){
            rdfsdp(i);
            ts.push_back(dp[i]+1);
        }
    }
    ll ans = 1;
    rep(i,ts.size()){
        ans = ans * ts[i] % MOD;
    }
    printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 3440
#include <stdio.h>
#include <ctype.h>
#include <string.h>

int main(void){
	char word_1[10];
	int count=0,i;
	scanf("%s",word_1);
	for(i=0;i<=strlen(word_1);i++){
		word_1[i]=tolower(word_1[i]);
	}
	while(1){
		char word_2[1000];
		scanf(" %s",word_2);
		if(strcmp(word_2,"END_OF_TEXT")==0) break;
		for(i=0;i<=strlen(word_2);i++){
		word_2[i]=tolower(word_2[i]);
		}
		if(strcmp(word_2,word_1)==0){
			count++;
		}
	}
	
	printf("%d\n",count);
	return 0;
}

Measured memory_bytes: 552
import java.io.*;
import java.math.*;
import java.util.*;

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

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

    private void solve(Scanner sc) {
        int N = sc.nextInt();
        long T = sc.nextInt();
        long[] t = new long[N];
        long sum = 0;
        for (int i = 0; i < N; ++i) {
            t[i] = sc.nextInt();

            if (i > 0) {
                sum += Math.min(t[i] - t[i - 1], T);
            }
        }

        _out.println(sum + T);
    }
    private static BigInteger C(long n, long r) {
        BigInteger res = BigInteger.ONE;
        for (long i = n; i > n - r; --i) {
            res = res.multiply(BigInteger.valueOf(i));
        }
        for (long i = r; i > 1; --i) {
            res = res.divide(BigInteger.valueOf(i));
        }
        return res;
    }
    private static BigInteger P(long n, long r) {
        BigInteger res = BigInteger.ONE;
        for (long i = n; i > n - r; --i) {
            res = res.multiply(BigInteger.valueOf(i));
        }
        return res;
    }
    /*
     * 10^10 > Integer.MAX_VALUE = 2147483647 > 10^9
     * 10^19 > Long.MAX_VALUE = 9223372036854775807L > 10^18
     */
    public static void main(String[] args) {
        long S = System.currentTimeMillis();

        Scanner sc = new Scanner(System.in);
        new Main().solve(sc);
        _out.flush();

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

Measured memory_bytes: 89060
using System;
using System.Linq;

namespace A___Rotation
{
    class Program
    {
        static void Main(string[] args)
        {
            var C1 = Console.ReadLine();
            var C2 = Console.ReadLine();

            Console.WriteLine(string.Compare(C1, string.Join("", C2.Reverse())) == 0 ? "YES" : "NO");
        }
    }
}


Measured memory_bytes: 13524
Module _20190420

    Sub Main()

        '山の数
        Dim intMountainCount As Integer = Console.ReadLine()

        '高さ
        Dim sHeight As String() = Console.ReadLine().Split(" ")

        Dim iMaxHeight As Integer = CInt(sHeight(0))
        Dim iWatchCount As Integer = 0
        For i As Integer = 0 To intMountainCount - 1

            If CInt(sHeight(i)) >= iMaxHeight Then

                iWatchCount = iWatchCount + 1

                iMaxHeight = CInt(sHeight(i))

            End If

        Next

        Console.WriteLine(iWatchCount)

    End Sub

End Module

Measured memory_bytes: 11220
#include <iostream>
#include <sstream>
#include <vector>
#include <cassert>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <utility>
#include <tuple>
#include <regex>
#include <map>

using namespace std;
using ull = unsigned long long;


int main() {
	ull a,b,c,d,e,k;
	cin >> a >> b >> c >> d >> e >> k;

	string ans = ":(";
	if (
		(b - a <= k) &&
		(c - a <= k) &&
		(d - a <= k) &&
		(e - a <= k) &&
		(c - b <= k) &&
		(d - b <= k) &&
		(e - b <= k) &&
		(d - c <= k) &&
		(e - d <= k) &&
		(e - a <= k)
		) {
		ans = "Yay!";
	}

	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 256
from sys import stdin

S,T = stdin.readline().rstrip().split()
A,B = [int(x) for x in stdin.readline().rstrip().split()]
U = stdin.readline().rstrip().split()

if S==U[0]:
	print(str(A-1)+" "+str(B))
else :
	print(str(A)+" "+str(B-1))

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

namespace lec09B
{
    class Program
    {
        static int size;

        static void Main(string[] args)
        {
            //setting part
            size = int.Parse(Console.ReadLine());
            int[] array = new int[size];
            string input = Console.ReadLine();
            string[] split = input.Split(' ');

            for (int i = 0; i < size; i++)
            {
                array[i] = int.Parse(split[i]);
            }

            //heap part
            BuildMaxHeap(array);

            //printf part
            foreach (int element in array){
                Console.Write(" {0}",element);
            }

            Console.WriteLine();
            Console.ReadLine();
        }

        static void BuildMaxHeap(int [] arr )
        {
            for (int i = size / 2 ; i > 0; i--)
            {
                MaxHeapify(arr, i);
            }
        }

        static void MaxHeapify (int [] arr , int i)
        {
            int l = i * 2;
            int r = i * 2 + 1;
            int largest;

            if ( l <= size && arr[l-1] > arr[i-1])
            {
                largest = l;
            } else
            {
                largest = i;
            }
            if ( r <= size && arr[r-1] > arr[largest-1])
            {
                largest = r;
            } 

            if (largest != i)
            {
                int temp = arr[i-1];
                arr[i-1] = arr[largest-1];
                arr[largest-1] = temp;

                MaxHeapify(arr , largest);
            }
        }
    }
}



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

using namespace std;

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

const long long MOD = 1e9 + 7;
const int INF = 1e9;
const double EPS = 1e-9;

int main() {
  ll N, M;
  cin >> N >> M;
  ll ans = 0;
  if (2 * N <= M) {
    ans = N;
    ll t = M - 2 * N;
    ans += t / 4;
  }
  else {
    ans = M / 2;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {

	public static void main(String[] args){
		Scanner stdIn=new Scanner(System.in);
		int N=stdIn.nextInt();
		int h[]=new int[N];
		int z=0,y=0,x=1,max=0,n=1,s=0;
		while(z<N){
			h[z]=stdIn.nextInt();
			if(h[z]>max)
				max=h[z];
			z++;
		}z=0;
		while(x<=max){
			while(y<N){
				if(h[y]<x){
					if(n==0)
						n=1;
				}
				else{
					if(n==1)
						s++;
					n=0;
				}
				y++;
			}
			x++;
			n=1;
			y=0;
			z+=s;
			s=0;
		}
		System.out.println(z);
	}
}


Measured memory_bytes: 21972
#include <iostream>
#include<bits/stdc++.h>
#define ll long long
#define MAXN 100000
using namespace std;
int main(){
       ll n;cin>>n;
	string strings;
	cin>>strings;
	ll right=0,gets=0,burys=0;
	for(ll i=0;i<n;i++){
		if(strings[i]=='R')right++;
		else if(strings[i]=='G')gets++;
		else burys++;
	}
	ll anss=right*gets*burys;
	for(ll i=0;i<n;i++){
		for(ll j=i+1;j<n;j++){
			if(strings[i]==strings[j])continue;
			ll k=j+(j-i);
			if(k>=n)continue;
			if(strings[k]==strings[i] || strings[k]==strings[j])continue;
			anss--;
		}
	}
	cout<<anss;
 
    return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <math.h>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#define REP(i,n) for(int i=0;i<n;i++)
typedef long long ll;

using namespace std;
int kaijo(int n){
	int ans = 1;
	if (n != 0){
		for (int i = 0; i < n; i++){
			ans *= (n - i);
		}
	}
	else{
		ans = 1;
	}
	return ans;
}

int main(){
	int n;
	cin >> n;
	cout << n / 3 << endl;

	return 0;
}

Measured memory_bytes: 768
#include<iostream>
using namespace std;
int main()
{
	int a,b,n,ans;
	cin>>n>>a>>b;
	a=a*n;
	if(a>b)
	{
		ans=b;
	}
	else
	{
		ans=a;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
from decimal import Decimal
W, H, x, y = map(int, raw_input().split())
d_W = Decimal(str(W) + ".0")
d_H = Decimal(str(H) + ".0")

menseki = d_W * d_H * Decimal("0.5")

val = 0
if x == W * 0.5 and y == H * 0.5:
  val = 1

print(str(menseki) + " " + str(val))

Measured memory_bytes: 4268