akhauriyash/Code-Regression huggingface dataset:
n, m = map(int, input().split())
plist = list(map(int, input().split()))

ufp = [i for i in range(n)]
ufs = [1 for _ in range(n)]

def root(i):
  pi = i
  while ufp[pi] != pi:
    pi = ufp[pi]
    ufp[pi] = root(pi)
  return pi

def union(i, j):
  pi, pj = root(i), root(j)
  if pi == pj:
    return
  if ufs[pi] < ufs[pj]:
    ufp[pi] = pj
  elif ufs[pj] < ufs[pi]:
    ufp[pj] = pi
  else:
    if pi < pj:
      ufp[pj] = pi
      ufs[pi] += 1
    else:
      ufp[pi] = pj
      ufs[pj] += 1

for _ in range(m):
  x, y = map(int, input().split())
  union(x-1, y-1)

ans = 0
for i, p in enumerate(plist):
  if root(i) == root(p-1):
    ans += 1

print(ans)


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

int main()
{
	int n;
	std::cin>>n;
	if (n < 100) {
		//std::cout << "error";
		return -1;
	}
	else if (n>999) {
		return -1;
	}
	int x = ((n-1) / 111);
	x = x * 111 + 111;
	std::cout << std::to_string(x);
	//std::cout << "Hello World!\n"; 
}

Measured memory_bytes: 256
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
#define pb push_back
#define __V vector
#define all(x) x.begin(), x.end()
#define oit ostream_iterator
#define mod 1000000007ll
using namespace std;
void doin() {
	cin.tie();
	cout.tie();
	ios::sync_with_stdio(0);
#ifndef ONLINE_JUDGE
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
}
template<typename X, typename Y>
istream& operator>>(istream& in, pair<X, Y> &a) {
	in >> a.first >> a.second;
	return in;
}
template<typename T>
void getv(T& i) {
	cin >> i;
}
template<typename T, typename ... Ns>
void getv(vector<T>& v, int n, Ns ... ns) {
	v.resize(n);
	for (auto& i : v)
		getv(i, ns...);
}
template<typename T>
void getv1(T& i) {
	cin >> i;
}
template<typename T, typename ... Ns>
void getv1(vector<T>& v, int n, Ns ... ns) {
	v.resize(n + 1);
	for (int i = 1; i <= n; i++)
		getv(v[i], ns...);
}
#ifdef _WIN32
#define getchar_unlocked() _getchar_nolock()
#define _CRT_DISABLE_PERFCRIT_LOCKS
#endif
inline void getch(char &x) {
	while (x = getchar_unlocked(), x < 33) {
		;
	}
}
inline void getstr(string &str) {
	str.clear();
	char cur;
	while (cur = getchar_unlocked(), cur < 33) {
		;
	}
	while (cur > 32) {
		str += cur;
		cur = getchar_unlocked();
	}
}
template<typename T> inline bool sc(T &num) {
	bool neg = 0;
	int c;
	num = 0;
	while (c = getchar_unlocked(), c < 33) {
		if (c == EOF)
			return false;
	}
	if (c == '-') {
		neg = 1;
		c = getchar_unlocked();
	}
	for (; c > 47; c = getchar_unlocked())
		num = num * 10 + c - 48;
	if (neg)
		num *= -1;
	return true;
}
typedef unsigned long long ull;
typedef long long ll;
typedef float ld;
typedef ll _I;
typedef pair<_I, _I> pi;
typedef pair<ld, ld> pd;
typedef map<_I, _I> mii;
typedef __V <_I> vi;
typedef __V <char> vc;
typedef __V <ld> vd;
typedef __V <vd> vvd;
typedef __V <pi> vpi;
typedef __V <__V<_I>> vvi;
typedef __V <__V<char>> vvc;
typedef __V <__V<pi>> vvpi;
using AntonTsypko = void;
using arsijo = AntonTsypko;
using god = arsijo;
uniform_real_distribution<double> double_dist(0, 1);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int main() {
	doin();
	ll n, pm, c;
	vi v;
	cin >> n;
	getv(v, n);
	vi d(all(v));
	sort(all(v), greater<int>());
	for(auto i : d) {
		if(i == v[0])
			cout << v[1] << "\n";
		else
			cout << v[0] << "\n";
	}
	return 0;
}


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

using namespace std;

/*  テンプレここから */
typedef long long ll;

#define rep(i, n) for(int i = 0; i < n; ++i)
#define repi(i, start, end) for(int i = start; i < end; ++i)
#define all(x) (x).begin(), (x).end()
#define INF (1e9)
#define add_mod(a, b, x) ( (ll)(a) + (ll)(b) ) % (ll)(x)
#define mul_mod(a, b, x) ( ((ll)(a) % (ll)(x)) * ((ll)(b) % (ll)(x)) ) % (ll)(x)
#define out(x) cout << (x) << endl;
#define outyes(bool_val) cout << (bool_val ? "yes" : "no") << endl;
#define outYes(bool_val) cout << (bool_val ? "Yes" : "No") << endl;
#define outYES(bool_val) cout << (bool_val ? "YES" : "NO") << endl;
#define outPossible(bool_val) cout << (bool_val ? "Possible" : "Impossible") << endl;
#define outPOSSIBLE(bool_val) cout << (bool_val ? "POSSIBLE" : "IMPOSSIBLE") << endl;

ll sub_mod(ll a, ll b, ll x){
    ll tmp = (a - b) % x;
    if(tmp < 0) tmp += x;
    return tmp;
}
ll gcd(ll a, ll b){
    if(b == 0) return a;
    else return gcd(b, a % b);
}

int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
/*  テンプレここまで */

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

    string s, t;
    cin >> s >> t;

    char s2t[30] = {0};
    char t2s[30] = {0};

    bool flag = true;
    rep(i, s.size()){
        if(s2t[s[i] - 'a'] == 0) s2t[s[i] - 'a'] = t[i];
        if(t2s[t[i] - 'a'] == 0) t2s[t[i] - 'a'] = s[i];

        flag = (s2t[s[i] - 'a'] == t[i] && t2s[t[i] - 'a'] == s[i]) && flag;
    }

    outYes(flag);
}

Measured memory_bytes: 916
import java.util.Scanner;

public class Main {
    private static final int MOD = 1_000_000_007;
    private static final String YES = "Yes";
    private static final String NO = "No";

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

