akhauriyash/Code-Regression huggingface dataset:
//
//  atcoder.cpp
//
//
///
#include <bits/stdc++.h>
#include <boost/optional.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/bimap/bimap.hpp>
#include <boost/bimap/multiset_of.hpp>
#include <boost/multi_array.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/algorithm/string.hpp>

#define REP(i, N) for(int i=0; i<(N); i++)
#define REC(f, ...) (void)0; const auto f = [&](const auto f, __VA_ARGS__)
using namespace std;
using namespace boost::integer;

using ll = long long;
namespace bst = boost;
template<typename T> class in {
    T value;
public:
    in() { cin >> value; }
    operator const T&() const { return value; }
    operator T&() { return value; }
    in& operator=(T source) { value = source; return *this; }
};
template<> class in<string> : public string {
public:
    in() { cin >> *this; }
};
template<class T> class inseq : public T {
public:
    template<typename... Arg> inseq(Arg... arg) : T(forward<Arg>(arg)...) { for (auto&& i : *this) cin >> i; }
};
template<class T> using invec = inseq<vector<T>>;

auto solve() {
  in<string> A, B;

  B.pop_back();

  return (A == B ? "Yes" : "No");
}

template<typename T> void plot(const T& func) { cout << func() << endl; }
template<> void plot<void()>(void(&func)()) { func(); }
template<> void plot<double()>(double(&func)()) { cout << setprecision(9) << func() << endl; }

int main() {
  plot(solve);

  return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define repz(i, z, n) for (decltype(n) i = (z); i < (n); i++)
#define rep(i, n) for (decltype(n) i = 0; i < (n); i++)

#define REPZ(i, z, n) for (decltype(n) i = (z); i <= (n); i++)
#define REP(i, n) for (decltype(n) i = 0; i <= (n); i++)
#define ALL(v) v.begin(), v.end()
#define SIZE(v) ((ll)(v).size())
#define MAX(v) (*max_element(ALL(v)))
#define MIN(v) (*min_element(ALL(v)))
#define INF 1000000000000  // 1E+12

// 略
#define PB push_back
#define F first
#define S second
#define MP make_pair
#define READ cin >>
#define PRINT cout <<
#define PYES cout << "Yes" << endl;
#define POK cout << "OK" << endl;
#define PNO cout << "No" << endl;
#define PNG cout << "NG" << endl;

using namespace std;

// デバッグ用
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cout << H << " ";
  debug_out(T...);
}

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

#ifdef _DEBUG
#define debug(...) debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

// typedef
typedef long long ll;
typedef unsigned long long ul;
typedef long double ld;
typedef pair<ll, ll> pl;

// const
// 円周率
const ld pi = acos(-1);
// mod用
// 1E+9 +7
const ll mod = (int)1e+9 + 7;
// 1s間で可能なループ回数2E+8回
// int        最大値2147483647         〜2E+9
// long long  最大値9223372036854775807〜9E+18
// 総和accumulate
// 単純リストvector<type> push_back
// 連想配列map<key,value> insert,
// 集合set<type>
// pair キーとバリューを格納 firstとsecondでアクセス
// 小数点指定 cout << fixed << setprecision(15) << endl;
// to_string<->stoi
// stoll(longlong)
// stod(double)
// deep copy v1->v2 copy(v1.begin(), v1.end(), back_inserter(v2) );
// 大文字65-90(-32)
// 小文字97-122(+32)
//  priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>
//  ba;
signed main() {
  // faster
  // C言語流の入出力は使用できない
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int a,p; cin >> a>> p;
  cout << (3*a+p)/2 << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
  int A[100],N,i,temp,j,count=0;
  
  scanf("%d",&N);
  for(i=0;i<N;i++){scanf("%d",&A[i]);}
  for(j=0;j<N;j++)
    {
  for(i=N-1;i>j;i--)
    {      if(A[i-1]>A[i])
	{
	  temp=A[i-1];
	  A[i-1]=A[i];
	  A[i]=temp;
	  count++;
	}
    }
    }
  for(i=0;i<N;i++){printf("%d",A[i]); if(i != N-1){printf(" ");}}
  printf("\n%d\n",count);
  return 0;
}

Measured memory_bytes: 604
#pragma GCC optimize ("O2") // "Ofast" for REAL FAST
// #pragma GCC optimization ("unroll-loops")

// #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#pragma GCC diagnostic ignored "-Wunused-variable"
#pragma GCC diagnostic ignored "-Wunused-result"
#pragma GCC diagnostic ignored "-Wunused-label"

#include <bits/stdc++.h>
#define DEBUG 1

using namespace std;

#define rep(i, a, b) for (i = (a); i < (b); i++)
#define trav(a, x) for (auto & a : x)
#define all(x) (x).begin (), (x).end ()
#define rall(x) (x).rbegin (), (x).rend ()
#define sz(x) (int) (x).size ()
#define FASTIO cin.sync_with_stdio (0); cin.tie (0); cin.exceptions (cin.failbit);

typedef long long ll;

typedef pair <int, int> pii;
#define f first
#define s second
#define mp(x, y) make_pair (x, y)

typedef vector <int> vi;
#define pb(x) push_back (x)

#define ddcout if (DEBUG) cout
#define ddprintf(fmt, ...) if (DEBUG) printf (fmt, ##__VA_ARGS__)

const ll   MOD   =  1e+9+7;
const ll   INF   =  0x3f3f3f3f3f3f3f3f;
const int  INFi  =  0x3f3f3f3f;
const ll   MAXN  =  1e+6+7; // UPDATE

int main ()
{
    int i, j;
    scanf ("%d %d", &i, &j);
    printf ("%d\n", 6 - i - j);

    return 0;
}


Measured memory_bytes: 256
a=list(map(int,input()))
if a[0]+a[1]+a[2]+a[3]==7:
    print(str(a[0])+"+"+str(a[1])+"+"+str(a[2])+"+"+str(a[3])+"=7")
    exit()
elif a[0]+a[1]+a[2]-a[3]==7:
    print(str(a[0])+"+"+str(a[1])+"+"+str(a[2])+"-"+str(a[3])+"=7")
    exit()
elif a[0]+a[1]-a[2]+a[3]==7:
    print(str(a[0])+"+"+str(a[1])+"-"+str(a[2])+"+"+str(a[3])+"=7")
    exit()
elif a[0]+a[1]-a[2]-a[3]==7:
    print(str(a[0])+"+"+str(a[1])+"-"+str(a[2])+"-"+str(a[3])+"=7")
    exit()
