akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
using namespace std;

int main(){
    long long a, b ,x;
    cin >> a >> b >> x;

    long long ans;

    if(a % x == 0) ans = b/x - a/x + 1;
    else ans = b/x - a/x;
    
    cout << ans << endl;
    return 0;
}

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

using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using vint = vector<int>;
using vvint = vector<vint>;
using vvvint = vector<vvint>;
using vdouble = vector<double>;
using vvdouble = vector<vdouble>;
using vvvdouble = vector<vvdouble>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using uint = unsigned int;
using ull = unsigned long long;

template<typename T> using uset = unordered_set<T>;
template<typename T1, typename T2> using umap = unordered_map<T1, T2>;

constexpr int INF = (1 << 30) - 1;
constexpr ll LLINF = 1LL << 60;
constexpr int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr char el = '\n';
constexpr int mod = 1000000007;

template<typename T> T gcd(T a, T b) { return (b ? gcd(b, a % b) : a); }
template<typename T> T lcm(T a, T b) { return (a / gcd(a, b) * b); }
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) { return (a > b && (a = b, true)); }
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) { return (a < b && (a = b, true)); }

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

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

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

template<typename T> 
struct BIT {
	vector<T> dat;

	BIT (int n) { dat.assign(n+1, 0); }

	void add(int k, T x) {
		for (++k; k < dat.size(); k += k & -k) dat[k] += x;
	}

	T query(int k) {
		T sum = 0;
		for (++k; k > 0; k -= k & -k) sum += dat[k];
		return (sum);
	}

	//[l, r]
	T fold(int l, int r) {
		return (query(r) - (l > 0 ? query(l-1) : 0));
	}

	int lower_bound(T x) {
		int l, r;
		l = -1, r = dat.size();
		while (l + 1 < r) {
			int m = (l + r) / 2;
			if (query(m) >= x) r = m;
			else l = m;
		}
		return (r);
	}
};


void Main() {
	int N; cin >> N;
	vector<BIT<int>> tree(26, BIT<int>(N+1));
	string S; cin >> S;
	for (int i = 0; i < N; i++) {
		tree[S[i]-'a'].add(i, 1);
	}
	int Q;
	cin >> Q;
	while (Q--) {
		int a; cin >> a;
		if (a == 1) {
			int i;
			char c;
			cin >> i >> c; --i;
			tree[S[i]-'a'].add(i, -1);
			S[i] = c;
			tree[S[i]-'a'].add(i, 1);
		} else {
			int l, r;
			cin >> l >> r; --r, --l;
			int cnt = 0;
			for (int i = 0; i < 26; i++) {
				if (tree[i].fold(l, r) > 0) cnt++;
			}
			cout << cnt << el;
		}
	}
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout << fixed << setprecision(20);
	Main();
	return (0);
}

Measured memory_bytes: 53120
#include<bits/stdc++.h>
using namespace std;
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define INF 100100100

int main(){

  int v, e; cin >> v >> e;
  int n = v;
  vector<vector<int> > dis(v, vector<int> (v, INF));
  for(int i = 0; i < e; i++){
    int a, b, c; cin >> a >> b >> c;
    dis[a][b] = c;
  }

  vector<vector<int> > dp((1 << n), vector<int> (n, INF));
  dp[0][0] = 0;
  for(int i = 0; i < (1 << n); i++){
    for(int j = 0; j < n; j++){
      for(int k = 0; k < v; k++){
        if((i & (1 << k)) != 0) continue;

        int cost = dp[i][j] + dis[j][k];

        chmin(dp[i | (1 << k)][k], cost);
      }
    }
  }  

  if(dp[(1 << v) - 1][0] == INF) cout << -1 << endl;
  else cout << dp[(1 << v) - 1][0] << endl;

  return 0;
}


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

int main()
{
    ll n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    s[k-1]=s[k-1]+('a'-'A');
    cout<<s<<endl;
    return 0;
}

Measured memory_bytes: 3596
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<numeric>
#include<iomanip>

using namespace std;

int main() {
	int n; cin >> n;
	vector<long long int>a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	vector<long long int>ans1(n / 2), ans2(n / 2);
	long long int tmp = 0;
	unsigned long long int sum1 = 0;
	unsigned long long int sum2 = 0;
	if (n % 2 == 0) {
		for (int i = 0; i < n / 2; i++) {
			ans1[i]= a[n - i - 1];
			ans2[i]= a[i];
		}
	}
	else {
		unsigned long long  x = n / 2;
		tmp = a[x];
		for (int i = 0; i < n / 2; i++) {
			ans1[i] = a[n - i - 1];
			ans2[i] = a[i];
		}

	}
	for (int i = 0; i < n/2; i++){
		sum1 += abs(ans1[i] - ans2[i]);
		sum2 += abs(ans1[i] - ans2[i]);
		if (i != n/2 - 1) {
			sum1 += abs(ans2[i] - ans1[i + 1]);
			sum2 += abs(ans1[i] - ans2[i + 1]);
		}
    }
	
	if (tmp != 0) {
		sum1 +=max(abs(tmp - ans1[0]),abs(tmp-ans2[n/2-1]));
		sum2+= max(abs(tmp - ans2[0]), abs(tmp - ans1[n / 2 - 1]));
	}
	if (tmp == 0) {
		if (abs(ans1[n / 2 - 1] - ans2[n / 2 - 1])
			< abs(ans1[0] - ans2[n / 2 - 1])){
			sum1 += -abs(ans1[n / 2 - 1] - ans2[n / 2 - 1])
			+ abs(ans1[0] - ans2[n / 2 - 1]);
	     }if(abs(ans1[n / 2 - 1] - ans2[n / 2 - 1])
			 < abs(ans2[0] - ans1[n / 2 - 1])) {
			 sum2 += -abs(ans1[n / 2 - 1] - ans2[n / 2 - 1])
				 + abs(ans2[0] - ans1[n / 2 - 1]);
		 }


	}
	cout << max(sum1,sum2) << endl;
}





Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rep2(i,s,n) for (int i = s; i < n; ++i)
#define all(a) a.begin(),a.end()
using namespace std;

