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

using namespace std;
#define taskname "TEST"
#define pb	push_back
typedef long double ld;
typedef long long ll;
const int maxn = 1e4 + 5;
const int mod = 1e9 + 7;
string s;

int dp[maxn][101][2] , d;
int cal(int pos , int m , bool pre)
{
    if(pos == s.size())return m == 0;
    int & res = dp[pos][m][pre];
    if(res != -1)return res;
    res = 0;
    int lim = (pre == 1 ? 9 : s[pos] - '0');
    for(int i = 0 ; i <= lim ; ++i)
    {
        res += cal(pos + 1 , (m + i) % d , pre | (i < lim));
        if(res >= mod)res -= mod;
    }
    return res;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	if(fopen(taskname".INP","r"))
        freopen(taskname".INP", "r",stdin) ,
        freopen(taskname".OUT", "w",stdout);
    fill_n(&dp[0][0][0],maxn*101*2,-1);
    cin >> s >> d;
    cout << (cal(0,0,0) - 1 + mod) % mod;
}


Measured memory_bytes: 9088
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define eb emplace_back
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
constexpr ll INF = (1LL << 30) - 1LL;
constexpr ll MOD = 1e9 + 7;
template <class T>
void chmin(T &a, T b) { a = min(a, b); }
template <class T>
void chmax(T &a, T b) { a = max(a, b); }
void ok() { cerr << "ok" << endl; }
template <class T>
struct Matrix {
    vector<vector<T>> a;
    Matrix() {}
    Matrix(int n, int m) : a(n, vector<T>(m)) {}
    inline const vector<T> &operator[](int k) const {
        return a.at(k);
    }
    inline vector<T> &operator[](int k) {
        return a.at(k);
    }
    Matrix I(int n) {
        Matrix mat(n, n);
        for (int i = 0; i < n; i++) {
            mat[i][i] = 1;
        }
        return mat;
    }
    Matrix &operator+=(const Matrix &rhs) {
        for (int i = 0; i < a.size(); i++) {
            for (int j = 0; j < a[i].size(); j++) {
                (*this)[i][j] += rhs[i][j];
            }
        }
        return (*this);
    }
    Matrix &operator-=(const Matrix &rhs) {
        for (int i = 0; i < a.size(); i++) {
            for (int j = 0; j < a[i].size(); j++) {
                (*this)[i][j] -= rhs[i][j];
            }
        }
        return (*this);
    }
    Matrix &operator*=(const Matrix &rhs) {
        int n = a.size(), m = a[0].size(), p = rhs[0].size();
        assert(m == rhs.a.size());
        vector<vector<T>> b(n, vector<T>(p));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < p; j++) {
                for (int k = 0; k < m; k++) {
                    b[i][j] += (*this)[i][k] * rhs[k][j];
                }
            }
        }
        swap(a, b);
        return (*this);
    }
    Matrix &operator^=(const long long &rhs) {
        long long n = rhs;
        Matrix res = Matrix::I(a.size());
        while (n > 0) {
            if (n & 1) {
                res *= (*this);
            }
            (*this) *= (*this);
            n >>= 1;
        }
        swap(a, res.a);
        return (*this);
    }
    Matrix operator+(const Matrix &rhs) const {
        return Matrix(*this) += rhs;
    }
    Matrix operator-(const Matrix &rhs) const {
        return Matrix(*this) -= rhs;
    }
    Matrix operator*(const Matrix &rhs) const {
        return Matrix(*this) *= rhs;
    }
    Matrix operator^(const long long &rhs) const {
        return Matrix(*this) ^= rhs;
    }
};
int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    Matrix<ll> a(2, 2), b(2, 1), res;
    a[0][1] = 1, a[1][0] = 1, a[1][1] = 1;
    b[0][0] = 1, b[1][0] = 1;
    if (n == 0) {
        cout << 1 << endl;
        return 0;
    }
    res = (a ^ (n - 1)) * b;
    cout << res[1][0] << endl;
}


Measured memory_bytes: 3240
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int, int>
#define vi vector<int>
#define pb emplace_back
#define sz(x) (int)x.size()
#define all(v) v.begin(), v.end()
#define x first
#define y second
#define rep(i, j, k) for(i=j; i<k; i++)
#define sep(i, j, k) for(i=j; i>k; i--)
const int N = 2e5+5, inf = 1e9+7;
int n, k, i, j;
int A[N];
int dp[N];
signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    int i, j, a, b, ans = 0;
    cin>>n;
    rep(i, 1, n+1) cin>>A[i];
    dp[n+1] = inf*inf;
    sep(i, n-1, 0) dp[i] = min(dp[i+1] + abs(A[i]-A[i+1]), dp[i+2] + abs(A[i]-A[i+2]));
    cout<<dp[1];
}

