akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef pair<string,ll> si;
typedef pair<ii,ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
#define sort(a) sort(a.begin(),a.end());
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define mp make_pair
#define F first
#define S second
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define nl "\n"
#define TC cin>>t;while(t--)
const int MOD = 1e9+7;
const ld PI = 3.1415926535898;
const ll LLMAX = LLONG_MAX;
 
int main()
{
	int r;
	cin>>r;
	ld a=1.0*PI*2*r;
	cout<<a<<nl;
}

Measured memory_bytes: 3752
#include <numeric>
#include<iostream>
#include<set>
#include <bitset>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include <cstdio>
#include<algorithm>
#include <sstream>
#include<string>
#include<string.h>
#include <cmath>
#include <iomanip>
#include <string>
#include<list>
using namespace std;
#define int long long
#define ll long long
#define mod  1000000007
#define inf 1e17
#define rep(i,j,n) for(int i=j;i<n;i++)
double pi = 3.141592653589793;
//使うやつはここから下に置こうな
//就職させてください!!!!
signed main(){
    string s;cin>>s;
    int w;cin>>w;
    for(int i=0;i<s.size();i+=w){
        cout<<s[i];
    }
    cout<<endl;
    return 0;
}

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

int main()
{
    int a , b;
    cin >> a >> b;
    if((a <= 9 and a >= 1) and (b >= 1 and b <= 9)) cout << a*b << endl;
    else cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b)-1);i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int, int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define pque(type) priority_queue<type,vector<type>,greater<type> >
#define memst(a,b) memset(a,b,sizeof(a))

int main(void){
	vector<int> c(3);
	cin >> c[0] >> c[1] >> c[2];
	sort(c.begin(),c.end());
	
	if(c[0]+c[1] == c[2]) cout << "Yes" << endl;
	else cout << "No" << endl;
	
	return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.PrintWriter
import kotlin.math.max
import kotlin.math.min

val br = BufferedReader(InputStreamReader(System.`in`))
val out = PrintWriter(System.out)

fun main() {
    br.use { out.use {
        solve()
        out.flush()
    } }
}

fun solve() {
    val n = readInteger()
    var ans = 1L
    var max = 0L
    for (i in 1L..n) {
        val count = countDiv(i, 2)
        if (count > max) {
            max = count
            ans = i
        }
    }
    out.println(ans)
}

/** O(log(n)) */
tailrec fun countDiv(n: Long, divisor: Long, count: Long = 0L): Long =
    if (n % divisor == 0L) countDiv(n / divisor, divisor, count + 1) else count

fun readInteger() = Integer.parseInt(br.readLine())
fun readLong() = java.lang.Long.parseLong(br.readLine())
fun readStringList() = br.readLine()!!.split(' ')
fun readIntegerList() = readStringList().map(Integer::parseInt)
fun readLongList() = readStringList().map(java.lang.Long::parseLong)
fun readDoubleList() = readStringList().map(java.lang.Double::parseDouble)


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

int n;
int a[200005];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    int curr = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] == curr + 1)
            curr++;
    }

    curr == 0 ? cout << -1 : cout << n - curr;

    return 0;   
}

Measured memory_bytes: 1024
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
const double EPS = 1e-9;
typedef pair<int, int> P;
typedef unsigned int ui;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
int main() {
	int n; vector<int>v; vector<int>u;
	int i = 1; int t = 1;
	while (t < 1000000) {
		v.push_back(t);
		if (t % 2)u.push_back(t);
		t *= (i + 3);
		t /= i;
		i++;
	}
	int dp1[1000000],dp2[1000000];
	fill(dp1, dp1 + 1000000, (int)MOD);
	fill(dp2, dp2 + 1000000, (int)MOD);
	dp1[0] = dp2[0] = 0;
	int len = v.size();
	rep(i, len) {
		rep(j, 1000000) {
			if (dp1[j]!=(int)MOD&&j + v[i] < 1000000) {
				dp1[j + v[i]] = min(dp1[j + v[i]], dp1[j] + 1);
			}
		}
	}
	len = u.size();
	rep(i, len) {
		rep(j, 1000000) {
			if (dp2[j] != (int)MOD&&j + u[i] < 1000000) {
				dp2[j + u[i]] = min(dp2[j + u[i]], dp2[j] + 1);
			}
		}
	}
	while (cin >> n, n) {
		cout << dp1[n] << " " << dp2[n] << endl;
	}
	return 0;
}


Measured memory_bytes: 10884
def sequence(lis, first_value):
    count = 0
    now_sum = first_value
    pre_sum = first_value
    for num in lis[1:]:
        now_sum += num
        if now_sum == 0 or pre_sum * now_sum > 0:
            count += abs(now_sum) + 1
            now_sum = -1 * pre_sum / abs(pre_sum)
        pre_sum = now_sum
    return int(count)

n = int(input())
a = [int(i) for i in input().split()]
if a[0] == 0:
    print(min(sequence(a, 1)+1, sequence(a, -1)+1))
else:
    print(min(sequence(a, a[0]), sequence(a, -1*a[0]/abs(a[0]))+abs(a[0])+1))

Measured memory_bytes: 14468
#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<b;i++)
using namespace std;
int main()
{
    string a, b, c;
    cin >> a >> b >> c;
    if (a[a.size()-1] == b[0] && b[b.size()-1] == c[0]) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
}


Measured memory_bytes: 256
/* BISMILLAHIR RAHMANIR RAHIM */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int mxn = 1e5 + 5;
ll f[mxn];

int main() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	ll n, k;
	cin >> n >> k;
	for(int i = 0, a, b; i < n; i++) {
		cin >> a >> b;
		f[a] += b;
	}
	for(int i = 1; i < mxn; i++) {
		if( k >= f[i] ) {
			k -= f[i];
		}
		else {
			k = 0;
		}
		if( k == 0 ) {
			cout << i << "\n";
			break;
		}
	}
}


Measured memory_bytes: 1024
// Problem: A - Takoyaki
// Contest: AtCoder - AtCoder Beginner Contest 176
// URL: https://atcoder.jp/contests/abc176/tasks/abc176_a
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <algorithm>
#include <cmath>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