elif  a[0]-a[1]+a[2]+a[3]==7:
    print(str(a[0])+"-"+str(a[1])+"+"+str(a[2])+"+"+str(a[3])+"=7")
    exit()
elif a[0]-a[1]+a[2]-a[3]==7:
    print(str(a[0])+"-"+str(a[1])+"+"+str(a[2])+"-"+str(a[3])+"=7")
    exit()
elif a[0]-a[1]-a[2]+a[3]==7:
    print(str(a[0])+"-"+str(a[1])+"-"+str(a[2])+"+"+str(a[3])+"=7")
    exit()
elif a[0]-a[1]-a[2]-a[3]==7:
    print(str(a[0])+"-"+str(a[1])+"-"+str(a[2])+"-"+str(a[3])+"=7")
    exit()


Measured memory_bytes: 3192
#include<cstdio>
#include<string>
#include<cstring>
#include<utility>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<algorithm>
#include<vector>
#include<iostream>
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define inf 0x7fffffff
using namespace std;
int a[100];
multiset<int> s;
int ge(int x)
{
	int sum=0,n=0;
	__typeof(s.begin()) it=s.end();
	it--;
	for(;it!=s.begin();it--)
	{
		sum+=*it;
		n++;
		if(n==x)
		{
			break;
		}
	}
	if(n<x)
	{
		sum+=*(s.begin());
	}
	return sum;
}
void print()
{
	for(__typeof(s.begin()) it=s.begin();it!=s.end();it++)
	{
		printf("%d ",*it);
	}
	printf("\n");
}
int main()
{
	int i,j,k,n,m,x,y;
	scanf("%d%d",&n,&m);
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	x=0;
	for(i=1;i<=m;i++)//uesd
	{
		if(i%2==0)
		{
			y=i/2+1;
			if(y>n)
			{
				continue;
			}
			for(j=2;j<=i;j+=2)//how many to choose
			{
				s.clear();
				for(k=0;k<y;k++)
				{
					s.insert(a[n-1-k]);
				}
				for(k=0;k<=y;k++)//left
				{
					x=max(x,ge(j));
					if(k==y)
					{
						break;
					}
					s.erase(s.find(a[n-y+k]));
					s.insert(a[k]);
				}
				y++;
				if(y>n)
				{
					break;
				}
			}
		}
		if(i%2==1)
		{
			y=i/2+1;
			if(y>n)
			{
				continue;
			}
			for(j=1;j<=i;j+=2)//how many to choose
			{
				s.clear();
				for(k=1;k<=y;k++)
				{
					s.insert(a[n-k]);
				}
				for(k=0;k<=y;k++)//left
				{
					x=max(x,ge(j));
					if(k==y)
					{
						break;
					}
					s.erase(s.find(a[n-y+k]));
					s.insert(a[k]);
				}
				y++;
				if(y>n)
				{
					break;
				}
			}
		}
	}
	printf("%d",x);
	return 0;
}

Measured memory_bytes: 256
#include <cmath>
#include <chrono>
#include <random>
#include <ctime>
#include <algorithm>
#include <iosfwd>
#include <iostream>
#include <list>
#include <ostream>
#include <streambuf>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define fori(i, n) for(ll i = 0; i < (n); ++i)
#define forI(i, n) for(ll i = 1; i <= (n); ++i)
#define pll pair<ll, ll>
#define ff first
#define ss second

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

#define pt pair<ll, ll>
#define x first
#define y second

pll operator+ (pll a, pll b){ return {a.x + b.x, a.y + b.y}; }

ll rand0m() {
    return (ull(rand()) << 15ull | ull(rand()));
}                   //[0 ... n)
ll rand0m(ll x) {
    return rand0m() % x;
}               //[0 ... n)
ll rand0m(ll minn, ll maxx) {
    return rand0m(maxx - minn + 1) + minn;
}   //[minn ... maxx]

const ll MAXN = 1e5 + 1;
const ll mod = 1e9 + 7;
const ll INF = 2e9 + 1000;

ll n, m, k;
ll a[MAXN];
ll dp[MAXN + 101];

void solve() {
    cin >> n >> k;
    fori(i, n) cin >> a[i];
    forI(i, n) dp[i] = INF;
    fori(i, n - 1) {
        forI(j, k) dp[i + j] = min(dp[i + j], dp[i] + abs(a[i + j] - a[i]));
    }
    cout << dp[n - 1];
}

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

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

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

int main() {

    int N;
    cin >> N;

    vector<double> A(N);

    double q = 0.0;

    rep(i, N) {
        cin >> A[i];
        q += 1.0 / A[i];
    }

    cout << setprecision(16) << 1.0 / q << endl;

    return 0;
}