Measured memory_bytes: 1792
#include<stdio.h>
#include<string.h>
int main(){
    char str[1001],p[1001],command[8],t;
    int a,b,c,i,q;
    scanf("%s",str);
    scanf("%d",&q);
    for(i=0;i<q;i++){
        scanf("%s",command);
        if(command[0]=='p'){
            scanf("%d",&a);
            scanf("%d",&b);
            for(;a<=b;a++){
                printf("%c",str[a]);
            }
            printf("\n");
        }else if(command[2]=='v'){
            scanf("%d",&a);
            scanf("%d",&b);
            for(;a<=b;a++){
                t=str[a];
                str[a]=str[b];
                str[b]=t;
                b--;
            }
        }else{
            scanf("%d",&a);
            scanf("%d",&b);
            scanf("%s",p);
            c=0;
            for(;a<=b;a++){
                str[a]=p[c];
                c++;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 2104
N = int(input())
ARR = list(map(int,input().split()))

def calculate(n,arr):

    result = [set() for i in range(n)]

    for index,ar in enumerate(arr):
        ar = ar - 1
        result[ar].add(index+1)


    for res in result:
        print(len(res))

calculate(N,ARR)

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

#define ll long long
#define UN unsigned
#define pb push_back
#define mod 1000000007
#define mt make_tuple
typedef tuple<int, int> tii;
typedef pair<int, int> pii;

const int N = 1e5 + 5;

void solve(){
    int n;
    cin >> n;

    vector<int> a(n), b(n), c(n);
    for(int i=0; i<n; i++){
        cin >> a[i] >> b[i] >> c[i];
    }

    int dp[N][3];
    dp[0][0] = a[0], dp[0][1] = b[0], dp[0][2] = c[0];

    for(int i=1; i<=n-1; i++){
        for(int j=0; j<3; j++){
            dp[i][j] = max(dp[i-1][(j+1)%3], dp[i-1][(j+2)%3]);
            if(j == 0)
                dp[i][j] += a[i];
            else if(j == 1)
                dp[i][j] += b[i];
            else
                dp[i][j] += c[i];
        }
    }

    cout << max(dp[n-1][0], max(dp[n-1][1], dp[n-1][2]));
}

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cerr.tie(nullptr);
    solve();
    return 0;
}

Measured memory_bytes: 2560
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <cassert>
#include <memory>
#include <stack>
#include <set>
#include <map>
#include <cctype>
#include <climits>
#include <list>
#include <queue>

#define INF 1000000000
#define MOD 1000000007
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

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

  int a[3];
  for(int i=0; i<3; i++) {
    cin>>a[i];
  }
  int b = a[0] * 100 + a[1] * 10 + a[2];

  string ans;
  if(b % 4 == 0) {
    ans = "YES";
  } else {
    ans = "NO";
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
def one_dimensional_worlds_tale(
        N: int, M: int, X: int, Y: int, x: list, y: list) -> bool:
    border_x = max([X] + x)
    border_y = min([Y] + y)
    return border_x < border_y


if __name__ == "__main__":
    N, M, X, Y = map(int, input().split())
    x = [int(s) for s in input().split()]
    y = [int(s) for s in input().split()]
    ans = one_dimensional_worlds_tale(N, M, X, Y, x, y)
    print('War' if not ans else 'No War')


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

int main(){

  int n;
  string s;
  cin >> n >> s;
  int ans = 0;
  for(int i = 0; i <= n - 3; i++) {
    if(s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C'){
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}


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

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPl(i, n) for (ll i = 0; i < (ll)(n); i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define REPRl(i, n) for(ll i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < (int)n; i++)
#define FORl(i, m, n) for(ll i = m; i < (ll)n; i++)
#define ALL(v) v.begin(), v.end()
ll gcd(ll a,ll b) {
  return b? gcd(b,a%b): a;  
}
ll lcm(ll a,ll b) {
  return a*b/gcd(a,b);
}
bool isLowerCase(char c){
  return (c>='a'&&c<='z');
}
int main() {
  string s,t;cin>>s>>t;
  cout << t<<s << endl;
}

Measured memory_bytes: 256
s=list(input())
s1=[]
for i in range(len(s)):
  if s[i]!="x":
    s1.append(s[i])
s2=s1[::-1]
if s1!=s2:
  print(-1)
  exit()
if s1==[]:
  print(0)
  exit()
A1=[0]*10**5
A2=[0]*10**5
i=0
j=0
while i<=len(s1)//2:
  if s[j]=="x":
    A1[i]+=1
    j=j+1
  else:
    i=i+1
    j=j+1
i=0
j=0
while i<=len(s1)//2:
  if s[-1-j]=="x":
    A2[i]+=1
    j=j+1
  else:
    i=i+1
    j=j+1
ans=0
for i in range(10**5):
  ans=ans+abs(A1[i]-A2[i])
print(ans)

Measured memory_bytes: 7084
N, M ,C = map(int, input().split())
B = list(map(int, input().split()))
n = 0
for i in range(N):
    a = list(map(int, input().split()))
    AB = [x * y for (x, y) in zip(a,B)]

    if sum(AB) > -C:
        n += 1

print(n)


Measured memory_bytes: 9052
#include<algorithm>
#include<iostream>
#include<functional>
#include<cmath>
#include<iomanip>
using namespace std;
int main(){
  int n,x[110000];
  cin>>n;
  for(int i=1;i<n+1;i++){
    cin>>x[i];
  }
  int ans=0;
  for(int i=1;i<n+1;i++){
    int k;
    k=x[i];
    if(x[k]==i)
      ans++;
  }
  cout<<ans/2<<endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define rep2(i, s, n) for (ll i = s; i < (ll)(n); i++)
#define repr(i, n) for (ll i = n; i >= 0; i--)
#define pb push_back
#define COUT(x) cout << (x) << endl
#define COUTF(x) cout << setprecision(15) << (x) << endl
#define ENDL cout << endl
#define DF(x) x.erase(x.begin())  // 先頭文字削除
#define ALL(x) x.begin(), x.end()
#define SORT(x) sort(ALL(x))
#define REVERSE(x) reverse(ALL(x))
#define init() \
  cin.tie(0);  \
  ios::sync_with_stdio(false)
#define debug(x) cerr << "[debug] " << #x << ": " << x << endl;
#define debugV(v)                       \
  cerr << "[debugV] " << #v << ":";     \
  rep(i, v.size()) cerr << " " << v[i]; \
  cerr << endl;
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using P = pair<ll, ll>;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
constexpr ld PI = 3.141592653589793238462643383279;
ll get_digit(ll x) {
  return to_string(x).size();
}

ll gcd(ll x, ll y) {
  return y ? gcd(y, x % y) : x;
}

ll lcm(ll a, ll b) {
  return a / gcd(a, b) * b;
}

vector<P> factorize(ll n) {
  vector<P> result;
  for (ll i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      result.pb({i, 0});
      while (n % i == 0) {
        n /= i;
        result.back().second++;
      }
    }
  }
  if (n != 1) {
    result.pb({n, 1});
  }
  return result;
}

vll divisor(ll n) {
  vll ret;
  for (ll i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      ret.push_back(i);
      if (i * i != n) ret.push_back(n / i);
    }
  }
  SORT(ret);
  return (ret);
}

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

signed main() {
  init();
  ll N, M;
  cin >> N >> M;

  vector<vll> to(N);

  rep(i, M) {
    ll a, b;
    cin >> a >> b;
    a--;
    b--;
    to[a].pb(b);
    to[b].pb(a);
  }

  vll keiro;
  rep(i, N) {
    if (i == 0) continue;
    keiro.pb(i);
  }

  ll ans = 0;
  do {
    vll keiro2 = keiro;
    keiro2.insert(keiro2.begin(), 0);
    bool flag = true;
    rep(i, N - 1) {
      ll a = keiro2[i];
      ll b = keiro2[i + 1];
      bool exist = find(ALL(to[a]), b) != to[a].end();
      if (!exist) {
        flag = false;
        break;
      }
    }

    if (flag) {
      ans++;
    }

  } while (next_permutation(ALL(keiro)));

  COUT(ans);

  return 0;
}

Measured memory_bytes: 3644
while True:
    N = input()
    if N == 0: break
    p = map(int, raw_input().split())
    n = 32
    c = 1
    i = 0
    while n:
        if c % 2 != 0:
            s = (n - 1) % 5
        else:
            if p[i] <= n:
                s = p[i]
            else:
                s = n
            if i == N-1:
                i = 0
            else:
                i += 1
        n -= s
        print n
        c += 1

Measured memory_bytes: 4232
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,s=0,d=0;
    int clr[9]={0,0,0,0,0,0,0,0,0};
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>m;
        if(m>=1&&m<=399) clr[0]++;
        if(m>=400&&m<=799) clr[1]++;
        if(m>=800&&m<=1199) clr[2]++;
        if(m>=1200&&m<=1599) clr[3]++;
        if(m>=1600&&m<=1999) clr[4]++;
        if(m>=2000&&m<=2399) clr[5]++;
        if(m>=2400&&m<=2799) clr[6]++;
        if(m>=2800&&m<=3199) clr[7]++;
        if(m>=3200) clr[8]++;
    }
    for(int i=0;i<8;i++)
    {
        if(clr[i]>0) d++;
    }
    s=d;
    s+=clr[8];
    if(d==0) d=1;
    cout<<d<<" "<<s<<endl;
    return 0;
}


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

namespace C
{
	internal class Program
	{
		public static void Main(string[] args)
		{
			var line = Console.ReadLine().Split().Select(int.Parse).ToArray();
			var n = line[0];
			var y = line[1] / 1000;

			var a = -1;
			while (true)
			{
				a++;

				if (9 * a > y - n) { break; }

				if ((y - n - 9 * a) % 4 == 0)
				{
					var b = (y - n - 9 * a) / 4;
					if (a + b > n) { continue; }

					Console.WriteLine($"{a} {b} {n - a - b}");
					return;
				}
			}

			Console.WriteLine("-1 -1 -1");
		}
	}
}

Measured memory_bytes: 13396
penki = [i for i in map(int, input().split())]
count = 3
if penki[0] == penki[1]:
    count -= 1
if penki[0] == penki[2]:
    count -= 1
if penki[1] == penki[2]:
    count -= 1
if penki[1] == penki[2] == penki[0]:
    count += 1
print(count)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
map<string,int >us;
string a[1<<17];
int sum[1<<17];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i]>>sum[i];
	for(int i=n-1;i;--i)
		sum[i]+=sum[i+1],us[a[i]]=sum[i+1];
	string ha;
	cin>>ha;
	cout<<us[ha];
	return 0;
}

Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int h , w;
  cin >> h >> w;
  char c[55][55];
  for(int i=1;i<=h;i++)
    {
      for(int j=1;j<=w;j++)cin >> c[i][j];
    }

  for(int i=1;i<=h;i++)
    for(int j = 1;j<=w;j++)
      {
	if(c[i][j] == '#')
	  {
	    if(c[i -1][j] =='.' && c[i + 1][j] == '.' && c[i][j - 1] =='.' && c[i][j + 1]=='.')
	      {
	      cout << "No" << endl;
	      return 0;
	       }
	  }

      }
  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int main() {
  string S;
  cin >>S;
 if(S=="SUN") {
   cout <<7 << endl;
 }
  else if(S=="MON") {
   cout <<6 << endl;
 }
 else if(S=="TUE") {
   cout <<5 << endl;
 }
 else if(S=="WED") {
   cout <<4 << endl;
 }
  else if(S=="THU") {
   cout <<3 << endl;
 }
  else if(S=="FRI") {
   cout <<2 << endl;
 }
 else if(S=="SAT") {
   cout <<1 << endl;
 }
}
  
 

Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <queue>

#pragma warning( disable: 4996 )

using namespace std;

typedef long long ll;

#define INF 100000000
#define EPS 1e-9

#define MAX_N 1234570

bool prime[MAX_N];
int dp[MAX_N];

vector<int> ans_list;

int main(){

	prime[0] = prime[1] = true;

	for (int i = 1; i < MAX_N; i++){
		dp[i] = dp[i - 1];
		if (!prime[i]){
			dp[i]++;
			for (int j = 2; i * j < MAX_N; j++){
				prime[i*j] = true;
			}
		}
	}

	while (true){
		int n;
		cin >> n;
		if (n == 0)
			break;

		ans_list.push_back(dp[2*n] - dp[n]);

	}

	for (int i = 0; i < ans_list.size(); i++){
		cout << ans_list[i] << endl;
	}


	return 0;

}

Measured memory_bytes: 7248
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	int n, k;
	cin >> n >> k;
	vi v(n);
	for (auto & i : v) cin >> i;
	ll sum = 0;
	vi sum1(n + 1), sum2(n + 1);
	REP(i, n)
	{
		sum += v[i];
		sum1[i + 1] = sum1[i] + v[i];
		sum2[i + 1] = sum2[i];
		if (v[i] > 0) sum2[i + 1] += v[i];
	}
	ll ans = 0;
	REP(i, n - k + 1)
	{
		ll a = sum2[i] + sum2[n] - sum2[i + k];
		ll b = max(0ll, sum1[i + k] - sum1[i]);
		chmax(ans, a + b);
	}
	cout << ans << endl;
	return 0;
}

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

int main()
{
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    rep(i, N) cin >> A.at(i);

    int res = 0;
    int right = 0;

    while (right < N) {
        if (right == 0) {
            right += K;
        } else {
            right += K - 1;
        }
        res++;
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 640
n = gets.chomp.to_i
a = []
n.times do
  a << gets.chomp.to_i
end
ans = 0
n.times do |i|
  ans += a[i] / 2
  if a[i] % 2 == 1  && i != n - 1 then
    if a[i + 1] != 0 then
      ans += 1
      a[i + 1] -= 1
    end
  end
end
puts ans


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

template <typename _tp> inline void read(_tp&x){
	char ch=getchar(),ob=0;x=0;
	while(ch!='-'&&!isdigit(ch))ch=getchar();if(ch=='-')ob=1,ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();if(ob)x=-x;
}

/*
a_n a_{n-1} ... a_2 a_1
+
d_n d_{n-1} ... d_2 d_1
=
a_1 a_2 ... a_{n-1} a_n
*/

/*
dp :
                (t)
... a[n-i] ... a[i+1] a[i] ...
... d[n-i] ... d[i+1] d[i] ...
   j      J   K      k
... a[i+1] ... a[n-i]
*/

const int N = 19;
int f[2][2][N], d[N];

int work(int n) {
	for(int i=0;i<=n;++i)
		f[0][0][i] = f[0][1][i] = f[1][0][i] = f[1][1][i] = 0;
	f[0][0][0] = 1;
	
	int ani, K, J;
	for(int i=0;i<(n>>1);++i)
	for(int j=0;j<2;++j)
	for(int k=0;k<2;++k) if(f[j][k][i])
		for(int t = 0; t < 10; ++ t) {
			ani = (t + d[i+1] + k)%10; // ani : a[n-i]
			K = (t + d[i+1] + k) >= 10;
			J = (j*10+t) - (d[n-i]+ani);
			if(J and J != 1) continue;
			if(!i and (!t or !ani)) continue;
			f[J][K][i+1] += f[j][k][i];
		}
	
	if(~n&1) return f[0][0][n>>1] + f[1][1][n>>1];
	int p = n + 1 >> 1, res = 0;
	for(int k = 0; k < 2; ++ k)
		for(int t = 0; t < 10; ++ t)
			if((t + d[p] + k)%10 == t)
				res += f[(t+d[p]+k)>=10][k][n>>1];
	return res;
}

int main() {
	int x, t = 0;
	for(read(x); x; x /= 10) d[++t] = x%10;
	int Ans = 0;
	for(int n = t; n <= (t<<1); ++ n)
		Ans += work(n);
	printf("%d\n", Ans);
	return 0;
}

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

int main(void)
{
    int N, r, l;
    int ans = 0;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> l >> r;
        ans += r - l + 1;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
//code by 27.
#include<stdio.h>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<math.h>
#include<vector>
#include<queue>
#include<map>
#include<stack>
#include<fstream>
#include<stdlib.h>
#include<set>
#include<cassert>
#include<climits>
#include<cmath>
#include<memory.h>
using namespace std;
const int MOD=1e9+7;
long long ypa(long long n,long long k)//a^
{
	//cout<<"3";                                                                                                                                                  
	if(k==1)return n;
	if(k==0)return 1;
	long long t=ypa(n,k/3);
	if(k%3==0)return t*t%MOD*t%MOD;
	else if(k%3==1)return t*t%MOD*t%MOD*n%MOD;
	else if(k%3==2)return t*t%MOD*t%MOD*n%MOD*n%MOD;
}
long long c(long long a,long long b)
{
	//cout<<"2"<<endl;
	a=min(a,b-a);
	if(a==0)return 1;
	long long s1=1,s2=1;
	for(int i=1;i<=a;i++)
	{
		s1*=i;
		s1=s1%MOD;
		s2*=i+b-a;
		s2=s2%MOD;
	}
	return s2*ypa(s1,MOD-2)%MOD;
}
int main()
{
	long long n,m,a,b;
	cin>>n>>m>>a>>b;
	long long s=0;
	long long s1=c(n-a-1,n-a+b-2);
	long long s2=c(a-1,m+a-b-1);
	for(long long i=b+1;i<=m;i++)
	{
		s1=s1*(n-a+i-2)%MOD*ypa((n-a+i-3-(n-a-1)+1),MOD-2)%MOD;
		s2=s2*(m+a-i-(a-1))%MOD*ypa(m+a-i,MOD-2)%MOD;
		//cout<<i<<"---"<<"s1:"<<s1<<"from:*"<<n-a+i-2<<"/"<<n-a+i-3-(n-a-1)+1<<"        ";
		//cout<<"s2:"<<s2<<"from:*"<<m+a-i-(a-1)<<"/"<<m+a-i<<endl;
		s+=s1*s2%MOD;
		s=s%MOD;
	}
	cout<<s;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int A,B,C;
int main(){
	cin>>A>>B>>C;
	if(B>A) swap(A,B);
	if(C>A) swap(A,C);
	if(C>B) swap(B,C);
	int ans=(A-B);
	C+=(A-B);
	B=A;
	ans+=(A-C)/2;
	if((A-C)%2==1) ans+=2;
	cout<<ans;
	return 0;
}


Measured memory_bytes: 256
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<string> vs;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define REPR(i,n) for(int i=n-1;i>=0;i--)
#define FORR(i,n,m) for(int i=n-1;i>=m;i--)
#define all(in) in.begin(),in.end()
#define ALL(in,K) in,in+K
#define INF 1e18
#define MOD 100000007
#define SIZE 105005
#define PI 	3.14159265358979323846

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int h[100000];
    for(int i=0;i<n;i++){
        cin >> h[i];
    }
    long long int ans[100000];
    fill(ans,ans+n,INF);
    ans[0] = 0;
    for(int i=0;i<n-1;i++){
        ans[i+1] = min(ans[i+1],ans[i]+abs(h[i]-h[i+1]));
        ans[i+2] = min(ans[i+2],ans[i]+abs(h[i]-h[i+2]));
    }
    cout << ans[n-1] << endl;
    return 0;
}


Measured memory_bytes: 1408
#include <stdio.h>

int main(void){
  int x,a,b;
  scanf("%d %d %d",&x,&a,&b);
  if((b-a)<=0)
    printf("delicious\n");
  else if((b-a)<=x)
    printf("safe\n");
  else
    printf("dangerous\n");
  return 0;
}


Measured memory_bytes: 128
import java.math.BigInteger;
import java.util.Scanner;

class Main {
    public static void main(String... args) {
        Scanner IN   = new Scanner(System.in);
        String S     = IN.next();
        long K = IN.nextLong();
        System.out.println(calc(K, 0, S));
    }

    public static Character calc(long k, int i, String s) {
        if (k == 1) {
            return s.charAt(i);
        } else {
            if (s.charAt(i) != '1') {
                return s.charAt(i);
            } else {
                return calc(k - 1, i + 1, s);
            }
        }
    }
}


Measured memory_bytes: 23636
#include<bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds;
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout) 
#define lli long long int
#define pb push_back
#define pob pop_back
#define rep(i,a,b) for(lli i=a;i<b;i++)
#define repv(a,b) for(int i=a;i>=b;i--)
#define itr vector<lli> :: iterator
#define maximum(a,b,c)  max(a,max(b,c))
#define minimum(a,b,c) min(a,min(b,c))
#define tim clock_t
#define db double
inline void fast()
{
	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL);
}


void solve(lli n)
{
	
}
	
int main()
{
	fast();
	
	lli t,n,sum;
	string s;
	cin>>t>>s;
	if(t<3200)
		cout<<"red";
	else cout<<s;

	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <queue>
#include <map>
#include <fstream>
#include <array>
#include <utility>
#include <functional>
#include <stack>

using namespace std;
typedef long long Int;
#define REP(i , x) for(int i = 0 ; i < x ; ++i)

typedef pair<int, int> P;

Int ans;

int main()
{
	int n;
	while (cin >> n){
		ans = 0;
		for (int i = 0; i < 600;i+= n){
			ans += i*i*n;
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1156
import sys
from functools import lru_cache

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, A, B, C = map(int, readline().split())
    (*L,) = map(int, read().split())

    @lru_cache(maxsize=None)
    def rec(i, a, b, c):
        if i == N:
            return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else INF

        res0 = rec(i + 1, a, b, c)
        res1 = rec(i + 1, a + L[i], b, c) + 10
        res2 = rec(i + 1, a, b + L[i], c) + 10
        res3 = rec(i + 1, a, b, c + L[i]) + 10

        return min(res0, res1, res2, res3)

    print(rec(0, 0, 0, 0))
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 22952
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=500010;
int f[M],a[M],n,lastzero;	//a[M]前一个0的位置 
char c[M];
int main()
{
	scanf("%d%s",&n,c+1);
//	scanf("%s",c+1);
	for(int i=1;i<=n;i++)
	{
		if(c[i]=='0')
			lastzero=i;
		a[i]=lastzero;
//		cout<<a[i]<<" ";
	}
	for(int i=1;i<=n;i++)
	{
		f[i]=f[i-1];
		if(c[i]=='1')
		{
/*			if(a[i]>1&&c[a[i]-1]=='1')
				f[i]=max(f[i],f[a[i]-2]+i-a[i]);	//以上一个101向后合并
			else if(c[i-1]=='0'&&c[i-2]=='1')
			{
				f[i]=max(f[i],f[a[i-2]]+i-2-a[i-2]);//这个1...101向左合并
				f[i]=max(f[i],f[a[i-2]+1]+i-3-a[i-2]);//与前面的1合并 
			} */
			if (c[i-1] =='0'&&c[i-2] == '1') {
                f[i]=max(f[i],f[a[i-2]]+(i-2)-a[i-2]);
                f[i]=max(f[i],f[a[i-2]+1]+(i-2)-(a[i-2]+1));
            }
            else if(a[i]>1&&c[a[i]-1]=='1')f[i]=max(f[i],f[a[i]-2]+i-a[i]);
		}
	}
	printf("%d\n",f[n]);
	return 0;
} 

Measured memory_bytes: 4608
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include <cmath>
#include <limits>
#include<set>
#include <iomanip>
#include <queue>
#include <map>
#include <string>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
const long long INF=(1LL<<62);
const double inf=pow(10,10);
double pi=3.141592653589793;
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const ll MOD = 1000000007;
void init(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
}

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

long long lcm(long long a,long long b){
	return a/gcd(a,b)*b;
}

int main(){
	init();
	ll x,t;cin>>x>>t;
	cout<<max(x-t,0LL)<<endl;
}


Measured memory_bytes: 256
## B - Guidebook
N = int(input())
val = []
for n in range(N):
    S, P = map(str, input().split())
    val.append([n+1, S, int(P)])
val = sorted(val, key=lambda x:(x[1],-x[2]))
for n in range(N):
    print(val[n][0])

Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-8;
const int inf=1e8;
//map<int,vp>tG;
//vector<map<int,vi> >tG;
map<int,map<int,bool> >tG;
/*int f(int a,int b){
	int r=-1,l=tG[a].size();
	while(l-r>1){
		int h=(r+l)/2;
		if(tG[a][h]<b)r=h;
		else l=h;
	}
	return l;
}*/
int main(){
	ll h,w,n;
	cin>>h>>w>>n;
	vector<ll>out(10);
	out[0]=(h-2)*(w-2);
	vp in(n);
	rep(i,n)cin>>in[i].first>>in[i].second;
//	tG=vector<map<int,vi> >(10010);
	rep(q,n){
		vvi G(5,vi(5));
		rep(i,5)rep(j,5){
			int x=in[q].first-2+i;
			int y=in[q].second-2+j;
			if(x<=0||y<=0||x>h||y>w)G[i][j]=-1;
		}
		loop(i,in[q].first-2,in[q].first+3)
			loop(j,in[q].second-2,in[q].second+3)if(tG[i][j]){
				G[i-in[q].first+2][j-in[q].second+2]=1;
//				if(x>=0&&x<5&&y>=0&&y<5)G[x][y]=1;
		}
//		rep(i,5){rep(j,5)cout<<" "<<G[i][j];cout<<endl;}
//		cout<<endl;
		rep(i,3)rep(j,3){
			int co=0;
			bool h=true;
			rep(k,3)rep(l,3)if(G[i+k][j+l]==-1)h=false;
			else if(G[i+k][j+l]==1)co++;
			if(!h)continue;
			out[co]--;
			out[co+1]++;
		}
//		tG[in[q].first/1000].pb(pii(in[q].second,in[q].first));
//		tG[in[q].first/100000][in[q].second].pb(in[q].first);
		tG[in[q].first][in[q].second]=1;
	}
	rep(i,10)cout<<out[i]<<endl;
}






Measured memory_bytes: 165120
import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long x = sc.nextLong();
        if (360 % x == 0) {
            System.out.println(360 / x);
        } else {
            long lcm = lcm(x, 360);
            System.out.println(lcm / x);
        }
    }

    private static long gcd(long a, long b) {
        long r;
        while( (r = a % b) != 0 ) {
            a = b;
            b = r;
        }
        return b;
    }

    private static long lcm(long a, long b) {
        return a * b / gcd(a,b);
    }
}


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

#include <iostream>
#include <vector>
#include <math.h>

std::unordered_map<long, int> mp;

int main(void) {
  int x;

  scanf("%d", &x);

  int xd = 0;
  int d = 1;
  for (long i = 0;; i++) {
    xd += x;
    if ((xd % 360) == 0){
      printf("%ld", i+1);
      return 0;
    }
  }

 

  return 0;
}

Measured memory_bytes: 3756
N = int(input())
num = list(map(int, input().split()))
max_count = 0
count = 0
for i in range(len(num)-1):
  if num[i] >= num[i+1]:
    count += 1
    if count > max_count:
      max_count = count
  elif num[i] < num[i+1]:
    count = 0
print(max_count)

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

const ll mod=1e9+7;
const int mxn=1e3+10;
ll dp[mxn][mxn];
char grid[mxn][mxn];
ll n,m;

inline ll add(ll a,ll b){
	return (a%mod + b%mod)%mod;
}

int main(){
	ll i,j;
	cin >> n >> m;
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			cin >> grid[i][j];
		}
	}
	dp[0][0]=1;
	dp[1][1]=1;
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			if(grid[i][j]=='.'){
				dp[i][j]=add(dp[i][j],dp[i-1][j]);
				dp[i][j]=add(dp[i][j],dp[i][j-1]);
			}
		}
	}
	cout << dp[n][m] << endl;
}