        int x1 = sc.nextInt();
        int x2 = sc.nextInt();
        int x3 = sc.nextInt();
        int x4 = sc.nextInt();
        int x5 = sc.nextInt();

        System.out.println(solve(x1, x2, x3, x4, x5));
    }

    private static int solve(int x1, int x2, int x3, int x4, int x5) {
        if (x1 == 0) return 1;
        if (x2 == 0) return 2;
        if (x3 == 0) return 3;
        if (x4 == 0) return 4;

        return 5;
    }
}

Measured memory_bytes: 35744
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<class T,class U> inline bool chmin(T&x,U y){if(x>y){x=y;return true;}return false;}
template<class T,class U> inline bool chmax(T&x,U y){if(x<y){x=y;return true;}return false;}
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

void solve(){
    int h,w,a,b;
    cin>>h>>w;
    set<pair<int,int>> st;
    multiset<int> d;
    fr(i,w){
        st.emplace(i,i);
        d.emplace(0);
    }
    Fr(i,h){
        cin>>a>>b;--a;;
        auto it=st.lower_bound(make_pair(a,0));
        int l{-1};
        for(;it!=st.end()&&it->first<=b;){
            l=it->second;
            if(it->first==w) d.erase(INT_MAX);
            else d.erase(d.find(it->first-it->second));
            it=st.erase(it);
        }
        if(l>=0){
            st.emplace(b,l);
            d.emplace(b==w?INT_MAX:b-l);
        }
        cout<<(*d.begin()==INT_MAX?-1:*d.begin()+i)<<'\n';
    }
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    solve();
}

Measured memory_bytes: 22296
#python3
from math import factorial
MOD = int(1e9)+7
def combination(n, k, md):
    c = 1
    for i in range(k):
        c *= (n-i)
        c %= MOD
    p = factorial(k)%MOD
    p = pow(p, md-2, md)
    return (c*p)%md 
def main():
    N, K = map(int, input().split())
    for i in range(1,K+1):
        ans = combination(K-1, i-1, MOD) * combination(N-K+1, i, MOD) % MOD
        print(ans)


main()


Measured memory_bytes: 3316
while True:
    a, op, b = map(str, input().split())
    if op == '?':
        break
    elif op == '+':
        print(int(a) + int(b))
    elif op == '-':
        print(int(a) - int(b))
    elif op == '*':
        print(int(a) * int(b))
    else:
        print('%d' %(int(a) // int(b)))


Measured memory_bytes: 5600
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
long long p[10001][101]={0},v[101][2];
int main(){
int i,j,n,w,l;
cin>>n>>w;
for(i=1;i<=n;i++)cin>>v[i][0]>>v[i][1];
for(i=1;i<=n;i++){
	for(j=1;j<=w;j++){
		if(j==v[i][1]){
			p[j][i]=v[i][0];
			for(l=0;l<=w-j;l++){
				if(w>=j+l)p[j+l][i]=max(p[j+l][i],p[j][i]+p[l][i-1]);
			}
			
		}
		p[j][i]=max(p[j][i],p[j][i-1]);
		p[j][i]=max(p[j][i],p[j-1][i]);
	}
}
cout<<p[w][n]<<endl;
return 0;
}

Measured memory_bytes: 10960
#include<iostream>
#include<vector>
#include<string>
#include<math.h>
using namespace std;
#define rep(i, n) for (int i=0; i<(int) (n);i++)
using ll = long long;
using P = pair<int,int>;

void solve_8(){//7m
    string a, b;
    cin >> a >> b;
    string tmp =  a+b;
    int c = atoi(tmp.c_str());
    //cout << c << endl;
    int c_square = sqrt(c);
    cout << (c_square * c_square == c? "Yes": "No") << endl;
    
}

void solve_8re(){
    string a, b;
    cin >> a >> b;
    //stoi -> int
    //stol -> long
    //stof -> float
    int c = stoi(a+b);
    int c_square = sqrt(c);
    cout << (c_square * c_square == c? "Yes": "No")<< endl;
}

void solve_9(){
    int n,k;
    cin >> n >> k;
    int sum_distance = 0;
    rep(i, n){
        int x;
        cin >> x;
        sum_distance += 2 * min(x, k-x);
    }
    cout << sum_distance;

    
}

void solve_C(){
    
}

void solve_D(){
    
}

void solve_E(){
    
}

void solve_F(){
    
}

int main(){
    //solve_8re();
    solve_9();
    //solve_C();
    //solve_D();
    //solve_E();
    //solve_F();
    return 0;
}

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

int n;

int main(){
	scanf("%d", &n);
	int cnt = 0;
	for (int i = 0, x; i < n; ++ i){
		scanf("%d", &x);
		if (x & 1){
			++ cnt;
		}
	}
	return printf((cnt & 1) ? "NO\n" : "YES\n"), 0;
}

Measured memory_bytes: 764
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }
    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int N = scan.nextInt();
        long[] l = new long[N+1];
        l[0] = 2;
        l[1] = 1;
        for (int i = 2; i <= N; i++) {
            l[i] = l[i-1] + l[i-2];
        }
        System.out.println(l[N]);
    }
}


Measured memory_bytes: 23764
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define LL long long
#define Fi first
#define Se second
using namespace std;
static const LL INF = 1LL<<61LL;
typedef pair<int,int> PII;