#define fastio  ios_base::sync_with_stdio(false); cin.tie(0);

using namespace std;

int main()
{
	float n,t,x;
	cin>>n>>x>>t;
	
	cout << (int)(ceil(n/x)*t);
	
	return 0;
}


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

int main () {
  string A, B, C;
  cin >> A >> B >> C;
  int a, b;
  a = A.size();
  b = B.size();
  if (A.at(a-1)==B.at(0)&&B.at(b-1)==C.at(0)) {
    cout << "YES" << endl;
  }
  else {
    cout <<"NO" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int lint
typedef long long lint;
typedef pair<int,int> P;
const int    INF=(int)1e9;
const int    MOD=(int)1e9+7;
const double EPS=(double)1e-10;
struct Accelerate_Cin{
    Accelerate_Cin(){
        cin.tie(0); ios::sync_with_stdio(0);cout<<fixed<<setprecision(20);
    };
};



signed main(){
  int n;
  queue<int>q;
  while(cin>>n,n){
    int dp[100];
    dp[1]=1,dp[2]=2,dp[3]=4;
    for(int t=1;t<30;t++){
      dp[t+3]=dp[t+2]+dp[t+1]+dp[t];
    }
    q.push(ceil((double)dp[n]/3650));
  }

  while(!q.empty()){
    cout<<q.front()<<endl;
    q.pop();
  }
  return 0;
}



Measured memory_bytes: 3004
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<time.h>
#define rep(i,n)for(ll i=0;i<n;i++)
#define ll long long
#define ggr getchar();getchar();return 0;
#define prique priority_queue
#define inf 1145141919364364
#define double long double
using namespace std;
typedef pair<ll, ll>P;
ll gcd(ll x, ll y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
ll lcm(ll x, ll y) {
	return x * y / gcd(x, y);
}
ll a[55];
signed main() {
	ll p, memo = 0;
	cin >> p;
	rep(i, p)cin >> a[i];
	rep(i, p) {
		if (a[i] == i + 1)memo++;
	}
	if (memo >= p - 2)puts("YES");
	else puts("NO");
	ggr
}





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

#define tm tm228
#define hash hash228
#define matr vector < vector < int > >
#define int long long
#define pii pair < int, int >
#define tri pair < pair < int, int >, int >
#define all(v) v.begin(), v.end()
#define endl "\n"

using namespace std;

void solve(){
    int n, m;
    cin >> n >> m;
    int ans = (n - 1) * n / 2 + (m - 1) * m / 2;
    cout << ans;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m = 1;
    //cin >> m;
    while (m--)
    {
        solve();
        cout << endl;
    }
    return 0;
}


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

int main(){
    // 制約見て！！！デカかったらlong longにすること！
    string s;
    cin >> s;
    int m = 753;
    rep(i,s.size()-2){
        string sub = s.substr(i,3);
        int x = stoi(sub);
        m = std::min(m,abs(x-753));
    }
    cout << m <<endl;
}

Measured memory_bytes: 3624
#include <iostream>
#include <vector>
#include <string>



using namespace std;

int N;
string S, T;



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

	string ans;
	ans.resize(2 * N);

	for (int i = 0; i < N; i++) {
		ans[2 * i] = S[i];
		ans[2 * i + 1] = T[i];
	}


	cout << ans << endl;

	return 0;
}



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

using namespace std;

int main() {
    int n;
    cin >> n;
    int x = n;
    int total = 0;
    while (x > 0) {
        total+=x%10;
        x/=10;
    }
    n%total == 0 ? cout << "Yes" << endl : cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3612
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[25];
ll dp(int l,int r,int xl,int xr){
	if (r-l<=1)return 0;
	ll ans=1e18;
	for (int i=l+1;i<=r-1;i++) ans=min(ans,dp(l,i,xl,xl+xr)+dp(i,r,xl+xr,xr)+a[i]*(xl+xr));
	return ans;
}
int main(){
	int n;
	cin>>n;
	for (int i=1;i<=n;i++) cin>>a[i];
	cout<<a[1]+a[n]+dp(1,n,1,1)<<endl;
	return 0;
}

Measured memory_bytes: 3660
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val k = sc.nextLong()
    val a = (1..n).map { sc.nextInt() - 1 }
    val used = Array(n) {-1L}

    var pos = 0
    var cost = 0L
    var preCost = -1L
    var loopStart = -1
    var loopCost = -1L
    while (true) {
        if (used[pos] != -1L) {
            loopStart = pos
            loopCost = cost - used[pos]
            preCost = used[pos]
            break
        }

        if (k == cost) {
            println(pos + 1)
            return
        }

        used[pos] = cost
        cost++
        pos = a[pos]
    }

    pos = loopStart
    var remCost = (k - preCost) % loopCost
    while (true) {
        if (remCost == 0L) {
            println(pos + 1)
            return
        }
        remCost--
        pos = a[pos]
    }
}

Measured memory_bytes: 66012
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9;
const double PI = acos(-1.0);

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

	int H, W;
	while(1) {
		cin >> H >> W;
		if(H == 0 && W == 0) break;
		for(int i = 0; i < H; i++) {
			for(int j = 0; j < W; j++) {
				if(i == 0 || i == H - 1 || j == 0 || j == W - 1) cout << "#";
				else cout << ".";
			}
			cout << "\n";
		}
		cout << "\n";
	}
	return 0;
}

Measured memory_bytes: 1176
#include<stdio.h>
#include <string>
#include <algorithm>
#include <iostream>
#include<cmath>
using namespace std;

const static long INF = 1e15+1;
long n, A[5], min_a, t;

int main() {
    scanf("%ld", &n);
    min_a = INF;

    for ( int i = 0; i < 5; i++ ) {
        scanf("%ld", &A[i]);

        if ( min_a > A[i] ) {
            min_a = A[i];
        }
    }
    
    if ( n % min_a == 0 ) {
        t = n / min_a + 4;
    } else {
        t = n / min_a + 5;
    }
    
    printf("%ld\n", t);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < (int)b; i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    int in[n] = {};
    rep(i, 0, m) {
        int s, t;
        cin >> s >> t;
        g[s].push_back(t);
        in[t]++;
    }

    queue<int> que;
    vector<int> ans;
    rep(i, 0, n) {
        if (in[i] == 0) {
            que.push(i);
            ans.push_back(i);
        }
    }
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        for (int nv : g[v]) {
            in[nv]--;
            if (in[nv] == 0) {
                que.push(nv);
                ans.push_back(nv);
            }
        }
    }
    if ((int)ans.size() != n) cout << 1 << endl;
    else cout << 0 << endl;
    return 0;
}



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