Measured memory_bytes: 12340
/*
    Take me to church
    I'll worship like a dog at the shrine of your lies
    I'll tell you my sins and you can sharpen your knife
    Offer me that deathless death
    Good God, let me give you my life
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, A[N];
int main()
{
    scanf("%d", &n);
    long long SM = 0;
    for (int i = 1; i <= n; i ++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        SM -= b; A[i] = a + b;
    }
    sort(A + 1, A + n + 1);
    for (int i = n; i > 0; i -= 2)
        SM += A[i];
    return !printf("%lld\n", SM);
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define deb(x) cout<< #x << " " << x << "\n";
#define INF 9223372036854775807
const ll mod=998244353;

ll n,m,k;
ll ans=0;

bool check(vector<string> a){
    ll r=0;
    for(ll i=0;i<n;i++){
        for(ll j=0;j<m;j++){
            if(a[i][j]=='#')
                r++;
        }
    }
    if(r==k)
        return true;
    return false;
}

void solve(ll i, ll j,vector<string> a){
    if(i==n && j==m){
        if(check(a))
            ans++;
        return;
    }
    i=min(i,n-1);
    j=min(j,m-1);
    solve(i+1,j+1,a);
    vector<string> b=a;
    for(ll r=0;r<m;r++)
        b[i][r]='-';
    solve(i+1,j+1,b);
    for(ll r=0;r<n;r++)
        a[r][j]='-';
    solve(i+1,j+1,a);
    for(ll r=0;r<n;r++)
        b[r][j]='-';
    solve(i+1,j+1,b);
}
 
int main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>n>>m>>k;
    vector<string> a(6);
    for(ll i=0;i<n;i++)
        cin>>a[i];
    solve(0,0,a);
    cout<<ans;





    return 0;
}

Measured memory_bytes: 3636
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        Map<String, Integer> map = new TreeMap<>();
        for(int i = 0; i < num; i++){
            String word = sc.next();
            if(map.containsKey(word))
              map.put(word, map.get(word)+1);
            else
              map.put(word, 1);
        }

        int most = 0;
        for(String n: map.keySet()){
          if(map.get(n) > most)
            most = map.get(n);
        }
        for(String n: map.keySet()){
          if(map.get(n) == most)
            System.out.println(n);
        }
    }
}


Measured memory_bytes: 85144
// #pragma GCC optimize("O3", "unroll-loops")
// #pragma GCC target("avx2")

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

typedef long long int ll;

#define endl '\n'
#define int long long
#define pb push_back
#define pii pair <int, int>
#define ff first
#define ss second
#define point pair <double, double>
#define watch(x) cerr << "\n" << (#x) << " is " << (x) << endl

void __print(int x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "\n[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

const int mod = 1e9 + 7;
//const int mod = 998244353;

void solve(){
  int n, w, ans = 0, h, p; cin >> n >> h;
  vector <int> dp(h+2, 0);
  for(int i = 1; i <= n; i++){
     cin >> w >> p;
     for(int j = h; j >= 1; j--){
        if((j-w) >= 0){
           dp[j] = max(dp[j], dp[j-w] + p);
        }
     }
  }
  for(int i = 1; i <= h; i++) ans = max(ans, dp[i]);
  cout << ans << '\n';
}

signed main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
        clock_t t1 = clock();
  int t = 1; //cin >> t;
  while(t--){      
     solve();
  }
        clock_t t2 = clock();
  //cout << "Time-Taken: " << ((t2 - t1) / (double)CLOCKS_PER_SEC) << endl;      
}


Measured memory_bytes: 1024
N = int(input())
H = [[int(x) for x in input().split()] for _ in range(N)]
dp = [[0]*3 for _ in range(N)]
dp[0][0] = H[0][0]
dp[0][1] = H[0][1]
dp[0][2] = H[0][2]
for i in range(N-1):
    dp[i+1][0] = max(dp[i][1] + H[i+1][0], dp[i][2] + H[i+1][0])
    dp[i+1][1] = max(dp[i][0] + H[i+1][1], dp[i][2] + H[i+1][1])
    dp[i+1][2] = max(dp[i][0] + H[i+1][2], dp[i][1] + H[i+1][2])

print(max(dp[-1]))

Measured memory_bytes: 44100
n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
def prepare(n, MOD):
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return fn, invs
 
def ncr(n, r, invs, MOD):
    ret = invs[r]
    for i in range(n, n - r, -1):
        ret = ret * i % MOD
    return ret

fn, invs = prepare(max(a, b), mod)
ans = (pow(2, n, mod) - 1 - ncr(n, a, invs, mod) - ncr(n, b, invs, mod)) % mod
print(ans)

Measured memory_bytes: 10868
import Foundation
func toTuple<T>(_ args: [T]) -> (T, T) { (args[0], args[1]) }
func readInts() -> [Int] { readLine()!.split(separator: " ").map { Int($0)! } }

let (h, w) = toTuple(readInts())
var ai: [String] = []
for _ in 0..<h {
  ai.append(readLine()!)
}
var line = ""
for _ in 0..<w+2 {
  line += "#"
}
print(line)
for a in ai {
  print("#\(a)#")
}
print(line)

Measured memory_bytes: 13504
import time
import sys
import math
import fractions
from functools import reduce
from collections import Counter
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]  # LIST INT
def LF(): return [float(x) for x in sys.stdin.readline().split()]  # LIST FLOAT
def LS(): return sys.stdin.readline().split()  # LIST STRING
def MI(): return map(int, sys.stdin.readline().split())  # MAP INT
def II(): return int(sys.stdin.readline())  # INPUT INT
def IS(): return input()  # INPUT STRING
def P(x): return print(x)
def C(x): return Counter(x)
def GCD_LIST(numbers):  # greatest common divisor
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):  # least common multiple
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))


N = II()
a = LI()
# aのすべての数の最小公倍数-1をaの各要素で割った剰余の和
lcm = LCM_LIST(a)
print(sum([(lcm - 1) % i for i in a]))

Measured memory_bytes: 5300
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

void Main()
{
    string s;
    cin >> s;
    int flag = 0;
    for (int i = 0; i < s.size(); i++)
    {
        if (i % 2 == 0)
        {
            if (s[i] == 'R' || s[i] == 'U' || s[i] == 'D')
            {
            }
            else
            {
                flag = 1;
            }
        }
        else
        {
            if (s[i] == 'L' || s[i] == 'U' || s[i] == 'D')
            {
            }
            else
            {
                flag = 1;
            }
        }
    }

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

int main()
{
    std::cout << std::fixed << std::setprecision(15);
    Main();
}

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

int calc(int n) {
  int s = 0;
  while (n != 0) {
    s += n % 10;
    n /= 10;
  }
  return s;
}

int main() {
  int n, a, b, s = 0;
  cin >> n >> a >> b;
  for (int i = 1; i <= n; i++) {
    if (a <= calc(i) && calc(i) <= b) {
      s += i;
    }
  }
  cout << s << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
 
 
int main()
{	
	string a,b;
	cin>>a>>b;
	if(a+b[b.length()-1]==b)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 3632
#include<stdio.h>

int main(){
  int i, n, p, c[50], ans, po;

  while(1){
    scanf("%d%d", &n, &p);
    if(!n && !p){
      break;
    }

    for(i=0; i<n; i++){
      c[i]=0;
    }
    
    ans=-1;
    i=0;
    po=p;
    while(1){
      /*if(c[i%n]==p){
	ans=i%n;
	break;
	}*/
      if(po==0){
	po=c[i%n];
	c[i%n]=0;
      }else{
	po--;
	c[i%n]++;
      }
      if(c[i%n]==p){
	ans=i%n;
	break;
	//printf("%d\n", i);
      }
      //      printf("%d %d\n", i, p);
      i++;
    
    }    
    
    printf("%d\n", ans);
  }

  return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