int main() {
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    cout << max(a*b,c*d) << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    long int n,a,b,s;
    scanf("%ld%ld%ld",&a,&b,&n);
     if(n<b-1)
         s=a*n/b;
      else
         s=a*(b-1)/b;
       printf("%ld\n",s);
    return 0;
}

Measured memory_bytes: 1684
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cout << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cout<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 200010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 29;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
///////////////////////////////////////////////////////////////////////////////////////////////////

int N, M;
int G[15][15];

int to[15][(1 << 15)];
ll dp[(1 << 15)];
ll pow2[1000];

void solve() {
	cin >> N >> M;
	rep(i, 0, M) {
		int a, b; cin >> a >> b; a--; b--;
		G[a][b] = 1;
	}

	pow2[0] = 1;
	rep(i, 0, 500) pow2[i + 1] = pow2[i] * 2 % mod;

	rep(i, 0, N) {
		rep(bit, 0, (1 << N)) {
			if((bit & (1 << i))) continue;
			int tmp = 0;
			rep(j, 0, N) {
				if(!(bit & (1 << j))) continue;
				tmp += G[i][j];
			}
			to[i][bit] = tmp;
		}
	}
	dp[0] = 1;
	rep(q, 0, (1 << N)) {
		for(int bit = q; bit; bit = (bit - 1) & q) {
			if((bit & (1 << 0)) && (bit & (1 << 1))) continue;
			int pbt = bit ^ q;
			int rbt = (1 << N) - 1 - q;
			ll mul = 1;
			ll cnt = 0;
			rep(i ,0, N) {
				if(!(rbt & (1 << i))) continue;
				MUL(mul, pow2[to[i][bit]] - 1);
			}
			rep(i, 0, N) {
				if(!(pbt & (1 << i))) continue;
				ADD(cnt, to[i][bit]);
			}
			// debug(bitset<3>(q), bitset<3>(pbt), bitset<3>(bit), bitset<3>(rbt), dp[pbt], mul, cnt);
			ADD(dp[q], dp[pbt] * mul % mod * pow2[cnt] % mod);
		}
		// debug(bitset<3>(q), dp[q]);
	}
	cout << dp[(1 << N) - 1] << "\n";
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
	srand((unsigned int)time(NULL));
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}



Measured memory_bytes: 2304
import java.util.*;

public class Main{
    static int mergecount(ArrayList<Integer> a){
        int count = 0;
        int n = a.size();

        if(n > 1){
            ArrayList<Integer> b = new ArrayList<Integer>();
            for(int i = 0; i < n / 2; i++) b.add(a.get(i));
            ArrayList<Integer> c = new ArrayList<Integer>();
            for(int i = n / 2; i < n; i++) c.add(a.get(i));

            count += mergecount(b);
            count += mergecount(c);
            for(int i=0, j=0, k=0; i < n; i++){
                if(k == c.size())      a.set(i, b.get(j++));
                else if(j == b.size()) a.set(i, c.get(k++));
                else if(b.get(j) <= c.get(k))  a.set(i, b.get(j++));
                else                 { a.set(i, c.get(k++)); count += n / 2 - j; }
            }
        }
        return count;
    }

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

        while(true){
            int n = sc.nextInt();
            if(n == 0) break;
            ArrayList<Integer> al = new ArrayList<Integer>();

            for(int i = 0; i < n; i++){
                al.add(sc.nextInt());
            }

            System.out.println(mergecount(al));
        }
    }
}

Measured memory_bytes: 12000
#include<stdio.h>
#include<math.h>

int isPrime(int x){
  if(x==2){
    return 1;
  }
  if(x<2 || x%2==0){
    return 0;
  }

  int i=3;
  while(i<=sqrt(x)){
    if(x%i==0){
      return 0;
    }
    i = i+2;
  }

  return 1;
}

int main(){
  int n;
  scanf("%d",&n);

  int N[n];
  int c=0;
  for(int i=0;i<n;i++){
    scanf("%d",&N[i]);
    if(isPrime(N[i])){
      c++;
    }
  }
  printf("%d\n",c);

  return 0;
}



Measured memory_bytes: 2636
#include <bits/stdc++.h>
using namespace std;
#define all(s) (s).begin(),(s).end()
typedef long long ll;

vector<pair<ll, ll>> dny(vector<pair<ll, ll>> vec, int N) {
	ll mxd = 0, mxe = 0;
	for (int i = 0;i < N;i++) {
		if (vec[i].first <= mxe) {
			vec[i].first = mxe;
			vec[i].second = mxd;
		}
		else {
			mxe = vec[i].first;
			mxd = vec[i].second;
		}
	}
	return vec;
}

int main() {
	int N;
	ll C;
	cin >> N >> C;
	vector<pair<ll,ll>> hantokei(N);
	vector<pair<ll, ll>> tokei(N);
	vector<pair<ll, ll>> hantokei2(N);
	vector<pair<ll, ll>> tokei2(N);
	
	vector<pair<ll, ll>> S(N);
	ll a, b;
	for (int i = 0;i < N;i++) {
		cin >> a >> b;
		tokei[i] = { b,a };
		hantokei[i] = { b,C - a };
	}
	reverse(all(hantokei));

	for (int i = 1;i < N;i++) { //そこまでの栄養
		tokei[i].first += tokei[i - 1].first;
		hantokei[i].first += hantokei[i - 1].first;
	}

	for (int i = 0;i < N;i++) { //栄養から消費カロリーを引いた値
		tokei[i].first -= tokei[i].second;
		tokei2[i].first = tokei[i].first - tokei[i].second;
		hantokei[i].first -= hantokei[i].second;
		hantokei2[i].first = hantokei[i].first - hantokei[i].second;
	}
	ll mxd = 0, mxe = 0;
	tokei = dny(tokei, N);
	tokei2 = dny(tokei2, N);
	hantokei = dny(hantokei, N);
	hantokei2 = dny(hantokei2, N);

	vector<ll> as;
	for (int i = 0;i < N - 1;i++) {
		as.push_back(tokei[i].first + hantokei2[N - 2 - i].first);
		as.push_back(tokei2[i].first + hantokei[N - 2 - i].first);
	}
	as.push_back(tokei[N - 1].first);
	as.push_back(hantokei[N - 1].first);

	sort(all(as));
	cout << as[as.size() - 1] << endl;
}

