akhauriyash/Code-Regression huggingface dataset:
#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() {cerr << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cerr<<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 = 1000010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = (1 << 30) - 1;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
mt19937 rng; //use it by rng() % mod, shuffle(all(vec), rng)
///////////////////////////////////////////////////////////////////////////////////////////////////

int N;
int used[MAX_N];
int tsed[MAX_N];

void solve() {
	cin >> N;
	rep(i, 0, N) {
		int a; cin >> a;
		tsed[a]++;
	}
	int res = 0;
	for(int i = 1; i <= 1000000; i++) {
		if(!tsed[i]) continue;
		if(tsed[i] == 1 && !used[i]) res++;
		for(int j = i; j <= 1000000; j += i) {
			used[j] = 1;
		}
	}
	cout << res << "\n";
}

uint32_t rd() {
	uint32_t res;
#ifdef __MINGW32__
	asm volatile("rdrand %0" :"=a"(res) ::"cc");
#else
	res = std::random_device()();
#endif
	return res;
}

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




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

int main(){
  string S,T;
 long long N,c,d,p,ans,k;
cin>>S>>T;
  ans=0;
  for(int i=0;i<3;i++){
    if(S[i]==T[i]){
      ans++;
    }
  }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pb push_back
#define pp pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
//const int64 INF = 1LL << 58;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
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 (a>b) { a=b; return 1; } return 0; }
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

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

	int n;
	cin >> n;
	vl a(n);
	map<ll , ll> mp1;
	map<ll , ll> mp2;
	rep(i,n){
		cin >> a[i];
		mp1[a[i]+i]++;
		mp2[i - a[i]]++;
	}
	ll ans = 0;
	for(auto it:mp1){
		if(mp2[it.fs]!=0){
			ans += (it.sc * mp2[it.fs]) ;
		}
	}
	cout << ans << endl;

    return 0;
}


Measured memory_bytes: 39028
#include <iostream>

using namespace std;

int main(int argc, char const* argv[])
{
	int i,j,k;
	int n;
	int a[15][15];

	while( cin >> n && n !=  0 ){
		k = 0;
		for( i = 0;i < 15;i++ ){
			for( j = 0;j < 15;j++ ){
				a[i][j] = 0;
			}
		}
		for( i = -n / 2;i <= n / 2;i++ )
			for( j = 0;j < n;j++ )
				a[(j + i + n) % n][(j - i + n) % n] = ++k;
		for( i = 0;i < n;i++ ){
			for( j = 0;j < n;j++ ) printf("%4d",a[i][j] );
			puts("");
		}
	}
	return 0;
}

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

