akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

int arr[22][22];
long long int dp[(1<<22)];
int n;
long long int call(long long int mask)
{
	
	 int i=__builtin_popcount(mask);
	 if(i==n)
	 return 1;
	 
	 if(dp[mask]!=-1)
	  return dp[mask];
	  
	long long int ans=0;
	for(int j=0;j<n;j++)
	{
		if(arr[i][j] && !(mask&(1<<j)))
		ans=(ans%1000000007+call((mask|(1<<j)))%1000000007)%1000000007;
	}
	return dp[mask]=ans%1000000007;
}

 int main() 
{  

 cin>>n;
 for(int i=0;i<n;i++)
  for(int j=0;j<n;j++)
    cin>>arr[i][j];

 
    for(int j=0;j<=(1<<n);j++)
      dp[j]=-1;
 
  cout<<call(0)<<endl;
 
	return 0;
} 

Measured memory_bytes: 18688
#include <iostream>
#include <vector>

using namespace std;
typedef pair<double, double> P;

double cross_product(P p1, P p2, P p3)
{
	P p[2];
	p[0].first = p2.first - p1.first;
	p[0].second = p2.second - p1.second;
	p[1].first = p3.first - p1.first;
	p[1].second = p3.second - p1.second;
	return(p[0].first * p[1].second - p[1].first * p[0].second);
}

void solve()
{
	int N;
	while(cin >> N, N)
	{
		vector<P> Vec(N);
		for(int i = 0; i < N; ++i)
		{
			scanf("%lf,%lf", &Vec[i].first, &Vec[i].second);
		}
		double min_x = Vec[0].first;
		int index = 0;
		for(int i = 1; i < N; ++i)
		{
			if(min_x > Vec[i].first)
			{
				min_x = Vec[i].first;
				index = i;
			}
		}
		vector<bool> used(N);
		for(int i = 0; i < N; ++i)
		{
			used[i] = false;
		}
		used[index] = true;
		int end = index;
		while(true)
		{
			for(int i = 0; i < N; ++i)
			{
				if(index == i)
				{
					continue;
				}
				bool flag = true;
				for(int j = 0; j < N; ++j)
				{
					if(index == j || i == j)
					{
						continue;
					}
					if(cross_product(Vec[index], Vec[i], Vec[j]) <= 0)
					{
						flag = false;
						break;
					}
				}
				if(flag)
				{
					used[i] = true;
					index = i;
					break;
				}
			}
			if(end == index)
			{
				break;
			}
		}
		int count = 0;
		for(int i = 0; i < N; ++i)
		{
			if(!used[i])
			{
				count++;
			}
		}
		cout << count << endl;
	}
}

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

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


int main(){
    
    int N,a,cn=0;cin>>N;
    map<int,int> mp;
    rep(i,0,N){
        cin>>a;
        mp[a]++;
    }
    for(auto it=mp.begin();it!=mp.end();it++){
        pair<int,int> pai=*it;
        if(pai.first>pai.second)cn+=pai.second;
        else cn+=pai.second-pai.first;
    }
    cout<<cn<<endl;
}






Measured memory_bytes: 4736
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <numeric>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

#define rep(i, N) for(int i = 0; i < N; ++i)

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))


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

    int h, w;
    cin >> h >> w;
    int n;
    cin >> n;
    int a;
    vs32 ans(h * w);
    int idx = 0;
    rep (i, n)
    {
        cin >> a;
        rep (j, a)
        {
            ans[idx++] = i + 1;
        }
    }

    rep (i, h)
    {
        rep (j, w)
        {
            if (j > 0) cout << " ";
            if (i & 1)
            {
                cout << ans[(i + 1) * w - j - 1];
            }
            else
            {
                cout << ans[i * w + j];
            }
        }
        cout << "\n";
    }
    return 0;
}



Measured memory_bytes: 384
import java.util.*;
 
public class Main{
    
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int K = sc.nextInt();
        sc.close();

        System.out.println((int)K*(int)Math.pow(K-1, N-1));
    }
}

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

int main(){
    int n;
    cin>>n;
    int p[n];
    for(int i=0;i<n;i++) cin>>p[i];
    int ans=0;
    int i=0;
    while(i<n){
        if(p[i]-1==i){
            i+=2;
            ans++;
        }
        else i++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;

VI a;
VI len;
VVI e;
VI lfs;
VI lfs_bef;
void dfs(int from, int to) {
  int pos = -1;
  int bef = 0;
  if (lfs.back() < a.at(to)) {
    lfs.push_back(a.at(to));
  } else {
    pos = distance(lfs.begin(), lower_bound(lfs.begin(), lfs.end(), a.at(to)));
    bef = lfs.at(pos);
    lfs.at(pos) = a.at(to);
  }
  len.at(to) = lfs.size();
  for (auto next : e.at(to)) {
    if (next == from) {
      continue;
    }
    dfs(to, next);
  }
  if (pos == -1) {
    lfs.pop_back();
  } else {
    lfs.at(pos) = bef;
  }
}
int main() {
  int n;
  cin >> n;
  a.resize(n);
  len.resize(n);
  e.resize(n);
  rep(i, n) { cin >> a.at(i); }
  rep(i, n - 1) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    e.at(u).push_back(v);
    e.at(v).push_back(u);
  }
  lfs = {a.at(0)};
  dfs(-1, 0);
  rep(i, n) { cout << len.at(i) << endl; }
}


Measured memory_bytes: 27180
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int x = sc.nextInt();
		int t = sc.nextInt();
		if(n % x == 0) {
			System.out.println(n / x * t);
		}else{
			System.out.println((n / x + 1) * t);
		}
	}
}

Measured memory_bytes: 35652
#include <bits/stdc++.h>
using namespace std;
int main(){
        int n; cin >> n;
        set<long long int> s;
        for (int x = 0; x < n; ++x){
            long long int q; cin >> q;
            s.insert(q);
        }
        if (s.size() == n){
            cout << "YES" << endl;
        }
        else{
            cout << "NO" << endl;
        }
    return 0;
}