Measured memory_bytes: 11664
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		double x1=sc.nextDouble(), y1=sc.nextDouble();
		double x2=sc.nextDouble(), y2=sc.nextDouble();
		
		double l = (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
		System.out.printf("%s", Math.sqrt(l));
		
	}
}



Measured memory_bytes: 28092
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        MyScanner in = new MyScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        B solver = new B();
        solver.solve(1, in, out);
        out.close();
    }

    static class B {
        String S;
        String T;

        public void solve(int testNumber, MyScanner in, PrintWriter out) {
            S = in.next();
            T = in.next();
            char[] s = S.toCharArray();
            char[] t = T.toCharArray();

            int min = t.length;
            for (int i = 0; i <= s.length - t.length; i++) {
                int cnt = 0;
                for (int j = 0; j < t.length; j++) {
                    if (s[i + j] != t[j]) cnt++;
                }
                min = Math.min(min, cnt);
            }
            out.println(min);
        }

    }

    static class MyScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public MyScanner(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    String rl = in.readLine();
                    if (rl == null) {
                        return null;
                    }
                    st = new StringTokenizer(rl);
                } catch (IOException e) {
                    return null;
                }
            }
            return st.nextToken();
        }

    }
}



Measured memory_bytes: 32768
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, n) for(int i=0; i<int(n); i++)
#define RNG(i, f, t) for(int i=int(f); i<=int(t); i++)
#define REV(i, f, t) for(int i=int(f); i>=int(t); --i)
#define ALL(v) (v).begin(), (v).end()
#define EXIT(answer) { cerr<<"EXIT #"<<__LINE__<<endl; cout<<answer<<endl; exit(0); }
#define sz(v) int(v.size())
bool RELAXED = false;
template<int,typename T> struct MINMAX{ T val; MINMAX(T val) : val(val) {} };
template<typename T> MINMAX<1,T> MAX(T val) { return MINMAX<1,T>(val); };
template<typename T> MINMAX<2,T> MIN(T val) { return MINMAX<2,T>(val); };
template<typename T, typename U> inline T& operator|=(T &lhs, MINMAX<1,U> rhs) { return lhs = (rhs.val > lhs ? (RELAXED=true,rhs.val) : (RELAXED=false,lhs)); }
template<typename T, typename U> inline T& operator|=(T &lhs, MINMAX<2,U> rhs) { return lhs = (rhs.val < lhs ? (RELAXED=true,rhs.val) : (RELAXED=false,lhs)); }
template<typename T, typename U> istream& operator>>(istream& in, pair<T,U> &p) { in>>p.first>>p.second; return in; }
template<typename T> inline vector<T> READ(int n) { vector<T> vec(n); FOR(i,n) cin>>vec[i]; return vec; }
template<typename T> using min_heap = priority_queue<T, vector<T>, greater<T> >;
typedef signed long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    ll x; cin>>x;
    ll h = x/500*1000 + x%500/5*5;
    cout<<h<<endl;

}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

int main() {

	std::string s, t;
	std::cin >> s >> t;

	std::vector<std::vector<int>>
		v( s.size() + 1,
			std::vector<int>(t.size() + 1, 0)
		);

	
	for (decltype(s.size()) i{ 1 }; i <= s.size(); ++i) {

		for (decltype(t.size()) j{ 1 }; j <= t.size(); ++j) {

			if (s[i - 1] == t[j - 1])
				v[i][j] = v[i - 1][j - 1] + 1;
			else
				v[i][j] = std::max(v[i][j - 1], v[i - 1][j]);
		}
	}

	/*
	for (auto&&e : v) {
		for (auto&&ee : e)
			std::cout << ee << " ";
		std::cout << "\n";
	}*/

	std::string ans;
	ans.reserve( std::min( s.size(), t.size() ) );
	auto size = v[s.size()][t.size()];

	auto si = s.size() ;
	auto ti = t.size() ;

	while ( si>0 &&ti>0) {
		
		if (s[si-1] == t[ti-1]) {
			ans += s[si-1];
			--si; --ti;
		}
		else if (v[si][ti] == v[si][ti - 1])
			--ti;
		else if (v[si][ti] == v[si - 1][ti])
			--si;
	}

	auto it = std::crbegin(ans);
	while (it != std::crend(ans)) {
		std::cout << *it;
		++it;
	}
	std::cout << "\n";

	return 0;
}

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

// ----------- define --------------
#define int long long
#define ii pair<int,int>
#define fi first
#define sc second
#define all(x) (x).begin(),(x).end()
// ---------------------------------

void MAIN() {
  int a; string s;
  cin >> a >> s;
  int b = stoi(s.substr(0, s.size() - 3)) * 100 + stoi(s.substr(s.size() - 2, 2));
  cout << a * b / 100 << '\n';
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) MAIN();
}


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

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

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16
#define mod 1000000007
#define B 10007