int solve() {
    string S;
    cin >> S;
    char c = 0;
    int n = 0;
    for ( auto s : S ) {
        if ( c != s ) {
            n++;
            c = s;
        }
    }
    return n - 1;
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lp(i,a,n) for(int i=(a);i<=(int)(n);++i)
#define lpd(i,a,n) for(int i=(a);i>=(int)(n);--i)
#define mem(a,b) memset(a,b,sizeof a)
#define all(v) v.begin(),v.end()
#define println(a) cout <<(a) <<endl
#define sz(x) ((int)(x).size())
#define readi(x) scanf("%d",&x)
#define read2i(x,y) scanf("%d%d",&x,&y)
#define read3i(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define mod 1000000007
#define eps 1e-8
#define infi 1000000000
#define infll 1000000000000000000ll
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef set<int> si;
typedef map<int,int> mii;

const int N = 100002;
int n;
mii f;

int main(){
    readi(n);
    lp(i,1,n){
        int x;
        readi(x);
        ++f[x], ++f[x+1], ++f[x-1];
    }

    int ans = 0;
    for(pii p : f) ans = max(ans, p.s);
    cout <<ans;
}

/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
*/


Measured memory_bytes: 4736
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<list>
#include<map>
#include<numeric>
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define ll long long

using namespace std;

ll a, b;

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

	if (x / 500 != 0) {
		a = x / 500;
		x = x % 500;
	}
	if (x / 5 != 0) {
		b = x / 5;
	}

	ll ans = a * 1000 + b * 5;

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
//#define rep(i,a,b) for(int i=a;i<b;i++)
#define T int t ;cin >> t;while(t--)
using namespace std ;
typedef long long ll;
const ll maxn=2e5+10;
//typedef unsigned long long ull;
int main()
{
    ll n;
    scanf("%lld",&n);
    char c[maxn];
    ll r=0,w=0;
    scanf("%s",c);
    for(ll i=0;i<strlen(c);i++)
    {
        if(c[i]=='R')
        {
            r++;
        }
    }
    for(ll i=0;i<r;i++)
    {
        if(c[i]=='W')
            w++;
    }
    cout<<w<<endl;
}


Measured memory_bytes: 3840
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pint;

int main(){
    char a,b;
    cin>>a>>b;
    if(a=='H'&&b=='H'||a=='D'&&b=='D') cout<<"H"<<endl;
    else cout<<"D"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REP2(i, a, b) for (int i = (a); i < (int)(b); i++)
typedef vector<int> VI;
typedef vector<VI> VVI;

double Main(int N, int K, VI& h)
{
    int ans = 0;
    REP(i, N) if(h[i] >= K) ans++;
    return ans;
}

int main(void){
    int N, K;
    cin >> N >> K;
    VI h(N);
    REP(i, N) cin >> h[i];
    cout << Main(N, K, h) << endl;
    return 0;
}

Measured memory_bytes: 640
#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;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define INF 999999999
#define M_PI 3.14159265358979323846
#define ALL(X) (X).begin(),(X).end()

#ifdef __LOCAL
    #define DBG(X) cout << #X << " = " << (X) << endl;
    #define SAY(X) cout << (X) << endl;
#else
    #define DBG(X)
    #define SAY(X)
#endif

#ifdef __LOCAL
    #include <filesystem>
    namespace fs = std::filesystem;
#endif

using namespace std;

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

int dx[]={1, 0, -1, 0, 0};
int dy[]={0, 1, 0, -1, 0};
const int INT_INF = (int)(2e9);
const ll  LL_INF = (ll)(2e18);
const int NIL = -1;
static mt19937 _g(time(nullptr));
 
std::string pad(int num){ char buffer[4]; std::snprintf(buffer, sizeof(buffer), "%03d", num); return buffer;}
inline ll randint(ll a, ll b) { ll w = (_g() << 31LL) ^ _g(); return a + w % (b - a + 1); }
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T> inline T sign(T x) { return T(x > 0) - T(x < 0); }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const map<T, S> p) { for (auto el : p) cout << "[" << el.first << "," << el.second << "] "; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline T fetch() { T ret; cin >> ret; return ret; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for (auto& elem : ret) cin >> elem; return ret; }

int N;
vector<int> P;

void input(){
    #ifdef __LOCAL
        fs::path path_to_file = __FILE__;
        fs::path input,output;
        input = output = path_to_file.parent_path();
        input += string("/input/") + string(path_to_file.stem()) + string(".txt");
        output += string("/output/") + string(path_to_file.stem()) + string(".txt");
        freopen(input.c_str(), "r", stdin);
        freopen(output.c_str(), "w", stdout);
    #endif
    cin >> N;
    P = fetch_vec<int>(N);
}

void solve(){
    input();
    int M=INT_INF;
    int ans=0;
    REP(i,N){
        if(M>=P[i]) ans++;
        M = min(M,P[i]);
    }
    cout << ans << endl;
    
}

int main()
{
    solve();
    return 0;
}


Measured memory_bytes: 1024
# -*- coding:utf8 -*-

n = int(input())
l = list(map(int, input().split()))
c = 0
flag = 1
while flag:
    flag = 0
    for i in reversed(range(1, n)):
        if l[i] < l[i - 1]:
            l[i], l[i - 1] = l[i - 1], l[i]
            flag = 1
            c += 1
print(' '.join(map(str, l)))
print(c)


Measured memory_bytes: 5608
using System;
using System.Linq;
class c
{
    static void Main()
    {
        var nm = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        var s = Console.ReadLine();
        var t = Console.ReadLine();
        if (nm[0] > nm[1])
        {
            nm = nm.OrderBy(_ => _).ToArray();
            var temp = s;
            s = t;
            t = temp;
        }
        long n = nm[0];
        long m = nm[1];
        int now = nm[1] % nm[0];
        while (now != 0)
        {
            nm[1] = nm[0];
            nm[0] = now;
            now = nm[1] % nm[0];
        }
        long gcd = nm[0];
        long lcm = n * m / gcd;
        bool judge = true;
        for (int i = 0; i < gcd; i++)
        {
            if (s[(int)(i * lcm / m)] != t[(int)(i * lcm / n)]) judge = false;
        }
        Console.WriteLine(judge ? lcm : -1);
    }
}

Measured memory_bytes: 13792
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

int nd(uint64_t x)
{
    int d;
    for(d=0;x%2==0;x/=2,d++);
    return d;
}

uint64_t gcd(uint64_t x, uint64_t y)
{
    uint64_t z;
    while(y != 0){
        z = x % y;
        x = y;
        y = z;
    }
    return x;
}

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

    int d = nd(a);
    if(d==0){
        printf("%d\n", 0);
        return 0;
    }
    uint64_t h = a/2;
    for(int ni=1; ni<N; ni++){
        int an;
        scanf("%d", &an);
        if(d != nd(an)){
            printf("%d\n", 0);
            return 0;
        }
        h *= (an/2) / gcd(h, (an/2));
    }

    printf("%"PRIu64,  M/h - M/(2*h));
    
    return 0;
}


Measured memory_bytes: 128
#include<stdio.h>
#include<string.h>

int main(void){
    // s: 入力文字列(操作する方)
    // t: 入力文字列(比較される方)
    // c1: "操作"のためにsの文字を入れる
    // c2: "操作"のためにtの文字を入れる
    // flag: 探索を終了する判定のフラッグ
    char s[200001], t[200001], c1, c2;
    int flag = 0;
    scanf("%s\n%s", s, t);
    int length = strlen(s);
    
    for(int i = 0; i < length; i++){ // tとsが同じか頭から1文字ずつ見ていく
        if(t[i] != s[i]){ // 違う文字があったら"操作"を始める
            // 入れ替える文字を代入しておく
            c1 = s[i];
            c2 = t[i];
            for(int j = 0; j < length; j++){ // sに入れ替える文字があるか頭から探す
                if(s[j] == c1){ // sの中に入れ替える文字があったら
                    if(j < i){
                        // tの位置より前を入れ替えようとした時
                        // 最後の比較は同じにならないのでbreakして早々に処理を終える
                        // forを早く抜けないと実行時間制限超過になる
                        flag = 1;
                        break;
                    }
                    s[j] = c2;
                    // 入れ替え終わった文字を次のifの判定で拾ってしまうので
                    // continueで次のループへ飛ぶ
                    continue;
                }
                if(s[j] == c2){ // 同上
                    if(j < i){
                        flag = 1;
                        break;
                    }
                    s[j] = c1;
                }
            }
        }
        if(flag){
            break;
        }
    }

    if(strcmp(s, t) == 0){
        printf("Yes\n");
    }
    else{
        printf("No\n");
    }
    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define pii pair< int, int>
#define fst first
#define sec second
using namespace std;

int dp[3007][3007] = {};
pii last[3007][3007] = {};

char s[3007] = {};
char t[3007] = {};


int main() {
	
	int i,j;
	int n,m;
	
	scanf("%s", s+1);
	scanf("%s", t+1);
	
	n = strlen(s+1);
	m = strlen(t+1);
	for( i=1; i<=n; i++) {
		for( j=1; j<=m; j++) {
			if( s[i] == t[j]) {
				dp[i][j] = dp[i-1][j-1] + 1;
				last[i][j] = { i-1, j-1};
			}
			else {
				dp[i][j] = max( dp[i][j-1], dp[i-1][j]);
				if( dp[i][j-1] >= dp[i-1][j])
					last[i][j] = { i, j-1};
				else
					last[i][j] = { i-1, j};
			}
		}
	}
	
	pii now = { n, m};
	string ans;
	while( now.fst != 0 && now.sec != 0) {
		pii p = last[now.fst][now.sec];
		if( p.fst < now.fst && p.sec < now.sec) {
			ans.push_back( s[now.fst]);
		}
		now = p;
	}
	reverse( begin(ans), end(ans));
//	printf("%d\n", dp[n][m]);
	cout << ans << "\n";
	
	return 0;
}

Measured memory_bytes: 109392
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int r,g,b;
    int ans;
    cin >> r >> g >>b;
    ans = 100*r + 10*g +b;
    if(ans%4==0){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

//Atcoder用

/*
 * BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] abc = br.readLine().split(" ");
		int a = Integer.parseInt(abc[0]);
		int b = Integer.parseInt(abc[1]);
		int c = Integer.parseInt(abc[2]);
 */
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] get = br.readLine().split(" ");
		int n = Integer.parseInt(get[0]);

		for(int c=0;c<26;c++){
			for(int d=0;d<15;d++){
				if((4*c) + (7*d) == n){
					System.out.println("Yes");
					System.exit(0);
				}
			}
		}
		System.out.println("No");
	}


}