int N;
int V[30];
int ans;
string s;
string temp;
int main(){
    cin>>N;
    cin>>s;
    rep(i,N){
        if(s[i]!='+')temp+=s[i];
    }
    sort(temp.begin(),temp.end());
    int t=0;
    rep(i,temp.size()){
        if(temp[i]==temp[i+1])V[t]++;
        else t++;
    }
    sort(V,V+t);
    int cnt=1;
    rep(i,t){
        //cout<<V[i]<<endl;
        if(V[i]!=0&&V[i]==V[i+1]){
            cnt++;
            continue;
        }
        if(cnt>1)ans+=cnt+cnt-1+4;
        else {
            if(V[i]>=1)ans+=3;
            else ans+=1;
        }
        if(i!=t-1)ans++;
        cnt=1;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1232
#include<stdio.h>
#include<string.h>
int check(char *p1,char *p2)			//p1是input,p2是测试数组 
{
	int len=strlen(p1),i;
	for(i=0;i<len;i++)
	{
		if(p1[i]!='?')
		{
			if(p1[i]!=p2[i])return 0;
		}
	}
	return 1;
}
void print(char *p)
{
	int len=strlen(p),i;
	for(i=0;i<len;i++)
	{
		if(p[i]=='?')
		{
			printf("a");
		}
		else
		{
			printf("%c",p[i]);
		}
	}
	printf("\n");
}
int main()
{
	int i,j,k;
	char input[51];
	char insert[51];
	char temp[51];						//接受测试数组 
	while(scanf("%s",input)!=-1)
	{
		scanf("%s",insert);
		int len1=strlen(input);
		int len2=strlen(insert);
		int count=0;
		
		for(i=len1-len2;i>=0;i--)
		{
			strcpy(temp,input);				//保护input不被破坏 
			strcpy(&temp[i],insert);
			temp[i+len2]=input[i+len2];	//把'\0'弄掉 
			if(check(input,temp))
			{
				count++;
				print(temp);
				break;
			}
		}
		if(count==0)printf("UNRESTORABLE\n");
	}
 } 

Measured memory_bytes: 256
#include<iostream>
using namespace std;
#define MAX 500000
#define SENTINEL 2000000000

int L[MAX/2+2],R[MAX/2+2];
int cnt;

void merge(int A[], int n, int left, int mid, int right){
  int n1 = mid - left;
  int n2 = right - mid;
  for(int i = 0; i < n1; i++)L[i] = A[left + i];
  for(int i = 0; i < n2; i++)R[i] = A[mid + i];
  L[n1] = R[n2] = SENTINEL;
  int i =0, j = 0;
  for(int k = left; k < right; k++){
    cnt++;
    if(L[i] <= R[j]){
      A[k] = L[i++];
    } else {
      A[k] = R[j++];
    }
  }
}

void mergeSort(int A[], int n, int left, int right){
  if(left+1 < right){
    int mid = (left + right) / 2;
    mergeSort(A, n, left, mid);
    mergeSort(A, n, mid, right);
    merge(A, n, left, mid, right);
  }
}

int main(){
  int A[MAX], n, i;
  cnt = 0;

  cin >> n;
  for(i = 0; i < n; i++)cin >> A[i];

  mergeSort(A, n, 0, n);

  for(i = 0; i < n; i++){
    if(i)cout << " ";
    cout << A[i];
  }
  cout << endl;

  cout << cnt << endl;

  return 0;
}



Measured memory_bytes: 6904
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n;
struct node
{
    int l,r;
    bool operator<(const node&o)const
    {
        return l==o.l?r>o.r:l<o.l;
    }
}a[N];
int pre[N],bk[N];
priority_queue<int>ql;
priority_queue<int,vector<int>,greater<int> >qr;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r);
    sort(a+1,a+1+n);
    int l=0,r=1e9;
    for(int i=1;i<=n;i++)
    {
        l=max(l,a[i].l);
        r=min(r,a[i].r);
        pre[i]=max(0,r-l+1);
    }
    l=0,r=1e9;
    for(int i=n;i>=1;i--)
    {
        l=max(l,a[i].l);
        r=min(r,a[i].r);
        bk[i]=max(0,r-l+1);
    }
    int ans=0;
    for(int i=1;i<n;i++)
        ans=max(ans,pre[i]+bk[i+1]);
    for(int i=1;i<=n;i++) ql.push(a[i].l),qr.push(a[i].r);
    for(int i=1;i<=n;i++)
    {
        l=-1,r=-1;
        if(ql.top()==a[i].l) l=ql.top(),ql.pop();
        if(qr.top()==a[i].r) r=qr.top(),qr.pop();
        int t=max(0,qr.top()-ql.top()+1);
        ans=max(ans,a[i].r-a[i].l+1+t);
        if(l!=-1) ql.push(l);
        if(r!=-1) qr.push(r);
    }
    printf("%d\n",ans);
}


Measured memory_bytes: 2812
// This is my template for fast solving
 
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <utility>
#include <unordered_map>
#include <map>
#include <unordered_set>
#include <set>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <memory>
#include <initializer_list>
#include <iomanip>
#include <stack>
#include <bitset>
#include <cstdio>
// #include <complex>
// #include <random>
 
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using ld = long double;

// const ll INF = 1e18;
// const ld INF = 1e20;
const ll MOD = 998244353;
// const ld EPS = 1e-10;
// const ld PI = acos(-1);

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

template<typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first >>  p.second;
    return is;
}
 
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    bool first = true;
    for (const auto& x : v) {
        if (!first) {
            os << " ";
        }
        first = false;
        os << x;
    }
    return os;
}

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

template<typename T>
ostream& operator<<(ostream& os, const set<T>& s) {
    bool first = true;
    for (auto x : s) {
        if (!first) {
            os << " ";
        }
        first = false;
        os << x;
    }
    return os;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& os, const map<T1, T2>& m) {
    bool first = true;
    for (auto x : m) {
        if (!first) {
            os << "\n";
        }
        first = false;
        os << x;
    }
    return os;
}

int count(int a, int b, int x, int y) {
    int res = b - a;
    res = min(res, abs(x - a) + abs(b - y) + 1);
    return res;
}

void solve() {
    ll n, x, y;
    cin >> n >> x >> y;
    vector<int> ans(n + 1);
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            ++ans[count(i, j, x, y)];
        }
    }
    for (int i = 1; i < n; ++i) {
        cout << ans[i] << "\n";
    }
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    // int t; // CodeJam style
    // cin >> t;
    // for (int i = 1; i <= t; ++i) {
    //     cout << "Case #" << i << ": ";
    //     solve();
    // }
 
    // int q;
    // cin >> q;
    // while (q--) {
    //     solve();
    // }

    solve();
 
    return 0;
}

Measured memory_bytes: 256
//  RAKSHIT KADAM
//ALWAYS USE &IT FOR ITERATING USING AUTO ...
 #include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree< int ,  null_type ,  less<int> ,  rb_tree_tag ,  tree_order_statistics_node_update>
#warning !!!check the size of arrayss!!!

// NUMERIC DEFINITIONS :
    #define INF 2000000000000000005
    #define MOD  1000000007
    #define newMOD  998244353
    #define MAX 300006
    #define pi 3.1415926535897932384626433832795
 
 #define ll long long
 #define int long long
 #define P(gg) for(auto rax:gg){cout<<rax<<" ";}cout<<endl;
 #define Need_for_speed(activated) ios_base :: sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
 #define satisfy ll t; cin>> t; while(t--)
 #define inp(n) int n;cin >> n
 #define mp make_pair
 #define pb push_back
 #define endl "\n"
 #define x first
 #define y second
 #define fore(i,a,b) for(ll i=a;i<b;i++)
 #define forci(i,n) for(ll i=0;i<n;i++)
 #define vi vector<ll>
 #define Endl endl
 #define lb lower_bound
 #define ub upper_bound