ll mod_pow(ll a,ll n){
  ll res=1;
  while(n>0){
    if(n&1)res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll N,Q;
string S;
ll hsum[100010];

ll calchash(ll l,ll r){
  return ((hsum[r]-hsum[l]+mod)%mod)*mod_pow(mod_pow(B,l),mod-2)%mod;
}

ll calchash2(ll l,ll r,ll k,char c){
  return (calchash(l,k)+c*mod_pow(B,k-l)%mod+calchash(k+1,r)*mod_pow(B,k+1-l)%mod)%mod;
}

int main(){
  cin>>S;
  N=S.size();
  ll p=1;
  rep(i,N){
    hsum[i+1]=(hsum[i]+S[i]*p)%mod;
    (p*=B)%=mod;
  }

  cin>>Q;
  while(Q--){
    ll L,R,T;
    cin>>L>>R>>T;
    L--;
    ll lb=L,ub=R-T+1;
    while(ub-lb>1){
      ll mid=(lb+ub)/2;
      if(calchash(L,mid)==calchash(L+T,mid+T))lb=mid;
      else ub=mid;
    }
    if(lb==R-T){
      cout<<"Yes"<<endl;
      continue;
    }

    { // lb
      ll v1=calchash2(L,R-T,lb,S[lb+T]);
      ll v2;
      if(lb<L+T){
        v2=calchash(L+T,R);
      }else{
        v2=calchash2(L+T,R,lb,S[lb+T]);
      }
      if(v1==v2){
        cout<<"Yes"<<endl;
        continue;
      }
    }
    { // lb+T
      ll v1;
      if(lb+T>=R-T){
        v1=calchash(L,R-T);
      }else{
        v1=calchash2(L,R-T,lb+T,S[lb]);
      }
      ll v2=calchash2(L+T,R,lb+T,S[lb]);
      if(v1==v2){
        cout<<"Yes"<<endl;
        continue;
      }
    }
    cout<<"No"<<endl;
  }
  return 0;
}



Measured memory_bytes: 4084
#include <bits/stdc++.h>
#include <random>
using namespace std;
#define init_random mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define start_routine cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); int begtime = clock();
#define end_routine int endtime = clock(); cerr << endl << "Time elapsed: " << (endtime - begtime)*1000/CLOCKS_PER_SEC << " ms"; return 0
#define contests_de_diya_kar 0
#define PB push_back
#define MP make_pair
#define int long long
#define sd(n) scanf("%lld", &n)
#define pd(n) printf("%lld", n)
#define MOD ((long long) (1000*1000*1000 + 7))
#define inf (int) 2e15
#define exit(a, b) return cout << a, b;
#define eps (double)1e-9
#define forn(a, b, i) for (int i = a; i < b; i += 1)
#define vi vector<int>
#define vb vector<bool>
#define all(v) v.begin(), v.end()
#define ll long long 
#define pii pair<int, int>
#define mii map<int, int> 
#define print(stuff) cout << stuff << endl
#define len(stuff) stuff.size()

int exp (int a, int b) {
  if (b == 0) return 1LL;
  int ans = exp(a, b/2);
  ans = (ans * ans);
  if (b % 2) ans = (ans * a);
  return ans;
}

int root (int n, int i) {
  int hi = min((int) pow(n, (long double) 1 / (long double) i) + 5LL, n);
  int lo = max(1LL, (int) pow(n, (long double) 1 / (long double) i) - 5LL);

  while (lo < hi - 3) {
    int mid = (lo + hi) / 2;
    int calc = exp(mid, i);
    if (calc > n) {
      hi = mid - 1;
    }
    else {
      lo = mid;
    }
  }

  int ret = lo;
  for (int j = lo; j <= hi + 4LL; j += 1) {
    if (exp(j, i) <= n) ret = j;
  } 
  return ret;
}

vi memo((int) 1e6 + 1, -1);
mii memo_mp;
int f (int n) {
  if (n <= (int) 1e6) {
    if (memo[n] != -1) return memo[n];
  }
  else if (memo_mp.find(n) != memo_mp.end()) return memo_mp[n];
  int ans = n - 1;
  for (int p = 2; p <= 60LL; p += 1) {
    int rt = root(n, p);
    if (rt <= 1) break;
    ans -= f(rt);
  }
  if (n <= (int) 1e6) memo[n] = ans;
  else memo_mp[n] = ans;
  return ans;
}

signed main()
{
  start_routine;
  #ifndef ONLINE_JUDGE
  // freopen("input.txt", "r", stdin);
  #endif
  int n, x;
  cin >> n >> x;

  int g = 0;

  for (int i = 0; i < n; i += 1) {
    int a;
    cin >> a;

    a -= x;
    a = abs(a);
    
    g = __gcd(g, a);
  }

  cout << g;
  end_routine;
}

Measured memory_bytes: 8064
#include<cstdio>
#include<map>
using namespace std;
long long n;
map<long long,long long>f; //数组无法开到 1e18;
long long fff(long long x)
{
    if(f[x]!=0) return f[x];
    else return f[x]=((fff(x/2)+fff((x-1)/2)+fff((x-2)/2)))%1000000007;
}
int main()
{
	scanf("%lld",&n);
    f[0]=1;
    f[1]=2;
    printf("%lld\n",fff(n));
    return 0;
}

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

signed main() {

    double w, h, x, y;
    cin >> w >> h >> x >> y;

    printf("%.09lf %d\n", w*h/2, (w/2==x)&&(h/2==y));

    return 0;
}

Measured memory_bytes: 256
//#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
	long q, h, s, d, n;
	long long P, p1;

	scanf("%ld %ld %ld %ld", &q, &h, &s, &d);
	scanf("%ld", &n);

	p1 = q * 4;
	if (p1 > h * 2) p1 = h * 2;
	if (p1 > s) p1 = s;
	if (p1 * 2 > d) {
		P = d;
		P *= n / 2;
		P += p1 * (n % 2);
	}
	else {
		P = p1*n;
	}
	printf("%lld\n", P);
	return 0;
}


Measured memory_bytes: 128
#include <cstdio>

const int MOD = (int)1e9 + 7;

void update(int& x, int a)
{
    x += a;
    if (x >= MOD) {
        x -= MOD;
    }
}

int pow(int n)
{
    int result = 1, a = 10;
    while (n) {
        if (n & 1) {
            result = 1LL * result * a % MOD;
        }
        a = 1LL * a * a % MOD;
        n >>= 1;
    }
    return result;
}

int main()
{
    int s;
    scanf("%d", &s);
    int result = s / 8, tmp = s, j = 1, len_j = 1, nxt_j = 10;
    while (true) {
        if (j == nxt_j) {
            len_j ++, nxt_j *= 10;
        }
        if (len_j > tmp) {
            break;
        }
        tmp -= len_j, j ++;
    }
    for (int i = 1, len_i = 1, nxt_i = 10; i < 10000000; ++ i) {
        while (len_j <= tmp) {
            tmp -= len_j, j ++;
            if (j == nxt_j) {
                len_j ++, nxt_j *= 10;
            }
        }
        if (tmp == 0) {
            result ++;
        }
        if (i == nxt_i) {
            len_i ++, nxt_i *= 10;
        }
        tmp += len_i;
    }
    auto check = [&](int d) {
        if (d * 8 <= s) {
            update(result, pow(s / d));
            update(result, MOD - pow(s / d- 1));
            update(result, MOD - d);
        }
    };
    for (int d = 1; d * d <= s; ++ d) {
        if (s % d == 0) {
            check(d);
            if (d * d != s) {
                check(s / d);
            }
        }
    }
    printf("%d\n", result);
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        
        Scanner sc = new Scanner(System.in);
        int num[] = new int[3];
        
        for(int i = 0; i < 3; i++) num[i] = sc.nextInt();
        Arrays.sort(num);
        int ans = num[2] * 10 + num[1] + num[0];
        
        System.out.println(ans);

    }
}


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