Measured memory_bytes: 24660
#include <stdio.h>
int main(){
  int N,M,i,sum,count;
  int A[100];
  sum=0;
  count=0;
  scanf("%d %d",&N,&M);
  for(i=0;i<N;i++){
    scanf("%d",&A[i]);
    sum=sum+A[i];
  }
  for(i=0;i<N;i++){
    if(A[i]*4*M>=sum) count++;
  }
  if(count<M) printf("No");
  else printf("Yes");
  return 0;
}

Measured memory_bytes: 128
N = int(input())
cord_list = [[0, 0, 0]]
flag = 0
for i in range(N):
    cord_list.append(list(map(int, input().split())))
    
for j in range(N):
    a = cord_list[j+1][0] - cord_list[j][0]
    b = cord_list[j+1][1] - cord_list[j][1]
    c = cord_list[j+1][2] - cord_list[j][2]
    if ((a - (abs(b) + abs(c)))%2 ==0) & ((abs(b) + abs(c)) <= a):
        pass
    else:
        print("No")
        flag += 1
        break
        
if flag == 0:
    print("Yes")

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

int main() {
  string s,t;
  cin>>s>>t;
  int a,b;
  cin>>a>>b;
  string u;
  cin>>u;
  if(s==u) a--;
  if(t==u) b--;
  cout<<a<<" "<<b<<endl;



}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
static constexpr int NUM = 7368792;
bool number[NUM];

int main()
{
	std::vector<int> results;
	int m, n;
	while(std::cin >> m >> n && n && m) {
		for (int i = 0; i < NUM; i++) number[i] = true;
		for (int i = 0; i < n + 1; i++) {
			while (!number[m++]) {}
			number[--m] = 0;
			int year = m;
			while ((year += m) < NUM) number[year] = 0;
		}
		results.push_back(m);
	}
	for (auto& x : results) {
		std::cout << x << std::endl;
	}
	return 0;
}

Measured memory_bytes: 10260
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fr first
#define sc second
#define pb push_back
#define mp make_pair
#define sz(c) c.size()
#define gcdll(x, y) __gcd(x, y)
#define lcmll(x, y) (x * y) / gcdll(x, y)
#define all(v) (v).begin(), (v).end()
#define rep(i, a, n) for (int i = a; i < n; ++i)
#define bs_v(v, x) binary_search(all(v), x)
#define bs_a(a, i, n, x) binary_search(a + i, a + n, x)
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

void solve()
{
    string s, a, b;
    cin >> s;
    if(s[sz(s)-1]=='s')s+="es";
    else s+='s';
    cout<<s<<'\n';
}