Measured memory_bytes: 12840
#define    ll           long long
#define    dd           double
#define    mp           make_pair
#define    pb           push_back
#define    se           second
#define    fi           first
#define    mod          10000007
#define    sob(v)       v.begin(),v.end()
#define    sobr(v)      v.rbegin(),v.rend()
#define    fr(i,a,b)    for(int i=a;i<=b;++i)
#define    frr(i,a,b)   for(int i=a;i>=b;--i)
#define    pi           acos(-1.00)
#define    check        cout<<"*"<<endl
#define    ffix(x)      cout<<fixed<<setprecision(x)
#define    fast         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)

#include<bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef map<int,int> mii;
typedef pair<int,int> pii;
typedef pair<int,vi> pp;

int dr[4]= {0,0,-1,1};
int dc[4]= {-1,1,0,0};

const int N=100;

int main()
{
    ll n;
    cin>>n;
    string s;
    while(n>0)
    {
        n-=1;
        s+=('a'+n%26);
        n/=26;
    }
    reverse(sob(s));
    cout<<s<<endl;
}


Measured memory_bytes: 3624
N = int(input())
*H, = map(int, input().split())
INF = 1 << 30
cost1 = []
cost2 = []
for i, h in enumerate(H):
    if i+1 < N:
        cost1.append(abs(H[i+1]-h))
    if i+2 < N:
        cost2.append(abs(H[i+2]-h))
cost2.append(INF)

dp = [INF]*(N+1)
dp[0] = 0
for i, (d, c1, c2) in enumerate(zip(dp, cost1, cost2)):
    if d + c1 < dp[i+1]:
        dp[i+1] = d + c1
    if d + c2 < dp[i+2]:
        dp[i+2] = d + c2
print(dp[N-1])


Measured memory_bytes: 19316
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

N, M = map(int,input().split())

mod = 10 ** 9 + 7
MAX = max(M,N)+10
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX
def cominit():
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    for i in range(2,MAX):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod//i) % mod
        finv[i] = finv[i-1] * inv[i] % mod
def cmb(n,r):
    if n < 0 or r < 0 or r > n:return 0
    if r > n/2: r = n-r        
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod
def permu(n,r):
    return fac[n] * finv[n-r]

cominit()

ans = permu(M, N)%mod
minus = 0
for i in range(1, N+1):
    minus += (-1)**((i-1)&1)*cmb(N,i)*permu(M-i, N-i)
    minus %= mod
ans += mod - minus
ans %= mod
ans *= permu(M,N)
ans %= mod
print(ans)

Measured memory_bytes: 95640
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<vector>
#include<cmath>
#include<cstdio>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define rp(a) while(a--)
#define pb push_back
#define mp make_pair
#define it ::iterator
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double EPS=1e-10;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
int main(){
	double x[4],y[4];
	while(cin>>x[0]>>y[0]){
		loop(i,1,4)cin>>x[i]>>y[i];
		if(x[2]<x[1]+EPS&&x[0]<x[3]+EPS&&y[0]<y[3]+EPS&&y[2]<y[1]+EPS)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
}

Measured memory_bytes: 1220
#include <bits/stdc++.h>
using namespace std;
int64_t combimation(int64_t n,int64_t r) {
    int64_t v = 1;
    for(int64_t i = 0;i < r;i++) {
        v = v * (n - i) / (i + 1);
    }
    return v;
}
int main() {
    int n;
    cin >> n;
    map<string,int64_t> S;
    string s;
    for(int i = 0;i < n;i++) {
        cin >> s;
        sort(s.begin(),s.end());
        if(S.count(s)) {
            S.at(s)++;
        }else {
            S[s] = 0;
        }
    }
    int64_t count = 0;
    for(auto p : S) {
        auto value = p.second;
        count += combimation(value + 1,2);
    }
    cout << count << endl;
}


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

int main() {
    string str;
    cin>>str;
    int n = str.length(),a=0,b=0;
    for(int i=0;i<n;i++){
        if(str[i] == 'A')a++;
        else b++;
    }
    if(a!=0 && b!=0){
        cout<<"Yes\n";
    }else{
        cout<<"No\n";
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) (x).begin(), (x).end()
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
  #define debug(x) cerr << #x " => " << (x) << endl
#else
  #define debug(x) 0
#endif
using lint = long long;
constexpr int    INF  = 1 << 29;
constexpr lint   INFL = 1LL << 61;
constexpr int    MOD  = (int)1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

int main(void) {
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  vector<int> l(q), r(q);
  rep (i, q) {
    int a, b;
    cin >> a >> b;
    l[i] = --a, r[i] = --b;
  }
  vector<int> ac_idx;
  rep (i, n - 1) if (s[i] == 'A' && s[i + 1] == 'C') ac_idx.push_back(i);
  vector<int> ans(q);
  debug(ac_idx);
  rep (i, q) ans[i] = lower_bound(all(ac_idx), r[i]) - lower_bound(all(ac_idx), l[i]);
  allrep (x, ans) cout << x << "\n";
  return 0;
}

Measured memory_bytes: 2508
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int t[1000][1000];
int x[1000][1000];
int n, m, a, b, c;
int s, g1, g2;
int z[1000][3];
int minx;

int main() {
	while (true) {
		memset(x, 0, sizeof(x));
		memset(z, 1, sizeof(z));
		memset(t, 0, sizeof(t));
		minx = 1500000000;
		cin >> n >> m >> s >> g1 >> g2;
		if (n == 0 && m == 0 && s == 0 && g1 == 0 && g2 == 0) { break; }
		for (int i = 0; i < m; i++) {
			cin >> a >> b >> c;
			x[a][b] = c;
		}
		z[s][0] = 0;
		z[g1][1] = 0;
		z[g2][2] = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				for (int k = 1; k <= n; k++) {
					if (x[j][k] >= 1) {
						if (z[j][0] < 100000000) {
							z[k][0] = min(z[k][0], z[j][0] + x[j][k]);
						}
					}
				}
			}
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				for (int k = 1; k <= n; k++) {
					if (x[k][j] >= 1) {
						if (z[j][1] < 100000000) {
							z[k][1] = min(z[k][1], z[j][1] + x[k][j]);
						}
					}
				}
			}
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				for (int k = 1; k <= n; k++) {
					if (x[k][j] >= 1) {
						if (z[j][2] < 100000000) {
							z[k][2] = min(z[k][2], z[j][2] + x[k][j]);
						}
					}
				}
			}
		}
		for (int i = 1; i <= n; i++) {
			minx = min(minx, z[i][0] + z[i][1] + z[i][2]);
		}
		cout << minx << endl;
	}
}