using namespace std;

int n;
int a[100000][3];
int dp[100001][4];

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i][0] >> a[i][1] >> a[i][2];
	memset(dp, -1, sizeof(dp));
	for (int i = 0; i <= n; i++)
	{
		for (int j = 1; j <= 3; j++)
		{
			if (i == 0)
				dp[i][j] = 0;
			else
			{
				for (int k = 1; k <= 3; k++)
				{
					if (k != j)
						dp[i][j] = max(dp[i][j], a[i - 1][j - 1] + dp[i - 1][k]);
				}
			}
		}
	}
	int ans = max(max(dp[n][1], dp[n][2]), dp[n][3]);
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 2944
from bisect import bisect_left, bisect_right
n=int(input())
a=sorted(map(int,input().split()))
b=sorted(map(int,input().split()))
c=sorted(map(int,input().split()))

ans=0
for i in range(n):
    s=b[i]
    upper=bisect_left(a,s)
    lower=n-bisect_right(c,s)
    ans+=(upper*lower)

print(ans)

Measured memory_bytes: 99508
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

int n;
vvi g;

P dfs(int v,int p){
	ll A=1,B=1;
	for(auto u:g[v]) if(u!=p){
		P p=dfs(u,v);
		(A*=p.first)%=mod;
		(B*=p.second)%=mod;
	}
	return {(A+B)%mod,A};
}

int main(){
	cin>>n;
	g=vvi(n);
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		u--;v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	cout<<dfs(0,-1).first<<endl;
}

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

#define rep(i, n) for(long long i=0;i<(long long)(n);i++)
#define rep2(i, s, n) for(long long i=(s);i<(long long)(n);i++)
#define repi(i, n) for(int i=0;i<(int)(n);i++)
#define rep2i(i, s, n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define chmax(s, t) s=max(s,t);
#define chmin(s, t) s=min(s,t); 

#define deg2rad(deg) (((deg)/360)*2*M_PI)
#define rad2deg(rad) (((rad)/2/M_PI)*360)

using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;

const ll INF = (1LL<<60);
const int INFi = (1<<29);

/*素数判定*/
bool is_prime(ll n){
    if(n==1) return false;
    for(ll i=2;i*i<=n;i++){
        if(n%i==0) return false;
    }
    return true;
}

/*約数列挙*/
vll enum_divisors(ll n){
    vll l;
    for(ll i=1;i*i<=n;i++){
        if(n%i==0){
            l.push_back(i);
            if(n/i != i) l.push_back(n/i);
        }
    }
   sort(all(l));
   return l;
}

/*素因数分解*/
vector<P> prime_factorize(ll n){
    vector<P> l;
    for(ll i=2;i*i<=n;i++){
        if(n%i!=0) continue;
        ll e = 0;
        while(n%i==0){
            e++;
            n /= i;
        }
        l.push_back({i, e});
    }
    if(n!=1) l.push_back({n, 1});
    return l;
}

/*最小公倍数*/
ll lcm(ll a, ll b){
    return a*b/__gcd(a,b);
}

/*最大公約数*/
ll gcd(ll a, ll b){
    return __gcd(a,b);
}

/*組み合わせ(Combination)*/
const ll CMAX = 1010000;
const ll CMOD = 1e9+7;
ll fac[CMAX], finv[CMAX], inv[CMAX];
// テーブルを作る前処理
void combinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (ll i = 2; i < CMAX; i++) {
		fac[i] = fac[i - 1] * i % CMOD;
		inv[i] = CMOD - inv[CMOD%i] * (CMOD / i) % CMOD;
		finv[i] = finv[i - 1] * inv[i] % CMOD;
	}
}
// 二項係数計算
ll comb(ll n, ll k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % CMOD) % CMOD;
}

/*階乗*/
ll factorial(ll n){
    const ll FMOD = 1e9+7;
    ll ret = n;
    for(ll i=n-1;i>0;i--){
        ret*=i;
        ret%=FMOD;
    }
    return (ret?ret:1);
}


int main(){

    ll n; cin >> n;
    ll ans = 0;
    ll mx = 0;
    rep(i, n){
        ll d1, d2;
        cin >> d1 >> d2;
        if(d1==d2){
            ans++;
        }
        else{
            ans = 0;
        }
        chmax(mx, ans);
    }

    cout << (mx>=3?"Yes":"No") << endl;

    return 0;
}

Measured memory_bytes: 3632
import sys
import math
readline = sys.stdin.readline
a, b = [int(x) for x in readline().strip().split(" ")]
ans = -1
for i in range(13, 1001):
    if a == math.floor(i * 0.08) and b == math.floor(i * 0.1):
        ans = i
        break
print(ans)


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

using namespace std;

