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

using namespace std;

const int N = 2e5 + 5;
const int M = 1e6 + 9;
const long long INF = 1e9 + 7;
const int SM = 1e3 + 4;
const double EPS = 3e-16;
const int K = 25;

//20:57 28.09.2019 Kazakhstan, Nur-Sultan
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n; cin >> n;
    
    vector<int> a(n), dp(n, 0);
    for(auto &i : a) cin >> i;
    
    
    dp[1] = abs(a[1] - a[0]);
    for(int i = 2; i < n; i++){
        dp[i] = min(dp[i - 1] + abs(a[i] - a[i - 1]), dp[i - 2] + abs(a[i] - a[i - 2]));
    }
    
    cout << dp[n - 1];
    return 0;
}
// IOI2020

Measured memory_bytes: 1024
n,m = map(int,input().split())
L = [[] for i in range(n)]
ans = [0]*m
l = [list(map(int,input().split())) for i in range(m)]

for i in range(len(l)):
  L[l[i][0]-1].append([l[i][1],i+1])
  
for ind,lis in enumerate(L):
  lis.sort()
  for j in range(len(lis)):
    ans[lis[j][1] - 1] = str(ind+1).zfill(6) + str(j+1).zfill(6)
    
print(*ans,sep = '\n')

Measured memory_bytes: 121056
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
using namespace std;
typedef long long ll;

const int INF = 1001001001;
const int MOD = 1e9+7;

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

vector<pair<ll, int>> factorize(ll n) {
    vector<pair<ll, int>> ret;
    for (ll i = 2; i*i <= n; i++)
    {
        if(n % i) continue;
        ret.emplace_back(i, 0);
        while (n%i == 0)
        {
            n /= i;
            ret.back().second++;
        }
    }
    if (n != 1) ret.emplace_back(n, 1);
    return ret;   
}