Measured memory_bytes: 8992
/* Author - thiolhub */

#include <bits/stdc++.h>

using namespace std;

#define ll              long long int
#define ld              long double
#define db              double
#define pi              3.1415926535897932384626
#define PI              acos(-1.0)
#define endl            "\n"
#define mod             1000000007
#define mk              make_pair
#define pb              push_back
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define ps(x,y)         fixed<<setprecision(y)<<x
#define w(t)            ll t; cin>>t; while(t--)
#define sc(a)	        scanf("%lld",&a);
#define pr(a)	        printf("%lld\n",a)
#define rep(i,a,n)		for(ll i=a;i<n;i++)
#define m(a)		    memset(a,0,sizeof(a))
#define FastIO          ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0)
#define min3(a,b,c)     min(a,min(b,c))



int main(){ FastIO;

int n,i,k;cin>>n>>k;
int a[n];for(i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
int s=0;
for(i=0;i<k;i++) s+=a[i];
cout<<s;

}

Measured memory_bytes: 3628
def solve(s):
    if(s[0] == "A"):
        v = s[1:]
        i = v.find("C")
        if(i >= 1 and i < len(v)-1):
            k = v[:i] + v[i+1:]
            if(k.islower()):
                return "AC"
    return "WA"
 
s = input()
print(solve(s))

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
const int N=305;
string s;
int dp[305][305][305],K;
int dfs(int l,int r,int x)
{
    if(r<l)return 0;
    if(l==r)return 1;
    if(dp[l][r][x]!=-1)return dp[l][r][x];//记忆化思想，减少搜索次数
    int t=max(dfs(l+1,r,x),dfs(l,r-1,x));//向左或右扩展一个
    if(s[l]==s[r])t=max(t,dfs(l+1,r-1,x)+2);//相等，进行扩展
    else if(x)t=max(t,dfs(l+1,r-1,x-1)+2);//改变一个字符，向内扩展
    return dp[l][r][x]=t;
}
int main()
{
    cin>>s>>K;
    memset(dp,-1,sizeof(dp));
    cout<<dfs(0,s.size()-1,K)<<endl;
    return 0;
}

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


int main(){
	while(1){
		int n,m,k;
		cin>>n>>m>>k;
		if(n==0) break;
		vip a(n);
		vvi b(n,vi(m));
		for(int i=0;i<n;i++) a[i].second=i+1;
		for(int i=0;i<k;i++){
			int x,y,z;
			string s;
			cin>>y>>z>>x>>s;
			y--;z--;
			if(s[0]=='W') b[y][z]++;
			else{
				a[y].first.first--;
				a[y].first.second+=b[y][z]*1200+x;
			}
		}
		sort(a.begin(),a.end());
		for(int i=0;i<n;i++){
			cout<<a[i].second<<' '<<-a[i].first.first<<' '<<a[i].first.second<<endl;
		}
	}
}


Measured memory_bytes: 3176
#include<bits/stdc++.h>
#include<string.h>
#include <math.h>
#include<iostream>
using namespace std;
typedef long long           ll;
typedef unsigned long long  ull;
typedef long double         ld;

#define sf                  scanf
#define pf                  printf
#define srev                reverse(s.begin(),s.end())
#define sortstr             sort(s.begin(), s.end());
#define gtl(x)              getline(cin, (x))
#define gcd(a, b)           __gcd(a, b)
#define lcm(a, b)           ((a)*((b)/gcd(a,b)))
#define PI                  acos(-1)
#define Precision(a) cout << fixed << setprecision(a)
#define FasterIO     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);


template <typename T> T Sqr(T x) { T n = x * x ; return n ;}
template <typename T> T Pow(T B,T P){ if(P==0) return 1; if(P&1) return B*Pow(B,P-1);  else return Sqr(Pow(B,P/2));}
template <typename T> T Abs(T a) {if(a<0)return -a;else return a;}
template <typename T> T Gcd(T a,T b){if(a<0)return Gcd(-a,b);if(b<0)return Gcd(a,-b);return (b==0)?a:Gcd(b,a%b);}
template <typename T> T Lcm(T a,T b) {if(a<0)return Lcm(-a,b);if(b<0)return Lcm(a,-b);return a*(b/Gcd(a,b));}
//scanf("%[^\n]%*c", str);
//sort(s,s+n,greater<int>());

int main()
{
    string s;
    cin >> s;
    string k;
    for(int i=0; i<s.size()/2; i++)
    {
        k+="hi";

    }
    if(s==k) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
int add(int a,int b){
	return (a+b)%MOD;
}
const int N=100100;
int n;
char s[N];
int a[N]={0};
int z1[N]={0};
int z2[N]={0};
int main(){
	scanf("%s",s);
	n=strlen(s);
	for(int i=0;i<n;i++){
		a[i]=s[i]=='a'?1:2;
	}

	int cur=0;
	int bb=false;
	int qwq;
	for(int i=n;i>=0;i--){
		bool e=a[i]==a[i+1];
		if(e){
			qwq=i+2;
			if(i<n){
				bb=true;
			}
		}
		z1[i]=add((e?z2:z1)[i+1],z2[qwq]);
		z2[i]=add(z2[i+1],z2[qwq]);
		cur=(cur+a[i])%3;
		if(cur==0){
			z2[i]=add(z2[i],1);
			if(i==n||(bb&&i>0)){
				z1[i]=add(z1[i],1);
			}
		}
	}
	int ans=z1[0];
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1536
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<iostream>
#include <iomanip>
#include<queue>
#include<algorithm>
#include <functional>
#include<vector>
#include <math.h>
using namespace std;

const int M_MAX = 100001;

int main() {
	int N, M;
	int L, R;
	int D[M_MAX] = {};
	int ans = 0;
	int Ltemp = 0, Rtemp = M_MAX;
	bool flag = false;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> L >> R;
		if (R < Ltemp) {
			flag = true;
			break;
		}
		if (L > Rtemp) {
			flag = true;
			break;
		}
		if (L > Ltemp) Ltemp = L;
		if (R < Rtemp) Rtemp = R;
	}
	if (flag) cout << 0 << endl;
	else cout << Rtemp-Ltemp+1 << endl;
}

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

int main() {
    int n;
    cin >> n;
    int k2 = 2;
    int a = 1;
    while (k2 <= n) {
      a = k2;
      k2 *= 2;
    }
    cout << a << endl; 
}

Measured memory_bytes: 3640
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <map>
#include <numeric>
#include <set>
#include <iomanip>
#include <functional>
#define FOR(i, a, n) for (long long i = (a); i < (n); i++)
#define REP(i, n) for(long long i = 0; i < (n); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define pb push_back
using namespace std;
typedef long long ll;

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

	int A, B;

	cin >> A >> B;

	REP(i, 100000)
	{
		if (A*i - (i - 1) >= B)
		{
			cout << i << endl;
			break;
		}
	}

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int INF=1<<21;
int main(){
  int n,m,s,g1,g2;
  int b1,b2,c;
  int ans=INF;
  int road[111][111];
  while(1){
    cin >> n >> m >> s >> g1 >> g2;
    if(n==0 && m==0 && s==0 && g1==0 && g2==0)break;
    for(int i=1;i<=n;i++){
      for(int j=1;j<=n;j++){
	road[i][j]=INF;
      }
      road[i][i]=0;
    }
    for(int i=0;i<m;i++){
      cin >> b1 >> b2 >> c;
      road[b1][b2]=c;
    }
    for(int k=1;k<=n;k++){
      for(int i=1;i<=n;i++){
	for(int j=1;j<=n;j++){
	  road[i][j]=min(road[i][j],road[i][k]+road[k][j]);
	}
      }
    }
    for(int i=1;i<=n;i++){
      ans=min(ans,road[s][i]+road[i][g1]+road[i][g2]);
    }
    cout << ans << endl;
    ans=INF;
  }
}

Measured memory_bytes: 1208
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int MOD = 1000000007;
const char nl = '\n';
const int MX = 100001; //check the limits, dummy
 
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);    
	
    int N; cin >> N;
    vi A(N), B(N); F0R(i, N) cin >> A[i] >> B[i];
    sort(all(A));
    sort(all(B));
    ll X, Y; 
    if (N % 2 == 1) {
        X = A[N/2];
        Y = B[N/2];
    } else {
        X = A[N/2 - 1] + A[N/2];
        Y = B[N/2 - 1] + B[N/2];
    }
 
    cout << Y-X+1 << nl;
	
	return 0;
}