Measured memory_bytes: 256
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cfloat>
#include <complex>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits.h>
#include <list>
#include <map>
#include <math.h>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define int long long
#define ll long long
#define P pair<int,int>
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define all(V) V.begin(),V.end()
#ifdef int
constexpr int INF = LLONG_MAX / 10;
#else
constexpr int INF = INT_MAX / 10;
#endif
constexpr double eps = 1e-9;
template <class T, class U>
inline bool chmax(T& lhs, const U& rhs) {
	if (lhs < rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
template <class T, class U>
inline bool chmin(T& lhs, const U& rhs) {
	if (lhs > rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
using namespace std;
inline ll gcd(ll a, ll b) {
	while (b) {
		ll c = a;
		a = b; b = c % b;
	}
	return a;
}
inline ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}
bool isprime(ll n) {
	if (n == 1)return false;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0)return false;
	}
	return true;
}
ll mypow(ll a, ll b) {
	if (!b)return 1;
	if (b & 1)return mypow(a, b - 1) * a;
	ll memo = mypow(a, b >> 1);
	return memo * memo;
}
signed main() {
	string s;
	cin >> s;
	string t = s;
	reverse(all(t));
	if (s != t) {
		puts("No");
		return 0;
	}
	t = s.substr(0, s.size() / 2);
	reverse(all(t));
	if (s.substr(0, s.size() / 2) != t) {
		puts("No");
		return 0;
	}
	t = s.substr(s.size() / 2 + 1, s.size() / 2);
	reverse(all(t));
	if (s.substr(s.size() / 2 + 1) != t) {
		puts("No");
		return 0;
	}
	puts("Yes");
	return 0;
}

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

int main() {
    long long N, M;
    cin >> N >> M;
    long long teisyutu_kaisuu = 1LL<<M;
    long long each_time = 1900LL * M + 100LL * (N - M);
    cout <<  each_time * teisyutu_kaisuu << endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
// Custom Header {{{
#define ALL(x) x.begin(), x.end()
#define rep(i, s, n)      for(int i(s); i < int(n); ++i)
#define endl '\n'
#ifndef YDK
#define eprintf(...)
#endif
using namespace std;
using i64 = long long;
using pii = pair<i64, i64>;
template<class A, class B>inline bool chmax(A &a, const B &b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b<a ? a=b,1 : 0;}
constexpr const int INF  = 0x3f3f3f3f;
constexpr const i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr const int MOD  = int(1e9) + 7;
// }}}

// Library {{{

// }}}

string N;
int L;
int dp[20][2];

int slv(int idx, bool tight)
{
    if (idx >= L) { return 0; }
    if (~dp[idx][tight]) return dp[idx][tight];

    const int lim = tight ? (N[idx] - '0') : 9;

    int ret = 0;
    for (int i = 0; i <= lim; ++i) {
        chmax(ret, i + slv(idx+1, tight && (i == lim)));
    }

    return dp[idx][tight] = ret;
}

signed main()
{
    cin >> N;
    L = N.length();

    memset(dp, -1, sizeof(dp));
    cout << slv(0, true) << endl;
    return 0;
}


Measured memory_bytes: 256
S = input()

L = []
for i in range(len(S)):
    L.append(S[i])
    
ans = 0

for i in range(2**(len(S)-1), 2**(len(S))):
    c = 0
    temp = bin(i)
    for j in range(3, len(temp)):
        if temp[j] == "1":
            temp_list = L[c:j-2]
            ans += int("".join(temp_list))
            c = j-2
    temp_list = L[c:]
    ans += int("".join(temp_list))
            
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i=0;i < (int)(n);i++)

int main(){
    int x,y;
    cin >> x >> y;
    cout << x+y/2 << endl;
    string s;

    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int N, D[55];
int num[13];

int res(int bit)
{
	int last = 0;
	int ret = 24;
	for (int i = 1; i < 24; ++i) {
		if ((bit >> i) & 1) {
			int dif = i - last;
			last = i;
			ret = min(ret, min(dif, 24 - dif));
		}
	}
	ret = min(ret, min(last, 24 - last));
	return ret;
}

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) scanf("%d", D + i);

	for (int i = 0; i < N; ++i) {
		++num[D[i]];
	}
	int mask = 0;
	int tg = 0;
	for (int i = 0; i <= 12; ++i) {
		if (num[i] >= 3 || (i == 12 && num[i] == 2) || (i == 0 && num[i] == 1)) {
			puts("0");
			return 0;
		}
		if (num[i] == 2) {
			mask |= 1 << i;
			mask |= 1 << (24 - i);
		} else if (num[i] == 1) {
			tg |= 1 << i;
		}
	}
	int ret = 0;
	for (int b = 0; b < (1 << 13); ++b) {
		int m2 = mask;
		for (int i = 0; i <= 12; ++i) {
			if (tg & (1 << i)) {
				if (b & (1 << i)) m2 |= 1 << (24 - i);
				else m2 |= 1 << i;
			}
		}
		ret = max(ret, res(m2));
	}
	printf("%d\n", ret);
	return 0;
}

Measured memory_bytes: 256
n = int(input())
c = 0
for _ in range(n):
    r = [int(e) for e in input().split(" ")]
    if(r[0] == r[1]):
        c += 1
    else:
        c = 0
    if(c == 3):
        print("Yes")
        break
else:
    print("No")



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

int k, s;
int res = 0;

int main(){
  cin >> k >> s;
  rep(i, k + 1){
    rep(j, k + 1){
      int x = i, y = j;
      if(x + y <= s && x + y >= s - k){
        //int z = s - x - y;
        
        //cerr << x <<" "<<y <<" "<<z <<endl;
        res++;
      }
    }
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define INF 9223372036854775807
typedef long long ll;
#define REP(i,n) for(int i=0;i<(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define rollcall cout<<"I'm Sucu."<<endl;
#define YES(s) s?cout << "YES" << endl:cout << "NO" << endl
#define Yes(s) s?cout << "Yes" << endl:cout << "No" << endl
#define Taka(s) s?cout << "Takahashi" << endl:cout << "Aoki" << endl
#define out(s,t,u) s?cout << t << endl:cout << u << endl
#define int ll
#define Endl endl


signed main(){
    int K,N,Ans=INF;
    int x[57],y[57];
    cin>>N>>K;
    REP(i,N){
        cin >> x[i]>>y[i];
    }
    REP(i,N){
        REP(j,N){
            REP(k,N){
                REP(l,N){
                    int lx=min(x[i],x[j]),rx=max(x[i],x[j]),uy=min(y[k],y[l]),dy=max(y[k],y[l]);
                    int c=0;
                    REP(m,N){
                        if(lx<=x[m]&&x[m]<=rx && uy<=y[m]&&y[m]<=dy){
                            c++;
                        }
                    }
                   // cout << c << endl;
                    if(c>=K){
                        Ans=min(Ans,(rx-lx)*(dy-uy));
                    }
                }
            }
        }
    }
    cout<<Ans << endl;
    return 0;
}   



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

int n, m;
int w[102], v[102];
long long f[102][100002];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for (int i=1;i<=n;i++)
        cin>>w[i]>>v[i];
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            if (j >= w[i])
                f[i][j] = max(f[i-1][j], f[i-1][j-w[i]] + v[i]);
            else f[i][j] = f[i-1][j];
        }
    }
    cout<<f[n][m];
}


Measured memory_bytes: 78464
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int main(){
  ll x,k,d;
  cin >> x >> k >> d;
  if(x>=0){
    ll v=x/d;
    if(v>=k){
      cout << abs(x-d*k) << endl;
    }
    else{
      if((k-v)%2==0){
        cout << abs(x%d) << endl;
      }
      else{
        cout << abs(x%d-d) << endl;
      }
    }
  }
  else{
    x=-1*x;
    ll v=x/d;
    if(v>=k){
      cout << abs((x-d*k)*(-1)) << endl;
    }
    else{
      if((k-v)%2==0){
        cout << abs((x%d)*(-1)) << endl;
      }
      else{
        cout << abs((x%d)*(-1)+d) << endl;
      }
    }
  }
}

Measured memory_bytes: 3668
n = gets.to_i
N = gets.strip.to_s
ary = N.split("").map(&:to_s)
ka = []
ary.each do |x|
  if x=="E"
    ka << 0
  else
    ka << 1
  end