int main() {
    ll a, b; cin >> a >> b;
    ll g = gcd(a, b);
    auto f = factorize(g);
    int ans = f.size() + 1;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
txtd = ["dreameraser",
        "dreamerase",
        "dreamer",
        "dream"]
txtd_n = [len(a) for a in txtd]
txtd_l = len(txtd)
txte = ["eraser",
        "erase"]
txte_n = [len(a) for a in txte]
txte_l = len(txte)
        
S = input()
len_idx = len(S)
i = 0
able = True
while i < len_idx:
  old_i = i
  remain = len_idx - i
  
  if S[i] == "d":
    for j in range(txtd_l):
      if remain >= txtd_n[j]:
        if S[i:i+txtd_n[j]] == txtd[j]:
          i += txtd_n[j]
          break
  elif S[i] == "e":
    for j in range(txte_l):
      if remain >= txte_n[j]:
        if S[i:i+txte_n[j]] == txte[j]:
          i += txte_n[j]
          break

  if old_i == i:
    able = False
    break

if able:
  print("YES")
else:
  print("NO")
  

Measured memory_bytes: 9228
N,Q=gets.split.map &:to_i
S=gets
t=[0]*-~N
N.times{|i|t[i+1]=t[i]+(S[i,2]=='AC' ? 1 : 0)}
Q.times{l,r=gets.split.map &:to_i;p t[r-1]-t[l-1]}

Measured memory_bytes: 3324
import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
L = [int(v) for v in input().split()]
res = deque()

for i in range(N):
    if i % 2 == 0:
        res.append(str(L[i]))
    else:
        res.appendleft(str(L[i]))
        
if N % 2 == 0:
    print(" ".join(res))
else:
    print(" ".join(reversed(res)))

Measured memory_bytes: 32948
#include<stdio.h>
#define INFTY 2000000000;
 
int cnt = 0;
 
void merge(int A[], int left, int mid, int right){
  int n1, n2, i, j, k;
  int L[250002], R[250002];
 
  n1 = mid-left;
  n2 = right-mid;
 
  for(i=0; i<n1; i++){
    L[i] = A[left + i];
  }
 
  for(i=0; i<n2; i++){
    R[i] = A[mid + i];
  }
 
  L[n1] = INFTY;
  R[n2] = INFTY;
 
  i=0;
  j=0;
 
  for(k=left; k<right; k++){
    cnt++;
    if(L[i] <= R[j]){
      A[k] = L[i];
      i = i+1;
    }else{
      A[k] = R[j];
      j = j+1;
    }
  }
}
 
void mergeSort(int A[], int left, int right){
  int mid;
 
  if(left+1 < right){
    mid = (left+right)/2;
    mergeSort(A,left,mid);
    mergeSort(A,mid,right);
    merge(A,left,mid,right);
 
  }
}
 
int main(){
  int i, n, left, right;
  int S[500000];
 
  scanf("%d", &n);
 
  for(i=0; i<n; i++){
    scanf("%d", &S[i]);
  }
 
  left = 0;
  right = n;
 
  mergeSort(S,left,right);
 
  printf("%d", S[0]);
 
  for(i=1; i<n; i++){
    printf(" %d", S[i]);
  }
  printf("\n");
  printf("%d", cnt);
  printf("\n");
}

Measured memory_bytes: 5672
#include<queue>
#include<cmath>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}
inline int bits(int m) { return (1<<m)-1; }
using Double = double;
const Double INF = 1e100;

int N;
LL X[15], Y[15], A[15];

Double D[15][15];
Double cst[1<<15];
Double sum[1<<15];
Double dp[1<<15];

void MAIN() {
    scanf("%d", &N);
    REP (i, N) scanf("%lld%lld%lld", X+i, Y+i, A+i);

    REP (s, 1<<N) if (s) {
	REP (i, N) if (s>>i&1) {
	    sum[s] = sum[s^(1<<i)] + A[i];
	    break;
	}
    }

    REP (i, N) REP (j, N) D[i][j] = hypot((Double)X[i]-X[j], (Double)Y[i]-Y[j]);
    REP (s, 1<<N) cst[s] = INF;
    REP (s, 1<<N) {
	if (__builtin_popcount(s) <= 1) cst[s] = 0;
	REP (i, N) if (s>>i&1) REP (j, N) if (~s>>j&1) amin(cst[s|1<<j], cst[s] + D[i][j]);
    }

    dp[0] = INF;
    REP (s, 1<<N) if (dp[s] > 0) {
	int other = bits(N) ^ s;
	if (other == 0) continue;
	int sup = other & (other-1);
	int small = sup ^ other;
	for (int t=sup; ; t=(t-1)&sup) {
	    int pc = __builtin_popcount(t|small);
	    Double val = (sum[t|small] - cst[t|small]) / pc;
	    amax(dp[s|t|small], min(val, dp[s]));
	    if (t == 0) break;
	}
    }
    double ans = dp[bits(N)];
    printf("%.12f\n", ans);
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



Measured memory_bytes: 1024
#include <stdio.h>

int n, A[50];

// 入力値のMから選んだ要素を引いていく再帰関数
int solve(int i, int m) {
    if(m==0) return 1;
    if(i>=n) return 0;
    int res = solve(i+1,m) || solve(i+1,m-A[i]);//①||②
	//①と②の()内はint solve()でぐるぐる回る→()内で計算が行われるので、上のif文に戻る
    return res;
}

int main(void) {
    int q, M, i;

    scanf("%d", &n);
    for(i=0;i<n;i++) scanf("%d",&A[i]);
    scanf("%d",&q);
    for(i=0;i<q;i++) {
        scanf("%d", &M);
        if(solve(0,M)) printf("yes\n");
        else printf("no\n");
    }
    return 0;
}


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

int main(){
  int a,b;
  cin >> a >> b;
  if(a>0 && b>0){cout << "Positive" << endl;}
  if(a<0 && b>0){cout << "Zero" << endl;}
  if(a<0 && b<0){int d=b-a+1;
                if(d%2==1){cout << "Negative" << endl;}else{cout << "Positive" << endl;}}
}

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void solve() {
    ll A, B, C, D;
    cin >> A >> B >> C >> D;
    bool t = true;
    while (A > 0 && C > 0) {
        if (t) {
            C -= B;
        } else {
            A -= D;
        }
        t ^= true;
    }
    if (A <= 0) {
        cout << "No" << '\n';
    } else {
        cout << "Yes" << '\n';
    }
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    return 0;
}


Measured memory_bytes: 3604
#include<iostream>
#include<string.h>
using namespace std;

char A[4002],B[4002];
short int length[4000][4000];
int mmax[200],mcor = 0;
int main(){
	int i,j,k,lenA,lenB;
	while(cin >> A[0]){
		cin >> A+1;
		cin >> B;
		lenA = strlen(A);
		lenB = strlen(B);
		for(i = 0;i < lenA;i++){
			for(j = 0;j < lenB;j++){
				length[i][j] = -1;
			}
		}
		//逆さからループしただけなのにオーダーが1/100になったww
		for(i = lenA-1;i >= 0;i--){
			for(j = lenB-1;j >= 0;j--){
				for(k = 0;;k++){
					if(i+k >= lenA || j+k >= lenB || A[i+k] != B[j+k]){
						length[i][j] = k;
						break;
					}
					else if(length[i+k][j+k] >= 0){
						length[i][j] = length[i+k][j+k]+k;
						break;
					}
				}
			}
		}
		for(i = 0;i < lenA;i++){
			for(j = 0;j < lenB;j++){
				if(mmax[mcor] < length[i][j])
					mmax[mcor] = length[i][j];
			}
		}
		mcor++;
	}
	for(i = 0;i < mcor;i++){
		cout << mmax[i] << endl;
	}
	return 0;
}

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

using namespace std;

int main() {
  ios::sync_with_stdio(false);

  int n, m;
  cin >> n;
  vector<int> v1(n);

  int tmp;
  for (int i = 0; i < n; i++) {
    cin >> tmp;
    v1[i] = tmp;
  }

  cin >> m;
  vector<int> v2(m);
  for (int i = 0; i < m; i++) {
    cin >> tmp;
    v2[i] = tmp;
  }

  vector<int> r;
  set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), inserter(r, r.end()));

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




Measured memory_bytes: 4684
#include<bits/stdc++.h>
/************************************************/
#define rep(i,n) for(int i=0;i<n;i++)
#define m_p make_pair
#define pb push_back
#define fr first
#define se second
#define forn(i,a,n) for(int i=a;i<n;i++)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define sz(s) s.size()
#define all(s) s.begin(),s.end()
#define zero(x) memset(x,0,sizeof(x))
#define vii vector<pair<int,int> >
#define mpis map<int,string>
#define mpii map<int,int>
#define mpsi map<string,int>
#define re return
#define mod 1000000007
/************************************************/
using namespace std;

long long get(){
	char c=getchar();
	long long x=0LL;
	while(c<'0'||c>'9')
	c=getchar();
	while(c>='0'&&c<='9'){
		x*=10LL;
		x+=(c-'0');
		c=getchar();
	}
	return x;
}
int n;
ll x,l;
pair<ll,ll> r[100001];
int main(){
	cin>>n;
	rep(i,n){
		cin>>x>>l;
		r[i]=m_p(x-l,x+l);
	}
	sort(r,r+n);
	int last=0,ans=1;
	for(int i=1;i<n;i++){
		if(r[last].se<=r[i].fr){
			last=i;
			ans++;
			continue;
		}
		if(r[last].se>=r[i].se){
			last=i;
			continue;
		}
	}
	cout<<ans;
	re 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <list>
using namespace std;

#define MOD 1000000007
#define p(x) cout << x << endl;
#define el cout << endl;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

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

    int x;
    cin >> x;

    switch (x){
        case 7:
            p("YES");
            break;
        case 5:
            p("YES");
            break;
        case 3:
            p("YES");
            break;
        default:
            p("NO");
            break;
    }

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
#define inf (int)(1e9+7)
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }









int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
   
    // frontを並べてsideで再利用する
    /*
     2 5 4 1 3
     4 1 5 3 2
     
     2
             3
       5
           1
         4
     */
    
    int n, m;
    while (cin >> n && n) {
        cin >> m;
        map<int, int> mp;
        int sum = 0;
        rep(i, n) {
            int h;
            cin >> h;
            sum += h;
            mp[h]++;
        }
        rep(i, m) {
            int h;
            cin >> h;
            if (mp[h]) {
                mp[h]--;
            } else sum += h;
        }
        cout << sum << endl;
    }
}