namespace AtC
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = ReadInt();
            var ta = ReadIntArray();
            int T = ta[0], A = ta[1];
            var H = ReadIntArray();
            int index = -1;
            double min = int.MaxValue;
            for (var i = 0; i < H.Length; i++)
            {
                var temp = T - H[i] * 0.006;
                var delta = Math.Abs(temp - A);
                if (delta < min)
                {
                    min = delta;
                    index = i;
                }
            }

            Out(index + 1);
        }

        //最小公倍数
        static int LCM(int num1, int num2)
        {
            var gcd = GCD(num1, num2);
            return num1 * (num2 / gcd);
        }

        static long LCM(long num1, long num2)
        {
            var gcd = GCD(num1, num2);
            return num1 * (num2 / gcd);
        }

        //最大公約数
        static int GCD(int num1, int num2)
        {
            int a = Math.Max(num1, num2);
            int b = Math.Min(num1, num2);
            int mod;
            while ((mod = a % b) != 0)
            {
                a = b;
                b = mod;
            }

            return b;
        }

        static long GCD(long num1, long num2)
        {
            long a = Math.Max(num1, num2);
            long b = Math.Min(num1, num2);
            long mod;
            while ((mod = a % b) != 0)
            {
                a = b;
                b = mod;
            }

            return b;
        }

        static int[] ReadIntArray()
        {
            return Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        }

        static int ReadInt()
        {
            return int.Parse(Console.ReadLine());
        }

        static long[] ReadLongArray()
        {
            return Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
        }

        static long ReadLong()
        {
            return long.Parse(Console.ReadLine());
        }

        static string ReadString()
        {
            return Console.ReadLine();
        }

        static void Out(object o)
        {
            Console.WriteLine(o);
        }
    }

    static class EnumerableExtension
    {
        public delegate void Function<in T>(T val);

        public static void ForEach<T>(this IEnumerable<T> enumerable, Function<T> function)
        {
            foreach (var x in enumerable)
            {
                function(x);
            }
        }
    }

    class PriorityQueue<T>
    {
    }
}

Measured memory_bytes: 13340
#include<bits/stdc++.h>
#define ll long long 
#define mp make_pair 
#define pb push_back
#define F first 
#define S second 
#define f(i,n) for(int i=0;i<n;i++) 

using namespace std;

void test(){
	ll n;
	cin>>n;
	if(n%1000==0)cout<<"0\n";
	else cout<<1000-n%1000<<"\n";	
}

int main(){
	int tests=1;
//	cin>>tests;
	while(tests--){
		test();
	}
}

Measured memory_bytes: 3592
n, d = [int(x) for x in input().split()]

temp_list = []
for _ in range(n):
    x_list = [int(x) for x in input().split()]
    temp_list.append(x_list)

ans = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        dist = sum([(y - z) ** 2 for y, z in zip(temp_list[i], temp_list[j])]) ** 0.5
        if int(dist) == dist:
            ans += 1
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define rep2(i, s, n) for (int i = s; i < (int)n; i++)
#define all(obj) obj.begin(), obj.end()
#define debug(x) cerr << #x << ":" << x << "\n"
#define vdebug(vec) cerr << #vec << ":"; for (auto e : vec) cerr << e << " "; cout << "\n"
#define YN(f) cout << (f ? "YES" : "NO") << endl
#define Yn(f) cout << (f ? "Yes" : "No") << endl
#define yn(f) cout << (f ? "yes" : "no") << endl
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;

int main () {
	int N; cin >> N;
	vi P(N); // index -> value
	map<int, int> m; // value -> index
	rep(i, N) { // 0-indexed
		cin >> P.at(i); // index -> value
		m[P.at(i)] = i; // value -> index
	}	
	// vdebug(P);
	// for (auto mi : m) cout << mi.first << " " << mi.second << endl;
	set<int> s;
	s.insert(-2); s.insert(-1); s.insert(N); s.insert(N + 1); // 番兵 ※重複不可のため
	ll ans = 0;
	for (int k = N; k > 0; k--) { // k:value
		s.insert(m.at(k)); // indexを入れる		
		auto it = s.lower_bound(m.at(k)); // 値kに対応する添字xに対応するiterator
		ll l2 = max(*prev(prev(it)), -1);
		ll l1 = *prev(it);
		ll x = *it;
		ll r1 = *next(it);
		ll r2 = min(*next(next(it)), N);
		// debug(k);
		// for (auto si : s) cout << si << " "; cout << endl;
		// debug (l2); debug(l1); debug(x); debug(r1); debug(r2);
		ll temp = k * ((l1 - l2) * (r1 - x) + (x - l1) * (r2 - r1));
		// debug(temp);
		ans += temp;
	}

	cout << ans << endl;
}


Measured memory_bytes: 9984
fiveh_num = int(input())
oneh_num = int(input())
ften_num = int(input())
sum = int(input())

count = 0

for x in range(0,fiveh_num+1):
  for y in range(0,oneh_num+1):
    for z in range(0,ften_num+1):
      ans = x*500 + y*100 + z*50
      if ans == sum:
        count += 1
      else:
        pass
print(count)

Measured memory_bytes: 3064
#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;
}
void print() { cout << "\n"; }
template <class T> void print(const T &x) { cout << x << "\n"; }
template <class T, class... Args> void print(const T &x, const Args &... args) {
    cout << x << " ";
    print(args...);
}
template <class T> void printVector(const vector<T> &v) {
    for(const T &x : v) {
        cout << x << " ";
    }
    cout << "\n";
}
using ll = long long;

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
const double EPS = 1e-7;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
const double PI = acos(-1);
constexpr int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