end
#累積和かな？
s = Array.new(n+1)
s[0] = 0
0.upto(n-1) do |i|
  s[i+1] = s[i] + ka[i]
end
#これで完了
#ここまでO(N)、このままO(N)だといけるはず
h = n
i = 1 #西から何人目？
while i <= n do
  c = n-i-s[n]+s[i]+s[i-1]
  if h > c
    h = c
  end
  i += 1
end
puts h

Measured memory_bytes: 45280
# -*- coding: utf-8 -*-
N = int(input())

X = 0
for i in range(N + 1):
    if 0 < i and i < 10 or 100 <= i and i < 1000 or 10000 <= i and i < 100000:
        X += 1
    else:
        X += 0
print(X)


Measured memory_bytes: 3064
class nCrMod():
    def __init__(self, mod):
        self.mod = mod
        self.fac = [1, 1]
        self.finv = [1, 1]
        self.inv = [0, 1]

    def prep(self, n):
        mod = self.mod
        f, fi = self.fac[-1], self.finv[-1]
        for i in range(len(self.fac), n + 1):
            fn = f * i % mod
            v = -self.inv[mod % i] * (mod // i) % mod
            fin = fi * v % mod
            f, fi = fn, fin
            self.fac.append(f)
            self.finv.append(fi)
            self.inv.append(v)

    def __call__(self, n, r):
        if len(self.fac) <= n:
            self.prep(n)
        return self.fac[n] * self.finv[r] * self.finv[n - r] % self.mod


def main():
    N, M = map(int, input().split())
    mod = 10**9 + 7
    nCr = nCrMod(mod)
    nPr = lambda n, r: nCr(n, r) * nCr.fac[r] % mod
    r = nPr(M, N) ** 2 % mod
    for i in range(1, N + 1):
        r = (r + (-1)**i * nCr(N, i) * nPr(M, i) * (nPr(M - i, N - i) ** 2)) % mod
    return r % mod

print(main())


Measured memory_bytes: 184860
import sys
from bisect import bisect_left

input = sys.stdin.readline


def main():
    N = int(input())
    L = list(map(int, input().split()))

    L.sort()
    ans = 0
    for a in range(N - 2):
        for b in range(a + 1, N - 1):
            x = bisect_left(L, L[a] + L[b])
            ans += (x - 1 - b)

    print(ans)


if __name__ == "__main__":
    main()


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

int manhattan(P a, P b) {
    return abs(a.first - b.first) + abs(a.second - b.second);
}

int main() {
    int n, m;
    cin >> n >> m;
    P p[n];
    P q[m];
    int mind[n];
    rep(i,n) {
        cin >> p[i].first >> p[i].second;
        mind[i] = 1000000000;
    }
    rep(i,m) {
        cin >> q[i].first >> q[i].second;
    }
    int ans[n];
    rep(i,n) {
        for(int j = m-1; j >= 0; j--) {
            int d = manhattan(p[i], q[j]);
            if (d <= mind[i]) {
                mind[i] = d;
                ans[i] = j+1;
            }
        }
    }
    rep(i,n) {
        cout << ans[i] << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef  long long int ll;
typedef  long double ld;
#define sync ios_base::sync_with_stdio(false); cin.tie(NULL) 
#define input(arr,n) for(ll i1=0;i1<n;i1++ )cin>>arr[i1]
#define mod 1000000007
#define F first
#define S second 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
//recursions\
#pragma comment(linker, "/stack:200000000")
//loops\
#pragma GCC optimize("unroll-loops")
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>//s.order_of_key(val) *s.find_by_order(ind)
using namespace std;
const int N = 1e6+5;
struct Q
{
	ll l, r, i, ans;
};
bool cmp1(Q x, Q y)
{
	return x.r < y.r;
}
bool cmp2(Q x, Q y)
{
	return x.i < y.i;
}
ll get(vector<ll>&v, ll idx)
{
	ll ans = 0;
	while(idx >= 0)
	{
		ans += v[idx];
		idx = (idx & (idx+1)) - 1;
	}
	return ans;
}
void upd(vector<ll>&v, ll idx, ll val)
{
	while(idx < v.size())
	{
		v[idx] += val;
		idx |= (idx + 1);
	}
}
int main()
{
	sync;
	ll n, q;
	cin >> n >> q;
	ll col[n];
	input(col, n);
	Q qry[q];
	for(ll i = 0 ; i < q; i++)
	{
		cin >> qry[i].l >> qry[i].r;
		qry[i].i = i;
	}
	sort(qry, qry + q, cmp1);
	ll idx = 0;
	vector<ll> bit(n + 1), last(n + 1,  -1);
	for(ll i = 0; i < n; i++)
	{
		if(last[col[i]] != -1)
			upd(bit, last[col[i]], -1);
		last[col[i]] = i + 1;
		upd(bit, i + 1, 1);
		while(idx < q && qry[idx].r == i + 1)
		{
			qry[idx].ans = get(bit, qry[idx].r) - get(bit, qry[idx].l - 1);
			idx++;
		}
	}
	sort(qry, qry + q, cmp2);
	for(ll i = 0; i < q; i++)
		cout << qry[i].ans << "\n";
}

Measured memory_bytes: 31148
import java.util.*;
import java.io.*;

public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();   
        int k = sc.nextInt();   
        int[] p = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = sc.nextInt();
        }
        int[] s = cumulativeSum(p);
        int sum = 0;
        int max = sum;
        for (int i = 0; i < n-k+1; i++) {
            sum = s[i+k] - s[i];
            if (max < sum) {
                max = sum;
            }
        }
        double res = max / 2.0 + k / 2.0;
        System.out.println(res);
    }
    // 累積和
    public static int[] cumulativeSum(int[] a) {
        int[] s = new int[a.length + 1];
        for (int i = 0; i < s.length; i++) {
            s[i] = 0;
        }
        for (int i = 0; i < a.length; i++) {
            s[i+1] = s[i] + a[i];
        }
        return s;
    }
}

Measured memory_bytes: 64216
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    X,N = map(int,input().split())
    P = set(map(int,input().split()))
    ans = -1
    M = INF
    for i in range(X - 105,X + 105):
        if i not in P:
            if M > abs(i - X):
                ans = i
                M = abs(i - X)
    print(ans)
if __name__ == '__main__':
    main()