Measured memory_bytes: 3148
#include <iostream>
#include <cmath>

int main(){
    using namespace std;
    int n;
    cin >> n;
    int res = 0;
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        bool isprime = true;
        int lim = (sqrt(a)+1 <= a-1) ? sqrt(a)+1 : a-1;
        for(int j = 2; j <= lim; j++){
            if(a % j == 0){
                isprime = false;
                break;
            }
        }

        if(isprime) res++;
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 3080
#pragma region
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))

using namespace std;

using i32 = int;
using i64 = long long;
using u64 = unsigned long long;
using f80 = long double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vu64 = vector<u64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << '\n'; exit(0); }
inline void no() { cout << "No" << '\n'; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); return a / gcd(a, b) * b; }
inline u64 xorshift() { static u64 x = 88172645463325252ull; x = x ^ (x << 7); return x = x ^ (x >> 9); }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { if (x < y) x = y; }
template <typename T> inline void amin(T &x, T y) { if (x > y) x = y; }
template <typename T> inline T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> inline T bis(T ok, T ng, function<bool(T)> f, T eps = 1) { while (abs(ok - ng) > eps) { T mi = (ok + ng) / 2; (f(mi) ? ok : ng) = mi; } return ok; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }
#pragma endregion

void solve() {
  int N;
  cin >> N;
  vi64 A(N);
  cin >> A;
  i64 xor_sum = 0;
  {
    rep(i, N) xor_sum ^= A[i];
    rep(i, N) A[i] &= ~xor_sum;
  }
  int p = 0;
  rrep(i, 60) {
    bool f = false;
    repi(j, p, N) if ((A[j] >> i) & 1) {
      swap(A[p], A[j]);
      f = true;
      break;
    }
    if (!f) {
      continue;
    }
    rep(j, N) {
      if (j == p) continue;
      if ((A[j] >> i) & 1) A[j] ^= A[p];
    }
    p++;
  }
  A.resize(60);
  i64 acc = 0;
  int src = -1;
  rrep(i, 60) {
    int pre = src;
    repi(j, src + 1, 60) if (A[j] & bit64(i)) {
      src = j;
      break;
    }
    if (src == pre) {
      continue;
    }
    acc ^= A[src];
  }
  i64 ans = acc * 2 + xor_sum;
  cout << ans << endl;
}


Measured memory_bytes: 1024
out=[]
while True:
	try:
		k=list(map(float,input().split(" ")))
	except:
		break

	O_x,O_y=k[0],k[1]
	A_x,A_y=k[2],k[3]
	B_x,B_y=k[4],k[5]
	P_x,P_y=k[6],k[7]

# P in triangle OAB
# iff  s+t<1 and s>0 and t>0 (OP=sOA+tOB)

	OA=(A_x-O_x,A_y-O_y)
	OB=(B_x-O_x,B_y-O_y)
	OP=(P_x-O_x,P_y-O_y)

	keisuu=1/( OA[0]*OB[1] - OA[1]*OB[0] )

	s=keisuu*(  OB[1]*OP[0]-OB[0]*OP[1] )
	t=keisuu*( -OA[1]*OP[0]+OA[0]*OP[1] )

	if s>0 and t>0 and s+t<1:
		out.append("YES")
	else:
		out.append("NO")

for i in out:
	print(i)

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

    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    # define M_PI  3.14159265358979323846


    void solve(){
        string s;
        cin>>s;
        string s1=s.substr(0,2);
        string s2=s.substr(2,2);
        int x=stoi(s1);
        int y=stoi(s2);
        int ans=0;
        if(x>=1 && x<=12)
            ans++;
        if(y>=1 && y<=12)
            ans+=2;
        if(ans==1)
            cout<<"MMYY";
        else if(ans==2)
            cout<<"YYMM";
        else if(ans==3)
            cout<<"AMBIGUOUS";
        else
            cout<<"NA";
    }
    int main(){
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        cout<<fixed;
        cout<<setprecision(10);
        int t=1;
//        cin>>t;
        for(int i=1;i<=t;i++){
            solve();
        }
        return 0;
    }


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A, B, p,m,k;
  cin >> A >> B ;
 
  p=A+B;
  m=A-B;
  k=A*B;
  if(p>=m && p>=k){
    cout << p << endl;
  }else if(m>=p && m>=k){
    cout << m << endl;
  }else if(k>=p && k>=m){
    cout << k << endl;
  }
  
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String s = sc.next();
		
		sc.close();
		
		int[] a = new int[4];
		for(int i = 0; i < s.length(); i++) {
			switch(s.charAt(i)) {
			case 'N':
				a[0]++;
				break;
			case 'W':
				a[1]++;
				break;
			case 'S':
				a[2]++;
				break;
			case 'E':
				a[3]++;
				break;
			}
		}
		
		if((a[0] == 0 && a[2] != 0) || (a[1] == 0 && a[3] != 0) || (a[2] == 0 && a[0] != 0) || (a[3] == 0 && a[1] != 0)) {
			System.out.println("No");
		} else {
			System.out.println("Yes");
		}
		
		return;
	}
	
}

Measured memory_bytes: 9940
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 200000
#define MAXV 4000
#define MO 1000000007
using namespace std;
int n,A[MAXN+5],B[MAXN+5];
int dp[MAXV+5][MAXV+5];
int fact[MAXV*2+5],inv[MAXV*2+5];
int PowMod(int a,int b)
{
	int ret=1;
	while(b)
	{
		if(b&1)
			ret=1LL*ret*a%MO;
		a=1LL*a*a%MO;
		b>>=1;
	}
	return ret;
}
void prepare()
{
	fact[0]=1;
	for(int i=1;i<=MAXV*2;i++)
		fact[i]=1LL*fact[i-1]*i%MO;
	inv[MAXV*2]=PowMod(fact[MAXV*2],MO-2);
	for(int i=MAXV*2-1;i>=0;i--)
		inv[i]=1LL*inv[i+1]*(1LL*i+1LL)%MO;
}
int C(int a,int b)
{
	return 1LL*fact[a]*inv[b]%MO*inv[a-b]%MO;
}
int main()
{
//	freopen("bbq.in","r",stdin);
//	freopen("bbq.out","w",stdout);
	prepare();
	scanf("%d",&n);
	int maxval=-1;
	for(int i=1;i<=n;i++)
	{
		scanf("%d %d",&A[i],&B[i]);
		maxval=max(maxval,A[i]);
		maxval=max(maxval,B[i]);
	}
	maxval++;
	for(int i=1;i<=n;i++)
		dp[maxval-A[i]][maxval-B[i]]++;
	for(int i=-maxval+1;i<=maxval;i++)
		for(int j=-maxval+1;j<=maxval;j++)
			dp[i+maxval][j+maxval]=(1LL*dp[i+maxval][j+maxval]+1LL*dp[i-1+maxval][j+maxval]+1LL*dp[i+maxval][j-1+maxval])%MO;
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		ans=(1LL*ans+1LL*dp[A[i]+maxval][B[i]+maxval])%MO;
		ans=((1LL*ans-1LL*C(A[i]+B[i]+A[i]+B[i],A[i]+A[i]))%MO+MO)%MO;
	}
	ans=1LL*ans*PowMod(2,MO-2)%MO;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 64384