#define pii pair<ll,ll>
 #define input freopen("input.txt", "r", stdin),freopen("output.txt", "w", stdout)
 #define time        cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
using namespace std;
//ll gcd(ll a, ll b){if (b == 0)return a;return gcd(b, a % b);}
//int power(int x, unsigned int y, unsigned int m){ if (y == 0) return 1;int p = power(x, y/2, m) % m;  p = (p * p) % m;                                                  return (y%2 == 0)? p : (x * p) % m;}
//ll modInverse(int a, int m){int g = gcd(a, m); { return power(a, m-2, m);}}

void solve()
{
    ll n;cin>>n;
    ll count=0;ll base=100;
    while(true)
    {
        base=base+base/100;count++;
        if(base>=n)
        {cout<<count<<endl;return;}
    }
    
}
signed main()
{
 
   
    Need_for_speed(activated);
//satisfy
//    {
//   solve();
//    }

 solve();
    return 0;
}


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

using namespace std;

int const N = 1234567;

int const MOD = 1000000007;

int mul(int a, int b) {
	return (int) ((long long) a * b % MOD);
}

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

struct edge {
	int from;
	int to;
	int w;
};

long long const INF = 1LL << 60;

long long d1[N], d2[N];
int w1[N], w2[N];

vector<edge> edges[N];
int n;