Measured memory_bytes: 9220
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); i++)
#define repi(i,a,b) for (int i=a;i<(b);i++)
using namespace std;
typedef long long ll;
  
  int main(void){
    cin.tie(0); //cin高速化
    ios::sync_with_stdio(false); //cin高速化
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    if(abs(a-c)<=d){
      cout << "Yes" << endl;
    }else if((d>=abs(a-b))&&(d>=abs(b-c))){
      cout<<"Yes"<<endl;
    }else{
      cout<<"No"<<endl;
    }
    return 0;

}
    

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

int main(){
    string s,t;
    cin >> s >> t;
    int count = 0;
    for(int i = 0;i < s.size();i++){
        if(s[i] != t[i]){
            count++;
        }
    }

    cout << count << endl;
    return 0;
}

Measured memory_bytes: 3836
a = [int(x) for x in input().strip().split()]
t = []
for i in range(a[0]):
  t.append(int(input().strip()))
t.sort()

m = 0
i = 0
while True:
  if i+a[1] - 1 > a[0] - 1:
    ii = a[0] - 1
  else:
    ii = i+a[1] - 1
  if t[ii] - t[i] <= a[2]:
    i = ii + 1
    m += 1
  else:
    for j in range(i+1, ii+1):
      if t[j] - t[i] > a[2]:
        m += 1
        i = j
        break
  if i == a[0]:
    break

print(m)


Measured memory_bytes: 7440
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <bitset>
#include <string>
using namespace std;

#define REP(i,n) for(int i=0; i<n; i++)
#define RPA(i,s,e) for(int i=s; i<=e; i++)
#define RPD(i,s,e) for(int i=s; i>=e; i--)
#define PB(a) push_back(a)
#define MP(i,s) make_pair(i,s)
#define SZ(a) (int)(a).size()
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a,b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
#define PRT3(a,b,c) cerr << (a) << ", " << (b) << ", " << (c) << endl

typedef vector<int> VI;
typedef long long LL;
typedef pair<int,int> PII;

const LL INF = 1ll<<60;
const double infd = 1.0e12;

LL n, m, p, a, b;
vector<LL> tickets;
LL graph[50][50];

double dp[(1<<8)+10][35];

void dfs(LL c, LL mask, double t) {
	if(dp[mask][c] > t) {
		dp[mask][c] = t;
		REP(i,m) {
			if(graph[c][i] != INF) {
				REP(k,n) {
					if((mask & (1ll<<k)) == 0) {
						LL next = mask | (1ll << k);
						double elp = graph[c][i] / (double)tickets[k];
						dfs(i, next, t + elp);
					}
				}
			}
		}
	}
}

void solve() {
	REP(i,(1<<n)) REP(j,m) dp[i][j] = infd;
	dfs(a, 0, 0.0);
	double ans = infd;
	REP(i,1<<n) {
		ans = min(ans, dp[i][b]);
	}
	if(ans == infd) {
		printf("Impossible\n");
		return;
	}
	printf("%.3f\n", ans);
}

void coding() {
	while(cin>>n>>m>>p>>a>>b, n|m|p|a|b) {
		a--; b--;
		tickets = vector<LL>(n);
		REP(i,n) cin >> tickets[i];
		REP(i,m) REP(j,m) graph[i][j] = INF;
		REP(i,p) {
			LL x, y, z;
			cin>>x>>y>>z;
			x--; y--;
			graph[x][y] = graph[y][x] = z;
		}
		solve();
	}
}

// #define _LOCAL_TEST

int main() {
#ifdef _LOCAL_TEST
	clock_t startTime = clock();
	freopen("test.dat", "r", stdin);
#endif

	coding();

#ifdef _LOCAL_TEST
	clock_t elapsedTime = clock() - startTime;
	cout << endl;
	cout << (elapsedTime / 1000.0) << " sec elapsed." << endl;
	cout << "This is local test" << endl;
	cout << "Do not forget to comment out _LOCAL_TEST" << endl << endl;
#endif
}

Measured memory_bytes: 1328
//#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,no-stack-protector") 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
 
#include <bits/stdc++.h>
 
#define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define repb(i, r, l) for (int i = r; i >= l; i--)
#define sz(a) (int)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp(a, b) make_pair(a, b)
#define ret(a) {cout << a; exit(0);}
 
using namespace std;                                                                                  
 
mt19937 mrand(random_device{}()); 
const ll mod = 1e9 + 7;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b,ll mod) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
 
typedef pair < int , int > pii ;                                            
typedef pair < long long  , long long > pll ;

const int N = 3e5 + 123;

int n, m, k;
vector < pii > gr[N];
int a[N];
int dp1[N] , cnt1[N], dp2[N], cnt2[N] , w[N] , v[N] , u[N];

main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int s , t;
	cin >> n >> m >> s >> t;

	rep(i , 1 , n)
		dp1[i] = dp2[i] = 1e17;
	dp1[s] = dp2[t] = 0;
	cnt1[s] = cnt2[t] = 1;
	
	for(int i = 1; i <= m; i++){
		cin >> u[i] >> v[i] >> w[i];
		gr[u[i]].pb({v[i],w[i]});
		gr[v[i]].pb({u[i],w[i]});
	}
	set < pii > st;
	st.insert({0 , s});
	
	while(sz(st) != 0){
		int u = (*st.begin()).se;
		st.erase(st.begin());
		for(auto to : gr[u]){
			if(dp1[to.fi] == dp1[u] + to.se)
				cnt1[to.fi] += cnt1[u], cnt1[to.fi] %= mod;
			else if(dp1[to.fi] > dp1[u] + to.se){
				st.erase({dp1[to.fi] , to.fi});
				dp1[to.fi] = dp1[u] + to.se;
				cnt1[to.fi] = cnt1[u];
                st.insert({dp1[to.fi],to.fi});
			}
		}
	}    

	st.insert({0 , t});
	while(sz(st) != 0){
		int u = (*st.begin()).se;
		st.erase(st.begin());
		for(auto to : gr[u]){
			if(dp2[to.fi] == dp2[u] + to.se)
				cnt2[to.fi] += cnt2[u] , cnt2[to.fi] %= mod;
			else if(dp2[to.fi] > dp2[u] + to.se){
				st.erase({dp2[to.fi] , to.fi});
				dp2[to.fi] = dp2[u] + to.se;
				cnt2[to.fi] = cnt2[u];
                st.insert({dp2[to.fi],to.fi});
			}
		}
	}	
	int tot = cnt1[t] * cnt1[t]%mod;
	for(int i = 1; i <= m; i++){
		if(dp1[u[i]] + dp2[v[i]] > dp2[u[i]] + dp1[v[i]])
			swap(u[i],v[i]);
		if(dp1[u[i]] + dp2[v[i]] + w[i] == dp1[t]){
			int l = max(dp1[u[i]],dp2[v[i]]) , r = min(dp1[u[i]],dp2[v[i]])+w[i];
			if(l < r)
				tot -= cnt1[u[i]] * cnt2[v[i]] % mod * cnt1[u[i]] % mod * cnt2[v[i]] % mod , tot += mod , tot %= mod;
		}
	}

	for(int i = 1; i <= n; i++)
		if(dp1[i] + dp2[i] == dp1[t] and dp1[i] == dp2[i])
			tot -= cnt1[i] * cnt2[i] % mod * cnt1[i] %mod * cnt2[i] % mod , tot += mod , tot %= mod;


	ret(tot);
        
}