#include <bits/stdc++.h>
#define rep(i,n) for ((i)=1;(i)<=(n);(i)++)
using namespace std;
int a[500005],b[500005],c[500005],n,i,j,l,r,mid,ans,aa[500005];
bool check(int x)
{
	int i,tp=0,j;
	rep(i,n)
	{
		if (aa[i]>aa[i-1])
		{
			tp++;
			a[tp]=b[tp-1]+1;
			b[tp]=aa[i];
			c[tp]=1;
		}
		if (aa[i]<aa[i-1])
		{
			while (b[tp]>aa[i])
			{
				if (a[tp]<=aa[i]) b[tp]=aa[i]; else tp--;
			}
		}
		if (aa[i]<=aa[i-1])
		{
			int f=aa[i]+1;
			for (j=tp;j;j--)
			{
				if (c[j]==x)
				{
					f=a[j];
				}
				else break;
			}
			if (j<1) return 0;
			if (a[j]==b[j]) c[j]++; else
			{
				b[j]--;
				j++;
				a[j]=b[j]=b[j-1]+1;
				c[j]=c[j-1]+1;
			}
			tp=j;
			if (f<=aa[i])
			{
				tp++;
				a[tp]=f;
				b[tp]=aa[i];
				c[tp]=1;
			}
		}
	}
	return 1;
}
int main()
{
	scanf("%d",&n);
	rep(i,n)
	{
		scanf("%d",&aa[i]);
	}
	l=0;r=ans=n;
	while (l<r)
	{
		mid=(l+r+1)/2;
		if (check(mid))
		{
			r=mid-1;
			ans=mid;
		}
		else l=mid;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 5760
/*** akshaykumar99 ***/
 
#include<bits/stdc++.h> 
using namespace std;
 
const long long MOD = 1e9+7;
const long double PI = acos(-1);
const long long N = 5e2+1;
 
#define ll int
// typedef long long ll;
typedef long double ld;

void test_case()
{
	ll h, w, m;
	cin >> h >> w >> m;
	vector<pair<ll,ll>> v;
	vector<ll> tot(h+1, 0);
	for(int i = 0; i < m; i++)
	{
		ll hh, ww;
		cin >> hh >> ww;
		v.push_back({hh, ww});
		tot[hh]++;
	}
	ll mx = 0, ind = 0;
	for(int i = 1; i <= h; i++)
	{
		if(mx < tot[i])
		{
			mx = tot[i];
			ind = i;
		}
	}
	tot.assign(w+1, 0);
	for(auto u : v)
	{
		if(u.first != ind)
		{
			tot[u.second]++;
		}
	}
	ll ans = 0;
	for(int i = 1; i <= w; i++)
	{
		ans = max(ans, mx + tot[i]);
	}
	tot.assign(w+1, 0);
	for(auto u : v)
		tot[u.second]++;
	mx = 0;
	for(int i = 1; i <= w; i++)
	{
		if(mx < tot[i])
		{
			mx = tot[i];
			ind = i;
		}
	}
	tot.assign(h+1, 0);
	for(auto u : v)
	{
		if(u.second != ind)
		{
			tot[u.first]++;
		}
	}
	for(int i = 1; i <= h; i++)
	{
		ans = max(ans, mx + tot[i]);
	}
	cout << ans << '\n';


}
 
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL); 
    ll tc=1;
    // cin>>tc;
    while(tc--)
        test_case();
    return 0;
}