//-------------------------------------

int N, A, B, C;
vector<string> s;
bool fin = false;
string ans;

void dfs(int d, int a, int b, int c, string &now) {
    if(fin) {
        return;
    }
    if(d == N && now.size() == N) {
        fin = true;
        ans = now;
        return;
    }
    if(s[d] == "AB") {
        if(a >= 1) {
            now += "B";
            dfs(d + 1, a - 1, b + 1, c, now);
            now.pop_back();
        }
        if(b >= 1) {
            now += "A";
            dfs(d + 1, a + 1, b - 1, c, now);
            now.pop_back();
        }
    } else if(s[d] == "AC") {
        if(a >= 1) {
            now += "C";
            dfs(d + 1, a - 1, b, c + 1, now);
            now.pop_back();
        }
        if(c >= 1) {
            now += "A";
            dfs(d + 1, a + 1, b, c - 1, now);
            now.pop_back();
        }
    } else {
        if(b >= 1) {
            now += "C";
            dfs(d + 1, a, b - 1, c + 1, now);
            now.pop_back();
        }
        if(c >= 1) {
            now += "B";
            dfs(d + 1, a, b + 1, c - 1, now);
            now.pop_back();
        }
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> A >> B >> C;
    s.resize(N);
    for(int i = 0; i < N; i++) {
        cin >> s[i];
    }
    string now = "";
    dfs(0, A, B, C, now);
    if(fin) {
        print("Yes");
        for(const auto &c : ans) {
            print(c);
        }
    } else {
        print("No");
    }
}

Measured memory_bytes: 13036
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#define pi 3.14159265358979323846264338327950

int main() {
	int A, B, C; std::cin >> A >> B >> C;
	if (A % 2 == 1 || B % 2 == 1 || C % 2 == 1) {
		std::cout << 0;
		return 0;
	}
	if (A == B && B == C && C == A) {
		std::cout << -1 << std::endl;
		return 0;
	}
	int count = 0;
	while (true) {
		int a = B / 2 + C / 2;
		int b = A / 2 + C / 2;
		int c = A / 2 + B / 2;
		++count;
		A = a;
		B = b;
		C = c;
		if (A % 2 == 1 || B % 2 == 1 || C % 2 == 1)
			break;
	}
	std::cout << count << std::endl;

	return 0;
}

Measured memory_bytes: 3640
using System;

public class Program
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine());
        if (n % 1000 == 0)
        {
            Console.WriteLine(0);
        }
        else
        {
            Console.WriteLine(1000 - (n % 1000));
        }
    }
}

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

   typedef long long ll;
   typedef pair<ll, ll> Pii;
   typedef vector<ll> Vi;
   typedef vector<Vi> VVi;

   const double EPS = (1e-7);
   const ll INF =(1e13);
   const double PI = (acos(-1));
   const ll MOD = ll(1e9) + 7;

   #define REP(i, n) for(ll i = 0; i < (ll)(n); i++)
   #define REPR(i, n) for(ll i = n; i > -1; i--)
   #define FOR(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
   #define ALL(x) (x).begin(),(x).end()
   #define SORT(x) sort((x).begin(), (x).end())
   #define RSORT(x) sort((x).rbegin(), (x).rend())
   #define REVERSE(x) reverse((x).begin(), (x).end())
   #define SZ(x) ((ll)(x).size())
   #define pb push_back
   #define mp make_pair

   //chmax(a, b): a>bならaをbで更新　更新したときにtrueを返す
   //chmin(a, b): a<bならaをbで更新　更新したときにtrueを返す
   template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
   template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

   #define dump(x) cerr<< #x << "= " << (x) << endl;

   ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
   ll pow(ll a, ll b){if (b == 0) return 1; else if (b % 2 == 0) return pow(a * a, b / 2); else return pow(a * a, b / 2) * a;}
   ll pow(ll a, ll b, ll m){if (b == 0) return 1; else if (a == 0) return 0; else if (b % 2 == 0) return (pow((a * a) % m, b / 2, m) % m); else return (pow((a * a) % m, b / 2, m) * a) % m;}
   ll residue(ll a, ll m){return ((a % m) + m) % m;};

   ll dx[4]={1,0,-1,0};
   ll dy[4]={0,1,0,-1};

int main(){
  string s; cin >> s;
  vector<string> helix = {"A", "C", "G", "T"};
  REP(i, 4){
    if(helix[i] == s) cout << (helix[(i ^ 3)]) << endl;
  }
}


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

int N, X;

int bounding(int d, int n){
  if(n == 0)
    return 0;
  else{
    int l;
    cin >> l;
    if(d + l <= X)
      return 1 + bounding(d+l, n-1);
    else
      return bounding(d+l, n-1);
  }
}

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

  cout << 1 + bounding(0, N) << endl;
  return 0;

}

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

int F[10005];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, t;
    cin >> n;
    int p = sqrt(10005);
    for (int i = 1; i < p; i++)
        for (int j = 1; j < p; j++)
            for (int k = 1; k < p; k++)
            {
                t = i * i + j * j + k * k + i * j + j * k + k * i;
                if (t < 10001)
                    F[t]++;
            }
    for (int i = 1; i <= n; i++)
        cout << F[i] << '\n';
}


Measured memory_bytes: 3660
#include <iostream>
#include <iosfwd>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cassert>
#include <cctype>
#include <climits>
#include <vector>
#include <bitset>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <deque>
#include <string>
#include <list>
#include <iterator>
#include <sstream>
#include <complex>
#include <fstream>
#include <functional>
#include <numeric>
#include <utility>
#include <algorithm>
#include <assert.h>
#include <unordered_map>

using namespace std;
long long mod = 1e9 + 7;
const int N = 3e5 + 500;

long long n, m, u, v, k, t, q, a, h;

pair <string, int> rest[N];

pair < pair <string, int>, int> srt[N];
vector <int> switches[N];
bool parity[N];
int P[N];