Measured memory_bytes: 4816
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define PI 3.14159265359
#define INF 1000100100//000000000
#define MOD 1000000007
#define all(x) (x).begin(),(x).end()
typedef long long ll;
#define P pair<int, int>
#define PP pair<P,P>
#define T tuple<int,int,int> 
using namespace std;

int main(){
  int h,w,mm; cin >> h >> w >> mm;
  vector<int> hl(h,0),wl(w,0);
  map<P,int> m; 
  rep(i,mm){
    int a,b; cin >> a >> b;
    a--; b--;
    m[P(a,b)]=1;
    hl[a]++;
    wl[b]++;
  }
  int nowh=0;
  int noww=0;
  vector<int> hsame;
  vector<int> wsame;
  rep(i,h){
      nowh=max(nowh,hl[i]);
  }
  rep(i,h){
      if(hl[i]==nowh) hsame.push_back(i);
  }
  rep(i,w){
      noww=max(noww,wl[i]);
  }
  rep(i,w){
      if(wl[i]==noww) wsame.push_back(i);
  }

  rep(i,hsame.size())rep(j,wsame.size()){
      if(!m[P(hsame[i],wsame[j])]){
          cout << noww+nowh << endl;
          return 0;
      }
  }

  cout << noww+nowh-1 << endl;
  
return 0;
}

Measured memory_bytes: 28420
x, y = map(int, input().split())
mod = 10 ** 9 + 7

if (x + y) % 3 != 0:
    print(0)