Measured memory_bytes: 8580
#include<iostream>
using namespace std;
int main(){
    int list[6]={};
    for(int i=0;i<6;i++){
        cin >> list[i];
    }
    int list1[6]={};
    for(int i=0;i<6;i++){
        cin >> list1[i];
    }
    int n=0;
    int x=0;
    int a;
    string s="NWSWSWRRRRNNNEEESESWNRRRSREWNNNSERSRWNNWWWNNNNSRSREWNSNNSNWNNWNENENRNENNWWWESWESRESWSERSRSEWSWESRRWEWREWWWERSWERSWRSWRSRWSWRWRRRRWRSEEERWSWR";
    for(int i=0;i<s.size();i++){
        if(s[i]=='W'){
            a=list[0];
            list[0]=list[2];
            list[2]=list[5];
            list[5]=list[3];
            list[3]=a;
            if(list[0]==list1[0] && list[1]==list1[1] && list1[2]==list1[2] && list[3]==list1[3] && list[4]==list1[4] && list[5]==list1[5]){
                x=1;
            }
            
        }else if(s[i]=='S'){
            a=list[0];
            list[0]=list[4];
            list[4]=list[5];
            list[5]=list[1];
            list[1]=a;
            if(list[0]==list1[0] && list[1]==list1[1] && list[2]==list1[2] && list[3]==list1[3] && list[4]==list1[4] && list[5]==list1[5]){
                x=1;
            }
            
        }else if(s[i]=='E'){
            a=list[0];
            list[0]=list[3];
            list[3]=list[5];
            list[5]=list[2];
            list[2]=a;
            if(list[0]==list1[0] && list[1]==list1[1] && list[2]==list1[2] && list[3]==list1[3] && list[4]==list1[4] && list[5]==list1[5]){
                x=1;
            }
        }else if(s[i]=='N'){
            a=list[0];
            list[0]=list[1];
            list[1]=list[5];
            list[5]=list[4];
            list[4]=a;
            if(list[0]==list1[0] && list[1]==list1[1] && list[2]==list1[2] && list[3]==list1[3] && list[4]==list1[4] && list[5]==list1[5]){
                x=1;
            }
            
        }
        
}if(x==1){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
}



Measured memory_bytes: 3224
// https://atcoder.jp/contests/dp/tasks/dp_c
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long ll;
typedef pair<int,int> pii;

const int N = int(1e5)+10;
const int MOD = int(1e9)+7;
const int INF = int(2e9)+5;
const ll INF64 = 1e18;

ll a[N][3],dp[N][3];

int main () {
    FastIO
    int n;cin>>n;
    for (int i=1;i<=n;i++) {
        for (int j=0;j<3;j++) {
            cin>>a[i][j];
            dp[i][j] = 0;
        }
    }
    for (int i=0;i<3;i++) dp[1][i] = a[1][i];
    for (int i=2;i<=n;i++) {
        dp[i][0] = max(dp[i-1][1],dp[i-1][2]) + a[i][0];
        dp[i][1] = max(dp[i-1][0],dp[i-1][2]) + a[i][1];
        dp[i][2] = max(dp[i-1][1],dp[i-1][0]) + a[i][2];
    }
    cout<<max(dp[n][0],max(dp[n][1],dp[n][2]));
    return 0;
}

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

int nx[100000], n, m;
string s;

int main()
{
    cin >> n >> m >> s;
    int nxt = n;
    for (int i = n; i >= 0; --i)
        if (s[i] == '1')
            nx[i] = nxt;
        else
            nx[i] = nxt = i;
    /*
    for (int i = 0; i < n + 1; ++i)
        cout << nx[i] << " ";
    cout << endl;
    */
    int i = n;
    vector<int> rj;
    while (i)
    {
        int t = i;
        i = max(0, i - m);
        i = nx[i];
        rj.push_back(t - i);
        if (i == t)
            return cout << -1 << endl, 0;
    }
    reverse(rj.begin(), rj.end());
    for (int i : rj)
        cout << i << " ";
    cout << endl;
}

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

int gcd(int a,int b){
  if(b>a)swap(a,b);
  int m=a%b;
  while(m!=0){
    a=b;
    b=m;
    m=a%b;
  }
  return b;
}

int main(){
  int N;cin>>N;
  int A[100100];
  for(int i=0;i<N;i++){
    cin>>A[i];
  }
  int ans=gcd(A[0],A[1]);
  for(int i=2;i<N-1;i++){
    ans=gcd(A[i],ans);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 640
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int a,b,c,d,e;
	while(cin>>a>>b>>c>>d>>e)
	{
		if(a<=c||b<=d||c<=0||d<=0)
			{
				cout<<"No"<<endl;
		        continue;
		}
		int k,m;
		k=abs(a-c);
			m=abs(b-d);
			m=min(m,k);
			if(m>=e)
				cout<<"Yes"<<endl;
			else 
				cout<<"No"<<endl;
	
	
	}


}

Measured memory_bytes: 3096
#include <stdio.h>

void fun1(int second);

int main()
{
	int S;
	scanf("%d",&S);
	
	fun1(S);
	
	return 0;
}

void fun1(int second)
{
	int h,m,s;
	h=m=s=0;
	
	s = second%60;
	m = second/60%60;
	h = second/(60*60);
	
	printf("%d:%d:%d\n",h,m,s);
}

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

#define LEN 1000000

typedef struct pp{
  char name[100];
  int t;
}P;

P Q[LEN+1];
int head=1, tail=1, n;

void enqueue(P x){
  Q[tail] = x;
  if(tail+1==LEN){
    tail = 0;
  }
  else{
    tail++;
  }   
}

P dequeue(){
  P a;
  a = Q[head];
  if(head+1==LEN){
    head = 0;
  }
  else{
    head++;
  }
  return a;
}
 
 
int main(){
  int c=0,ans=0;
  int i,q,count=0;
  scanf("%d %d",&n,&q);

  for(i=1;i<=n;i++){
    scanf("%s",Q[i].name);
    scanf("%d",&Q[i].t);
    enqueue(Q[i]);
  }


  
  while(1){
    c++;
    if(n==count)break;
    if(Q[c].t-q>0){
      ans+=q;
      Q[c].t-=q;
      enqueue(Q[c]);
    }
    else{
      ans+=Q[c].t;
      printf("%s %d\n",Q[c].name,ans);
      count++;
      Q[c]=dequeue();
    }
  }
  
  return 0;
}

Measured memory_bytes: 21072
import numpy as np
ans=0
D=int(input())
C=np.array(list(map(int,input().split())))
last_day=np.array([0 for _ in range(26)])

for day in range(1,D+1):
    score=np.array(list(map(int,input().split())))
    tmp=C*(last_day-day)
    #今回行うコンテストで得られる
    idx=np.argmax(tmp+score)
    # ans=ans+score[idx]+np.sum(tmp)+abs(tmp[idx])
    last_day[idx]=day
    print(idx+1)

Measured memory_bytes: 27240
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long N,K,Ans=1;
	cin>>N>>K;
	if(N==1)
	{
		cout<<K<<endl;
		return 0;
	}
	for(int i=2;i<=sqrt(K);i++)
	{
		int Cnt=0;
		long long Tmp=i;
		while(K%Tmp==0)
		{
			Cnt++;
			K/=Tmp;
		}
		Cnt/=N;
		for(int j=0;j<Cnt;j++)
			Ans*=Tmp; 
	}
	cout<<Ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int A[3];
    cin>>A[0]>>A[1]>>A[2];
    int ans=0;
    sort(A,A+3);
    if(A[0]%2!=A[1]%2||A[1]%2!=A[2]%2){
        if(A[0]%2==A[1]%2) A[0]++,A[1]++;
        if(A[1]%2==A[2]%2) A[1]++,A[2]++;
        else A[0]++,A[2]++;
        ans++;
    }
    cout<<ans+(A[2]-A[0])/2+(A[2]-A[1])/2;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static int N, M;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        System.out.println(to_hop(N) + to_hop(M));
    }
    public static int to_hop(int temp)
    {
         return (temp*(temp-1)) / 2;

    }

}