Measured memory_bytes: 39024
#include <bits/stdc++.h>
#define Maxn 400007
#define eps 1e-7
using namespace std;
int n;
int p[Maxn],fa[Maxn];
int cnt[2][Maxn];
struct node
{
	int cnt0,cnt1,id;
	bool operator < (const node &a) const
	{
		return 1LL*cnt0*a.cnt1<1LL*cnt1*a.cnt0;
	}
};
priority_queue<node> que;
int find(int x)
{
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main()
{
	scanf("%d",&n);
	for (int i=2;i<=n;i++)
		scanf("%d",&p[i]);
	for (int i=1;i<=n;i++)
	{
		int val;
		scanf("%d",&val);
		++cnt[val][i];
		fa[i]=i;
	}
	long long ans=0;
	for (int i=2;i<=n;i++)
		que.push((node){cnt[0][i],cnt[1][i],i});
	while (!que.empty())
	{
		node now=que.top();
		que.pop();
		int pos=now.id;
		if (cnt[0][pos]==now.cnt0&&cnt[1][pos]==now.cnt1)
		{
			int new_pos=fa[pos]=find(p[pos]);
			ans+=1LL*cnt[0][pos]*cnt[1][new_pos];
			cnt[0][new_pos]+=cnt[0][pos];
			cnt[1][new_pos]+=cnt[1][pos];
			if (new_pos!=1) que.push((node){cnt[0][new_pos],cnt[1][new_pos],new_pos});
		}
	}
	printf("%lld\n",ans);
	return 0;
}


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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(ll i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

// 300, 10min

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;
#define MAX_N 100010

ll N;
ll A[MAX_N] = {};
ll B[MAX_N] = {};

signed main()
{
    cin >> N;
    REP(i, N) { cin >> A[i]; }
    REP(i, N) { cin >> B[i]; }
    ll a_diff = 0, b_diff = 0;
    REP(i, N) {
        if(A[i] > B[i]) { b_diff += A[i]-B[i]; }
        else { a_diff += (B[i]-A[i]) / 2; }
    }
    if(b_diff <= a_diff) { printf("Yes\n"); }
    else { printf("No\n"); }
    return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#define MOD (1e9 +7)
 
using namespace std;
int x, n , m;
int price[13] = {0};
int skills[13][13] = {0};
vector<int> v;


void call(int sum[13], int idx, int cost)
{
    if(idx > n) return;

    int new_sum[13] = {0};
    bool is_x = true;
    for(int i = 1; i <= m; i++){
        new_sum[i] = sum[i] + skills[idx][i];
        is_x = is_x && (new_sum[i] >= x);
    }
    if(is_x){v.push_back(cost+price[idx]);}

    call(sum, idx+1, cost);
    call(new_sum, idx+1, cost+price[idx]);
}


 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); 
    
    cin >> n >> m >> x;
    for(int i = 1; i <= n; i++){
        cin >> price[i];
        for(int j = 1; j <= m; j++) cin >> skills[i][j];
    }
    int sum[m+1] = {0};

    call(sum, 1, 0);
    if(v.size() == 0) cout << "-1";
    else sort(v.begin(), v.end()), cout << v[0];



    return 0;
}

Measured memory_bytes: 3676
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/




int N, A[101010][3], dp[101010][3];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) rep(j, 0, 3) cin >> A[i][j];

    rep(lst, 0, 3) dp[1][lst] = A[0][lst];
    rep(i, 1, N) rep(lst, 0, 3) {
        rep(nxt, 0, 3) if (lst != nxt) chmax(dp[i + 1][nxt], dp[i][lst] + A[i][nxt]);
    }
    int ans = 0;
    rep(lst, 0, 3) chmax(ans, dp[N][lst]);
    cout << ans << endl;
}


Measured memory_bytes: 2560
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;

using ll = long long;
using pll = pair<ll, ll>;

ll dp[101][305];

int main() {
    int N, W;
    cin >> N >> W;
    int ws = 0, sum = 0;
    for(int i = 0; i < N; i++) {
        int w, v;
        cin >> w >> v;
        if(i == 0) ws = w;
        w -= ws;
        for(int j = i; j >= 0; j--) {
            for(int k = sum; k >= 0; k--) {
                dp[j+1][k+w] = max(dp[j+1][k+w], dp[j][k] + v);
            }
        }
        sum += w;
    }

    ll ans = -(1<<30);
    for(int i = 0; i <= N; i++) {
        for(int j = 0; j <= sum; j++) {
            ll x = (ll)ws * i + j;
            if(x <= W) {
                ans = max(ans, dp[i][j]);
            }
        }
    }

    cout << ans << endl;

    return 0;
}

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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, ans = 0;
  cin >> n;
  int a[n], b[n] = {};
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    if (i != 0 && a[i - 1] == a[i] && !b[i - 1]) {
      ans++;
      b[i] = 1;
    }
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
  int N;
  cin >> N;
  vector<int> X(N);
  for(int i=0; i<N; ++i)
  {
    cin >> X[i];
    X[i] -= i + 1;
  }
  sort(X.begin(), X.end());

  long long ans=0;
  for(int i=0; i<N; ++i)
  {
    ans += abs(X[i]-X[N/2]);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <cstdio>
#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 <complex>
#include <stack>
#include <queue>
#include <iomanip>
#include <array>
#include <numeric>
#include <regex>
#include <bitset>
#include <deque>

using namespace std;
typedef long long ll;
typedef pair<int, int> p_ii;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)

const int INF = 1e9;
const double PI = acos(-1.0);
const ll MOD = 1e9 + 7;