else:
    time = (x + y) // 3
    if time > x or time > y:
        print(0)
    else:
        move_time = sorted([x - time, y - time])
        
        if move_time[0] == 0:
            print(1)
        else:
            ans = 1
            for i in range(2, time+1):
                ans *= i
                ans %= mod
            
            const = 1
            for i in range(1, move_time[1]+1):
                const *= i
                const %= mod
                
                if i == move_time[0]:
                    inv0 = pow(const, mod-2, mod)
                
            inv1 = pow(const, mod-2, mod)
        
            print((ans * inv0 * inv1) % mod)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define ss(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl
#define rep(i, j, n) for (int i = j; i <= n; ++i)
#define per(i, j, n) for (int i = n; j <= i; --i)
#define all(x) x.begin(), x.end()
 
using namespace std;

char s[4005];

int main() {		
	int n;
	scanf ("%d", &n);
	scanf ("%s", s + 1);
	int a = 0, b = 0, c = 0;
	rep(i, 1, n) {
		if (s[i] == 'R') a++;
		if (s[i] == 'G') b++;
		if (s[i] == 'B') c++;
	}
	ll res = (ll) a * b * c;
	rep(i, 1, n) {
		rep(j, 1, n) {
			if (i + j > n) break;
			if (i - j < 1) break;
			if (s[i] != s[i - j] && s[i] != s[i + j] && s[i - j] != s[i + j]) res--;
		}
	}
	printf ("%lld\n", res);
	
	
	return 0;
}


Measured memory_bytes: 3760
/*
  coded by: mi_ni_
  "LIVE LONG AND PROSPER"
*/
 
#include <bits/stdc++.h>
using namespace std;

#define FAST_IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define newl '\n'
#define TEST_CASE(fun) int tc; cin>>tc; while(tc--){ fun(); }
#define TEST_CASE_2 int tc; cin>>tc; for(int i=1;i<=tc;i++)
#define TEST_CASE_3(fun) int tc; cin>>tc; for(int i=1;i<=tc;i++){ cout<<"Case #"<<i<<": "; fun(); }
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define forn(i,n) for(int i=0;i<(int)(n);i++)
#define forab(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define forabr(i,a,b) for(int i=(int)(a);i>=(int)(b);i--)
#define trav(i,x) for(auto& i:x)

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>;
using vi=vector<int>;
using vl=vector<ll>;
using vii=vector<pii>;
using vll=vector<pll>;

const ld pi=acosl(-1);
const int inf=(int)1e9+7;
const ll llinf=(ll)1e18+7;
const ld eps=1e-7;

//other
template<typename T> inline bool powerof2(T a){ return (a&&(!(a&(a-1)))); }
template<typename T> inline T log_2(T a){ T res=-1; while(a){ a/=2; res++; } return res; }

//make sure to choose TEST_CASE in main for multiple test cases
void solve(){
	int x;
	cin>>x;
	x>=30 ? cout<<"Yes"<<newl : cout<<"No"<<newl;
}

int main(){
	FAST_IO
	cout<<fixed<<setprecision(15);
	cerr<<fixed<<setprecision(10);
	//init_fact();
	//TEST_CASE(solve)
	//TEST_CASE_2{}
	//TEST_CASE_3(solve)
	solve();
	return 0;
}

Measured memory_bytes: 3648
n = int(input())
h = list(map(int, input().split()))
cost = [0] * n
cost[0] = 0
cost[1] = abs(h[0] - h[1])
for i in range(2, n):
  cur_h = h[i]
  cost[i] = min(
    cost[i-1] + abs(h[i-1] - cur_h),
    cost[i-2] + abs(h[i-2] - cur_h))
print(cost[-1])

Measured memory_bytes: 13980
#include <iostream>
  
using namespace std;
  
int main(void){
  int a,b;
  cin >> a >> b;
  
  if(a==b){
      cout << "a == b";
  }
  else if(a<b){
      cout << "a < b";
  }
  else{
      cout << "a > b";
  }
  
  cout << endl;
  
  return 0;
  
}


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

int main() {
    long long n, d;
    cin>>n>>d;
    int ans=0;
    for(int i=0;i<n;i++)
    {
        long long x, y;
        cin>>x>>y;
        if(sqrt(x*x + y*y)<= d)
        {
            ans++;
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3672
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
  // 標準入力高速化のおまじない
  // scanfとの同期を切る。以降紛らわしいのでscanf使用不可。
  ios::sync_with_stdio(false);
  // // cin前の自動flashをやめる
  cin.tie(nullptr);

  int map_height, map_width, amount_of_movement;
  cin >> map_height >> map_width >> amount_of_movement;

  int sx,sy,gx,gy;
  cin >> sx >> sy >> gx >> gy;
  sx--, sy--, gx--, gy--;

  const int INF = 2e9;
  // 最短でその座標に到達できる手数を記録していく(TODO: 初期値検討)
  vector<vector<int>> vec_map(map_height, vector<int>(map_width, INF));

  // mapを取得 string=char[]なのでcharの2次元配列と同じ意味
  vector<string> str_map(map_height);
  for(int i=0; i < map_height; i++){
    cin >> str_map[i];
  }

  vec_map[sx][sy] = 0;
  // sp = starting point 次に調べる起点座標
  queue<pair<int,int>> sp_que;
  sp_que.push(make_pair(sx,sy));

  vector<int> direction_x = {1,-1,0,0};
  vector<int> direction_y = {0,0,1,-1};
  int move_count = 0;
  while(!sp_que.empty()){
    pair<int,int> p = sp_que.front();
    int x = p.first, y = p.second;
    sp_que.pop();
    move_count = vec_map[x][y] + 1;

    // 動ける範囲は上下左右の４方向
    for(int i = 0; i < 4; i++){
      int try_x = x,try_y = y;
      for(int m = 1; m <= amount_of_movement; m++){
        try_x += direction_x[i];
        try_y += direction_y[i];

        // マップ外に出ようとしたら打ち切り
        if(try_x < 0 || try_x >= map_height || try_y < 0 || try_y >= map_width) break;

        // 通行止めなら打ち切り
        if(str_map[try_x][try_y]=='@') break;

        // 遠回りしていることがわかったら打ち切り
        if(vec_map[try_x][try_y] < move_count) break;
        if(vec_map[try_x][try_y] == move_count) continue;

        vec_map[try_x][try_y] = move_count;
        sp_que.push(make_pair(try_x, try_y));
      }
    }
  }

  int result = vec_map[gx][gy];
  if(result == INF) result = -1;
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 11092
using System;
class aoj{
	static void Main(){
		int a=int.Parse(Console.ReadLine());
		int h,m,s;
		s=a%60;
		m=(a-s)/60;
		m=m%60;
		h=(((a-s)/60)-m)/60;
		Console.WriteLine("{0}:{1}:{2}",h,m,s);
	}
}

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

int main()
{
  int N,K,x;
  cin >> N >> K;
  int L=0;
  for(int i=0;i<N;i++){
    cin >> x;
    L += 2*min(x,K-x);
  }
    cout << L <<endl;
}

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

#define ASC(vec) vec.begin(), vec.end()    // 昇順ソート 例：sort(ASC(vec));
#define DESC(vec) vec.rbegin(), vec.rend() // 降順ソート 例：sort(DESC(vec));
#define rep(i, n) for (int i = 0; i < (n); i++)
#define Rep(i, n) for (int i = 1; i < n; i++)
#define REP(i, vec) for (auto i = vec.begin(); i != vec.end(); ++i)

const int       mod = 1000000007;
const int       inf = (1 << 21);
const long long INF = 1LL << 60;

using ii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
using vd = vector<double>;
using vb = vector<bool>;
using vl = vector<ll>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvb = vector<vector<bool>>;
using vii = vector<pair<int, int>>;
using vll = vector<pair<ll, ll>>;

template<class T>
inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T>
inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T>
inline T GCD(T a, T b) { return b ? GCD(b, a % b) : a; }
template<class T>
inline T LCM(T a, T b) { return (a + (b - 1)) / b; }
template<class T>
inline T round_int(T a, T b) {return (a + (b - 1)) / b; }

constexpr array<int, 9> dx = { 0, 1, 0, -1, -1, 1, 1, -1, 0 };
constexpr array<int, 9> dy = { 1, 0, -1, 0, 1, 1, -1, -1, 0 };

// ──────────────────────────────────────────────────────────────────

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	swap(a, b);
	swap(a, c);
	cout << a << " " << b << " " << c << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

namespace ABC138
{
    class E
    {
        static void Main(string[] args)
        {
            string s = Console.ReadLine();
            string t = Console.ReadLine();

            Dictionary<char, List<long>> dict = new Dictionary<char, List<long>>();

            for (int i = 0; i < s.Length; i++)
            {
                if (!dict.ContainsKey(s[i]))
                {
                    dict.Add(s[i], new List<long>());
                    dict[s[i]].Add(i);
                }
                else if (dict.ContainsKey(s[i]))
                {
                    dict[s[i]].Add(i);
                }
            }

            // NGの時
            for (int i = 0; i < t.Length; i++)
            {
                if (!dict.ContainsKey(t[i])) { Console.WriteLine(-1); return; }
            }

            //<--debug
            //for (long i = 0; i < t.Length; i++)
            //{
            //    Console.WriteLine(string.Join(" ", dict[t[i]]));
            //}
            //debug-->

            //long count = 0;
            long current = -1;
            int index = 0;
            long turn = 0;

            foreach (var c in t)
            {
                var list = dict[c];

                index = list.BinarySearch(current + 1);
                if (index < 0) { index = ~index; }
                if (list.Count <= index) { index = 0; turn++; }

                current = list[index];

                /*
                if (list[index] < current)
                {
                    count += (long)s.Length - (current + 1) + list[index] + 1;
                    current = list[index];
                }
                else
                {

                    count += list[index] - current;
                    current = list[index];
                }
                 */
                //Console.WriteLine("count : " + count);
            }

            Console.WriteLine((long)s.Length * turn + current + 1);
        }
    }
}


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

struct dat{
  int r, w;
  bool operator<(const dat &R)const{
    if(r!=R.r) return r>R.r;
    return w<R.w;
  }
};

int n, dp[1005];
dat rw[1005];

int main(){
  
  while(cin>>n, n){

    int sum=0, sum2=0;
      
    for(int i=0;i<n;i++){
      cin>>rw[i].r>>rw[i].w;
      sum+=rw[i].r;
      sum2+=rw[i].w;
    }
    
    sort(rw,rw+n);

    if(rw[0].r*2<=sum){
      cout<<sum+sum2<<endl;
      continue;
    }
    
    int space=rw[0].r*2-sum;
    
    int ans=sum2;
    
    memset(dp,0,sizeof(dp));
    
    dp[0]=1;
      
    for(int i=1;i<n;i++){
      
      for(int j=space;j>=0;j--){
	if(!dp[j]) continue;
	if(j+rw[i].w<=space) dp[j+rw[i].w]=1;
      }
    }
    
    int maxs=0;
    
    for(int i=0;i<=space;i++)
      if(dp[i]) maxs=max(maxs,i);

    cout<<rw[0].r*2+(ans-maxs)<<endl;
    
  }
  
  return 0;
}

Measured memory_bytes: 3164
#include <algorithm>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
// const int INF = (1 << 30) - 1;
// const ll LL_INF = (1LL << 62) - 1;
// const ll MOD = 1e9 + 7;

int A, B;

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

  if (B == 1) {
    cout << 0 << endl;
    return 0;
  }

  int ans = 1;
  int num = A;
  while (num < B) {
    ans++;
    num += (A - 1);
  }

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

Measured memory_bytes: 384
import java.util.*;
class Main
{
    public static void main (String[] args)
    {
        Scanner sc = new Scanner(System.in);
        String s = sc.next(), t = sc.next();
        int s_len = s.length();
        int t_len = t.length();
        String ans = "";
        int k = -1;
        for(int i = s_len - t_len; i >= 0; i--){
            boolean flag = true;
            for(int j = 0; j < t_len; j++)
                if(s.charAt(i+j) != t.charAt(j) && s.charAt(i+j) != '?'){
                    flag = false;
                    break;
                }
            if(flag){
                k = i;
                break;
            }
        }
        if(k < 0) System.out.println("UNRESTORABLE");
        else{
            for(int i = 0; i < k; i++){
                if(s.charAt(i) != '?')
                    ans += s.charAt(i);
                else ans += 'a';
            }
            for(int i = k; i < k + t_len; i++)
                ans += t.charAt(i - k);
            for(int i = k + t_len; i < s_len; i++)
                 if(s.charAt(i) != '?')
                    ans += s.charAt(i);
                 else ans += 'a';
            System.out.println(ans);
        }
    }
}

Measured memory_bytes: 22868
# pythonはindexでstringの文字を変更できない
s = list(input())
t = list(input())
x = 0
ans = []
gotk = False

# pythonて関数にするとスコープの外の変数参照できないんだっけ？

# 0 <= k <= s - t
def match(k):
  for i in range(len(t)):
    if s[i + k] != t[i] and s[i + k] != "?":
      return False
  return True

def construct(k,s):
  for i in range(len(t)):
    s[i + k] = t[i]
  for i in range(len(s)):
    if s[i] == "?":
      s[i] = "a"
  return s

# 大きいkから探せば良い(今回逆順にしてるためrangeの第二引数が直前まで処理されることに注意！)
for i in range(len(s) - len(t),-1,-1):
  if match(i):
    x = i
    gotk = True
    break

if gotk == True:
  ans = construct(x,s)
  print("".join(ans))
else:
  print("UNRESTORABLE")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define TEST int t = 1; while(t--) solve()

void solve(){
    
    string s;
    cin>>s;
    string t;
    cin>>t;
    t.pop_back();
    if(t==s)
    {
    	cout<<"Yes";
    }
    else
    {
    	 cout<<"No";
    }
}

signed main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); TEST; return 0;
}

Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define MOD 2019
#define M(x) ((x+MOD)%MOD)
#define MAX 2010

int main()
{
	ll L, R;
	cin >> L >> R;
	ll ans = inf;
	if (R - L >= 2018)
		ans = 0;
	else
		for (ll i = L;i <= R;++i)
			for (ll j = i + 1;j <= R;++j)
				ans = min(ans, M(i * j));
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1001001001;
const ll LINF = 1001001001001001;
const int MOD = 1000000007;

template <typename T>
void print(const T &v);

int main()
{
    int n;
    cin >> n;
    int ans = 1000 - (n % 1000);
    if (ans == 1000)
    {
        ans = 0;
    }
    cout << ans << endl;
    return 0;
}

// Use For Debug
template <typename T>
void print(T const &v)
{
    for (int i = 0; i < v.size(); i++)
    {
        if (i)
            cout << ' ';
        cout << v[i];
    }
    cout << endl;
}

Measured memory_bytes: 3588
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        scan.close();
        System.out.print(n +":");
        for(int i = 2; i * i <= n; i++) {
            if(n % i == 0) {
                while(n % i == 0) {
                    System.out.print(" " + i);
                    n = n / i;
                }
            }
        }
        if(n != 1) {
            System.out.print(" " + n);
        }
        System.out.println();
    }
}


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

#define MorsheD ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
typedef long long ll;

int main() {
	// ===================
	MorsheD;
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	// ===================

	ll x, k, d;
	cin >> x >> k >> d;

	x = abs(x);
	ll t = k;

	k -= min(k, (x / d));
	x -= min(t, x / d) * d;

	if (k % 2) {
		x -= d;
	}

	cout << abs(x) << '\n';

	return 0;
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
inline void normal(ll &a)
{
    a %= MOD;
    (a < 0) && (a += MOD);
}
inline ll modMul(ll a, ll b)
{
    a %= MOD, b %= MOD;
    normal(a), normal(b);
    return (a*b)%MOD;
}
inline ll modAdd(ll a, ll b)
{
    a %= MOD, b %= MOD;
    normal(a), normal(b);
    return (a+b)%MOD;
}
inline ll modSub(ll a, ll b)
{
    a %= MOD, b %= MOD;
    normal(a), normal(b);
    a -= b;
    normal(a);
    return a;
}
inline ll modPow(ll b, ll p)
{
    ll r = 1;
    while(p)
    {
        if(p&1)
            r = modMul(r, b);
        b = modMul(b, b);
        p >>= 1;
    }
    return r;
}

inline ll modInverse(ll a)
{
    return modPow(a, MOD-2);
}
inline ll modDiv(ll a, ll b)
{
    return modMul(a, modInverse(b));
}

map<int,int>cnt;



main()
{

    ll n,k,ans;
    cin>>n>>k;
    cnt[k]=1;
    ans=k;
    for(int i=k-1; i>=1; --i)
    {
        int rp=k/i;
        cnt[i]=modPow(rp,n);
        for(int j=i+i; j<=k; j+=i)
        {
            cnt[i]=cnt[i]+MOD-cnt[j];
            if(cnt[i]>=MOD)
                cnt[i] -= MOD;
        }
        ans += 1LL * cnt[i] * i;
        ans %= MOD;
    }

    cout<<ans<<endl;


}


Measured memory_bytes: 8336
#include<math.h>
#include<limits.h>
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<sstream>
#include<list>
#include<queue>
#include <algorithm>
#include<initializer_list>
#include<map>
#include<set>
using namespace std;
int main() {
	int n;
	cin >> n;
	vector<int>a(n, 0);
	for (int i = 0; i < n; i++)cin >> a[i];
	int m;
	cin >> m;
	vector<int>b(m, 0);
	for (int i = 0; i < m; i++)cin >> b[i];
	map<int, int> d, t;
	for (int i = 0; i < n; i++)d[a[i]]++;
	for (int i = 0; i < m; i++)t[b[i]]++;
	
	for (int i = 0; i < m; i++) {
		if (t[b[i]] > d[b[i]]) {
			cout << "NO";
			return 0;
		}
	}
	cout << "YES";
	return 0;
}





Measured memory_bytes: 20608
#include <iostream>
#include <stdio.h>
using namespace std;
int main() {
int h,v,i,l,r,a[31];
char c;
for (i=0;i<31;i++) a[i]=i;
cin >> h >> v;
for (i=0;i<v;i++) {
	scanf("%d%c%d",&l,&c,&r);
	swap(a[l],a[r]);
}
for (i=1;i<=h;i++) cout << a[i] << endl;
return 0;
}

Measured memory_bytes: 1240
def func(o, e):
  pwd = ""
  if len(o) == len(e):
    for i in range(len(o)):
      pwd += o[i] + e[i]
  else:
    for i in range(len(e)):
      pwd += o[i] + e[i]
    pwd += o[len(o)-1]
  print(pwd)

o = input()
e = input()

func(o, e)

Measured memory_bytes: 3060
/*
[abc105] D - Candy Distribution
*/

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

const int MAX_N = 100000;

int N, M;
int a[MAX_N];

ll solve() {
    map<int, int> cnt;
    int s = 0;
    cnt[0]++;
    for (int i = 0; i < N; i++) {
        (s += a[i]) %= M;
        cnt[s]++;
    }

    ll ans = 0;
    for (auto &kv : cnt) {
        ll v = kv.second;
        ans += v * (v - 1) / 2;
    }

    return ans;
}

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

    cout << solve() << endl;

    return 0;
}


Measured memory_bytes: 3584
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iterator>
#pragma warning(disable:4996)
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223372036854775807
#define INF 2147483647
#define MOD 1000000007
using namespace std;

struct Edge {
    long from;
    long to;
    long cost;
};

int main(int argc, char* argv[])
{
    char str0[12]={0};
    char str1[12]={0};
    char str2[12]={0};
    scanf("%s", str0);
    scanf("%s", str1);
    scanf("%s", str2);

    if(str0[strlen(str0)-1]==str1[0] &&
       str1[strlen(str1)-1]==str2[0] ) {
        printf("YES\n");
    }
    else {
        printf("NO\n");
    }

    return 0;
}


Measured memory_bytes: 128
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
	n = readline() |> parseInt
	a = readline() |> split |> parseMap |> sort
	k = a[n]
	d = Dict{Int,Int}()
	for i in 1:n
		if haskey(d,a[i])
			d[a[i]] += 1
		else
			d[a[i]] = 1
		end
	end
	lf = 0
	if a[n-1]!=a[n]
		lf = 1
	end
	l = Int[]
	if k%2==0
		push!(l,k>>1)
		for i in k>>1+1:k
			push!(l,i)
			push!(l,i)
		end
	else
		for i in (k+1)>>1:k
			push!(l,i)
			push!(l,i)
		end
	end
	m = length(l)
	if m>n
		lf = 1
	end
	for i in 1:m
		if !haskey(d,l[i])
			lf = 1
		else
			if d[l[i]]==0
				lf = 1
			else
				d[l[i]] -= 1
			end
		end
	end
	mx = n
	for i in keys(d)
		if d[i]>0
			mx = min(mx,i)
		end
	end
	if mx<=(k+1)>>1
		lf = 1
	end
	println(lf==0?"Possible":"Impossible")
end

main()

Measured memory_bytes: 116136
#include <iostream>
#include <set>
#include <map>
#include <array>
#include <cassert>
#include <queue>
#include <cstring>
#include <vector>
#include <list>
#include <algorithm>

#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

#define all(v) (v).begin(), (v).end()
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define mp make_pair

template <typename T>
bool uax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template <typename T>
bool uin(T& a, T b) { if (b < a) { a = b; return true; } return false; }

using namespace std;

typedef pair<int, int> pii;
typedef vector<pii> vpi;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef list<int> li;
typedef vector<li> vli;
typedef vector<vpi> vvpi;
typedef long long i64;

const int inf = 1e9;

void solve_c() {
  int n;
  cin >> n;
  vi ra(n), rb(n);
  forn(i, n*2) {
    char c; cin >> c;
    int x; cin >> x;
    --x;
    (c == 'W' ? ra : rb)[x] = i;
  }
  vvi d(n + 1, vi(n + 1, inf));
  vvi p(n + 1, vi(n + 1, 0));
  d[0][0] = 0;
  vvi da(n + 1, vi(2 * n + 1, 0));
  vvi db(n + 1, vi(2 * n + 1, 0));
  forn(i, n) {
    forn(j, 2 * n + 1) {
      da[i + 1][j] = da[i][j] + (ra[i] > j ? 1 : 0);
      db[i + 1][j] = db[i][j] + (rb[i] > j ? 1 : 0);
    }
  }
  auto cost = [&] (vi& a, vi& b, vvi& da, vvi& db, int i, int j) {
    return da[i][a[i]] + db[j][a[i]];
    int s = 0;
    forn(t, j) if (b[t] > a[i]) s += 1;
    forn(t, i) if (a[t] > a[i]) s += 1;
    assert(s == da[i][a[i]] + db[j][a[i]]);
    return s;
  };
  forn(i, n + 1) {
    forn(j, n + 1) {
      if (d[i][j] == inf) continue;
      if (i + 1 <= n) uin(d[i + 1][j], d[i][j] + cost(ra, rb, da, db, i, j));
      if (j + 1 <= n) if (uin(d[i][j + 1], d[i][j] + cost(rb, ra, db, da, j, i))) p[i][j+1] = 1;
    }
  }
  if (0) {
    int i = n, j = n;
    while (i+j) {
      if (j && p[i][j]) { cout << '1'; --j; }
      else { cout << '0'; --i; }
    }
    cout << endl;
  }
  int ans = d[n][n];
  cout << ans << endl;
}

void solve_b() {
  int n, m;
  cin >> n >> m;
  vi p(n);
  forn(i, n) { cin >> p[i]; --p[i]; }
  vvi g(n);
  forn(i, m) {
    int v, u; cin >> v >> u;
    --v; --u;
    g[v].pb(u); g[u].pb(v);
  }
  int ans = 0;
  vi used(n, 0);
  queue<int> Q; vi comp;
  forn(i, n) if (!used[i]) {
    Q.push(i); used[i] = 1; comp.pb(i);
    while (!Q.empty()){ 
      int v = Q.front(); Q.pop();
      for(int u: g[v]) if (!used[u]) {
        used[u] = 1; Q.push(u); comp.pb(u);
      }
    }
    sort(all(comp));
    for (int j: comp) ans += binary_search(all(comp), p[j]);
    comp.clear();
  }
  cout << ans << endl;
}

void solve_a() {
  string s;
  cin >> s;
  int k;
  cin >> k;
  vector<string> vs;
  fore(j, 1, k) forn(i, s.length() - j + 1) {
    vs.pb(s.substr(i, j));
  }
  sort(all(vs));
  vs.erase(unique(all(vs)), vs.end());
  cout << vs[k - 1] << endl;
}

int main() {
#ifdef HOME
  freopen("input.txt", "rt", stdin);
#endif
  solve_c();
  return 0;
}


Measured memory_bytes: 94336
p = int(input().split()[1])
a = list(map(int, input()))
if 10 % p == 0:
  r = sum(i for i, x in enumerate(a, 1) if x % p == 0)
else:
  d = [1] + [0] * (p - 1)
  s, y = 0, 1
  for x in reversed(a):
    s = (s + x * y) % p
    d[s] += 1
    y = y * 10 % p;
  r = sum(i * (i - 1) // 2 for i in d)
print(r)

Measured memory_bytes: 5096