Measured memory_bytes: 35948
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
#include<iterator>
#include<list>
using namespace std;
typedef  long long int lint;
typedef pair<int, int> IP;
typedef pair<lint, lint> LLP;
typedef pair<char, char>CP;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define llower(v,hoge) *lower_bound(v.begin(), v.end(), hoge)
#define lupper(v,hoge) *upper_bound(v.begin(), v.end(), hoge)

int main() {
	int Q;
	cin >> Q;
	set<lint>S;
	lint a, x;
	rep(i, Q) {
		cin >> a >> x;
		if (a == 0) {
			S.insert(x);
			cout << S.size() << endl;
		}
		else if (a == 1) {
			cout << S.count(x) << endl;
		}
		else if (a == 2) {
			S.erase(x);
		}
	}
}




Measured memory_bytes: 12404
// fahadmd16(IIEST Shibpur)

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

#define ll                          long long
#define pb                          push_back
#define pf                          push_front
#define eb                          emplace_back
#define mp                          make_pair
#define ff                          first
#define ss                          second
#define db                          double
#define pll                         pair<ll, ll>
#define ALL(a)                      (a).begin(),(a).end()
#define endl                        "\n"

#define forn(i, n) for (ll i = 0; i < n; i++)
#define forn1(i, n) for (ll i = 1; i < n; i++)
#define ford(i, n) for (ll i = n - 1; i >= 0; i--)
#define forab(i, a, b) for(ll i = a; i < b; i++)
#define eps 1e-10

#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)


#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define trace1(x)                cout<<#x<<": "<<x<<endl
#define trace2(x, y)             cout<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cout<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
#define trace(v) for(auto it=v.begin();it!=v.end();it++)cout<<*it<<" ";cout<<endl;


const ll sz = 1e5 + 3;
const ll mod = 1e9 + 7;
const ll mod2 = 1e9;


typedef vector<ll> VL;
typedef vector<pll > VLL;
typedef vector<vector<ll> > VVL;

ll power(ll n, ll k, ll m) {
    ll ans = 1;
    while (k) {
        if (k & 1)ans = (ans * n) % m;
        k /= 2;
        n = (n * n) % m;
    }
    return ans;
}

void solver() {
    ll n; cin >> n;
    VL a(n + 1);
    forab(i, 2, n + 1)cin >> a[i];
    map<ll, set<ll> > mp;

    forab(i, 2, n + 1) {

        mp[a[i]].insert(i);
    }

    forn1(i, n + 1) {
        cout << mp[i].size() << " ";
    }
    cout << endl;

}


int main() {
// #ifndef ONLINE_JUDGE
//     freopen("input.txt", "r", stdin);
//     freopen("output.txt", "w", stdout);
// #endif
    IOS;
    ll T = 1; //cin >> T;
    forn1(i, T + 1) {
        clock_t z = clock();
        solver();
        debug("Total Time: %.3f\n", (double)(clock() - z) / CLOCKS_PER_SEC);
    }
    return 0;
}


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

int main(){
	char roma[100];
	int num,tmp1,tmp2,len,i;

	while(scanf("%s",roma)!=EOF){
		num=0;
		tmp2=1001;
		len=strlen(roma);		
		for(i=0;i<len;i++){
			if(roma[i]=='I')
				tmp1=1;
			else if(roma[i]=='V')
				tmp1=5;
			else if(roma[i]=='X')
				tmp1=10;
			else if(roma[i]=='L')
				tmp1=50;
			else if(roma[i]=='C')
				tmp1=100;
			else if(roma[i]=='D')
				tmp1=500;
			else if(roma[i]=='M')
				tmp1=1000;
		
			if(tmp1<=tmp2)
				num+=tmp1;
			else{
				num-=tmp2;
				num+=tmp1-tmp2;
			}
			tmp2=tmp1;
		}
		printf("%d\n",num);
	}

	return 0;
}

Measured memory_bytes: 540
use proconio::input;
use proconio::marker::{Chars, Usize1};
use std::iter::Iterator;
use std::collections::HashSet;
use std::cmp::*;
use itertools::Itertools;

#[allow(unused_macros)]
macro_rules! max {
    ($x:expr) => {
      $x
    };
    ($x:expr, $($xs:tt)+) => {
      max($x,max!($($xs)+))
    };
  }
  
  #[allow(unused_macros)]
  macro_rules! min {
    ($x:expr) => {
      $x
    };
    ($x:expr, $($xs:tt)+) => {
      min($x,min!($($xs)+))
    };
  }

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn main() {
    input! {
    l: i64,
    r: i64,
    }

    let mut min  = std::i64::MAX;
    for i in l..r {
      for j in i+1..=r{
        let ans = (i * j) % 2019;

        if ans == 0 {
          println!("{}", ans);
          return;
        }

        min = min!(min, ans);
      }
    }

    println!("{}", min);


}


Measured memory_bytes: 2112
push(@p,$p=$p*2+1),push@c,$c=$c*2+3for$c--..55;sub f{($n,$x)=@_;$n?$x>1+$c[$n-1]?$p[$n-1]+1+f($n-1,$x-2-$c[$n-1]):f($n-1,$x-1):$x>0}print<>!~$"+f$`,$'

Measured memory_bytes: 512
// Try AtCoder
// author: Leonardone @ NEETSDKASU

fn main() {
    let mut stdin = String::new();
    std::io::Read::read_to_string(
        &mut std::io::stdin(),
        &mut stdin).unwrap();
    let mut stdin = stdin.split_whitespace();
    let mut get = || stdin.next().unwrap();
    macro_rules! get {
        ($t:ty) => (get().parse::<$t>().unwrap());
        () => (get!(i64));
    }
    
    let n = get!(usize);
    let mut vs = vec![];
    for _ in 0 .. n {
        vs.push(get!());
    }
    let ws = vs.clone();
    vs.sort();
    let mut d = 0;
    for i in 0 .. n {
        if vs[i] != ws[i] {
            d += 1;
        }
    }
    if d == 0 || d == 2 {
        println!("YES");
    } else {
        println!("NO");
    }
}

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