void dijkstra(long long *d, int *ways, int start) {
	set<pair<long long, int> > q;
	for (int i = 0; i < n; i++) d[i] = INF;
	d[start] = 0;
	ways[start] = 1;
	q.insert({d[start], start});
	while (!q.empty()) {
		auto e = *q.begin();
		q.erase(q.begin());
		int v = e.second;
		for (auto &e : edges[v]) {
			if (d[e.to] > d[e.from] + e.w) {
				q.erase({d[e.to], e.to});
				d[e.to] = d[e.from] + e.w;
				ways[e.to] = ways[e.from];
				q.insert({d[e.to], e.to});
			} else if (d[e.to] == d[e.from] + e.w) {
				add(ways[e.to], ways[e.from]);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	int m;
	cin >> n >> m;
	int s, t;
	cin >> s >> t;
	--s;
	--t;
	for (int i = 0; i < m; i++) {
		int v, u, w;
		cin >> v >> u >> w;
		--v;
		--u;
		edges[v].push_back({v, u, w});
		edges[u].push_back({u, v, w});
	}
	dijkstra(d1, w1, s);
	dijkstra(d2, w2, t);
	long long shortest = d1[t];
	int ans = mul(w1[t], w2[s]);
	assert(w1[t] == w2[s]);
	for (int i = 0; i < n; i++) {
		if (shortest == d1[i] + d2[i] && d1[i] == d2[i]) {
			int have = mul(w1[i], w2[i]);
			add(ans, MOD - mul(have, have));
		}
	}
	for (int v = 0; v < n; v++) {
		for (auto &e : edges[v]) {
			if (d1[v] * 2 < shortest && d2[e.to] * 2 < shortest && d1[v] + d2[e.to] + e.w == shortest) {
				int have = mul(w1[v], w2[e.to]);
				add(ans, MOD - mul(have, have));
			}
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 52660
#include<iostream> //cinなど
#include<string> //文字列
#include<algorithm> //sort など
#include<math.h> //paw(冪乗など)
#include<set> // 集合
#include<map> //写像
#include<stdio.h> //printf
#include<stack>

using namespace std;
int main(){
  int N,sum,C,K;
  cin>>N;
  sum = 800 * N;
  K = N / 15;
  C = 200 * K;
  cout<< sum - C <<endl;
return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long n, s=0;
  cin>>n;
  for(int i=1; i<=n; i++){
   // if(i%3!=0) cout<<i<<endl;
    if(i%15!=0 && i%3!=0 && i%5!=0)s+=i;
  }
  cout<<s;
}


Measured memory_bytes: 3568
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int i=1;
		do{
			int x=i;
			if(x%3 == 0){
				System.out.print(" "+i);
				continue;
			}
			while(true){
			if(x%10 == 3){
				System.out.print(" "+i);
				break;
			}	
			x /=10;
			if(x != 0) continue;
			else break;
		}
	}
		while(++i <= n);			
		System.out.println();
		sc.close();
	}
}

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

const int INF = 1000000000;
const int INI = 0;
int n, a[101010], b[101010], c[101010], dp[101010][3];

int main(){
  cin >> n;
  rep(i, n) cin >> a[i] >> b[i] >> c[i];
  rep(i, n) dp[i][0] = dp[i][1] = dp[i][2] = INI;
  dp[0][0] = a[0];
  dp[0][1] = b[0];
  dp[0][2] = c[0];
  
  for(int i = 0; i < n - 1; i++){
    //dp[i + 1][後] = max(遷移先, dp[i][前] + 後[i + 1])
    dp[i + 1][0] = max(dp[i + 1][0], dp[i][1] + a[i + 1]);
    dp[i + 1][0] = max(dp[i + 1][0], dp[i][2] + a[i + 1]);
    dp[i + 1][1] = max(dp[i + 1][1], dp[i][0] + b[i + 1]);
    dp[i + 1][1] = max(dp[i + 1][1], dp[i][2] + b[i + 1]);
    dp[i + 1][2] = max(dp[i + 1][2], dp[i][0] + c[i + 1]);
    dp[i + 1][2] = max(dp[i + 1][2], dp[i][1] + c[i + 1]);
  }
  //rep(i, n){cerr << dp[i][0] <<" "<< dp[i][1] <<" "<< dp[i][2] << endl;}
  
  int res = dp[n - 1][0];
  res = max(dp[n - 1][1], res);
  res = max(dp[n - 1][2], res);
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
#include<cmath>
#include<cstring>
#include<climits>
#define int long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
#define asc(a,n) sort(a,a+n);
#define dsc(a,n) sort(a,a+n,comp);
#define fo(i,x,y) for(int i=x;i<y;i++)
#define inarr(x) int n; cin>>n; int x[n]; fo(i,0,n){cin>>x[i];}
#define test int t; cin>>t; while(t--)
using namespace std;

int basic(){freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);return 0;}
bool comp(int a,int b){return a>b;}



int32_t main()
{ //basic(); 
  fast;
  int a,b,c,d;
  cin>>a>>b>>c>>d; int flag=0;
  while(a>0 and c>0)
  {
    if(flag==0){ c=c-b; if(c<=0){break;} flag=1;}
    if(flag==1){ a=a-d; if(a<=0){break;}flag=0;}
  }
  if(c<=0){cout<<"Yes";}
  else{cout<<"No";}
  
}





//

Measured memory_bytes: 3648
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
using namespace std;

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

	if (abs(a - c) <= d
		|| (abs(a - b) <= d && abs(b - c) <= d))
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}

	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

#include <limits.h>

using namespace std;

typedef long long ll;

template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

const int INF = INT_MAX / 2;

int main(void) {
    int K, N;
    cin >> K >> N;

    vector<int> as;
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        as.push_back(a);
    }
    as.push_back(as[0] + K);

    int ans = INF;
    for (int i = 0; i < (int) as.size() - 1; i++) {
        chmin(ans, K - (as[i + 1] - as[i]));
    }

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


Measured memory_bytes: 4300
N = int(input())
A = list(sorted(map(int, input().split())))
B = list(sorted(map(int, input().split())))
C = list(sorted(map(int, input().split())))

ret = 0
i, j, k = 0, 0, 0

while j < N:
    while i < N and A[i] < B[j]:
        i += 1
    while k < N and C[k] <= B[j]:
        k += 1

    ret += i * (N - k)
    j += 1

print(ret)


Measured memory_bytes: 24096
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int,int> p;
 
int main(){
    vector<p> v;
    int n,data,num;
     
    cin >> n;
    for(int i = 0 ; i < n ; i++){
      cin >> num >> data;
      v.push_back(p(-data,num));
    }
    stable_sort(v.begin(),v.end());
    cout << v[0].second << ' ' << (-1)*v[0].first << endl;

    return 0;
}

Measured memory_bytes: 1204
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#define INT long long
using namespace std;
INT n, m;

int main()
{
    cin>>n;
    INT t = n;
    while( t )
    {
        m*=10;

        m += t%10;
        t/=10;
    }
    if( m == n ) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 256
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

a, b = [0], [0]
for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N + 1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
            j -= 1
    ans = max(ans, i + j)
print(ans)

Measured memory_bytes: 47528
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <iterator>
#include <cmath>
#include <iomanip>
#include <functional>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
int main() {
	long long N, K;
	scanf("%ld%ld", &N, &K);
	N = N % K;
	N = min(N, abs(N - K));
	printf("%ld", N);
}

Measured memory_bytes: 3804
moji=list(input())
for i in range(len(moji)//2):
    if moji[i] != moji[-i-1]:
        print("No")
        exit()
mojia=[]
mojib=[]
count=0
for i in moji:
    if count < len(moji)//2:
        mojia.append(i)
    if count > len(moji)//2:
        mojib.append(i)
    count = count+1
for i in range(len(mojia)//2):
    if mojia[i] != mojia[-i-1]:
        print("No")
        exit()
for i in range(len(mojib)//2):
    if mojib[i] != mojib[-i-1]:
        print("No")
        exit()
print("Yes")


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

int main() {
	while(1){
     string s;
     cin>>s;
     if(s=="0")break;
     
     int a=0,b=0;
     for(int i=1;i<s.size();i++){
         if(s[i]=='A')a++;
         if(s[i]=='B')b++;
     }
    if(a>b)a++;
    else b++;
     cout<<a<<" "<<b<<endl;
	}
	return 0;
}

Measured memory_bytes: 1184
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define IFOR(i, m, n) for (ll i = n - 1; i >= m; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define FOREACH(x, a) for (auto&(x) : (a))
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) ll(x.size())

vector<ll> v;

vector<ll> calcRui(const vector<ll>& z) {
  ll n = SZ(z);
  vector<ll> l(n + 1, 0);
  REP(i, n) { l[i + 1] = l[i] + v[i]; }
  REP(i, n) { l[i + 1] -= z[i]; }
  return l;
}
vector<ll> calcMax(const vector<ll>& a) {
  ll n = SZ(a);
  vector<ll> l(n, 0);
  l[0] = a[0];
  FOR(i, 1, n) { l[i] = max(l[i - 1], a[i]); }
  return l;
}

int main() {
  ll n, c;
  cin >> n >> c;
  vector<ll> x(n);
  v = vector<ll>(n);
  REP(i, n) { cin >> x[i] >> v[i]; }
  vector<ll> l = calcRui(x);
  vector<ll> lm = calcMax(l);

  vector<ll> y(n);
  REP(i, n) { y[i] = c - x[i]; }
  reverse(ALL(y));
  reverse(ALL(v));
  vector<ll> r = calcRui(y);
  vector<ll> rm = calcMax(r);

  // REP(i, n + 1) { cout << rm[i] << " \n"[i == n]; }

  ll ans = max(lm[n], rm[n]);

  REP(i, n + 1) {
    ll j = n - i;
    ans = max(ans, l[i] - (i == 0 ? 0 : x[i - 1]) + rm[j]);
    ans = max(ans, r[i] - (i == 0 ? 0 : y[i - 1]) + lm[j]);
  }

  cout << ans << endl;
}

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

using namespace std;
using ll = long long;

//container util
#define SORT(c) sort((c).begin(),(c).end())
#define all(a) (a).begin(), (a).end()

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//print
#define pv(val) cerr << #val << '=' << (val) << endl

const int INF = 1e9;

int main(void){

	int X; cin >> X;

	int ans;
	if(X >= 400 and X < 600) ans = 8;
	if(X >= 600 and X < 800) ans = 7;
	if(X >= 800 and X < 1000) ans = 6;
	if(X >= 1000 and X < 1200) ans = 5;
	if(X >= 1200 and X < 1400) ans = 4;
	if(X >= 1400 and X < 1600) ans = 3;
	if(X >= 1600 and X < 1800) ans = 2;
	if(X >= 1800 and X < 2000) ans = 1;

	cout << ans << endl;

	return 0;

}


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

int main() {
    int n;
    int m;
    string l;
  
   cin >> n >> m >> l;
  
   //cout << n << endl;
   ///cout << m << endl;
   //cout << l << endl;
  
  int sum = n + m + 1;
  
  int flaga = 0;
  
for(int i = 0;i<sum;i++){
  
  int flag = 0;
  
  
  
  if(i<n){
    
  // cout << i << endl;
//    cout << n << endl;
      for(int j = 0;j<=9;j++){
        
         int aa =l[i]-'0';
        
     //   cout << aa << endl;
        
         if(aa==j){
           flag = 1;
         }
      }
    
    if(flag==0){
      cout << "No" << endl;
      flaga = 0;
      break;
    }
    
  }else if(i==n){
    
    if(l[i]!='-'){
      cout << "No" << endl;
      flaga = 0;
      flag = 0;
       break;
    }
    
  }else if(i>n){
    
  //   int aa =l[i]-'0';
    //    cout << l[i] << endl;
    //     cout << aa << endl;
    
     for(int j = 0;j<=9;j++){
        
         int aa =l[i]-'0';
        
       //  cout << aa << endl;
        
         if(aa==j){
           flag = 1;
         }
      }
    
    if(flag==0){
      cout << "No" << endl;
      flaga = 0;
      break;
    }
  }
     
flaga = flag;
}
  
  if(flaga == 1){
     cout << "Yes" << endl;
  }
  
  
  return 0;
}

Measured memory_bytes: 256
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int Max_N(105);
typedef long long int LL;

int N, Head[Max_N], Total, To[Max_N << 1], Next[Max_N << 1], Deg[Max_N], Max[Max_N], Ans1;
LL Cnt[Max_N], Sum[Max_N], Ans2;

inline void Add_Edge(int s, int t)
{
	++Total, To[Total] = t, Next[Total] = Head[s], Head[s] = Total;
}

void dfs(int u, int fa, int dep)
{
	Ans1 = max(Ans1, dep);
	for (int i = Head[u], v;i;i = Next[i])
		if ((v = To[i]) != fa)
			dfs(v, u, dep + 1);
}

void arrange(int u, int fa, int dep)
{
	Max[dep] = max(Max[dep], Deg[u]), ++Cnt[dep], Sum[dep] += Deg[u];
	for (int i = Head[u], v;i;i = Next[i])
		if ((v = To[i]) != fa)
			arrange(v, u, dep + 1);
}

void prepare()
{
	memset(Sum, 0, sizeof(Sum)), memset(Max, 0, sizeof(Max)), memset(Cnt, 0, sizeof(Cnt));
}

void work()
{
	if (Cnt[(Ans1 + 1) / 2 + 1])
		return;
	for (int i = 1;i <= (Ans1 + 1) / 2 - 1;++i)
	{
		LL t = Cnt[i] * Max[i] - Sum[i];
		Cnt[i + 1] += t, Sum[i + 1] += t;
	}
	Ans2 = min(Ans2, Cnt[(Ans1 + 1) / 2]);
}

int main()
{
	scanf("%d", &N);
	for (int i = 1, u, v;i != N;++i)
		scanf("%d%d", &u, &v), Add_Edge(u, v), Add_Edge(v, u), ++Deg[u], ++Deg[v];
	for (int S = 1;S <= N;++S)
		dfs(S, -1, 1);
	printf("%d ", (Ans1 + 1) / 2), Ans2 = 0X3F3F3F3F3F3F3F3FLL;
	for (int u = 1;u <= N;++u)
		for (int i = Head[u], v;i;i = Next[i])
			v = To[i], prepare(), arrange(u, v, 1), arrange(v, u, 1), work();
	for (int u = 1;u <= N;++u)
		prepare(), arrange(u, -1, 1), work();
	printf("%lld", Ans2);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	vector<int> a(n);
	for(int i=0;i<n;i++) cin>>a[i];
	int ans=1;
	int mode=0;
	for(int i=1;i<n;i++)
	{
		if(mode==0)
		{
			if(a[i]==a[i-1]) continue;
			if(a[i]>a[i-1])
				mode=1;
			else
				mode=-1;
		}
		else if(mode==1)
		{
			if(a[i]<a[i-1])
			{
				mode=0;
				ans++;
			}
		}
		else
		{
			if(a[i]>a[i-1])
			{
				mode=0;
				ans++;
			}
		}
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 3716
#include <bits/stdc++.h>
#define maxn (int)(1e5)
#define i64 long long
#define pii pair<i64,i64>
#define all(x) x.begin(),x.end()
#define LB(x,v) lower_bound(all(x), v) - x.begin()
#define fread() freopen("in.txt", "r", stdin);
using namespace std;
int h[maxn+2];

int solve(int n,int k){
    int ans =0;
    for(int i=0;i<n;i++) if(h[i] >=k) ans++;
    return ans;
}

int main() {
    /*BEFORE SUBMIT, CHECK
    sample i/o format
    statements for debugging are removed/comment out
    global values / stl containers are initialized/cleared for each test (if needed)
    all array size are sufficient
    loop variable or output value doesn't cross min/max limit of input
    // */
  
    
    int n,k;
    while(scanf("%d %d",&n, &k)==2){
        for(int i=0;i<n;i++) scanf("%d",&h[i]);
        printf("%d\n", solve(n,k));     
    }
    return 0;
}

Measured memory_bytes: 640
import sys

f_i = sys.stdin

n = int(f_i.readline())

adj = [[(int(cost), int(v_n)) for v_n, cost in zip(x.split()[2::2], x.split()[3::2])] for x in f_i]

import heapq

def dijkstra():
    PQ = [(0, 0)]
    isVisited = [False] * n
    distance = [999900001] * n

    distance[0] = 0
    
    while PQ:
        uc = heapq.heappop(PQ)
        u = uc[1]

        if uc[0] > distance[u]:
            continue

        isVisited[u] = True
        
        for vc in adj[u]:
            v = vc[1]
            if isVisited[v] == True:
                continue
            t_cost = distance[u] + vc[0]
            if t_cost < distance[v]:
                distance[v] = t_cost
                heapq.heappush(PQ, (t_cost, v))

    for v, d in enumerate(distance):
        print(v, d)


dijkstra()

Measured memory_bytes: 70656
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
using namespace std;
#define ll int64_t
const long MOD = 1e9 + 7;
const long LINF = 1e13;
const long LLINF = 1e18;


template <class T>
T Swap(T &r, T &l) {
    T tmp = r;
    l = r;
    r = tmp;
}


ll cal(int len, int H, int W)
{
  ll ret = LLINF;
  ll a1 = 1LL * len * H;
  ll a2 = 1LL * (W - len) * (H / 2), a3 = 1LL * (W - len) * (H - (H / 2));
  ret = min(ret, max({ a1, a2, a3 }) - min({ a1, a2, a3 }));
 
  a2 = 1LL * H * ((W - len) / 2);
  a3 = 1LL * H * (W - len - (W - len) / 2);
  return min(ret, max({ a1, a2, a3 }) - min({ a1, a2, a3 }));
}



int main() {
    long w, h;
    cin >> h >> w;

    // h,wは10^5

    long smax;
    long smin;

    long smallS = LINF;

    for (int k = 0; k < 2; ++k) {
        // if (k == 1)Swap<long>(h, w);
        if (k==1){
        long tmp =h;
        h = w;
        w = tmp;
        }


        for (long i = 1; i <= h /2; ++i) {       /* code */
            // iを１つ目の分岐点とする.
            long l = w / 2;
            long l2 = w - l;
            // long l2= w / 2 + w % 2;

            long s1, s2, s3;
            s1 = w * i;
            s2 = (h - i) * l;
            s3 = (h - i) * l2;

            // smax = max(s3, max(s1, s2));
            // smin = min(s3, min(s1, s2));
            // // long s = abs(smax - smin);
            smallS = min(smallS, max({s1,s2,s3} ) - min({s1,s2,s3}) );


            long m = (h - i);
            long m2 = m / 2;
            long m3 = m - m2;
            // s1 = w * i;
            s2 = m2 * w;
            s3 = m3 * w;


            smallS = min(smallS, max({s1,s2,s3} ) - min({s1,s2,s3}) );

            // smallS = min(smallS,(long)cal(i,w,h));
        }   

    }




    cout << smallS;


    return 0;
}

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

int main(void){
  const int inf=1<<30;
  typedef tuple<int,int,int>t3;
  int n,Q,i,cur=0,s,t,x,v;
  priority_queue<t3,vector<t3>,greater<t3>>q;
  scanf("%d %d",&n,&Q);vector<int> ans(Q,-1),ds(Q);
  multiset<int>ms;ms.insert(inf);
  for (i=0;i<n;i++){
    scanf("%d %d %d",&s,&t,&x);
    q.push(make_tuple(s-x,x,1));
    q.push(make_tuple(t-x,x,0));
  }

  for (i=0;i<Q;i++)scanf("%d",&ds[i]);

  while (!q.empty()){
    t3 e=q.top();q.pop();
    tie(t,x,s)=e, v=*ms.begin();v=v!=inf?v:-1;
    while(cur<Q&&ds[cur]<t)ans[cur++]=v;
    if(s)ms.insert(x);
    else ms.erase(ms.find(x));
  }

  for (i=0;i<Q;i++)printf("%d\n",ans[i]);
  return 0;
}


Measured memory_bytes: 18904
#include<iostream> 
#include<iomanip> 
#include<vector> 
#include<map> 
#include<set> 
#include<algorithm> 
#include<numeric> 
#include<limits> 
#include<bitset> 
#include<functional> 
#include<type_traits> 
#include<queue> 
#include<stack> 
#include<array> 
#include<random> 
#include<utility> 
#include<cstdlib> 
#include<ctime>
#define INT_MAX 2147483647
#define _LIBCPP_DEBUG 0
#define _GLIBCXX_DEBUG
#define rep(i,n) for (int i = 0; i < (n); ++i)	
using namespace std;

int max(int a,int b) {
	int max;
	if (a > b) max = a;
	else max = b;
	return max;
}
int min(int a, int b) {
	int min;
	if (a < b) min = a;
	else min = b;
	return min;
}

int main() {
	
	int n, m;
	int a[55];
	int b[55];

	cin >> n >> m;
	int numa[55] = { 0 };
	int numb[55] = { 0 };

	rep(i, m) {
		cin >> a[i] >> b[i];
	}
	rep(i, m) {
		numa[a[i]-1]++;
		numb[b[i]-1]++;
	}

	int k[55] = { 0 };
	rep(i, n) {
		k[i] = numa[i] + numb[i];
		cout << k[i] << endl;
	}
}

Measured memory_bytes: 888
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
const int INF = 1e9;
const int MOD = 1000000007;

const int MAX = 1000000;

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

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


long long modpow(long long a, long long b,long long d){
        bitset<30> bit(b);
        string s = bit.to_string();
        long long ret = 1;
        for (int i = 0;i< s.length(); ++i){
                ret *= ret;
                if(s[i]-'0') ret *= a;
                ret %= d;
        }
        return ret;
}

long long COM(ll n,ll r){
        ll res = 1;
        for(int i=1;i <= r;i++){
                res = (res * (n-i+1))%MOD;
        }
        
        res = (res * finv[r]) %MOD;
        return res;
}


int main(){
        COMinit();
        ll n,a,b;
        cin >>n >>a >> b;
        ll ans = (modpow(2,n,MOD) - 1 + MOD)%MOD;
        ans = (ans - COM(n,a) + MOD)%MOD;
        ans = (ans - COM(n,b) + MOD)%MOD;  

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



Measured memory_bytes: 23680
s = input()

def func(s):
    for i in range(0, len(s), 2):
        if s[i] not in "RUD":
            return "No"

    for i in range(1, len(s), 2):
        if s[i] not in "LUD":
            return "No"

    return "Yes"

print(func(s))


Measured memory_bytes: 2940
from collections import defaultdict
n = int(input())
d_ls = list(map(int, input().split()))
m = int(input())
t_ls = list(map(int, input().split()))

have_dict = defaultdict(int)
must_dict = defaultdict(int)
for i in range(n):
    have_dict[d_ls[i]] += 1
for i in range(m):
    must_dict[t_ls[i]] += 1
ans = 'YES'
for i in range(m):
    if must_dict[t_ls[i]] > have_dict[t_ls[i]]:
        ans = 'NO'
print(ans)



Measured memory_bytes: 57252
#include<bits/stdc++.h>
using namespace std;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define MOD (int)1e9+(int)7
typedef long long ll;
//dark power
//#define int ll
//define Error、大抵は、セミコロン忘れとか、Defineは関係ない

vector<int> d(100000);
vector<int> b(100000);
class UnionFind{
	public:
	signed find(signed x){
		if(d[x]==x){
			return x;
		}else{
			return d[x]=find(d[x]);
		}
	}
	UnionFind(signed n){rep(i,n){d[i]=i;b[i]=0;}}
	void unite(signed x,signed y){
		x=find(x);
		y=find(y);
		if(x==y)return;
		if(b[x]<b[y]){
			d[x]=y;
		}else{
			d[y]=x;
			if(b[x]==b[y])b[x]++;
		}
	}
	bool same(signed x,signed y){return (find(x)==find(y));}
};

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	UnionFind u(n);
	vector<pair<pair<int,int>,int> > a(n);
	vector<pair<int,pair<int,int> > > dis(2*n-2);
	rep(i,n){cin>>a[i].first.first>>a[i].first.second;a[i].second=i;}
	sort(all(a),[&](auto x,auto y){return (x.first.first<y.first.first);});
	rep(i,n-1){
		dis[i].first=a[i+1].first.first-a[i].first.first;
		dis[i].second.first=a[i].second;
		dis[i].second.second=a[i+1].second;
	}
	sort(all(a),[&](auto x,auto y){return (x.first.second<y.first.second);});
	rep(i,n-1,2*n-2){
		dis[i].first=a[i+1-(n-1)].first.second-a[i-(n-1)].first.second;
		dis[i].second.first=a[i-(n-1)].second;
		dis[i].second.second=a[i+1-(n-1)].second;
	}
	sort(all(dis),[&](auto x,auto y){return (x.first<y.first);});
	int count=0;
	int sum=0;
	int c=0;
	int max=0;
	rep(i,2*n-2){
		if(u.same(dis[i].second.first,dis[i].second.second))continue;
		u.unite(dis[i].second.first,dis[i].second.second);
		sum+=dis[i].first;
	}
	cout<<sum<<endl;
	return 0;
}

Measured memory_bytes: 4608
#include <iostream>
#include <vector>
#include <string>
#include <map>

using namespace std;

#define loop(i,a,b) for(int i=(a); i<(int)(b); i++)
#define rep(i,b) loop(i,0,b)

map<char,char> itoc, ctoi;
int main(){
    int n;
    rep(i,26){
        itoc[i]='A'+i;
        itoc[i+26]='a'+i;
        ctoi['A'+i]=i;
        ctoi['a'+i]=i+26;
    }

    while(cin>>n,n){
        vector<int> key(n);
        rep(i,n) cin>>key[i];
        string m; cin>>m;
        rep(i,m.size()){
            int c=ctoi[m[i]];
            c=(c-key[i%(key.size())]+52)%52;
            cout<<itoc[c];
        }
        cout<<endl;
    }
}

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

int main() {
    int N;
    cin >> N;
    int p;
    cin >> p;
    int count = 1;
    int P;
    rep(i,N-1){
        cin >> P;
        if(P <= p) count++;
        p = min(p,P);
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/***********************************************/
/* Dear online judge:
 * I've read the problem, and tried to solve it.
 * Even if you don't accept my solution, you should respect my effort.
 * I hope my code compiles and gets accepted.
 *  ___  __     _______    _______      
 * |\  \|\  \  |\  ___ \  |\  ___ \     
 * \ \  \/  /|_\ \   __/| \ \   __/|    
 *  \ \   ___  \\ \  \_|/__\ \  \_|/__  
 *   \ \  \\ \  \\ \  \_|\ \\ \  \_|\ \ 
 *    \ \__\\ \__\\ \_______\\ \_______\
 *     \|__| \|__| \|_______| \|_______|
 */
const long long mod = 1000000007;

//vector<vector<int> > all;
//vector<int> cur;
//int N;
//
//void bt(int idx) {
//	if(idx == N) {
//		all.push_back(cur);
//		return;
//	}
//	for(int i = 1;i <= N;i++) {
//		cur.push_back(i);
//		bt(idx+1);
//		cur.pop_back();
//	}
//}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

//	cin>>N;
//	bt(0);
//	set<vector<int> > res;
//	for(auto v : all) {
//		vector<int> c;
//		for(int i = 0;i < N;i++) cout<<v[i]<<" \n"[i+1 == N];
//		for(int i = 0;i < N;i++) {
//			set<int> s;
//			for(int j = 0;j < N;j++) if(i != j) s.insert(v[j]);
//			cout<<s.size()<<" \n"[i+1 == N];
//			c.push_back(s.size());
//		}
//		sort(c.begin(),c.end());
//		res.insert(c);
//		cout<<'\n';
//	}
//	for(auto v : res) {
//		for(int i = 0;i < N;i++) cout<<v[i]<<" \n"[i+1 == N];
//	}
	
	int N;
	cin>>N;
	vector<int> a(N);
	for(int i = 0;i < N;i++) cin>>a[i];
	sort(a.begin(),a.end());
	if(a[0]+1 < a.back()) {
		cout<<"No\n";
		return 0;
	}
	if(a.back() == 1) {
		cout<<"Yes\n";
		return 0;
	}
	if(a[0] == N - 1) {
		cout<<"Yes\n";
		return 0;
	}
	int mx = a.back() - 1;
	int mn = mx - (N - a.back() - 1);
	int c = count(a.begin(),a.end(),a.back()-1);
	if(c <= mx && c >= mn) {
		cout<<"Yes\n";
		return 0;
	}
	cout<<"No\n";
	return 0;
}


Measured memory_bytes: 640
#include <regex>
#include "bits/stdc++.h"
#define FOR(i, s, e) for (int i = int(s); i < int(e); ++i)
#define REP(i, e) FOR(i, 0, e)
#define INF (INT_MAX / 2)
#define LINF (LLONG_MAX / 2)
#define EPS (1.0e-8)
#define mkpr make_pair
const int MGN = 10;
const int ARY_SZ_MAX = (int)1e7;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>;
using vc = vector<char>; using vvc = vector<vc>;
using vb = vector<bool>; using vvb = vector<vb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>; using psl = pair<string, ll>;


bool first_greater_second_smaller(const pair<int,string>& left, const pair<int,string>& right) {
    if (left.first==right.first) return left.second < right.second;
    else return left.first > right.first;
}

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


  int N; cin>>N;
  vs S(N); REP(i,N) cin>>S[i];
  
  map<string, int> mp;
  REP(i,N) mp[S[i]] += 1;

  vector<pair<int,string>> vp;
  for(auto p : mp) {
    vp.push_back(mkpr(p.second, p.first));
  }

  sort(vp.begin(), vp.end(), first_greater_second_smaller);

  int top = vp[0].first;
  for(auto p : vp) {
    if (p.first == top) cout << p.second << endl;
    else break;
  }


  return 0;
}


Measured memory_bytes: 29680