int main()
{
    IOS;
    int T = 1;
    //cin >> T;
    rep(i, 1, T + 1)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 3640
import sys
import numpy as np
import random
from decimal import Decimal
import itertools
import re
import bisect
from collections import deque, Counter
from functools import lru_cache

sys.setrecursionlimit(10**9)
INF = 10**13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
def SERIES(n): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ')
def GRID(h,w): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ').reshape(h,-1)[:,:w]
def GRIDfromString(h,w): return np.frombuffer(sys.stdin.buffer.read(), 'S1').reshape(h,-1)[:,:w]
MOD = 1000000007

def main():
	n, a = LI()
	x_list = np.array(LI())
	nx = n*max(x_list+[a])
	y_list = x_list - a
	dp = np.full((n+1,2*nx+1),INF)

	def dfs(j,t):
		dp_value = dp[j,t]
		if dp_value == INF:
			if j == 0 and t == nx:
				dp_value = 1
			elif j >= 1 and (y_list[j-1] < t - 2*nx or y_list[j-1] > t):
				dp_value = dfs(j-1, t)
			elif j >= 1 and 0 <= t - y_list[j-1] <= 2*nx:
				dp_value = dfs(j-1, t) + dfs(j-1, t-y_list[j-1])
			else:
				dp_value = 0
			dp[j,t] = dp_value
		return int(dp_value)

	print(dfs(n, nx) -1)


if __name__ == '__main__':
    main()

Measured memory_bytes: 17492
#include <stdio.h>

int main(){
  int num,yen;
  scanf("%d %d", &num, &yen);
  yen /= 1000;
  int sum,k;
  int answer[3] = {-1,-1,-1};
  for(int i = 0; i <= num; ++i){
    if(10 * i > yen) break;
    for(int j = 0; j <= num - i; ++j){
      k = num - i - j;
      sum = 10 * i + 5 * j + k;
      if(sum == yen){
        answer[0] = i;
        answer[1] = j;
        answer[2] = k;
      }else if(sum > yen) break;
    }
  }
  printf("%d %d %d\n",answer[0],answer[1],answer[2]);
  return 0;
}

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

const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1);