const int mod=1000000007;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;cin >> n;
	vector<int> a(n);
	vector<int> b(n);
	rep(i,n){
		cin >> a.at(i);
		b.at(a.at(i))++;
	}
	if(n%2==0){
		for(int i=1;i<n;i+=2){
			if(b.at(i)!=2){
				cout << 0 << endl;
				return 0;
			}
		}
	}
	else{
		for(int i=0;i<n;i+=2){
			if(i==0){
				if(b.at(i)!=1){
					cout << 0 << endl;
					return 0;
				}
			}
			else if(b.at(i)!=2){
				cout << 0 << endl;
				return 0;
			}
		}
	}
	ll ans=1;
	rep(i,n/2){
		ans*=2;
		ans%=mod;
	}
	cout << ans << endl;
}

Measured memory_bytes: 1024
using System;
using static System.Console;
using System.Collections.Generic;
using System.Linq;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var nums = InputNumList();
            WriteLine(nums.Sum() - nums.Max() == nums.Max() ? "Yes" : "No");
        }

        static int InputNum()
        {
            return int.Parse(ReadLine());
        }
        static List<int> InputNumList()
        {
            return ReadLine().Split(' ').Select(int.Parse).ToList();
        }
    }
}



Measured memory_bytes: 13268
import java.io.*;
import java.util.*;
import java.math.*;
import java.util.regex.Pattern;
import java.util.regex.Matcher;