int main() {
   ios::sync_with_stdio(false);cin.tie(0);
   cin >> n >> m;
   for (int i = 1; i <= m; ++i) {
      cin >> k;
      for (int j = 1; j <= k; ++j) {
         cin >> u;
         switches[u - 1].push_back(i);
      }
   }
   int sol = 0;
   for (int i = 1; i <= m; ++i) {
      cin >> P[i];
      P[i] %= 2;
   }
   for (int i = 0; i < (1 << n); ++i) {
      for (int j = 0; j < n; ++j) {
        if ((i & (1 << j))) {
           for (int k = 0; k < switches[j].size(); ++k) {
              parity[switches[j][k]] ^= 1;
           }
        }
      }
      
      bool valid = true;
      for (int j = 1; j <= m; ++j) {
         if (parity[j] != P[j]) {
            valid = false;
            //cout << i << " " << j << " " << parity[j] << " " << P[j] << endl;
            break;
         }
      }
      //cout << valid << endl;
      sol += valid;
      for (int i = 1; i <= m; ++i) parity[i] = false;
   }
   
   cout << sol << endl;
}






Measured memory_bytes: 19072
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#define rep(i,N) for(int i=0;i < (N);i++)
using namespace std;

int main(){
	string S,T;
	cin>>S;
	cin>>T;
	int Ans=T.size();

	rep(i,S.size()-T.size()+1){
		int cnt=0;
		rep(j,T.size()){
			if(S[i+j]!=T[j])cnt++;
		}
		Ans=min(Ans,cnt);
	}
	cout<<Ans<<endl;
}

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

int main(){
  int n;
  cin>>n;
  string s=to_string(n);
  for(auto d:s){
    if(d=='7'){
      cout<<"Yes"<<endl;
      return 0;
    }
  }
  cout<<"No"<<endl;
}

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string a;
  cin >> a;
  if(a == "hi"){
    cout << "Yes" << endl;}
  else if(a == "hihi"){
    cout << "Yes" << endl;}
  else if(a == "hihihi"){
    cout << "Yes" << endl;}
   else if(a == "hihihihi"){
    cout << "Yes" << endl;}
 else if(a == "hihihihihi"){
    cout << "Yes" << endl;}
  else{cout << "No" << endl;}
}

Measured memory_bytes: 256
def m():
    n = int(input())
    t, a = map(int, input().split())
    h = list(map(int, input().split()))
    b = []
    diff = 10 ** 6
    ans = 0
    for i in range(n):
        tmp = t - h[i] * 0.006
        d = abs(tmp - a)
        b.append((d, i+1))
    b.sort(key=lambda x: x[0])
    return b[0][1]
print(m())

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

int main(){
  int a,b;
  cin>>a>>b;
  if(a+b==15){
    cout<<"+"<<endl;
  }else if(a*b==15){
    cout<<"*"<<endl;
  }else{
    cout<<"x"<<endl;
  }
}


Measured memory_bytes: 256
from collections import deque
n, m = map(int, input().split())
lst = [[] for _ in range(n)]
visited = [0] * n
for _ in range(m):
    a, b = map(int, input().split())    
    a -= 1
    b -= 1
    lst[a].append(b)
    lst[b].append(a)

def dfs(st):
    global visited
    global c
    stack = deque([st])
    visited[st] = 1
    c = 1
    while stack:
        nw = stack.pop()
        if visited[nw] == 0:
            c = 1
        for _ in lst[nw]:
            if visited[_] == 0:
                visited[_] = 1
                c += 1
                stack.append(_)
        
ans = 0
for _ in range(n):
    if visited[_] == 0:
        dfs(_)
        ans = max(ans, c)    
print(ans)

Measured memory_bytes: 45268
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define PI 3.14159265358979323

//int calc1(float a,float b,float c,float d,float e,float f,float *x,float *y);
//void quick(int *,long long,long long);
//int comp(char *a,char *b);

int main(){
	
	float xa,ya,xb,yb,xc,yc,xd,yd;
	int flag;

	while(scanf("%f,%f,%f,%f,%f,%f,%f,%f",&xa,&ya,&xb,&yb,&xc,&yc,&xd,&yd)!=EOF){
		if((xb-xa)*(yd-ya)-(xd-xa)*(yb-ya)>0)
			flag=1;
		else
			flag=-1;

		if     (( (xc-xb)*(ya-yb)-(xa-xb)*(yc-yb) )*flag<0)
			printf("NO\n");
		else if(( (xd-xc)*(yb-yc)-(xb-xc)*(yd-yc) )*flag<0)
			printf("NO\n");
		else if(( (xa-xd)*(yc-yd)-(xc-xd)*(ya-yd) )*flag<0)
			printf("NO\n");
		else 
			printf("YES\n");
	}	
	return 0;
}

Measured memory_bytes: 604
fun main() {
    val (n, m) = nextIntList()
    val mod = 1_000_000_007L
    val factList = sizedArray(m + 1, 0L)
    val modInvList = sizedArray(m + 1, 0L)

    var a = 1L
    repeat(m + 1) {
        factList[it] = a
        modInvList[it] = modinv(a, mod)
        a = a.times(it.plus(1)).rem(mod)
    }
    var res = 0L
    repeat(n + 1) { k ->
        val c = factList[n].times(modInvList[k]).rem(mod).times(modInvList[n - k]).rem(mod)
        val p1 = factList[m].times(modInvList[m - k]).rem(mod)
        val p2 = factList[m - k].times(modInvList[m - n]).rem(mod)
        val t = c.times(p1).rem(mod).times(p2).rem(mod).times(p2).rem(mod)
        if (k % 2 == 0) {
            res = res.plus(t).rem(mod)
        } else {
            res -= t
            if (res < 0) {
                res += mod
            }
        }
    }
    println(res)
}

// # Utils
// ## Input
fun next() = readLine()!!
fun nextInt() = next().toInt()
fun nextLong() = next().toLong()
fun nextDouble() = next().toDouble()
fun nextList() = next().split(" ")
fun nextIntList() = next().split(" ").map(String::toInt)
fun nextLongList() = next().split(" ").map(String::toLong)
fun nextDoubleList() = next().split(" ").map(String::toDouble)

// ## Array
inline fun <reified T> sizedArray(size: Int, default: T) = Array(size) { default }