int main(void)
{
    ll n, m, ans;
    cin >> n >> m;
    vector<ll> x(m),dist;
    rep(i,m) cin >> x[i];
    sort(all(x));
    if(n>=m) ans = 0;
    else{
        rep(i,m-1) dist.push_back(abs(x[i+1]-x[i]));
        ll sum = accumulate(all(dist), 0LL);
        sort(rall(dist));
        rep(i,n-1) sum -= dist[i];
        ans = sum;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5048
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1166&lang=jp
AC
"""
import sys
from sys import stdin
from collections import deque
input = stdin.readline


def bfs(maze, w, h):
    # ????????????????§????????????´????????§?¨??????????
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]

    # ??????????????°???(S)??¨??´????????°???(G)?????????
    sx = 0                   #  ??????????????°????????§?¨?
    sy = 0
    gx = w - 1               #  ??´????????°????????§?¨?
    gy = h - 1

    d = [[float('inf')] * w for _ in range(h)] #  ??????????????°?????????????????¢???INF??§?????????
    Q = deque()
    Q.append((sx, sy))
    d[sy][sx] = 0
    while Q:
        cx, cy = Q.popleft()        #  ?????¨??°?????§?¨?
        if cx == gx and cy == gy:
            return d[gy][gx] + 1    #  ?????????????????????????????§????????°????±?????????????????????????????????§????????£?????§????????°+1?????????
        for i in range(len(dx)):
            nx = cx + dx[i]
            ny = cy + dy[i]
            #  ?§????????????§???????????? ?????? ??¢?????¢?´¢?????§???????????°??????????????§?????¢?´¢????¶???????
            if is_passable(maze, w, h, cx, cy, dx[i], dy[i]) and d[ny][nx] == float('inf'):
                Q.append((nx, ny))
                d[ny][nx] = d[cy][cx] + 1
    return 0                    #  ??¨??¢?´¢??????????????´???????????§???????????????????????£???


def is_passable(maze, w, h, cx, cy, dx, dy):
    # ?§????????????°????????????????????????????????? ?????? ??????????£???????????????¨ ????¢????
    if not 0 <= (cx + dx) < w:
        return False
    if not 0 <= (cy + dy) < h:
        return False
    if dy == -1:                #  up
        return True if maze[cy*2-1][cx] == 0 else False
    if dy == 1:                 #  down
        return True if maze[cy*2+1][cx] == 0 else False
    if dx == -1:                #  left
        return True if maze[cy*2][cx-1] == 0 else False
    if dx == 1:                 #  right
        return True if maze[cy*2][cx] == 0 else False


def solve(maze, w, h):
    return bfs(maze, w, h)


def main(args):
    while True:
        w, h = map(int, input().split(' '))
        if w == 0 and h == 0:
            break

        maze = []
        for d in range(h*2-1):
            maze.append([int(x) for x in input().strip().split(' ')])

        res = solve(maze, w, h)
        print(res)


if __name__ == '__main__':
    main(sys.argv[1:])
    

Measured memory_bytes: 7984
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i ++)
#define irep(i,n) for (int i = (int)(n) - 1;i >= 0;--i)
using namespace std;
using ll = long long;
using PL = pair<ll,ll>;
using P = pair<int,int>;
constexpr int INF = 1000000000;
constexpr long long HINF = 1000000000000000;
constexpr long long MOD = 1000000007;// = 998244353;
constexpr double EPS = 1e-4;
constexpr double PI = 3.14159265358979;

using u64 = unsigned long long;
constexpr u64 M = 2305843009213693951; // 2^61 - 1
constexpr u64 MASK31 = 2147483647; // 2^31 - 1
constexpr u64 MASK30 = 1073741823; // 2^30 - 1
constexpr u64 POSITIVIZER = 4*M;

u64 CalcMod(u64 x) {
    u64 res = (x >> 61) + (x&M);
    if (res >= M) res -= M;
    return res;
}
u64 mul(u64 x,u64 y) {
    u64 au = (x >> 31),ad = (x&MASK31),bu = (y >> 31),bd = (y&MASK31);
    u64 m = au * bd + ad * bu;
    u64 mu = (m >> 30),md = (m&MASK30);
    u64 ans = 2*au*bu + mu + (md << 31) + ad*bd;
    return CalcMod(ans);
}

struct RollingHash {
    static u64 B;
    int N;
    vector<u64> hash,power;
    RollingHash(const string &s) {
        N = (int)s.size();
        hash.resize(N + 1,0); power.resize(N + 1,0);
        hash[0] = 0; power[0] = 1;
        for (int i = 0; i < (int)s.size(); ++i) {
            hash[i + 1] = CalcMod(mul(hash[i],B) + s[i]);
            power[i + 1] = mul(power[i],B);
        }
    }
    u64 get() {return hash[N];}
    u64 get(int k) {return hash[k];}
    u64 get(int l,int r) {return CalcMod(hash[r] + POSITIVIZER - mul(hash[l],power[r - l]));}
};

mt19937_64 mt;
uniform_int_distribution<unsigned long long> rng(2,M - 2);
unsigned long long RollingHash::B = rng(mt);

int main() {
    int N; cin >> N;
    vector<string> S(N);
    rep(i,N) cin >> S[i];

    sort(S.begin(),S.end(),[](const string &a,const string &b){return a.size() < b.size();});
    set<u64> before;
    ll ans = 0;
    rep(i,N) {
        string s = S[i];
        reverse(s.begin(),s.end());
        u64 hash = 0;
        vector<int> alpha(26,0);
        rep(j,s.size()) alpha[s[j] - 'a'] ++;
        rep(k,26) {
            if (alpha[k]) {
                u64 now = CalcMod(k + 97);
                if (before.count(now)) ++ans;
            }
        }
        rep(j,s.size()) {
            hash = CalcMod(mul(hash,RollingHash::B) + s[j]);
            alpha[s[j] - 'a'] --;
            u64 x = mul(hash,RollingHash::B);
            rep(k,26) {
                if (alpha[k]) {
                    u64 now = CalcMod(x + k + 97);
                    if (before.count(now)) ++ans;
                }
            }
        }
        before.insert(hash);
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 18648
from bisect import bisect
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    X, N = map(int, input().split())
    P = list(map(int, input().split()))

    if not N:
        print(X)
        return

    nums = []
    for i in range(min(P) - 1, max(P) + 2):
        if i not in P:
            nums.append(i)
    i = bisect(nums, X)
    if abs(nums[i] - X) < abs(nums[i-1] - X):
        print(nums[i])
    else:
        print(nums[i-1])


main()


Measured memory_bytes: 9192
import sys
from collections import Counter

def main():
    N = int(sys.stdin.readline().strip())
    ans = 0
    present = {}
    for i in range(N):
        temp = "".join(sorted(sys.stdin.readline().strip()))
        if temp not in present:
            present[temp] = 1
            
        else:
            ans += present[temp]
            present[temp] +=1
        
        
    print("%d" % ans)

def solve():
    pass


if __name__ == "__main__":
    main()

Measured memory_bytes: 56412
import queue
n,m=map(int,input().split())
e=[[] for _ in range(n+1)]
INF=10**18
d=[INF]*(n+1)
ans=[0]*(n+1)
for _ in range(m):
  a,b=map(int,input().split())
  e[a]+=[b]
  e[b]+=[a]
q=queue.Queue()
q.put(1)
d[1]=0
while not q.empty():
  now=q.get()
  for to in e[now]:
    if d[to]==INF:
      ans[to]=now
      d[to]=d[now]+1
      q.put(to)
print('Yes')
for i in ans[2:]:
  print(i)

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

using namespace std;

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

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



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

int n, pos;
vector<int> pre, in, post;

void rec(int l, int r) {
  if ( l >= r ) return;
  int root = pre[pos++];
  int m = distance(in.begin(), find(in.begin(), in.end(), root));
  rec(l, m);
  rec(m + 1, r);
  post.push_back(root);
}

void solve() {
  pos = 0;
  rec(0, pre.size());
  for ( int i = 0; i < n; i++ ) {
    if ( i ) cout << " ";
    cout << post[i];
  }
  cout << endl;
}

int main() {
  int k;
  cin >> n;

  for ( int i = 0; i < n; i++ ) {
    cin >> k;
    pre.push_back(k);
  }

  for ( int i = 0; i < n; i++ ) {
    cin >> k;
    in.push_back(k);
  }

  solve();

  return 0;
}

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

namespace ABC086
{
    class C
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());

            int[] t = new int[N + 1];
            int[] x = new int[N + 1];
            int[] y = new int[N + 1];

            x[0] = 0;
            y[0] = 0;
            t[0] = 0;

            for (int i = 1; i <= N; i++)
            {
                string[] input = Console.ReadLine().Split(' ');
                t[i] = int.Parse(input[0]);
                x[i] = int.Parse(input[1]);
                y[i] = int.Parse(input[2]);
            }

            int t2 = 0;
            int x2 = 0;
            int y2 = 0;
            for (int i = 0; i < N; i++)
            {
                x2 = x[i + 1] - x[i];
                y2 = y[i + 1] - y[i];
                t2 = t[i + 1] - t[i];

                if (t2 < (x2 + y2))
                {
                    Console.WriteLine("No");
                    return;
                }

                if ((t2 - (x2 + y2)) % 2 != 0)
                {
                    Console.WriteLine("No");
                    return;
                }
            }

            Console.WriteLine("Yes");

        }
    }
}


Measured memory_bytes: 16196
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <string>
#include <cstring>

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

using namespace std;
using ll = long long int;
using ull = unsigned long long;

constexpr ull mod = 1e9+7;
constexpr int N = 13;
ull dp[100010][N];

float myPower(int a, int n) { // aのn乗の計算
	float x = 1;
	while (n > 0) { // 全てのbitが捨てられるまで
		if ( n & 1) { // 一番右のbitが１のとき
			x *= a;
		}
		a *= a;
		n >>= 1; // bit全体を右に1つシフトして一番右を捨てる
	}
	return x;
}

int main() {
	int m1, m2, d1, d2;
	cin >> m1 >> d1 >> m2 >> d2;
	if (m1 != m2) {
		cout << "1";
	} else {
		cout << "0";
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
    return '"' + s + '"';
}

string to_string(const char* s) {
    return to_string((string) s);
}

string to_string(bool b) {
    return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
    bool first = true;
    string res = "{";
    for (int i = 0; i < static_cast<int>(v.size()); i++) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(v[i]);
    }
    res += "}";
    return res;
}

template <size_t N>
string to_string(bitset<N> v) {
    string res = "";
    for (size_t i = 0; i < N; i++) {
        res += static_cast<char>('0' + v[i]);
    }
    return res;
}

template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for (const auto &x : v) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

int n, m;
int const mxn = 2e5;
vector<int> tree[mxn];
bool ok = 0;
void dfs(int v, int depth) {
    if (depth == 2) {
        if(v == n) {
            ok = 1;
        }
        return;
    }
    for (auto c : tree[v]) {
        dfs(c, depth + 1);
    }
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        tree[a].push_back(b);
    }
    dfs(1, 0);
    if (ok) {
        cout << "POSSIBLE";
    } else {
        cout << "IMPOSSIBLE";
    }
}


Measured memory_bytes: 11804
from collections import deque

n = int(input())
a = [int(i) for i in input().split()]
b = deque()
if n % 2 == 0:
    for i in range(n):
        if i % 2 == 0:
            b.append(a[i])
        else:
            b.appendleft(a[i])
else:
    for i in range(n):
        if i % 2 == 0:
            b.appendleft(a[i])
        else:
            b.append(a[i])
print(*list(b))

Measured memory_bytes: 32268
P = input()
count = 0

if(P[0] == "R" and P[1] == "S"):
  count = 1
elif(P[0] == "S" and P[1] == "S" and P[2] == "S"):
  count = 0
elif(P[0] == "R" and P[1] == "R" and P[2] == "R"):
  count = 3
elif(P[0] == "S" and P[1] == "R" and P[2] == "R"):
  count = 2
elif(P[0] == "R" and P[1] == "R" and P[2] == "S"):
  count = 2
else:
  count = 1

print(count)

Measured memory_bytes: 61812
import sys

input=sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

x=sum(A[i]*(-1)**i for i in range(0,N))

ans=[0 for i in range(0,N)]

ans[0]=x

for i in range(1,N):
    ans[i]=2*A[i-1]-ans[i-1]

print(*ans)

Measured memory_bytes: 61284
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
        }

        public void Solve(ConsoleInput cin)
        {
            var n = cin.ReadInt;
            var a = cin.ReadLongArray(n);

            long ret1 = 0, ret2 = 0;

            {
                long psum = -1;
                long sum  = 0;
                for (int i = 0; i < n; ++i)
                {
                    sum += a[i];
                    if (sum >= 0 && psum > 0)
                    {
                        ret1 += sum + 1;
                        sum = -1;
                    }
                    else if (sum <= 0 && psum < 0)
                    {
                        ret1 -= sum - 1;
                        sum = 1;
                    }
                    psum = sum;
                }
            }
            {
                long psum = 1;
                long sum  = 0;
                for (int i = 0; i < n; ++i)
                {
                    sum += a[i];
                    if (sum >= 0 && psum > 0)
                    {
                        ret2 += sum + 1;
                        sum = -1;
                    }
                    else if (sum <= 0 && psum < 0)
                    {
                        ret2 -= sum - 1;
                        sum = 1;
                    }
                    psum = sum;
                }
            }

            WriteLine(Min(ret1, ret2));
        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); }}
        public int ReadInt { get { return int.Parse(Read); }}
        public long ReadLong { get { return long.Parse(Read); }}
        public double ReadDouble { get { return double.Parse(Read); }}
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret;}
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret;}
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret;}
    }
}


Measured memory_bytes: 31196
#include <vector>
#include <cmath>
#include <algorithm>
#include <iostream>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const string NO = "IMPOSSIBLE";

void solve(long long A, long long B){
  ll C = A+B;
  if((A+B)%2==0 )
    cout<< (A+B)/2 <<endl;
  else
    cout << NO << endl;
}

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


Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int X = sc.nextInt();
    int x[] = new int[N];
    int ans = 0;
    for(int i = 0;i < N;i++){
      x[i] = Math.abs(sc.nextInt() - X);
    }
    ans = x[0];
    for(int i = 1;i < N;i++){
      ans = gcd(ans,x[i]);
      if(ans == 1){
        break;
      }
    }
    System.out.println(ans);
  }
  static int gcd(int a,int b){
    if(a < b) return gcd(b,a);
    if(b == 0) return a;
    return gcd(b, a % b);
  }
}


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

int main() {
    int k,s; cin >> k >> s;
    int cnt = 0;
    rep(i,k+1) {
        rep(j,k+1){
            int z = s-i-j;
            if (0 <= z && z<= k) cnt++;
        }
    }

    cout << cnt << endl;
}

Measured memory_bytes: 256
#![allow(non_snake_case)]

use std::io::{stdin, Read};
use std::str::FromStr;
fn read_option<T: FromStr>() -> Option<T> {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok()
}
fn read<T: FromStr>() -> T {
    let opt = read_option();
    opt.expect("failed to parse token")
}

fn main() {
    let n: usize = read();
    let vec: Vec<usize> = (0..n).map(|_| read()).collect();
    let max: usize = *vec.iter().max().unwrap();
    let mut digit = 0;
    while 2_usize.pow(digit) < max {
        digit += 1;
    }
    let mut map: Vec<Vec<usize>> = vec![];
    for mut v in vec {
        let mut now = vec![];
        for _ in 0..=digit {
            now.push(v % 2);
            v /= 2;
        }
        map.push(now);
    }
    let mut v2 = vec![];
    for i in 0..=digit {
        let mut sum: usize = 0;
        for j in 0..map.len() {
            sum += map[j][i as usize];
        }
        v2.push(sum);
    }
    let mut ans = vec![0; map.len()];
    for (j, v) in map.into_iter().enumerate() {
        for (i, &val) in v.iter().enumerate() {
            if v2[i] % 2 == 0 {
                ans[j] += 2_usize.pow(i as u32) * val;
            } else {
                let rev = if val == 0 { 1 } else { 0 };
                ans[j] += 2_usize.pow(i as u32) * rev;
            }
        }
    }
    println!(
        "{}",
        ans.iter()
            .map(|x| x.to_string())
            .collect::<Vec<_>>()
            .join(" ")
    );
}


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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<int, int> Pi;
typedef vector<ll> Vec;
typedef vector<int> Vi;
typedef vector<string> Vs;
typedef vector<vector<ll>> VV;

#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define rep(i, n) REP(i, 0, n)
const int INF=1e9;
const int MAX=100005;
const int MOD=1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;
#define ALL(v) v.begin(), v.end()
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a,b)
#define Each(a,b) for(auto &a :b)
#define REPM(i, mp) for (auto i = mp.begin(); i != mp.end(); ++i)
#define dbgmap(mp) for (auto i = mp.begin(); i != mp.end(); ++i) { cout << i->first <<":"<<i->second << endl;}
#define dbgarr(n,m,arr) rep(i,n){rep(j,n){cout<<arr[i][j]<<" ";}cout<<endl;}
#define sum(v) accumulate(ALL(v),0)
#define fi first
#define se second

template<typename T1, typename T2>
ostream &operator<<(ostream &s, const pair<T1, T2> &p) { return s<<"("<<p.first<<", "<<p.second<<")"; }

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

// 2 dimentional vector
template<typename T>
ostream &operator<<(ostream &s, const vector<vector<T> > &vv) {
    int len=vv.size();
    for(int i=0; i<len; ++i) {
        s<<vv[i]<<endl;
    }
    return s;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,m;
    cin>>n>>m;
    ll l=1;
    ll r=n;
    rep(i,m) {
        ll a, b;
        cin>>a>>b;
        l=max(l, a);
        r=min(r, b);
    }
    ll ans = 0;
    if(r>=l){
        ans=r-l+1;
    }else{
        ans = 0;
    }
    cout<<ans<<endl;
    return  0;
}


Measured memory_bytes: 256
n=int(input())
A=[int(x) for x in input().split()]
B=sorted(A)
Alice=[]
Bob=[]
while len(B)!=0 and len(B)!=1:
  Alice.append(B[-1])
  B.pop()
  Bob.append(B[-1])
  B.pop()
if len(B)==1:
  Alice.append(B[0])
  B.pop()
print(sum(Alice)-sum(Bob))


Measured memory_bytes: 8904
#include<cstdio>
#include<algorithm>

using namespace std;

int x[100100];
int N;

long long dis(long long a, long long b){
	if(a > b) return a - b;
	else return b - a;
}

long long calc(){
	long long cur = x[0];
	long long res = 0;
	for(int i = 1; i < N; ++i){
		long long tmp = x[i];
		if(cur > 0){
			if(tmp >= -cur){
				res += dis(-cur - 1, tmp);
				tmp = -cur - 1;
			}
		}else{
			if(tmp <= -cur){
				res += dis(-cur + 1, tmp);
				tmp = -cur + 1;
			}
		}
		cur += tmp;
	}
	return res;
}

long long solve(){
	if(x[0] != 0){
		long long tmp = calc();
		long long tmp1;
		if(x[0] > 0){
			tmp1 = dis(x[0], -1);
			x[0] = -1;
		}else{
			tmp1 = dis(x[0], 1);
			x[0] = 1;
		}
		long long tmp2 = tmp1 + calc();
		return min(tmp, tmp2);
	}
	x[0] = 1;
	long long tmp = calc();
	x[0] = -1;
	long long tmp2 = calc();
	return min(tmp, tmp2) + 1;
}

void input(){
	scanf("%d", &N);
	for(int i = 0; i < N; ++i){
		scanf("%d", x + i);
	}
}

int main(){
	input();
	long long ans = solve();
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 512
//     THE ONLY WAY IS UP

#include<bits/stdc++.h>

#define ll              long long int
#define ld              long double
#define f1(i, a, b)     for(ll i = a; i < b; i++)
#define f2(a, b)        for(auto a : b)
#define ar(v, i)        v[i]
#define in_(x)          ll x; cin >> x;
#define ino_(type, x)   type x; cin >> x;
#define pb              push_back

using namespace std;

int main()
{
    in_(n)
    
    ll fc, hc;
    if(n / 500 > 0)
    {
        fc = n / 500;
        n -= fc * 500;
    }
    
    if(n / 5 > 0)
    {
        hc = n / 5;
        n -= hc * 5;
    }
    
    cout << fc * 1000 + hc * 5 << endl;
    
}

Measured memory_bytes: 256
# 2138~
# アイディア 2140
# permutationを使って，N!通りの経路を実際に作ってそれらの経路を足して最終的にpermutation数で割れば良い
# 実装2200

N = int(input())

X=[]
Y=[]
for _ in range(N):
    xi,yi = map(int,input().split())
    X.append(xi)
    Y.append(yi)
XY = [[x,y] for x,y in zip(X,Y)]
import itertools

All = itertools.permutations(XY)
distance = 0
import math
for j,xy in enumerate(All):
    for i,xiyi in enumerate(xy):
        if i == 0:
            start = xiyi
            continue
        now = xiyi
        distance += math.sqrt((start[0]-now[0])**2+(start[1]-now[1])**2)
        start = now
    num = j
print(distance/(num+1))



Measured memory_bytes: 3064
N,W=map(int,input().split())
w,v=[0]*N,[0]*N
for i in range(N):
    w[i],v[i]=map(int,input().split())
dp=[[float('inf')]*(sum(v)+1) for i in range(N+1)]

dp[0][0]=0
for i in range(1,N+1):
    for j in range(len(dp[0])):
        if j>=v[i-1]:
            dp[i][j]=w[i-1]+dp[i-1][j-v[i-1]]
        dp[i][j]=min(dp[i][j],dp[i-1][j])

ans=0
for i in range(len(dp[0])):
    if dp[N][i]<=W:
        ans=i
print(ans)

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

typedef unsigned long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;

#define INF (int)(1e9)

#define rep(i,n) for(int i=0; i<(n); i++)
#define REP(i,start,end) for(int i=(start);i<=(end);i++)
#define all(n) begin(n),end(n)

#define DEBUG

int main()
{
	int n;
	cin >> n;
	vi a(n);
	rep(i,n) cin >> a[i];

	int t = 1;
	//bool flag = false;
	int broke = 0;
	rep(i,n)
	{
		if(t == a[i])
		{
			++t;
			++broke;
			//flag = true;
		}
	}
	int ans = n - broke;
	if(broke != 0) cout << ans << endl;
	else cout << -1 << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#define int long long
#define uint unsigned long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
using namespace std;


signed main()
{
	int s, c;
	cin >> s >> c;

	if (s >= c / 2)
	{
		cout << (c / 2) << endl;
		return 0;
	}

	int cnt = s;
	c -= s * 2;
	cnt += (c / 4);
	cout << cnt << endl;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int mod = 1000000007;

long long pow2 ( long long a, long long st ) {
    long long ret = 1;
    while ( st ) {
        if ( st&1 ) { ret *= a; ret %= mod; }
        st /= 2;
        a *= a;
        a %= mod;
    }
    return ret;
}
long long f[(1<<20)], invf[(1<<20)];
void pre () {
    f[0] = 1;
    invf[0] = 1;
    for ( int i = 1 ; i < (200042) ; i ++ ) {
        f[i] = f[i-1]*i%mod;
        invf[i] = pow2 ( f[i] ,mod-2 );
    }
}
long long comb( long long n, long long k ) {
    return f[n]*invf[k]%mod*invf[n-k]%mod;
}

int main () {
    pre();
    int w, h, a, b;
    cin >> h >> w >> a >> b;

    long long allSt = w+h-2;

    long long ans = comb( allSt, w-1 ), steps = (h-a)+b-1;

    for ( int cntDs = h-a; cntDs < h && cntDs <= steps; cntDs ++ ) {
        ans -= comb( steps, cntDs )*comb( allSt-steps, h-cntDs-1 )%mod;
        if ( ans < 0 ) { ans += mod; }
    }
    cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 3840