#define ll long long

ll f(ll n)
{
    return n % 2 ? (n + 1) / 2 % 2 : n / 2 % 2 ^ n;
}

int main()
{
    ll a, b;
    cin >> a >> b;

    cout << (f(a - 1) ^ f(b)) << "\n";
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
// nichijou
#define REP(i,a,b) for (int i(a), _B(b); i < _B; ++i)
#define RP(i,n) REP(i,0,n)
#define PER(i,a,b) for(int i((a)-1), _B(b); i >= _B; --i)
#define PR(i,n) PER(i,n,0)
#define REP1(i,a,b) REP(i,a,(b)+1)
#define RP1(i,n) REP1(i,1,n)
#define PER1(i,a,b) PER(i,(a)+1,b)
#define PR1(i,n) PER1(i,n,1)
#define DO(n) REP(__i,0,n)
template<typename T>
void cmax(T & a, T b) {a = max(a, b);}
template<typename T>
void cmin(T & a, T b) {a = min(a, b);}

// data type
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define F first
#define S second

// STL container
typedef vector<int> vi;
typedef vector<ll> vll;
#define SZ(a) ((int)a.size())
#define ALL(a) a.begin(), a.end()
#define CLR(a) a.clear()
#define BK(a) (a.back())
#define FT(a) (a.front())
#define DB(a) a.pop_back()
#define DF(a) a.pop_front()
#define PB push_back
#define EB emplace_back

/* I gave you my heart and then you turned around. */
void _BG(const char * s) {}
template<typename T, typename ... TT>
void _BG(const char * s,T a, TT...b)
{
	for (int c = 0; *s && (c || *s != ','); ++s) {
		cerr<<*s;
		switch (*s) {
		case '(':
		case '[':
		case '{':
			++c;
			break;
		case ')':
		case ']':
		case '}':
			--c;
			break;
		}
	}
	cerr<<" = "<<a;
	if (*s) {
		cerr<<", ";
		_BG(++s,b...);
	} else
		cerr<<endl;
}
#define BG(...) do { \
	cerr << __PRETTY_FUNCTION__ << ':' << __LINE__ << ": "; \
	_BG(#__VA_ARGS__,__VA_ARGS__); \
} while(0)

/* Reading input is now 20% cooler! */
bool RD(void) {return true;}
bool RD(char & a) {return scanf(" %c", &a) == 1;}
bool RD(char * a) {return scanf("%s", a) == 1;}
bool RD(double & a) {return scanf("%lf", &a) == 1;}
bool RD(int & a) {return scanf("%d", &a) == 1;}
bool RD(ll & a) {return scanf("%lld", &a) == 1;}

template<typename T, typename ... TT>
bool RD(T & a, TT & ...  b) {return RD(a) && RD(b...);}

/* Do princesses dream of magic sheep? */
#define RI(a) int a; RD(a)
#define RII(a,b) RI(a); RI(b)
#define RIII(a,b,c) RI(a); RII(b,c)
#define RIIII(a,b,c,d) RI(a); RIII(b,c,d)

/* For it's time for you to fulfill your output. */
void PT(const char a) {putchar(a);}
void PT(const char * a) {fputs(a, stdout);}
void PT(char * a) {fputs(a, stdout);}
void PT(const double a) {printf("%.16f", a);}
void PT(const int a) {printf("%d", a);}
void PT(const ll a) {printf("%lld", a);}

/* The line will last forever! */
template<char sep = ' ',char end = '\n'>
void PL(void) {if (end) PT(end);}
template<char sep = ' ',char end = '\n',typename T, typename ... TT>
void PL(const T a, const TT ...  b) {PT(a); if (sizeof...(b) && sep) PT(sep); PL<sep,end>(b...);}

/* Good Luck && Have Fun ! */
const int M = 1e9+7;
int mul(int a,int b) {return a * 1LL * b % M;}
int f(int n) {return n ? mul(n,f(n-1)) : 1;}
int main()
{
	RII(n,m);
	if (n > m)
		swap(n,m);
	if (m - n > 1)
		PL(0);
	else if (m - n == 1)
		PL(mul(f(m),f(n)));
	else
		PL(mul(2,mul(f(n),f(n))));
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;
const double pi = 3.14159265358979323846;
#define rep(i,n) for(ll i=0;i<n;i++)

int main(){
	int n;cin>>n;
	ll a[n],sum=0,mn=INF;
	int cnt=0,cnt0=0;
	rep(i,n){
		cin>>a[i];
		if(a[i]<0) cnt++;
		else if(a[i]==0) cnt0++;
		sum+=abs(a[i]);
		mn=min(mn,abs(a[i]));
	}
	ll ans=0;
	if(cnt%2==0||cnt0>0) ans=sum;
	else ans=sum-2*mn;

	cout<<ans<<"\n";
}

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

using namespace std;

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

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

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

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

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

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int n;
vi g[125252];

int p[125252];
int sz[125252];
bool vstd[125252];

int main(){
  scanf("%d",&n);
  REP(i,n-1){
    int s,t;
    scanf("%d%d",&s,&t);
    --s;--t;
    g[s].push_back(t);
    g[t].push_back(s);
  }
  vi roots;
  REP(i,n){
    int cnt = 0;
    for(int x : g[i]){
      if(g[x].size()>=2)cnt++;
    }
    if(cnt>=3){
      puts("-1");return 0;
    }
    sz[i] = cnt;
  }
  REP(i,n){
    if(g[i].size()==1){
      if(sz[g[i][0]]<=1 && !vstd[g[i][0]]){
        vstd[g[i][0]] = true;
        roots.push_back(i);
      }
    }
  }
  if(roots.size()==0){
    puts("-1");return 0;
  }
  vi ans(n,n+1);
  for(int root : roots){
    vector<bool> used(n,false);
    vi p;
    int v = 1;
    int cur = root;
    used[cur]=true;
    while(true){
      int cnt = 0;
      int nxt = -1;
      for(int x : g[cur])if(!used[x]){
        cnt++;
        if(g[x].size()>=2)nxt=x;
      }
      int res = v++;
      REP(_,cnt-1)p.push_back(v++);
      p.push_back(res);
      if(nxt==-1){
        p.push_back(v++);
        break;
      }
      for(int x : g[cur]){
        used[x] = true;
      }
      cur = nxt;
    }
    CHMIN(ans, p);
  }
  REP(i,n)printf("%d%c",ans[i],i==n?'\n':' ');
  return 0;
}


Measured memory_bytes: 8432
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
#define inf (int)(1e9+7)
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }





int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    
    
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    
    
    ll ans = 0, ans2 = 0;
    // 最初の項を正にする場合
    {
        ll sum = a[0];
        if (a[0] <= 0) {
            sum = 1;
            ans += 1 - a[0];
        }
        rep3(i, 1, n) {
            sum += a[i];
            if (i % 2 != 0 && sum >= 0) {
                ans += abs(-1 - sum);
                sum = -1;
            } else if (i % 2 == 0 && sum <= 0) {
                ans += abs(1 - sum);
                sum = 1;
            }
        }
    }
    {
        ll sum = a[0];
        if (a[0] >= 0) {
            sum = -1;
            ans2 += abs(-1 - a[0]);
        }
        rep3(i, 1, n) {
            sum += a[i];
            if (i % 2 != 0 && sum <= 0) {
                ans2 += abs(1 - sum);
                sum = 1;
            } else if (i % 2 == 0 && sum >= 0) {
                ans2 += abs(-1 - sum);
                sum = -1;
            }
            // cout << "s " << sum << " " << ans2 << endl;
        }
    }
    // cout << ans << " " << ans2 << endl;
    cout << min(ans, ans2) << endl;
}