// ## mod^-1
//    [NOTE] CANNOT use this for 0, mod, 2mod, 3mod ...(return wrong value)
fun modinv(num: Long, mod: Long): Long {
    var a = num
    var b = mod
    var u = 1L
    var v = 0L
    while (b > 0) {
        val t = a.div(b)
        a -= t * b
        a = b.also { b = a } // swap a and b
        u -= t * v
        u = v.also { v = u } // swap u and v
    }
    u %= mod
    if (u < 0) u += mod
    return u
}

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

typedef __int128 lint;
typedef long long ll;
const ll md=998244353;

char s[109];
map<lint,int> ha[109];

inline ll f(int len,lint s)
{
	if(!len)return 1;
	if(ha[len].find(s)!=ha[len].end())
		return ha[len][s];
	
	ll ret=(1+(s&1))*f(len-1,s>>1)%md;

	lint st=0,c;
	for(int i=1;i<=len;i++)
	{
		st=st<<1|1,c=s&st;
		for(int j=i+i;j<=len;j+=i)
		{
			c&=(s>>j-i);
			ret=(ret+f(i,c)*f(len-j,s>>j)%md)%md;
		}
	}

	return ha[len][s]=ret;
}

int main()
{
	if(fopen("vj.in","r"))
	{
		freopen("vj.in","r",stdin);
		freopen("vj.out","w",stdout);
	}

	scanf("%s",s+1);
	int len=strlen(s+1);
	lint state=0;
	for(int i=len;i;i--)
		state=state<<1|(s[i]=='1');
	printf("%lld\n",f(len,state));
	return 0;
}


Measured memory_bytes: 3840
#include<iostream>
#include<iomanip>
using namespace std;
int main() {
	int n;
	cin >> n;
	int K = 0;
	for (int i = 1; i <= n; i++) {
		if (i % 2 != 0) K++;
	}
	double ans = (double)K / (double)n;
	cout << fixed << setprecision(8) << ans;
	return(0);
}

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

using namespace std;

bool isPrime(int n){
	if(n==1) return false;
	for(int i=2;i<(int)(sqrt(n)+1);i++){
		if((n%i)==0){
			return false;
		}
	}
	return true;
}

int main() {
	int n,p;
	while(cin >> n){
		p=0;
		for(int i=1;i<=n;i++){
			if(isPrime(i)&&isPrime(n-i+1)) p++;
		}
		cout << p << endl;
	}
}

Measured memory_bytes: 868
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define pb push_back
#define sz(i) (int)(i.size())
#define F first
#define S second
#define L long double
#define P pair<int, int>
const int inf = 0x3f3f3f3f3f3f3f3LL;
const int mod = (int)1e9 + 7;
using namespace std;
#if LOCAL
#include "../../tr.h"
#else
#define tr(...)
#define endl '\n'
#endif
template<class T> void smin(T& a, T val) {if (a > val) a = val;}template<class T> void smax(T& a, T val) {if (a < val) a = val;}
const int N = (int)1e5 + 10;

int n, m;
multiset<int> ms;

int32_t main(){_

   cin>>n>>m;

   vector<P> a(n);

   for (int i = 0; i < n; ++i)
   {
      cin>>a[i].F >> a[i].S;
   }

   sort(a.begin(), a.end());

   int ans = 0;
   int idx = 0;

   for (int i = 1; i <= m; ++i)
   {
      while(idx < n and a[idx].F <= i){
         ms.insert(a[idx].S);
         idx++;
      }
      if (!ms.empty()){
         auto it = ms.end();
         --it;
         ans += *it;
         ms.erase(it);
      }
   }
   
   cout<<ans;

   return 0;
}

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