int main() {
	
	string S;
	cin >> S;

	vector<ll> dp(100010), a(100010), ab(100010), sum(100010);
	dp[0] = 0; a[0] = 0; ab[0] = 0; sum[0] = 1;

	rep(i, S.size()) {
		if (S[i] == '?') {
			a[i + 1] = (sum[i] + 3 * a[i]);
			ab[i + 1] = (a[i] + 3 * ab[i]);
			dp[i + 1] = (ab[i] + 3 * dp[i]);
			sum[i + 1] = sum[i] * 3;
		}
		else {
			a[i + 1] = a[i]; ab[i + 1] = ab[i]; dp[i + 1] = dp[i];
			if (S[i] == 'A') {
				a[i + 1] += sum[i];
			}
			else if (S[i] == 'B') {
				ab[i + 1] += a[i];
			}
			else if (S[i] == 'C') {
				dp[i + 1] += ab[i];
			}
			sum[i + 1] = sum[i];
		}
		a[i + 1] %= MOD;
		ab[i + 1] %= MOD;
		dp[i + 1] %= MOD;
		sum[i + 1] %= MOD;
	}

	cout << dp[S.size()] << endl;

	return 0;
}

Measured memory_bytes: 3584
/**
 *    Author:  Oak_limy
 *    Created: 2020-09-19 21:02:43
**/
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <limits>
#include <list>
#include <map>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>
#include <cwchar>
#include <cwctype>
#define endl '\n'
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define zy -2147382637
#define bql 2147483647
#define ll long long
#define ull unsigned long long
#define ld long double
#define il inline
#define sz(x) x.size()
#define rp(i, l, r) for (int i = l; i <= r; i++)
#define rb(i, r, l) for (int i = r; i >= l; i--)
#define fi first
#define se second
#define pb push_back
#define up upper_bound
using namespace std;
ll max(ll a,ll b){if(a>b)return a;else return b;}
ll min(ll a,ll b){if(a<b)return a;else return b;}
ll lowbit(ll x){return x&(-x);}
ll prime(ll x){
   if(x<=1)return false;
   for(int i=2;i<=int(sqrt(x));i++){
       if(x%i==0)return false;
   }return true;
}bool cmp(ll a,ll b){return a>b;}
ll gcd(ll a,ll b){ll r;while(b>0){r=a%b;a=b;b=r;}return a;}
ll powmod(ll a,ll b,ll mod) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
inline int readint() {
    char c = getchar(); int w = 1; int x = 0;
    while (!isdigit(c))
        (c == '-') && (w = -w), c = getchar();
    while (isdigit(c))
        x = (x << 3) + (x << 1) + (c ^ '0'), c = getchar();
    x *= w;
    return x;
}
inline ll readll() {
    char c = getchar(); ll w = 1; ll x = 0;
    while (!isdigit(c))
        (c == '-') && (w = -w), c = getchar();
    while (isdigit(c))
        x = (x << 3) + (x << 1) + (c ^ '0'), c = getchar();
    x *= w;
    return x;
}
void fl(string name){
    freopen((name+".in").c_str(),"r",stdin);
    freopen((name+".out").c_str(),"w",stdout);
}
const int dx[8] = {-1, 1, 0, 0, -1, 1, -1, 1},
          dy[8] = {0, 0, -1, 1, -1, -1, 1, 1};

int main(){
    string s;
    cin>>s;
    if(s[s.size()-1]!='s')cout<<s<<'s'<<endl;
    else cout<<s<<"es"<<endl;
    return 0;
}
/* stuff to remember
    * int overflow, array bounds
    * special cases (n=1? n=0?)
    * do something instead of nothing and stay organized
    * USE STATIC ARRAYS
    * DEFINING ARRAYS BEFORE main()
    * DO NOT DEFINE ARRAYS IN main()
    * USE INT INSTEAD OF LL,NOTICE THE MLE
*/

Measured memory_bytes: 3692
N = int(input())
if 1<=N and 9>=N:
    print(N)
elif 10<=N and 99>=N:
    print(9)
elif 100<=N and 999>=N:
    print(N-90)
elif 1000<=N and 9999>=N:
    print(909)
elif 10000<=N and 99999>=N:
    print(N-9090)
else:
    print(90909)

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

int mod=1e18+7;
D w,h,v,t,X,Y,x,y,r,w1,h1,w2,h2;
D dx[2],dy[2];

D get_h(double a){
  return r*r-a*a;
}

int UP(D h){
  D ny=abs(y-Y);
  int idx=1;
  if(y<=Y)ny=dy[1]-(Y-y),idx=0;
  //cout<<ny<<' '<<h<<endl;
  //ny-=abs(y-Y);
  int l=0,r=1e6;
  while(l<r){
    int mid=(l+r)/2;
    bool flag=0;
    if(!mid)flag=1;
    else if(mid==1)flag=(ny<=h);
    else{
      D NY=ny;
      NY+=dy[0]*((mid-1)/2);
      NY+=dy[1]*((mid-1)/2);
      if((mid-1)%2) NY+=dy[idx];
      if(NY<=h)flag=1;
      else flag=0;
      //if(mid==2)cout<<NY<<endl;
    }
    if(!flag)r=mid;
    else l=mid+1;
  }
  return l-1;
}

int DOWN(D h){
  D ny=-abs(Y-y);//y-Y;
  int idx=0;
  if(y>=Y)ny=-dy[0]+(y-Y),idx=1;
  //cout<<ny<<endl;
  //ny+=abs(y-Y);
  //cout<<ny<<' '<<h<<endl;
  int l=0,r=1e6;
  while(l<r){
    int mid=(l+r)/2;
    bool flag=0;
    if(!mid)flag=1;
    else if(mid==1)flag=(abs(ny)<=h);
    else{
      D NY=ny;
      NY-=dy[0]*((mid-1)/2);
      NY-=dy[1]*((mid-1)/2);
      if((mid-1)%2) NY-=dy[idx];
      if(abs(NY)<=h)flag=1;
      else flag=0;
    }
    if(!flag)r=mid;
    else l=mid+1;
  }
  return l-1;
}
int Binary_search(D h){//cout<<h<<endl;
  int s1=UP(h);
  int s2=DOWN(h);
  if(y==Y)s1++;
  //cout<<h<<' '<<s1<<' '<<s2<<endl;
  return (s1+s2)%mod;
}

int LEFT(){
  D nx=x;
  int idx=0,ans=0;
  if(X<=x)nx=x-dx[0],idx=1;
  while(1){
    //cout<<nx<<endl;
    D h=get_h(abs(nx-X));
    if(h<0)break;
    h=sqrt(h);
    //cout<<nx-X<<endl;
    ans+=Binary_search(h);
    ans%=mod;
    nx-=dx[idx++];
    idx%=2;
  }
  return ans;
}