class Main{
	
	public static ArrayList<Integer> sort(ArrayList<Integer> list){
		for (int i=0; i<list.size()-1;i++ ){
			for (int j=list.size()-1; j>i;j-- ){
				if(list.get(j) < list.get(j-1)){
					int t = list.get(j);
					list.set(j,list.get(j-1));
					list.set(j-1,t);
				}
			}
		}
		return list;
	}

	public static boolean hand_straight(ArrayList<Integer> list){
		if(list.get(0) == 1){
			if(list.get(1) == 10 && list.get(2) == 11 && list.get(3) == 12 &&
					list.get(4) == 13)return true;
		}
		for (int i=1; i<list.size(); i++){
			if(list.get(i) == list.get(i-1) + 1);
			else return false;
		}

		return true;
	}

	/** 
	 *ツ姪ーツづーツチツェツッツクツつキツづゥツδソツッツド 
	 * 
	 * @param list ツ偲ィツ札ツづーツ格ツ納ツつキツづゥツδ環スツト
	 * @return ツ姪ーツづ個鳴シツ前ツづーツ陛板つキ
	 */
	public static String check_poker(ArrayList<Integer> list){
		int base;
		int m_same = 1;
		int t_same = 1;
		int pair = 0;
		int count = 0;
		
		for(int i = 0; i < 4;i++){
			t_same = 1;
			base = list.get(i);
			count ++;
			for(int j = count;j < 5;j++){
				if(i != j){
					if(base == list.get(j)){
						t_same++;
					}
				}
			}
			if(t_same == 2)pair++;
			if(t_same > m_same)m_same = t_same;
		}
		
		list = sort(list);
		
		if(hand_straight(list) == true) return "straight";
		if(m_same == 4) return "four card";
		if(m_same == 3 && pair == 2) return "full house";
		if(m_same == 3) return "three card";
		if(pair == 2) return "two pair";
		if(pair == 1) return "one pair";
		return "null";
	}
	
	
	public static void print_poker(ArrayList<Integer> list){
		ArrayList <Integer> inp = new ArrayList<Integer>();
		
		for(int i=0;i<list.size()/5;i++){
			for(int j=0;j<5;j++){
				inp.add(list.get(i*5+j));
			}
			System.out.println(check_poker(inp));
			inp.clear();
		}

	}
		