int main(void){
  vector< P > u;
  vector< P > l;
  vector< int > r; 
  int x,k,q;
  cin >> x;
  r.push_back(0);
  u.push_back(P(x,x));
  l.push_back(P(0,0));
  cin >> k;
  for(int i = 0;i < k;++i){
    int tmp;cin >> tmp;
    r.push_back(tmp);
    int d = r[i+1] - r[i];
    if(i % 2 == 0){
      //down
      if(l[i].first - d > 0){
        u.push_back(P(u[i].first-d,u[i].second));
        l.push_back(P(l[i].first-d,l[i].second));
      }else if(u[i].first - d > 0){
        int nl = l[i].second + (d - l[i].first);
        u.push_back(P(u[i].first-d,u[i].second));
        l.push_back(P(0,nl));
      }else{
        u.push_back(P(0,0));
        l.push_back(P(0,0));
      }
    }else{
      //up
      if(u[i].first + d < x){
        u.push_back(P(u[i].first+d,u[i].second));
        l.push_back(P(l[i].first+d,l[i].second));
      }else if(l[i].first + d < x){
        int nu = u[i].second - (u[i].first - (x - d));
        u.push_back(P(x,nu));
        l.push_back(P(l[i].first+d,l[i].second));
      }else{
        u.push_back(P(x,0));
        l.push_back(P(x,0));
      }
    }
  }
  /*
  for(int i = 0;i < k+1;++i){
    printf("(%d,%d) ", l[i].first, u[i].first);
  }
  cout << endl;
  for(int i = 0;i < k+1;++i){
    printf("(%d,%d) ",l[i].second, u[i].second);
  }
  cout << endl;
  */        
  cin >> q;
  for(int i = 0;i < q;++i){
    int t,a;
    cin >> t >> a;
    int idx = (upper_bound(r.begin(),r.end(),t) - r.begin()) - 1;
    int d = t - r[idx];
    int calc;
    if(a <= l[idx].second){
      calc = l[idx].first;
    }else if(a >= u[idx].second){
      calc = u[idx].first;
    }else{
      calc = l[idx].first + (a - l[idx].second);
    }
    if(idx % 2 == 0){
      cout << max(calc-d,0) << endl;
    }else{
      cout << min(calc+d,x) << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 3428
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define mod 1000000007
#define all(v)  v.begin(),v.end()
#define pb push_back;0
ll power(ll a,ll x){if(x==0) return 1;ll y=power(a,x/2);ll ans=(y*y)%mod; if(x%2) ans=(ans*a)%mod;return ans;}
ll inv(ll a){return power(a,mod-2);}




 int main(){

 ios_base:: sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
 
 int n,k;
 string s;
 cin>>n>>k>>s;
 k--;
 for(int i=0;i<n;i++){
     if(i==k){
        s[i]=(s[i]-'A'+'a');
     }
 }
 cout<<s<<endl;

}


Measured memory_bytes: 256
#include <stdio.h>
int main(){
    int h, w;
    int i, j;

    while(1){
        scanf("%d %d",&h, &w);
        if(h == 0 && w == 0) break;

        for(i = 0; i < h; i++){
            for(j = 0; j < w; j++){

                if((i+j)%2 == 0) printf("#");
                else printf(".");
                
            }
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}


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

int main() {
  int A, B;
  int a[3];


  cin >> A >> B;

  a[0] = A + B;
  a[1] = A - B;
  a[2] = A * B;

  sort(a, a + 3);

  cout << a[2] << endl;

  return (0);
}


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

int main(){
    string n;
    cin >> n;
    string ans ="No";
    for(auto x: n){
        if(x=='7') ans="Yes";
    }
    cout << ans << endl;
}

Measured memory_bytes: 3628
#include<stdio.h>
int main(void){
  int n,a[10];
  scanf("%d",&n);
  int all=1,bad=1;
  for(int loop=0;loop<n;++loop){
    scanf("%d",a+loop);
    all*=3;
    if(a[loop]%2==0){
      bad*=2;
    }
  }
  printf("%d",all-bad);
  return 0;
}

Measured memory_bytes: 128
// 2012/12/14 Tazoe

#include <iostream>
using namespace std;

int main()
{
while(true){
	int n;
	cin >> n;

if(n==0)
break;

	int m = 1000-n;

	int sum = 0;

	sum += m/500;
	m %= 500;

	sum += m/100;
	m %= 100;

	sum += m/50;
	m %= 50;

	sum += m/10;
	m %= 10;

	sum += m/5;
	m %= 5;

	sum += m;

	cout << sum << '\n';
}

	return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<string>

using namespace std;

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

string s;
string t = "YAKI";

int main(){
    cin >> s;
    bool flag = true;

    if(s.size()>=4){
        REP(i, 4){
            if(s[i] != t[i]){
                flag = false;
            }
        }
    } else {
        flag = false;
    }

    if(flag){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		final Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		long[] arr = new long[(int) n];
		for(int i = 0; i < n; i++) {
			arr[i] = sc.nextLong();
		}
		//一項目を負にするか正にするか
		long seiT = 0L;
		long ruisekiWA = 0L;
		for(int i = 0; i < n; i++) {//正のとき
			ruisekiWA += arr[i];
			if(i%2==0) {//正にする
				if(ruisekiWA > 0) {

				} else {
					seiT += 1 - ruisekiWA;
					ruisekiWA = 1;
				}
			} else {//負にする
				if(ruisekiWA < 0) {

				} else {
					seiT += ruisekiWA + 1;
					ruisekiWA = -1;
				}
			}
		}
		long fuT = 0L;
		ruisekiWA = 0L;
		for(int i = 0; i < n; i++) {//負のとき
			ruisekiWA += arr[i];
			if(i%2==0) {//負にする
				if(ruisekiWA < 0) {

				} else {
					fuT += ruisekiWA + 1;
					ruisekiWA = -1;
				}
			} else {//正にする
				if(ruisekiWA > 0) {

				} else {
					fuT += 1 - ruisekiWA;
					ruisekiWA = 1;
				}
			}
		}
		System.out.println(Math.min(seiT, fuT));
	}
}

Measured memory_bytes: 57656
def main():
  n,k,*t=map(int,open(0).read().split())
  c,e=k,[0]*(n+1)
  for v in t:
    e[v]+=1
    if(v>1)-e[v]:
      c=c*(k-e[v])%(10**9+7)
  print(c)
main()

Measured memory_bytes: 25076
#include <iostream>
#include <iomanip>
#include <vector>
#include <array>
using namespace std;

int main(){
    int n;

    while(cin>>n,n){
        vector<vector<int>> v(n);
        vector<int> lv(n+1,0);

        for(auto &x:v){
            x.resize(n);
            for(auto &y:x){
                int t;
                cin>>t;
                y=t;
            }
        }

        for(auto &x:v){
            int sum=0;
            for(auto y:x){
                sum+=y;
            }
            x.push_back(sum);

            for(int i=0;i<=n;i++){
                lv[i]+=x[i];
            }
        }

            for(auto x:v){
                for(auto y:x){
                        cout<<setw(5)<<y;
                }
                cout<<endl;
            }

            for(auto x:lv){
                cout<<setw(5)<<x;
            }

            cout<<endl;
    }

    return 0;
}

Measured memory_bytes: 1224
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;

int main(){
    ll n;
    cin >> n;
    vector<ll> c(n);
    set<ll> st[200000];
    for(int i = 0;i < n;i ++){
        cin >> c[i];c[i] --;
        st[c[i]].insert(i);
    }
    ll dp[n];
    dp[0] = 1;
    for(int i = 1;i < n;i ++){
        auto ite = st[c[i]].lower_bound(i);
        if(ite!=st[c[i]].begin()){
            dp[i] = dp[*(-- ite)];
            if(*ite!=i-1) dp[i] += dp[i-1];
        }else dp[i] = dp[i-1];
        dp[i] %= mod;
    }
    cout << dp[n-1] << endl;
    return 0;
}

Measured memory_bytes: 22144
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

#define For(i, j, k) for(int i = j; i <= k; i++)
#define Forr(i, j, k) for(int i = j; i >= k; i--)

using namespace std;

const int N = 5000010;

struct Interval{
	int id, L, R;
	
	bool operator < (const Interval& v) const{
		return L ^ v.L ? L > v.L : id < v.id;
	}

}A[N];

int n, m, ans[N];

struct Binary_Indexed_Tree{
	
	int c[N];

	inline int lowbit(int x){
		return x & (-x);
	}

	void add(int x){
		while(x <= m){
			c[x]++;
			x += lowbit(x);
		}
	}

	int sum(int x){
		int ret = 0;
		while(x){
			ret += c[x];
			x -= lowbit(x);
		}
		return ret;
	}
}T;

int main(){
	scanf("%d%d", &n, &m);
	For(i, 1, n) scanf("%d%d", &A[i].L, &A[i].R), A[i].id = 0;
	int c = n;
	For(i, 2, m) for(int j = i; j - i + 1 <= m; j += i) A[++c] = (Interval){i, j - i + 1, min(j - 1, m)};
	sort(A + 1, A + c + 1);
	For(i, 1, c){
		if(!A[i].id) T.add(A[i].R);
		else ans[A[i].id] -= T.sum(A[i].R);
	}
	For(i, 1, m) printf("%d\n", ans[i] + n);
	return 0;
}

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

int mod = 1'000'000'007;

int main(){
    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;
    vector<char> tmp;
    for (int i = 0; i < n; i++){
        if (s[i] == t[i]) tmp.push_back('A');
        else {
            tmp.push_back('B');
            i++;
        }
    }
    long long dp;
    if (tmp[0] == 'A') dp = 3;
    else dp = 6;
    for (int i = 1; i < tmp.size(); i++){
        if (tmp[i-1] == 'A'){
            dp *= 2;
            dp %= mod;
        }
        else if (tmp[i] == 'B'){
            dp *= 3;
            dp %= mod;
        }
    }
    cout << dp << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fo(i,a,b) for(int i= a ; i < b ; ++i)
#define rep(i,n) fo(i,0,n)
#define pln(n) printf("%lld\n",n)
#define sll(n) scanf("%lld",&n)
#define ss(n) scanf("%s",n)
#define vi vector < int >
#define pii pair < int , int >
#define pb push_back
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define dbg(x) { cout<< #x << ": " << (x) << endl; }
#define dbg2(x,y) { cout<< #x << ": " << (x) << " , " << #y << ": " << (y) << endl; }
#define dbg3(x,y,z) { cout<< #x << ": " << (x) << " , " << #y << ": " << (y) <<" , "<< #z <<": "<<(z)<<endl; }
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define vll vector<long long>
#define vvi vector<vector<int>>
#define si set<int>
#define tr(c, it) \
for(decltype(c.begin()) it = c.begin(); it!= c.end(); it++)
#define pis pair<int,string>
#define present(c, x) (c.find(x) != c.end())
#define cpresent(c, x) (find(all(c),x) != c.end())
#define mod (int)(1e9 + 7) 

using namespace std;

int main(){
	int n;
	cin >>n;
	cout << fixed << setprecision(15);
	vector<double> p(n);
	for(int i = 0; i < n; i++){
		cin >> p[i];
	}
	double dp[n+1][n+1];
	if(n == 0){
		cout << 0 << endl;
	}
	// dp[i] is the probabilty  upto i'th index
	dp[0][0] = 1;
	for(int heads = 1; heads <= n; heads++){
		dp[0][heads] = 0;
	}
	for(int i = 1; i <= n; i++){
		dp[i][0] = dp[i-1][0] * (1 - p[i-1]);
	}
	for(int i = 1; i <= n; i++){
		for(int heads = 1; heads <= i; heads++){
			dp[i][heads] = dp[i-1][heads-1] * (p[i-1]) + dp[i-1][heads] * (1 - p[i-1]);
		}
	}
	double ans = 0;
	// for(int i = 1; i <= n; i++){
	// 	for(int heads = 0; heads <= i; heads++){
	// 		cout << dp[i][heads] << " ";
	// 	}cout << endl;
	// }
	for(int k = (n+1)/2; k <= n; k++){
		ans += dp[n][k];
	}
	cout << ans << endl;
}

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

ll Ep(int x, int y){
  if(y == 0) return 1;
  if(y == 1) return x;
  ll r = Ep(x,y/2);
  if(y%2 == 1) return r *r%MOD *x%MOD;
  else return r *r%MOD;
}

int main(){
  int n;
  cin >> n;
  vector<int> an(n,0);
  for(int i=0; i<n; ++i){
    int x;
    cin >> x;
    ++an[x];
  }
  bool ansis = true;
  if(n%2 == 1 && an[0] != 1) ansis = false;
  for(int st = (n%2)? 2:1; st<n; st+=2){
    if(an[st] != 2) ansis = false;
  }
  if(!ansis){
    cout << 0 << endl;
    return 0;
  }
  cout << Ep(2,n/2) << endl;
}

Measured memory_bytes: 3756
#include "bits/stdc++.h"
using namespace std;
#define Fast_IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
vector<vector<int>> dp;
int solve(vector<int> &a, int i, int j) {
	if (i > j) {
		return 0;
	}
	if (i == j) {
		return a[i];
	}

	if (~dp[i][j])
		return dp[i][j];

	int c1 = a[i] + min(solve(a, i + 1, j - 1), solve(a, i + 2, j));
	int c2 = a[j] + min(solve(a, i + 1, j - 1), solve(a, i, j - 2));

	return dp[i][j] = max(c1, c2);
}

int32_t main() {
	Fast_IO
	int n; cin >> n;
	dp = vector<vector<int>>(n, vector<int>(n, -1));

	vector<int> a(n);
	for (auto &i : a)
		cin >> i;

	cout << 2 * solve(a, 0, n - 1) - accumulate(a.begin(), a.end(), 0LL);
}

Measured memory_bytes: 73688
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,k;
  cin>>n>>k;
  vector<int>arr(n);
  for(auto &i:arr)cin>>i;
  vector<int>ans(n);
  ans[0]=0;
  for(int i=1;i<n;i++){
    int mn=INT_MAX;
    for(int j=max(i-k,0);j<i;j++){
      mn=min(mn,ans[j]+abs(arr[i]-arr[j]));
    }
    ans[i]=mn;
  }
  cout<<ans[n-1]<<endl;
}

Measured memory_bytes: 4000
n,m=map(int,input().split())

L,R=0,n+1
for i in range(m):
    l,r = map(int,input().split())
    if L<l:
        L=l
    if r<R:
        R=r

if (R>=L):
    print(R-L+1)
else:
    print(0)


Measured memory_bytes: 3060