int main(){
    int n;
    long min = 9999999999999;
    long s=0;
    long s2 = 0;
    int i = 0;
    cin >> n;
    int v[n];
    for(i=0;i<n;i++){
        cin>>(v[i]);
        s = s+v[i];
    }
    for(i=0;i<n-1;i++){
        s2 = s2 + v[i];
        if(abs(s-2*s2)<min){
            min = abs(s-2*s2);
        }
    }
    cout<<min;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main()
{   /// Standing in the hall of fame
    ios_base::sync_with_stdio() , cin.tie(NULL) , cout.tie(NULL);
    int a , b , c , s;
    cin >> a >> b;
    if(b == 1)return cout << "0\n" , 0;
    s = a , c = 1;
    while(s < b)
        s += (a-1) , c++;
    cout << c << "\n";
    return 0;
}


Measured memory_bytes: 256
//BUGSBUNNY
//IIT ROORKEE
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define double long double
#define ld long double
#define endl '\n'
#define vi vector<int>
#define vvi vector<vi>
#define vs vector<string>
#define vl vector<long long>
#define vpii vector<pii>
#define vpipii vector<pipii>
#define vb vector<bool>
#define pb push_back
#define pob pop_back
#define mp make_pair
#define pii pair<int,int>
#define pipii pair<int,pii>
#define piipi pair<pii,int>
#define pld pair<long double,long double>
#define mod 1000000007 
// #define mod 998244353
#define rep(i,n) for (ll i = 0; i < n; i++)
#define repp(i,a,b) for(ll i = a ; i<b ; i++)
#define reppr(i,a,b) for(ll i = a-1 ; i>=b ; i--)
#define repr(i,n) for (ll i = n - 1; i >= 0; i--)
#define ff first
#define ss second
#define pc putchar_unlocked
#define gc getchar_unlocked
#define inf 9223372036854775807
#define infn -9223372036854775807
#define pi 3.14159265358979323846
#define eps 0.0000000001
#define sp << " " <<
#define setprec(x) cout << fixed << setprecision(x);
#define REVERSE(a) reverse(all(a));
#define SORT(a) sort(all(a));
#define all(n) n.begin(),n.end()
 
//GCD and LCM
    int gcd (int a, int b) { return b ? gcd (b, a % b) : a; }
    int lcm (int a, int b) { return a / gcd(a, b) * b; }
 
//Modular Exponentiation
    int powmod(int x,int y) 
    { 
        if (y == 0) return 1; 
        int p = powmod(x, y/2) % mod; 
        p = (p * p) % mod;   
        return (y%2 == 0)? p : (x * p) % mod; 
    }
 
//Modular Inverse
    int inverse(int a) 
    { 
       return powmod(a,mod-2); 
    }

//Binomial Coefficients
    int fact[200010], factinv[200010] , first = 0;
    void Util_nCr()
    {
        fact[0] = 1 , factinv[0] = 1;
        repp(i,1,200010)
        {
            fact[i] = (fact[i-1] * i)%mod;
            factinv[i] = (factinv[i-1] * inverse(i))%mod;
        }
    }
    int nCr(int n , int r)
    {
        if(!first) first = 1 , Util_nCr();             
        return ((fact[n] * inverse(fact[n-r]) % mod * inverse(fact[r]))%mod) ;
    }

void solve();
signed main()
{
    //-------------------------------------------------------------------------------   
        ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
        clock_t clk = clock();
    //-------------------------------------------------------------------------------   
    //-------------------------------------------------------------------------------
        int t = 1;
        // cin >> t;    
        rep(i,t)
            solve();
    //-------------------------------------------------------------------------------
        clk = clock() - clk;
        cerr << fixed << setprecision(12) << "Time: " << ((double)clk)/CLOCKS_PER_SEC;
    //-------------------------------------------------------------------------------
}

void solve()
{
    int s , w;
    cin >> s >> w;
    if(w>=s)
        cout << "unsafe\n";
    else
        cout << "safe\n";
}  

Measured memory_bytes: 3804
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define Repr(i, n, a) for (int i = (n); i >= (a); i--)
#define rep(i, n) Rep(i, 0, n)
#define repr(i, n) Repr(i, n, 0)
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;

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

    int n, m;
    cin >> n >> m;
    int a[20][20] = {};
    rep(i, m)
    {
        int k;
        cin >> k;
        rep(j, k)
        {
            int x;
            cin >> x;
            x--;
            a[i][x] = 1;
        }
    }
    vector<int> p(m);
    rep(i, m) cin >> p[i];
    int ans = 0;
    for (int i = 0; i < (1 << n); i++)
    {
        int cnt = 0;
        rep(j, m)
        {
            int num = 0;
            rep(k, n) if (a[j][k] == 1 && (i & (1 << k))) num++;
            if (num % 2 == p[j] % 2)
                cnt++;
        }
        if (cnt == m)
            ans++;
        //cout << i << " " << cnt << endl;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.*;

// UVa 11504

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		int a = in.nextInt();
		char c = in.next().toCharArray()[0];
		int b = in.nextInt();
		
		if (c == '+') {
			System.out.println(a + b);
		} else {
			System.out.println(a - b);
		}
	}
}

Measured memory_bytes: 22612
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>
#include <map>
#include <time.h>
#include <iomanip>
#include <bitset>

using namespace std;

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

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod (ll)(1e9+7)
#define int ll

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

signed main() {
    string s;
    cin >> s;
    int ans = 0;
    bool f = false;
    for(int i = 0; i < s.length(); i++) {
        ans++;
        if(i > 0 && s[i] == s[i - 1]) {
            if(f) f = false;
            else {
                i++, f = true;
                if(i == s.length()) ans--;
            }
        }
        else f = false;
    }

    cout << ans << endl;
}


Measured memory_bytes: 720
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <climits>
#include <set>
#include <map>
#include <iomanip>
#include <cassert>
#include <functional>
#include <cstring>

using namespace std;

#define mp make_pair
#define FOR(i, a, b) for(int (i)=a;(i)<=(b);++(i))
#define rep(i, n)  FOR(i,0,n-1)
#define FFOR(i, a, b) for(int (i)=a;(i)>(b);--(i))
#define rrep(i,n) FFOR(i,0,n)
#define vsort(v) sort((v).begin(), (v).end());					//小さい順
#define rvsort(v) sort(v.begin(), v.end(),greater<>());		//大きい順
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define all(c) (c).begin(),(c).end()
#define ll long long
#define lb long double
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define vs vector<string>
#define vc vector<char>
#define vvc vector<vector<char>>
#define Print(p) cout<<(p)<<endl
#define F first
#define S second
#define pb push_back
#define ll long long
#define mod 1000000007LL
#define INF 123456789012345
typedef pair<ll, ll> P;
typedef pair<int, P> PP;

const int maxn =1e5 + 10;

vector<P> goen[maxn],gosn[maxn];
ll ryoen[maxn],ryosn[maxn];
ll dist[maxn];
ll ans[maxn];