int RIGHT(){
  D nx=x;
  int idx=1,ans=0;
  if(X>=x)nx=x+dx[1],idx=0;
  while(1){
    //cout<<nx-X<<endl;
    D h=get_h(abs(nx-X));
    //cout<<h<<endl;
    if(h<0)break;
    h=sqrt(h);
    //cout<<nx-X<<endl;
    ans+=Binary_search(h);
    ans%=mod;
    nx+=dx[idx++];
    idx%=2;
  }
  return ans;
}

int EQUAL(){
  if(X!=x)return 0;
  return Binary_search(r);
}

signed main(){
  cin>>w>>h>>v>>t>>X>>Y>>x>>y;
  r=v*t;
  w1=x;w2=w-x;
  h1=y;h2=h-y;
  dx[0]=w1*2;
  dx[1]=w2*2;
  dy[0]=h1*2;
  dy[1]=h2*2;
  int s1=LEFT();
  int s2=RIGHT();
  int s3=EQUAL();
  cout<<(s1+s2+s3)%mod<<endl;
}



Measured memory_bytes: 3228
s = input()
t = input()
n_s = len(s)
n_t = len(t)

ans_li = []
for i in range(n_s-n_t+1):
    u = s[i:i+n_t]
    flag = True
    for j in range(len(u)):
        if (u[j]!='?' and u[j]==t[j]) or u[j]=='?':
            continue
        flag = False
    if flag:
        ans_li.append(s[:i].replace('?','a')+t+s[i+n_t:].replace('?','a'))
if ans_li==[]:
    print('UNRESTORABLE');exit()
ans_li.sort()
print(ans_li[0])

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


int main(){
	bool kind[8]={false};

	int n;	cin>>n;
	int tmp=0;
	for(int i=0;i<n;i++){
		int a;	cin>>a;
		if(a>=3200){
			tmp++;
		}else{
			kind[a/400]=true;
		}
	}

	int ans=0;
	for(int i=0;i<8;i++){
		ans+=kind[i];
	}

	printf("%d %d\n", max(1,ans),ans+tmp);

	return 0;
}


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

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

Measured memory_bytes: 3604
#include <bits/stdc++.h>
#define rep(i, x, N) for (int i = x; i < (N); i++)
using namespace std;
int main()
{
    string s, t, ans;
    int n;
    cin >> n >> s >> t;
    for (int i = 0; i < n; i++)
    {
        cout << s[i] << t[i];
    }
    cout << endl;
}


Measured memory_bytes: 256
import heapq

x,y,a,b,c = map(int,input().split())
r = list(map(int,input().split()))
g = list(map(int,input().split()))
w = list(map(int,input().split()))

r.sort(key = lambda x:-x)
g.sort(key = lambda x:-x)
w.sort(key = lambda x:-x)


rg = []
for i in range(x):
    rg.append(r[i])

for i in range(y):
    rg.append(g[i])

rg.sort(key = lambda x:x)


ind = 0
ans = 0
for i in range(x+y):
    if ind <= c-1 and w[ind] > rg[i]:
        ans += w[ind]
        ind += 1
    else:
        ans += rg[i]

print(ans)

Measured memory_bytes: 121956
import sys
input = sys.stdin.readline
N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

ans = B[A[0]-1]
for i in range(1,N) :
    ans += B[A[i]-1]
    if A[i] - A[i-1] == 1 :
        ans += C[A[i-1]-1]

print(ans)


Measured memory_bytes: 3064
#define _[2<<17]
n,i;B _,T _,F _;long M,D _,P _,R _;s(u,i,p,I){R[i]=i?s(u,T[i],p),(I=B[i])-p?s(I,F[I],u),D[u]=D[u]*-~D[I]%M:D[u]:++D[u];}S(u,x,p,i,I){for(i=F[u];I=B[i];I-p?S(I,R[i]*x%M+1,u),x=x*-~D[I]%M:0)i=T[i];P[n-u]=x%M;}main(u,v){for(;~scanf("%d%d",&u,&v);)i++?T[i-1]=F[u],T[i]=F[B[F[u]=i-1]=v],B[F[v]=i++]=u:(n=u,M=v);s(1,F[1]);for(S(1,1);n--;)printf("%d ",P[n]);}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

#define DEBUG(x) cout<<#x<<": "<<x<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

#define CHMIN(a, b) a=min((a), (b))
#define CHMAX(a, b) a=max((a), (b))

const ll MOD=1000000007ll;
// const ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, i;
	cin>>n>>i;
	cout<<n-i+1<<'\n';
	return 0;
}


Measured memory_bytes: 256
<?php
	fscanf( STDIN, "%d", $t );
	$h = intval( $t / 3600 );
	$m = intval( ( $t % 3600 )/60 );
	$s = intval( ( $t % 3600 )%60 );
	echo $h, ":", $m, ":", $s;
?>

Measured memory_bytes: 6520
#include <iostream>
#include <algorithm>
#define DAY_LENGTH 86400
#define FOUR_TO_SEVEN 10800
using namespace std;

bool check(int k, int ts[], int n) {
    for (int i = 0; i <= 2 * n - k; i++) {
        if (ts[k - 1 + i] - ts[i] <= FOUR_TO_SEVEN)
            return true;
    }
    return false;
}

int main() {
    int n;
    cin >> n;
    int ts[n << 1], t = 0;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        ts[i] = (t + a) % DAY_LENGTH;
        t = (ts[i] + b) % DAY_LENGTH;
    }
    sort(ts, ts + n);
    for (int i = 0; i < n; i++) {
        ts[i + n] = ts[i] + DAY_LENGTH;
    }

    int lb = 0, ub = n + 1, ans = 0;
    for (int mid = (lb + ub) / 2; ub - lb > 1; mid = (lb + ub) / 2) {
        if (check(mid, ts, n)) {
            ans = mid;
            lb = mid;
        } else {
            ub = mid;
        }
    }
    cout << ans << endl;
    return 0;
}


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

int main() {
    string s1,s2,s3;
    cin>>s1>>s2>>s3;
    vector<char>v;
    v.push_back(s1[0]-'a');
    v.push_back(s2[0]-'a');
    v.push_back(s3[0]-'a');
    for(int i=0;i<v.size();i++){
        cout<<char(v[i]+65);
    }
}

Measured memory_bytes: 256