	public static void main(String args[]) throws IOException{
		String str;
		ArrayList <Integer> inp = new ArrayList<Integer>();

		Scanner scan = new Scanner(System.in);

		while(scan.hasNext()){
			str = scan.next();
			String [] strAry = new String[str.length()];
			strAry = str.split(",");
			for(int j=0;j<strAry.length;j++){
				Pattern p = Pattern.compile("[0-9]*");
				Matcher m = p.matcher(strAry[j]);
				if(m.find()){
					int x = Integer.valueOf(m.group(0)).intValue();
					inp.add(x);
				}
			}
		}
		print_poker(inp);
	}
}

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

void call(int n) {
  for (int i = 1; i <= n; ++i) {
    int x = i;
    if (x % 3 == 0) {
      cout << " " << i;
    } else {
      while (x > 0) {
        if (x % 10 == 3) {
          cout << " " << i;
          break;
        }
        x /= 10;
      }
    }
  }
  cout << endl;
}

int main() {
  int n;
  cin >> n;
  call(n);
}


Measured memory_bytes: 3104
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.concurrent.SynchronousQueue;

class Main {
	public static void main(String[] args) throws IOException {
		new Main().run();
	}

	void run() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long[] a = new long[n];
		for (int i = 0; i < n; ++i) {
			a[i] = sc.nextLong();
		}
		long[] sum = new long[n];
		for (int i = 0; i < n; ++i) {
			sum[i] = (i > 0 ? sum[i - 1] : 0) + a[i];
		}

		long ans = Long.MAX_VALUE / 16;
		int[] sign = { -1, 1 };
		for (int f = 0; f <= 1; ++f) {
			long d = 0;
			long cnt = 0;
			for (int i = 0; i < n; ++i) {
				if (sign[(i + f) % 2] == sign(sum[i] + d))
					continue;
				cnt += Math.abs(sign[(i + f) % 2] - (sum[i] + d));
				d += sign[(i + f) % 2] - (sum[i] + d);
			}
			ans = Math.min(ans, cnt);
		}
		System.out.println(ans);


	}

	int sign(long x) {
		return Long.compare(x, 0);
	}

	void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}

Measured memory_bytes: 50816