void dik(ll start,ll n,vector<P> go[],ll ryo[])
{
	priority_queue< P,vector<P>,greater<P> > que;
	que.push(mp(0,start));
	rep(i,maxn-1) dist[i] = INF;
	dist[start] = 0;

	while(!que.empty())
	{
		ll nown = que.top().second;
		ll nowc = que.top().first;
		que.pop();

		rep(i,go[nown].size())
		{
			ll nxtn = go[nown][i].first;
			ll nxtc = nowc + go[nown][i].second;
			if(dist[nxtn] <= nxtc) continue;
			dist[nxtn] = nxtc;
			que.push(mp(nxtc,nxtn));
		}
	}
	
	rep(i,n) ryo[i] = dist[i];
}

int main() {
	
	ll n,m,s,t;cin>>n>>m>>s>>t;
	s--,t--;
	rep(i,m)
	{
		int u,v,a,b;cin>>u>>v>>a>>b;
		u--,v--;
		goen[u].pb(mp(v,a));
		goen[v].pb(mp(u,a));
		gosn[u].pb(mp(v,b));
		gosn[v].pb(mp(u,b));
	}

	dik(s,n,goen,ryoen);
	dik(t,n,gosn,ryosn);

	ans[n-1]=ryoen[n-1]+ryosn[n-1];
	for(int i=n-2;i>=0;i--)	ans[i] = min(ans[i+1],ryoen[i]+ryosn[i]);

	rep(i,n) cout << 1000000000000000 - ans[i] << endl;

	return 0;
}

Measured memory_bytes: 21932
N = int(input())
A = list(map(int,input().split()))
B = [0]*(10**6)
c = int()
ans = int(0)
for i in range(len(A)):
  B[A[i]] += 1

for i in range(1,len(B)-2):
  c = 0
  c += B[i-1]
  c += B[i]
  c += B[i+1]
  if ans <= c:
    ans = c
print(ans)

Measured memory_bytes: 91156
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
int main(void){
  char a[11];
scanf("%s",&a);
 int b= strlen(a);
int c[20];

 for(int i =0;i<b;i++){
   c[i]= a[i]-'0';
 };
int  d[20];
 for(int i=0;i<b-2;i++){
   d[i]=100 * c[i] + c[i+1] *10 + c[i+2];
 }
 int win = d[0];
 for(int i=0;i<b-2;i++){
   if(abs(win-753)>abs(d[i]-753)){
     win = d[i];
   }
 }
 printf("%d",abs(win-753));
 return 0;
}


Measured memory_bytes: 256
# import numpy as np
import sys, math, heapq
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")

S = int(input())
num = S // 3
res = 0


fact = [1]
for i in range(1, S + 10):
    fact.append(fact[-1] * i % MOD)


def rev(x):
    return pow(x, MOD - 2, MOD)


def cmb(i, k):
    if i < k:
        return 0
    return fact[i] * rev(fact[k]) * rev(fact[i - k]) % MOD


def cmb2(n, r, p):
    r = min(n - r, r)
    if r == 0:
        return 1
    over = 1
    for i in range(n, n - r, -1):
        over = over * i % p
    under = 1
    for i in range(1, r + 1):
        under = under * i % p
    inv = pow(under, p - 2, p)
    return over * inv % p


def h(i, k):
    return cmb(i + k - 1, k)


for r in range(1, num + 1):
    val = h(r, S - 3 * r)
    # print("r, val", r, val)
    res += val
res %= MOD
print(res)


Measured memory_bytes: 67856
import sys
sys.setrecursionlimit(10**7)
S = input()
K = int(input())