Measured memory_bytes: 640
import sys
sys.setrecursionlimit(10**9)
mod=10**9+7
m,n=map(int,input().split())
grid=[list(input()) for _ in range(m)]
cache={}
def dp(i,j):
  if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j]=='#':
    return 0
  elif (i,j) in cache:
    return cache[(i,j)]
  elif i==m-1 and j==n-1:
    return 1
  cache[(i,j)]=dp(i+1,j)+dp(i,j+1)
  return cache[(i,j)]

print(dp(0,0)%mod) 
  

Measured memory_bytes: 417252
#include<cstdio>
#include<algorithm>
const long long inf = 1e17+7;
int a[55];
long long b[55];
//for good one
int vis[55];

int bruteForce(int n){
    int cnt = 0;
    while(true){
        //for(int i = 1; i <= n; i++) printf("%d ",a[i]);
        //printf("\n\n");
        int find = -1;
        for(int i = 1; i <= n; i++) if(find==-1 || a[i]>a[find]) find = i;
        if(a[find]<n) break;
        else{
            cnt++;
            for(int i = 1; i <= n; i++){
                if(i==find) a[i] -= n;
                else a[i]++;
            }
        }
    }
    return cnt;
}

long long max(long long a,long long b){ return a>b?a:b; }

long long min(long long a,long long b){ return a>b?b:a; }

int isGood(long long n){
    long long badMaxn = -1, goodMaxn = -1, goodMin = inf;
    for(int i = 1; i <= n; i++){
        if(vis[i]){
            goodMaxn = max(b[i],goodMaxn);
            goodMin = min(b[i],goodMin);
        }
        else{
            badMaxn = max(b[i],badMaxn);
        }
    }
    if(goodMin>n && (badMaxn==-1 || goodMin>=badMaxn+(long long)(n+1)) && (goodMaxn-goodMin)<(n+1ll)) return 1;
    else return 0;
}

void jump(long long n,long long& cnt){
    long long badMaxn = -1, goodMin = inf;
    long long goodCnt = 0;
    for(int i = 1; i <= n; i++){
        if(vis[i]) goodMin = min(b[i],goodMin), goodCnt++;
        else badMaxn = max(b[i],badMaxn);
    }
    long long L = 1, R = inf;
    long long res = -1;
    while(L<=R){
        long long M = (L+R)/2;
        if((badMaxn==-1 || goodMin>=badMaxn+M*(n+1ll)) && goodMin>=n+(n-(goodCnt-1))*M){
            res = M;
           L = M+1;
        }
        else R = M-1;
    }
    cnt += res*goodCnt;
    for(int i = 1; i <= n; i++){
        if(vis[i]) b[i] -= (n-(goodCnt-1))*res;
        else b[i] += goodCnt*res;
    }
}

long long solve(int n){
    long long res = 0;
    while(true){
        //printf("seq: ");
        //for(int i = 1; i <= n; i++) printf("%lld ",b[i]);
        //printf("\n");
        //printf("cnt = %lld\n\n",res);
        int find = -1;
        for(int i = 1; i <= n; i++) if(find==-1 || b[i]>b[find]) find = i;
        if(b[find]<n) break;
        else{
            //printf("find = %d\n",find);
            res++;
            if(!vis[find]) vis[find] = 1;
            for(int i = 1; i <= n; i++){
                if(i==find) b[i] -= (long long)n;
                else b[i]++;
            }
            if(isGood(n)) jump(n,res);
        }
    }
    return res;
}

int main(){
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++){ 
        scanf("%lld",&b[i]);
        //a[i] = b[i];
    }
    //printf("%d\n",bruteForce(n));
    printf("%lld\n",solve(n));
    return 0;
}


Measured memory_bytes: 1716
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
const int MOD = 1000000007;
const int INF = numeric_limits<int>::max() / 2;
typedef pair<int,int> P;
using Graph = vector<vector<int>>;

int modpow(int x, int n, int mod) {
    int res = 1;
    while (n > 0) {
        if (n & 1) {  // nが奇数のとき
            res *= x;
            res %= mod;
        }
        x *= x;
        x %= mod;
        n >>= 1;
    }
    return res;
}



signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int N, K;
	cin >> N >> K;

	int ans = 0;
	int A[K+1]{};
	for(int i=K;i>=1;i--){
		int num = K / i;
		// ans += i * (modpow(num, N, MOD);
		int W = i*2;
		int count = 0;
		while(W <= K){
			count += A[W];
			count %= MOD;
			W += i;
		}
		A[i] = (modpow(num, N, MOD) + MOD - count) % MOD;
		ans += i * A[i];

		ans %= MOD;
	}
	cout << ans << endl;
}

Measured memory_bytes: 4436