lenS = len(S)
if lenS == 1:
    print(K//2)
    exit()

cnt_one = 0
i = 0
while i < lenS-1:
    if S[i] == S[i+1]:
        cnt_one += 1
        i += 2
    else:
        i += 1

if K == 1:
    print(cnt_one)
    exit()

SS = S*2
lenSS = len(SS)

cnt_two = 0
i = 0
while i < lenSS-1:
    if SS[i] == SS[i+1]:
        cnt_two += 1
        i += 2
    else:
        i += 1

if len(set(S)) == 1:
    if lenS%2 == 1:
        if K%2 == 0:
            ans = (cnt_two) * (K//2)
        else:
            ans = (cnt_one * (K//2 + 1)) + ((cnt_two-cnt_one) * (K//2))
        print(ans)
        exit()

print((cnt_two - cnt_one)*(K-1) + cnt_one)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define REP(i,n) for(int i = 0; i < n; i++)
#define REPR(i,n) for(int i = n; i >= 0; i--)
#define FOR(i,m, n) for(int i = m-1; i < n; i++)
#define INF 2000000000
#define ALL(v) v.begin(), v.end()
#define chmax(x,y) (x = max(x,y))
#define chmin(x,y) (x = min(x,y))
#define FILL2D(A,c) fill(A[0], A[0] +sizeof(A)/sizeof(**A),c)
#define FILL3D(A,c) fill(A[0][0], A[0][0] +sizeof(A)/sizeof(***A),c)
//vector<vector<要素の型>> 変数名(要素数1, vector<要素の型>(要素数2, 初期値))
//vector<intなど> 変数名(要素数,初期値)
using namespace std;
typedef long long ll;
//gcd,lcmセット
ll gcd(ll a, ll b){
   if (a%b == 0) return b;
   else return gcd(b, a%b);
}
ll lcm(ll a, ll b){	
   return a*b/gcd(a, b);
}
bool isPrime(ll x){
    int i;
    if(x < 2)return false;
    else if(x == 2) return true;
    if(x%2 == 0) return false;
    for(i = 3; i*i <= x; i += 2) if(x%i == 0) return false;
    return true;
}
//dfsではvector<vector<int>> g(n);で◎
int main(){
  int a,b,c,x,y;
  cin>>a>>b>>c>>x>>y;
  int mx=INF;
  for(int i=0;i<=100000;i++){
    mx=min(mx,max(a*(x-i),0)+max(b*(y-i),0)+c*2*i);
    
  }
    cout<<mx<<endl;
}

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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define ALL(a) (a).begin(),(a).end()
#define X first
#define Y second

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


const double PI = 3.14159265358979;

void solve()
{
  ll n, a, b, c, d;
  cin >> n;
  vector<P> red(n);
  vector<P> blue(n);
  vector<bool> r_used(n, false);
  for(int i = 0; i < n; ++i)
  {
    cin >> a >> b;
    red[i] = P(a, b);
  }
  for(int i = 0; i < n; ++i)
  {
    cin >> c >> d;
    blue[i] = P(c, d);
  }

  // sort(ALL(red));
  sort(ALL(blue));

  int ans = 0;  
  for(int i = 0; i < n; ++i)
  {
    int rj = -1;
    for(int j = 0; j < n; ++j)
    {
      if (r_used[j]) continue;
      if (red[j].X < blue[i].X && red[j].Y < blue[i].Y)
      {
        if ((rj == -1) || red[rj].Y < red[j].Y)
        {
          rj = j;
        }
      }
    }
    if (rj != -1)
    {
      r_used[rj] = true;
      ans++;
    }
  }
  cout << ans;
}

int main()
{
  fastio;
  solve();

  return 0;
}

Measured memory_bytes: 3664
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

money = 10**15
N, M, s, t = map(int, input().split())
s -= 1; t -= 1
graph = [[[] for i in range(N)] for _ in range(2)]
for i in range(M):
  u, v, a, b = map(int, input().split())
  u -= 1; v -= 1
  graph[0][u].append((v, a)); graph[0][v].append((u, a))
  graph[1][u].append((v, b)); graph[1][v].append((u, b))


def dijkstra(s, mode):
  dist = [-1] * N
  dist[s] = 0
  e = []
  for child, cost in graph[mode][s]:
    heappush(e, (cost, child))
  while e:
    cost, node = heappop(e)
    if dist[node] >= 0:
      continue
    dist[node] = cost
    for child, c in graph[mode][node]:
      if dist[child] >= 0:
        continue
      heappush(e, (cost+c, child))
  return dist
  
dist = [dijkstra(s, 0), dijkstra(t, 1)]  
value = [dist[0][i]+dist[1][i] for i in range(N)]

ans = []
cost = []
for i in range(N-1, -1, -1):
  heappush(cost, value[i])
  ans.append(money - cost[0])

print(*(ans[::-1]), sep='\n')

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

using ll = long long;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = (n); i > 0; i--)
#define all(n) n.begin(), n.end()
#define print(n) cout << n << endl

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    int n,m,s,c;
    cin >> n >> m;
    vector<int> ans(n,-1);
    rep(i,m){
        cin >> s >> c;
        s--;
        if(n != 1 && s==0 && c==0){
            ans[0] = -2;
            break;
        }else if(ans[s] != -1 && ans[s] != c){
            ans[0] = -2;
            break;
        }else{
            ans[s] = c;
        }
    }

    if(ans[0]==-2) print(-1);
    else{
        int sum=0,o=1;
        rep(i,n){
            if(i==n-1 && ans[n-1-i]==-1 && n!=1) ans[n-1-i]=1;
            else if(ans[n-1-i]==-1) ans[n-1-i]=0;
            sum+=ans[n-1-i]*o;
            o *= 10;
        }
        print(sum);
    }
    return 0;
}

Measured memory_bytes: 256
N = gets.chomp.to_i
A = Array.new(N+1)
XY = Array.new(N+1)
1.upto(N) do |x|
  A[x] = gets.chomp.to_i
  XY[x] = {}
  A[x].times do
    y, flag = gets.chomp.split(" ").map(&:to_i)
    XY[x][y] = flag
  end
end

require "set"

def mujun?(root, sj = Set.new, nj = Set.new)
  XY[root].each do |y, flag|
    if (flag == 1 && (XY[y][root] == 0 || nj.include?(y))) ||
      (flag == 0 && sj.include?(y))
      return true
    end
  end
  false
end

ALL = (1..N).to_set
nj = ALL.select {|x| mujun?(x)}.to_set
rest = (ALL - nj).to_a
rest.size.downto(0) do |n|
  rest.combination(n) do |sj|
    nnj = ALL - sj
    if sj.select {|x| mujun?(x, sj, nnj)}.empty?
      puts n
      exit
    end
  end
end
puts 0


Measured memory_bytes: 3324
#include <stdio.h>

#define min(a, b) ((a) < (b) ? (a) : (b))

int main(void)
{
	int N, A, B, ans = 0;
	scanf("%d %d %d", &N, &A, &B);

	ans = min(A * N, B);
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 128
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string>
#include<iostream>
#include<cctype>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include <algorithm>
#include<math.h>
#include<set>
#include<map>
#include<iomanip>

//#include<bits/stdc++.h>


using namespace std;


int main() {

	int k, s;
	cin >> k >> s;
	int ans = 0;
	for (int i = 0; i <= k; i++) {
		for (int j = 0; j <= k; j++) {
			if (s - i - j < 0)break;
			if (s-i - j <=k )ans++;
			
		}
	}

	cout << ans << endl;
	return 0;

}




Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(A) (A).begin(), (A).end()
#define ll long long
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

const ll mod = 1e9 + 7;
const ll INF = -1 * ((1LL << 63) + 1);
const int inf = -1 * ((1 << 31) + 1);

const int MAX = 200005;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    COMinit();
    int n,k;
    cin >> n >> k;
    ll ans = 0;
    rep(i,min(n+1,k+1)){
        ans += COM(n,i)*COM(i+n-i-1,i);
        ans %= mod;
    }
    cout << ans << endl;
}

Measured memory_bytes: 4992
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <math.h>
#include <cmath>
#include <limits.h>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <functional>
#include <stdio.h>
using namespace std;

long long MOD = 1000000007;

int func( string s ) {
    int ret = 0;
    for ( int i = 0; i < s.length(); i++ ) {
        ret += s[i] - '0';
    }
    return ret;
}

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

    long long a = 1;
    while ( a < N ) {
        a *= 10;        
    }
    if ( a != 1 ) { a /= 10; }

    cout << max( func(to_string( N/a*a-1 )), func(to_string(N)) );
    
    return 0;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
b = [0] * n
cnt = 0
cnt_0 = 0
for i in range(n):
    if a[i] < 0:
        cnt += 1
    elif a[i] == 0:
        cnt_0 += 1
    b[i] = abs(a[i])

if cnt % 2 == 0 or cnt_0 >= 1:
    ans = sum(b)
else:
    ans = sum(b) - min(b) * 2

print(ans)

Measured memory_bytes: 19936