akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
using lli = long long;
#define rep(i,n) for(int i=0;i<n;i++)

lli n;
string s;

int main(void){
	cin >> n >> s;
	vector<lli> sume(n+1), sumw(n+1);
	rep(i, s.size()){
		sume[i+1] = sume[i];
		sumw[i+1] = sumw[i];
		if(s[i] == 'E'){
			sume[i+1]++;
		}else{
			sumw[i+1]++;
		}
	}
	lli ans = 1e18;
	rep(i, n){
		ans = min(ans, sumw[i]+sume[n]-sume[i+1]);
	}
	cout << ans << endl;
	return 0;
}


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


Measured memory_bytes: 256
def main():
  S = input("")
  T = input("")
  
  length = len(T)
  S_sub_T = len(S) - length

  max_match = 0
  S_offset = 0
  for i in range(S_sub_T+1):
    match = 0
    for j in range(length):
      if(S[i + j] == T[j]):
        match += 1
    if(max_match < match):
      max_match = match
  
  need_replace = length - max_match
  print(need_replace)
 
if __name__ == "__main__":
  main()

Measured memory_bytes: 9048
#include <bits/stdc++.h>
#define N 501
using namespace std;
int n,ans=N;char s[N];
inline int read()
{
	int x=0,c=getchar();while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-48,c=getchar();return x;
}
int main()
{
	scanf("%s",s+1);n=strlen(s+1);
	for(int i=0;i<26;i++){
		int ss=0,l=0;
		for(int j=1;j<=n;j++)
			if(s[j]==i+97)ss=max(ss,j-l-1),l=j;
		if(l)ans=min(ans,max(ss,n-l));
	}
	printf("%d\n",ans);
}

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

int main() {
    list<int> li;
    int n;
    cin >> n;

    string command;
    int x;
    for (int i = 0; i < n; i++) {
        cin >> command;
        if (command == "insert") {
            cin >> x;
            li.push_front(x);
        } else if (command == "delete") {
            cin >> x;
            for (auto it = li.begin(); it != li.end(); it++) {
                if (*it == x) {
                    li.erase(it);
                    break;
                }
            }
        } else if (command == "deleteFirst") {
            li.pop_front();
        } else {
            li.pop_back();
        }
    }

    for (auto it = li.begin(); it != li.end(); it++) {
        if (it != li.begin()) cout << " ";
        cout << *it;
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 34308
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>
#include <functional>

using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template<typename T> using VT = vector<T>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define EB emplace_back
#define GREATER(T) T, VT<T> greater<T>
template<typename T> inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

void solve() {
    int N, X, T;
    cin >> N >> X >> T;

    cout << ((N + X - 1) / X) * T << endl;
}

int main(void) {
#ifndef ONLINE_JUDGE
    const auto in_stream = freopen("../in.txt", "r", stdin);
    if (in_stream == nullptr) {
        cerr << "ERROR!" << endl;
        return 1;
    }
#endif

    solve();

#ifndef ONLINE_JUDGE
    fclose(in_stream);
#endif
}


Measured memory_bytes: 3632
// Created by ...
#include <bits/stdc++.h>

#define db1(x) cout<<#x<<"="<<x<<'\n'
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'

#define vll vector< ll >
#define M 100000
#define MD 1000000007
#define pb push_back
#define rep(i,a,b) for(ll i = a; i <= b; ++i)
#define fo(i,a,b) for(int i = a; i<= b; ++i)
#define pii pair<ll,ll> 
#define vec(a) vector<a >
#define all(a) a.begin(),a.end()
#define se second
#define fi first
#define inf 0xffffffff
#define inchar getchar_unlocked
#define outchar(x) putchar_unlocked(x)
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

using namespace std;
using ll = long long;
ll md=MD;

ll exp(ll a,ll b){ll r=1ll;while(b>0){if(b&1){r=r*(a%md);r=(r+md)%md;}b>>=1;a=(a%md)*(a%md);a=(a+md)%md;}return (r+md)%md;}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll Min(ll a,ll b){if(a<b)return a; return b;}
ll Max(ll a,ll b){if(a>b)return a; return b;}
int32_t main() {
    IOS;

        ll n,ans=2;
        cin>>n;
        if(n==2){cout<<"1"; return 0;}
        vll v;
        for(int i=2;i*i<=n;++i)if(n%i==0)v.pb(i);
       	//for(int i:v)cout<<i<<" ";
       	//cout<<endl;
        vll tt(v.size(),n);
    	for(int i=0;i<v.size();++i)
    	{
    		while(tt[i]%v[i]==0)tt[i]/=v[i];
    		if(tt[i]%v[i]==1)++ans;
    	}
    	//for(int i:tt)cout<<i<<" ";
    	int i;
    	--n;
    	for(i=2;i*i<(n-1);++i)if(n%i==0)ans+=2; //cout<<endl;
    	if(i*i==n)++ans;
    	cout<<ans;

        cout<<'\n';
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"

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

ll f(ll x) {
    if (x%2 == 0) {
        return x ^ (((x/2)%2 == 0) ? 0 : 1);
    } else return (((x+1)/2)%2 == 0) ? 0 : 1;
}

void solve() {
    ll A,B;
    cin >> A >> B;
    A = max(0LL,A-1);
    cout << (f(A)^f(B)) << endl;

}

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

Measured memory_bytes: 3572
r,g,b,n= map(int,input().split())
R = n//r
G = n // g
B = n // b
ans =0
for i in range(R+2):
    for j in range(G+2):
        if n - (i*r+j*g)< 0:
            continue
        if (n - (i*r+j*g) )%b ==0 and n - (i*r+j*g)>=0:
            ans +=1
print(ans)

Measured memory_bytes: 40684
import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    MOD = 10**9+7
    A,T,G,C = 0,1,2,3
    dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
    for i in range(4):
        for j in range(4):
            for k in range(4):
                if i==A and j==G and k==C:
                    continue
                if i==A and j==C and k==G:
                    continue
                if i==G and j==A and k==C:
                    continue
                dp[3][i][j][k] = 1

    if N == 3:
        print("61")
    else:
        for n in range(4,N+1):
            for i in range(4):
                for j in range(4):
                    for k in range(4):
                        for l in range(4):
                            if i==A and j==G and k==C:
                                continue
                            if i==A and j==C and k==G:
                                continue
                            if i==G and j==A and k==C:
                                continue
                            if l==A and i==G and k==C:
                                continue
                            if l==A and j==G and k==C:
                                continue
                            dp[n][i][j][k] += dp[n-1][l][i][j]
                            dp[n][i][j][k] %= MOD
        ans = 0                    
        for i in range(4):
            for j in range(4):
                for k in range(4):
                    ans += dp[-1][i][j][k]
        print(ans%MOD)

if __name__ == "__main__":
    main()

Measured memory_bytes: 3440
// Aizu Vol-10 1004: Pair of Primes
// 2017.8.16 bal4u@uu

#include <stdio.h>

#define MAX  10000
#define SQRT 100     // sqrt(MAX)
char prime[MAX + 5], *p, *q, *pmax;

int main()
{
	int N, k, ans;

	for (pmax = prime + MAX, k = 3, p = prime + 3; k <= SQRT; k += 2, p += 2)
		if (!*p) for (q = p + k; q <= pmax; q += k) *q = 1;
	prime[1] = 1, prime[2] = 0;	for (p = prime + 4; p <= pmax; p += 2) *p = 1;

	while (scanf("%d", &N) == 1) {
		for (ans = 0, p = prime + 1, q = prime + N, k = 0; k < N; k++, p++, q--)
			if (!*p && !*q) ans++;
		printf("%d\n", ans);
	}
	return 0;
}

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

int h, w, k;
char s[51][51];
int dp[51][51][1 << 12][4], dx[]{ 1,-1,0,0 }, dy[]{ 0,0,1,-1 };
bool used[51][51];
void mark(int x, int y, int t, int s) {
	used[x][y] = true;
	if (!s)return;
	int a = t % 4;
	x -= dx[a], y -= dy[a];
	t >>= 2;
	mark(x, y, t, s - 1);
}
int rec(int x, int y, int t, int a, int cnt) {
	if (dp[x][y][t][a] != -1)return dp[x][y][t][a];
	int res = -INF;
	rep(i, 4) {
		if (i % 2 && !a)continue;
		int nx = x + dx[i], ny = y + dy[i];
		if (nx < 0 || ny < 0 || nx >= h || ny >= w || s[nx][ny] == '#')continue;
		memset(used, 0, sizeof(used));
		mark(x, y, t, cnt);
		int v = ((!used[nx][ny] && '1' <= s[nx][ny] && s[nx][ny] <= '9') ? s[nx][ny] - '0' : 0);
		int p = (t >> (k * 4 - 2)) << (k * 4 - 2); p = t - p;
		p = (p << 2) + i; int b = cnt; if (b < 2 * k)b++;
		int o = rec(nx, ny, p, a - i % 2, b);
		if (o != -INF)res = max(res, o + v);
	}
	if (x == h - 1 && y == w - 1 && res == -INF)return dp[x][y][t][a] = 0;
	return dp[x][y][t][a] = res;
}
int main() {
	scanf("%d%d%d", &h, &w, &k);
	rep(i, h)scanf("%s", s[i]);
	memset(dp, -1, sizeof(dp));
	printf("%d\n", rec(0, 0, 0, k, 0));
}

Measured memory_bytes: 169644
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
using namespace std;
int main(void){
    ll n;cin>>n;
    vector<ll> a(n);
    rep(i,n) cin>>a[i];
    rep(i,n){
        a[i]-=(i+1);
    }
    sort(a.begin(),a.end());
    ll all=(n%2==0)? (a[n/2-1]+a[n/2])/2:a[n/2];
    ll res=1e+18+3;
    for(ll i=-10;i<=10;i++){
        ll nn=all+i;
        ll buf=0;
        rep(j,n){
            buf+=abs(a[j]-nn);
        }
        chmin(res,buf);
    }
    cout<<res<<endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define pii pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
#define sz(x) ((ll)(x).size())
#define pb push_back
#define mp make_pair
#define bit(n) (1LL<<(n))
#define F first
#define S second
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll INF = 1LL<<60;
const ll mod = (int)1e9 + 7;

int main() {
    int H,W,h,w;
    cin >> H >> W >> h >> w;
    cout << H*W-h*W-H*w+h*w;
    


}

/*



 */


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std; 
#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}

const int64 mod = 1e9+7;
map<int64, int64> memo[212345];

int main(void){
	int64 K, N;
	cin >> N >> K;
	vector<int64> h(N);
	REP(i, N) cin >> h[i];
	sort(all(h));
	int64 res = INF_LL;
	REP(i, N-K+1) {
		res = min(res, h[i+K-1]-h[i]);
	}
	cout << res << endl;
}


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

const int64_t MOD = 1000000007;
typedef int64_t ll;
typedef uint64_t ull;

#define INF LLONG_MAX

#define FOR(i, start, end) for(uint64_t i=start; i<end; i++)
#define REP(i, n) FOR(i, 0, n)

// 最大公約数gcd
// 最小公倍数lcm=m*n/gcd
uint64_t gcd(uint64_t m, uint64_t n) {
  uint64_t temp;
  while (m % n != 0){
    temp = n;
    n = m % n;
    m = temp;
  }
  return n;
}

uint64_t lcm(uint64_t m, uint64_t n) {
  return (m*n)/gcd(m,n);
}

// vector<vector<uint64_t> > v(n+1, vector<uint64_t>(n+1, 0))
// v[n][k]に組み合わせ数が入る。
void comb(vector<vector <uint64_t> > &v){
  for(uint64_t i = 0;i <v.size(); i++){
    v[i][0]=1;
    v[i][i]=1;
  }
  for(uint64_t k = 1;k <v.size();k++){
    for(uint64_t j = 1;j<k;j++){
      v[k][j]=(v[k-1][j-1]+v[k-1][j]);
    }
  }
}

// 掛け算オーバーフロー判定
bool is_product_overflow(uint64_t a, uint64_t b) {

	uint64_t prod = a * b;
	
	return (prod / b != a);
}

//素因数分解
void primeFactorization(uint64_t a, list<uint64_t> &factors){ //素因数分解を出力するプログラム
  long i,sq;
  if(a%2==0){ //偶数の場合
    factors.push_back(2);
    primeFactorization(a/2,factors); //2で割った値で再帰
    return;
  }
  sq = sqrt(a);
  for(i=3;i<=sq;i+=2){ //3以上√a以下の奇数の場合
	if(a%i==0){
	  factors.push_back(i);
      primeFactorization(a/i,factors); //割れた値で再帰
      return;
	}
  }
  //偶数でも3以上√a以下の奇数の場合でも割り切れない場合
  if(a!=1){ //aが1でないなら、a自身は素数
    factors.push_back(a);
  }
}

// フェルマーの小定理
// mod. m での a の逆元 a^{-1} を計算する
// (a/b)%m = a*movinv(b,m)%m  
int64_t modinv(int64_t a, int64_t m) {
    int64_t b = m, u = 1, v = 0;
    while (b) {
        int64_t t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

// 円周率
// M_PI

// #include <iomanip> // setprecisionを使用するのに必要
// cout << std::fixed << std::setprecision(15) << y << endl;

// 昇順
// priority_queue<int, vector<int>, greater<int> > queue;

signed main() {
  int n, y;
  cin >> n >> y;
  
  int price[2] = {};
  for(int i=0;i<=n;i++){
    price[0] = i*10000;
    if(price[0] > y) break;
    for(int j=0;j<=n-i;j++){
      price[1] = price[0]+j*5000+(n-i-j)*1000;
      if(price[1]==y){
        cout << i << " " << j << " " << n-i-j << endl;
        return 0;
      }
    }
  }
  cout << "-1 -1 -1" << endl;
  return 0;
}



Measured memory_bytes: 3520
import math
import sys

sys.setrecursionlimit(10000)
INF = float('inf')


def inv(x):
    return pow(x, MOD - 2, MOD)


def comb(n, r, mod):
    # https://fushime2.hatenablog.com/entry/2016/11/12/155543
    return (math.factorial(n) * inv(math.factorial(n - r)) * inv(math.factorial(r))) % mod


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


def pyramid(n):
    return n * (n + 1) * (n + 2) // 6


MOD = 10 ** 9 + 7

# K ==2 の場合
# print(pyramid(N - 1) * M ** 2 + pyramid(M - 1) * N ** 2)
k2 = (pyramid(N - 1) * M ** 2 + pyramid(M - 1) * N ** 2) % MOD
# k2 を何回使うか
c = comb(N * M - 2, K - 2, mod=MOD)
print(k2 * c % MOD)


Measured memory_bytes: 73820
using static System.Math;
using System;

public class Hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var h = int.Parse(line[0]);
        var w = int.Parse(line[1]);
        var k = int.Parse(line[2]);
        var map = new int[h, w];
        for (int i = 0; i < k; i++)
        {
            line = Console.ReadLine().Trim().Split(' ');
            var x = int.Parse(line[0]) - 1;
            var y = int.Parse(line[1]) - 1;
            map[x, y] = int.Parse(line[2]);
        }
        getAns(h, w, map);
    }
    static void getAns(int h, int w, int[,] map)
    {
        var dp = new long[h, w, 4];
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++)
                for (int k = 0; k < 4; k++)
                    dp[i, j, k] = -1;
        dp[0, 0, 0] = 0;
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++)
            {
                for (int k = 2; k >= 0; k--)
                {
                    if (dp[i, j, k] >= 0) dp[i, j, k + 1] = Max(dp[i, j, k + 1], dp[i, j, k] + map[i, j]);
                }
                for (int k = 0; k < 4; k++)
                {
                    if (dp[i, j, k] >= 0)
                    {
                        if (i + 1 < h) dp[i + 1, j, 0] = Max(dp[i + 1, j, 0], dp[i, j, k]);
                        if (j + 1 < w) dp[i, j + 1, k] = Max(dp[i, j + 1, k], dp[i, j, k]);
                    }
                }
            }
        var ans = long.MinValue;
        for (int i = 0; i < 4; i++)
            ans = Max(ans, dp[h - 1, w - 1, i]);
        Console.WriteLine(ans);
    }
}


Measured memory_bytes: 362500
#include <iostream>
#include <vector>
#include <cmath>
#include <cstdint>

using namespace std;

template<typename T>
class RmQ {
private:
    uint32_t n;
    T max;
    vector<T> vec;

    T inner_find(uint32_t a, uint32_t b, uint32_t k, uint32_t l, uint32_t r) {
        if (r <= a || b <= l) {
            return max;
        }
        if (a <= l && r <= b) {
            return vec[k];
        } else {
            int val_l = inner_find(a, b, k * 2 + 1, l, (l + r) / 2);
            int val_r = inner_find(a, b, k * 2 + 2, (l + r) / 2 , r);
            return min(val_l, val_r);
        }
    }

public:
    RmQ(uint32_t num, T max) : max(max) {
        n = (uint32_t)pow(2, ceil(log2(num)));
        vec.resize(2 * n - 1);
        fill(vec.begin(), vec.end(), max);
    }

    void update(uint32_t i, T x) {
        i += n - 1;
        vec[i] = x;
        while (i > 0) {
            i = (i - 1) / 2;
            vec[i] = min(vec[i * 2 + 1], vec[i * 2 + 2]);
        }
    }

    T find(uint32_t a, uint32_t b) {
        return inner_find(a, b, 0, 0, n);
    }
};

int main() {
    int32_t n, q;
    scanf("%d %d", &n, &q);

    RmQ<int32_t> rmq(n, INT32_MAX);

    for (int32_t i = 0; i < q; i++) {
        int32_t com, x, y;
        scanf("%d %d %d", &com, &x, &y);

        if (com) printf("%d\n", rmq.find(x, y+1));
        else rmq.update(x, y);
    }

    return 0;
}

Measured memory_bytes: 4184
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
using ll = long long int;
const ll MOD = 1000000007;

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    ll ans = 0;
    ll sum = 0;
    for(int i = 0; i < n; i++){
        sum += a[i];
        sum %= MOD;
    }
    for(int i = 0; i < n; i++){
        sum -= a[i];
        sum += MOD;
        sum %= MOD;
        ll coans = sum;
        coans *= a[i];
        coans %= MOD;
        ans += coans;
        ans %= MOD;
    }

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

Measured memory_bytes: 4044
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AtCoder
{
    class Program
    {
        private const int MODULO = 1000000007;
        private static string Read() { return Console.ReadLine(); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }

        static int Mod(int a, int b)
        {
            return (a % b + b) % b;
        }
        static int[] Convert(string s)
        {
            return s.Select(c => (c == 'S') ? 1 : -1).ToArray();
        }
        static int[] Solve(int N, int[] S)
        {
            var T = (S[1] == 1) ? new[] { "SSS", "WSW", "SWW", "WWS" }.Select(Convert)
                                : new[] { "SSW", "WSS", "SWS", "WWW" }.Select(Convert);
            foreach (int[] t in T)
            {
                int[] ans = new int[N];
                Array.Copy(t, ans, 3);
                for (int i = 2; i < N; ++i)
                {
                    int a0 = Mod(-2 + i, N);
                    int a1 = Mod(-1 + i, N);
                    int a2 = Mod( 0 + i, N);
                    ans[a2] = ans[a0] * ans[a1] * S[a1];
                }
                if (Enumerable.Range(0, N).All(i =>
                {
                    int a0 = Mod(-1 + i, N);
                    int a1 = Mod( 0 + i, N);
                    int a2 = Mod( 1 + i, N);
                    return (ans[a0] * ans[a2] == ans[a1] * S[a1]);
                }))
                {
                    return ans;
                }
            }
            return null;
        }
        static void Main(string[] args)
        {
            int N = ReadInt();
            string s = Read();
            int[] ans = Solve(N, s.Select(c => (c == 'o') ? 1 : -1).ToArray());
            Console.WriteLine((ans != null) ? new string(Array.ConvertAll(ans, n => (n == 1) ? 'S' : 'W')) : "-1");
        }
    }
}


Measured memory_bytes: 15328
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;

int main() {
    int n;
    cin >> n;
    vector<string> s(n);
    for (int i = 0; i < n; i++) {
        cin >> s.at(i);
    }
    map<string, int> cnt;
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        sort(s.at(i).begin(), s.at(i).end());
        if (cnt.count(s.at(i))) {
            ans += cnt.at(s.at(i));
            cnt.at(s.at(i))++;
        } else {
            cnt[s.at(i)] = 1;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 14312
#include <bits/stdc++.h>
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
#define ll long long
#define fr first
#define sc second
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll a, b, c, d;
	cin >> a >> b >> c >> d;

	ll ans = -2e18;
	ans = max(a * c, ans);
	ans = max(a * d, ans);
	ans = max(b * c, ans);
	ans = max(b* d, ans);
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 3648
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int MAXN=1e5+5;
int a[MAXN];
int G[105][105];

int main()
{
    int h,w;
    while(cin>>h>>w)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;++i)
            cin>>a[i];
        int cnt=1;
        for(int i=1;i<=h;++i)
        {
            if(i&1)
            {
                for(int j=1;j<=w;++j)
                {
                   if(a[cnt]>0) {G[i][j]=cnt;--a[cnt];}
                   else if(a[cnt]==0) {++cnt;G[i][j]=cnt;--a[cnt];}
                }
            }else
            {
                for(int j=w;j>=1;--j)
                {
                    if(a[cnt]>0) {G[i][j]=cnt;--a[cnt];}
                    else if(a[cnt]==0) {++cnt;G[i][j]=cnt;--a[cnt];}
                }
            }
        }
        for(int i=1;i<=h;++i)
        {
            for(int j=1;j<=w;++j)
            {
                if(j!=w) cout<<G[i][j]<<" ";
                else cout<<G[i][j]<<endl;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>
#include <cmath>
#include <utility> // pair make_pair
#include <algorithm>
#include <functional>
#include <iomanip>
#include <climits> // LLONG_MAX, LLONG_MIN, INT_MIN, INT_MAX
#include <assert.h>

#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,63,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define ll long long
#define int ll
#define INF INT_MAX/10

using namespace std;
using Pi = pair<int, int>;
using Graph = vector<vector<int> >;
using WeightGraph = vector<vector<Pi> >;


string S;
string T;

vector<int> Indexes[26];

signed main() {
  cin >> S >> T;
  
  for (int i = 0; i < S.size(); i++) {
    // cout << S[i] << " "<< S[i] - 'a' << endl;
    Indexes[S[i] - 'a'].push_back(i);
  }


  int ans = (Indexes[T[0] - 'a'].empty() ? -1 : Indexes[T[0] - 'a'][0]);
  if (ans == -1 ) {
    cout << ans << endl;
    return 0;
  }
  int prev_index  = Indexes[T[0] - 'a'][0];
  for (int i = 1; i < T.size(); i++) {
    if (ans > 1e100)  {
      cout << -1 << endl;
      return 0;
    }
    if (Indexes[T[i]- 'a'].empty()) {
      cout << -1 << endl;
      return 0;
    } else {
      // cout << " " << prev_index << " " << ans << endl;
      // cout << T[i] << " ";
      // int flag = 0;
      int k = upper_bound(Indexes[T[i]-'a'].begin(), Indexes[T[i]-'a'].end(), prev_index) - Indexes[T[i]- 'a'].begin();
      if (k == Indexes[T[i]-'a'].size()) {
        ans += Indexes[T[i] - 'a'][0] - prev_index + S.size();
        prev_index = Indexes[T[i] - 'a'][0];
      } else {
        ans += Indexes[T[i]-'a'][k] - prev_index;
        prev_index = Indexes[T[i]-'a'][k];
      }
      // for (auto next_index : Indexes[T[i] - 'a']) {
      //   if (next_index > prev_index) {
      //     ans += next_index - prev_index;
      //     prev_index = next_index;
      //     flag = 1;
      //     break;
      //   } 
      // }
      // if (flag == 0) {
      // }
    }
  }
  cout << ans+1 << endl;
}


Measured memory_bytes: 1724
#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define irep(i,a,b) for(ll i=ll(a);i>=ll(b);i--)
using ll = long long;
using namespace std;

int main(){
	string s;
    cin>>s;
    ll dp[110000][20];
    dp[0][0]=1;
    ll st;
    rep(i,0,s.length()){
        if(s[i]=='?')st=-1;
        else st=ll(s[i]-'0');
        rep(j,0,10){
            if(st!=-1 && st!=j)continue;
            rep(k,0,13){
                dp[i+1][(k*10+j)%13]+=dp[i][k];
            }
        }
        rep(j,0,13) dp[i+1][j]%=1000000007;
    }
    cout<<dp[s.length()][5];
}

Measured memory_bytes: 17024
#include <iostream>
#include <algorithm>
using namespace std;
int gcd (int a, int b) {
	for (;;) {
		if (!(a %= b)) return b;
		if (!(b %= a)) return a;
	}
}
int main () {
	int a, b, n, m;
	while (cin >> a >> b) {
		m = (n = gcd (a, b)) ? a/n*b : 0;
		cout << n << " " << m << endl;
	}
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define inf INFINITY
#define file freopen( "input.txt" , "r" , stdin) ; freopen( "output.txt" , "w" , stdout) ;
#define Gamed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define _3102_ main()
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
const int N = 2e5 + 100;
const ll MX = 1e9;
const ll mod = 1e9 + 7;
const double eps = 1e-9 ;

char grid[1100][1100] ;
int n, m, dp[1100][1100] = { } ;

ll solve ( int i , int j ){
	if ( i < 0 || j < 0 ) return 0 ;
	if ( dp[i][j] != -1) return dp[i][j] ;
	if ( i == 0 && j == 0 ) return dp[i][j] = 1 ;
	if ( grid[i][j] == '#') return dp[i][j] = 0 ;
	return dp[i][j] = (( solve(i-1,j)%mod + solve(i,j-1)%mod))%mod ;
}

int _3102_{
	Gamed
	cin >> n >> m ;
	for ( int i = 0 ; i < n ; i ++){
		for ( int j = 0 ; j < m ; j ++){
			cin >> grid[i][j] ;
		}
	}
	memset ( dp , -1 , sizeof dp) ;
	cout << solve( n - 1 , m - 1 ) << endl ;
	return 0;
}

/*
3 4
...#
.#..
....
*/


Measured memory_bytes: 9492
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int M = 1e9+7,ms = 1e3+9;
int dp[ms][ms];
char matrix[ms][ms];
int n, m;

bool is_valid(int i, int j){
  return (i>=0 and i <n and j >=0 and j < m and matrix[i][j] !='#');
}


int solve(int x, int y){

  if(x == n-1 and y == m-1)
    return dp[x][y] = true;

  int &ans = dp[x][y];
  if(~ans)
    return ans;

  ans = 0;

  if(is_valid(x+1, y)){
    ans = (ans + solve(x+1, y))%M;
  }
  if(is_valid(x, y+1)){
    ans = (ans + solve(x, y+1))%M;
  }

  return ans;
}

main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  cin >> n >> m;
  for(int i = 0; i <n; i++)
    for(int j = 0; j < m; j++) cin >> matrix[i][j];


  memset(dp, -1, sizeof dp);

  cout<<solve(0, 0);
}

Measured memory_bytes: 9344
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int s = sc.nextInt();
        int count = 0;
        for (int i = 0; i <= k; i++) {
            for (int j = 0; j <= k; j++) {
                if (s - (i + j) <= k && 0 <= s - (i + j))
                    count++;
            }
        }
        System.out.println(count);
    }
}


Measured memory_bytes: 23124
#include <iostream>

int main(){
   int N;
   std::cin >> N;
   int p[N];
   for(int i=0; i<N; ++i)
      std::cin >> p[i];

   bool flag = true;
   int count = 0;
   for(int i=0; i<N; ++i){
      if(p[i]>i+1) count++;
   }
   if(count<2) std::cout << "YES" << std::endl;
   else std::cout << "NO" << std::endl;

   return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int a,b,c;
int largest;
int middle;
int smallest;

int main(void) {
	scanf("%d %d %d",&a,&b,&c);
/*	largest=a;
	if(largest<=b){
		largest=b;
		if(largest<=c){
			largest=c;
		}
		else;
	}
	else;

	smallest=a;
	if(smallest>=b){
		smallest=b;
		if(smallest>=c){
			smallest=c;
		}
		else;
	}
	else;
*/


	if(a<=b){
		largest=b;
		smallest=a;
		if(c>=largest){
				middle=b;
				largest=c;
		}
		else if(c<largest){
				if(c<=smallest){
					middle=a;
					smallest=c;
				}
				else{
					middle=c;
				}
			}
	}
	else if(a>b){
		largest=a;
		smallest=b;
		if(c>=largest){
				middle=largest;
				largest=c;
		}
		else if(c<largest){
				if(c<=smallest){
					middle=smallest;
					smallest=c;
				}
				else{
					middle=c;
				}
			}
	}


			 	printf("%d %d %d\n",smallest,middle,largest);

	return 0;

}



Measured memory_bytes: 2040
#include <bits/stdc++.h>
using namespace std;
char Map[60][60];
int Num[60][60];
int n,m;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>Map[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(Map[i-1][j-1]=='#') Num[i][j]++;
			if(Map[i-1][j]=='#') Num[i][j]++;
			if(Map[i-1][j+1]=='#') Num[i][j]++;
			if(Map[i][j-1]=='#') Num[i][j]++;
			if(Map[i][j+1]=='#') Num[i][j]++;
			if(Map[i+1][j-1]=='#') Num[i][j]++;
			if(Map[i+1][j]=='#') Num[i][j]++;
			if(Map[i+1][j+1]=='#') Num[i][j]++;
		}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(Map[i][j]=='#') cout<<"#";
			else cout<<Num[i][j];
		}
		cout<<"\n";
	}	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define dunk(a) cout << (a) << endl
using namespace std;
typedef long long ll;

int n,k;
string s;

int main(){
    cin >> n >> k;
    cin >> s;

    if(s[k-1] == 'A') s[k-1] = 'a';
    if(s[k-1] == 'B') s[k-1] = 'b';
    if(s[k-1] == 'C') s[k-1] = 'c';

    dunk(s);
}

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

typedef long long ll;

int main(){
	const int INF = 1e9;
	int n,x;
	cin >> n >> x;
	vector<int> X;
	X.push_back(x);
	rep(i,n){
		int t; cin >> t;
		X.push_back(t);
	}
	sort(X.begin(),X.end());

	int ans = INF;
	rep(i,n){ ans = min(ans, X[i+1]-X[i]); }
	rep(i,n){ ans = __gcd(X[i+1]-X[i],ans); }

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

Measured memory_bytes: 892
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scan = new Scanner(System.in);
		
		//金額取得
		int input = scan.nextInt();
		
		//税抜き計算
		//切り上げ価格
		int ceil =(int) Math.ceil(input/1.08);
		
		//切り捨て価格
		int floor =(int)Math.floor(input/1.08);
		
		if((int)Math.floor(ceil*1.08)==input) {
			System.out.println(ceil);
		}
		else if((int)Math.floor(floor*1.08)==input) {
			System.out.println(floor);
		}
		else {
			System.out.println(":(");
		}
		
		
	}

}


Measured memory_bytes: 21844
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        if (b % a == 0) {
            System.out.println(a+b);
        } else {
            System.out.println(b - a);
        }
    }
}


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

const int N = 100000 + 5;
const long long inf = 1e18;

int n;
int k;
int h[N];
long long memo[N];

int main(){
	scanf("%d %d", &n, &k);
	for(int i = 1; i <= n; i++) scanf("%d", &h[i]);
	for(int i = n - 1; i >= 1; i--){
		memo[i] = inf;
		for(int j = 1; j <= k and i + j <= n; j++){
			memo[i] = min(memo[i], abs(h[i] - h[i + j]) + memo[i + j]);
		}
	}
	printf("%lld\n", memo[1]);
	return 0;
}

Measured memory_bytes: 4996
treeRoot = {'left': None, 'right': None, 'p': None, 'val': None}

root = None


def insert(val):
    global root
    z = {'left': None, 'right': None, 'p': None, 'val': val}
    x = root
    y = None
    while x:
        y = x
        if z['val'] < x['val']:
            x = x['left']
        else:
            x = x['right']
    z['p'] = y
    if y is None:
        root = z
    else:
        if z['val'] < y['val']:
            y['left'] = z
        else:
            y['right'] = z


def inorder(root):
    if root is None:
        return
    inorder(root['left'])
    print(' ', end='')
    print(root['val'], end='')
    inorder(root['right'])


def preorder(root):
    if root is None:
        return
    print(' ', end='')
    print(root['val'], end='')
    preorder(root['left'])
    preorder(root['right'])


M = int(input())
for _ in range(M):
    line = input().strip()
    if line == 'print':
        inorder(root)
        print('')
        preorder(root)
        print('')
    else:
        inst, k = line.split()
        k = int(k)
        if inst == 'insert':
            insert(k)
        elif inst == 'find':
            pass
        elif inst == 'delete':
            pass

Measured memory_bytes: 173244
#include <bits/stdc++.h>
 
typedef long long ll;
using namespace std;
const int MOD = 1e9+7;
int cache[1001][1001];
bool is_valid(int row, int col, int n, int m){
	return (row>=0 && row<n) && (col>=0 && col<m);
}
int calc(char ar[][1001], int row, int col, int N, int M) {
	if(!is_valid(row, col, N, M) || ar[row][col]=='#') {
		return 0;
	}
	
	if(row==N-1 && col==M-1) {
		return 1;
	}
	
	if(cache[row][col]!=-1) {
		return cache[row][col];
	}
	
	int right = calc(ar, row+1, col, N, M);
	int down = calc(ar, row, col+1, N, M);
	cache[row][col] = (right + down)%MOD;
	return cache[row][col];
}

int main() {
	int n,m;
	cin>>n>>m;
	char ar[1001][1001];
	int dp[1001][1001];
	for (int i=0; i<n; i++)	{
		for (int j=0; j<m; j++) {
			cin>>ar[i][j];
			dp[i][j] = 0;
			//cache[i][j] = -1;
		}
	}
	
	
	dp[0][0] = 1;
	for (int i=0; i<n; i++) {
		for (int j=0; j<m; j++) {
			if(i==0 && j==0) {
				continue;
			}
			if(ar[i][j]=='#') {
				continue;
			}
			dp[i][j] = (i-1>=0 ? dp[i-1][j] : 0);
			dp[i][j] +=(j-1>=0 ? dp[i][j-1] : 0);
			dp[i][j]%=MOD;
		}
	}
	cout << dp[n-1][m-1]; 
	return 0;
}

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

int main(){
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i=0;i<n;i++) {
		cin >> a[i];
	}
	bool flag = true;
	for(int i=n-2;i>=0;i--) {
		if(a[i] > a[i+1]) {
			a[i]--;
			if(a[i] != a[i+1]) {
				flag = false;
			}
		}
	}
	for(int i=0;i<n-1;i++) {
		if(a[i] > a[i+1]) flag =false;
	}
	cout << ((flag)?"Yes":"No") << endl;
}

Measured memory_bytes: 640
import java.io.*;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] line1 = br.readLine().split(" ");
    int vertical = Integer.parseInt(line1[0]);
    int horizontal = Integer.parseInt(line1[1]);
    
    boolean[][] square = new boolean[vertical+2][horizontal+2];
    char[] data;
    
    for(int i=0; i<vertical; i++){
      data = br.readLine().toCharArray();
      for(int j=0; j<horizontal; j++){
        square[i+1][j+1] = (data[j] == '#');
      }
    }
    for(int i=0; i<horizontal+2; i++){
      square[0][i] = false;
      square[vertical+1][i] = false;
    }
    for(int i=0; i<vertical+2; i++){
      square[i][0] = false;
      square[i][horizontal+1] = false;
    }
    for(int i=0; i<vertical; i++){
      for (int j=0; j<horizontal; j++){
        if(square[i+1][j+1] && (!square[i+1][j] && !square[i+1][j+2] && !square[i][j+1] && !square[i+2][j+1])){
          System.out.println("No");
          return;
        }
      }
    }
    System.out.println("Yes");
  }
}

Measured memory_bytes: 24660
A, B = [int(i) for i in input().split()]

if A == 0 and B == 0:
    print('0')

elif A == 1 and B >= 0:
    print(A + B)

elif A >= 0 and B == 1:
    print(A + B)

elif A > 0 and B > 0:
    print(A * B)

elif A < 0 and B < 0:
    print(A * B)

elif A <= 0 and B >= 0:
    print(A + B)

else:  # A >= 0 and B <= 0:
    print(A - B)


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


string S;
int main(){
	cin >> S;
	if(S.size() < 4){
		cout << "No" << endl;
	}else{
		if(S[0] == 'Y' &&
			S[1] == 'A' &&
			S[2] == 'K' &&
			S[3] == 'I'){
			cout << "Yes" << endl;
		}else{
			cout << "No" << endl;
		}
	}

}


Measured memory_bytes: 256
from collections import Counter

n = int(input())
ss = []
for _ in range(n):
    ss.append(input().rstrip())
ctr = Counter(ss)

a = sorted([(-v, k) for k, v in ctr.items()])
maxv = a[0][0]
for i in range(len(a)):
    if a[i][0] != maxv:
        break
    print(a[i][1])

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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
typedef long long ll;

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

  if(a+b+2*(long double)sqrtl(a*b)<c) cout << "Yes";
  else cout << "No";
}

Measured memory_bytes: 3624
k = int(input())
table = [False] * k
i = 1
now = 7
while True:
    if now % k == 0:
        print(i)
        exit()
    if table[now % k]:
        print(-1)
        exit()
    table[now % k] = True
    now = (now * 10 + 7) % k
    i += 1


Measured memory_bytes: 71032
#include <bits/stdc++.h>
#define R register
#define mp make_pair
#define ll long long
#define pii pair<int, int>
using namespace std;
const int N = 210000;

ll n, sum[N], ans = 1e18;

template <class T>
inline void read(T &x) {
    x = 0;
    char ch = getchar(), w = 0;
    while (!isdigit(ch)) w = (ch == '-'), ch = getchar();
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    x = w ? -x : x;
    return;
}

int main() {
    int x;
    read(n);
    for (R int i = 1; i <= n; ++i)
        read(x), sum[i] = sum[i - 1] + x;
    for (R int i = 1; i < n; ++i)
        ans = min(ans, abs(sum[n] - 2 * sum[i]));
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
//todo: compare with tle
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
ll arr[2000050];
ll g(int x,int y);
ll f(int x,int y);
ll cal(ll a,int b);
int main(){  
	int r1, r2, c1, c2;  
	arr[0]=1;
	for (int i=1;i<2000010;i++) arr[i]=(arr[i-1]*(ll)i)%MOD;
	cin>>r1>>c1>>r2>>c2;
	ll ans=g(r2,c2)-g(r1-1,c2)-g(r2,c1-1)+g(r1-1,c1-1);
	ans%=MOD;
	if (ans<0) ans+=MOD;
	cout<<ans;
	return 0;
}

ll g(int x,int y) {
	ll sum=0;
	for (int i=1;i<=x+1;i++) 
		(sum+=f(i,y))%=MOD;
	return sum;
}

ll f(int x,int y) {
	return arr[x+y]*cal(arr[x],MOD-2)%MOD*cal(arr[y],MOD-2)%MOD;
}

ll cal(ll a,int b) {
	if (b==0) return 1;
	if (b%2==1) return a*cal(a*a%MOD,b/2)%MOD;
	else return cal(a*a%MOD,b/2); 
}


Measured memory_bytes: 15872
d, g = map(int, input().split())
g //= 100
PC = [ list(map(int, input().split())) for _ in range(d) ]
P, C = zip(*PC)
C = [i//100 for i in C]
ans = float("inf")
for i in range(2**d):
  count = 0
  end = 0
  l = []
  for j in range(d):
    if i>>j & 1:
      count += P[j]
      end += (j+1)*P[j] + C[j]
    else:
      l += [j+1]*(P[j]-1)
  l.sort()
  while end < g and l:
    end += l.pop()
    count += 1
  if end < g:
    continue
  ans = min(ans, count)
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; //int:2*10**9
typedef long double ld;
typedef pair<ll,ll> P;
#define REP(i,n) for(ll i = 0; i<(ll)(n); i++)
#define REPS(i,n) for (ll i = 1; i<=(ll)(n); i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define vec2(name,i,j) vector<vector<ll>> name(i,vector<ll>(j))
#define vec2f(name,i,j,k) vector<vector<ll>> name(i,vector<ll>(j,k))
#define vec3(name,i,j,k) vector<vector<vector<ll>>> name(i,vector<vector<ll>>(j,vector<ll>(k)))
#define vec3f(name,i,j,k,l) vector<vector<vector<ll>>> name(i,vector<vector<ll>>(j,vector<ll>(k,l)))
#define vec4(name,i,j,k,l) vector<vector<vector<vector<ll>>>> name(i,vector<vector<vector<ll>>>(j,vector<vector<ll>>(k,vector<ll>(l))))
#define vec4f(name,i,j,k,l,m) vector<vector<vector<vector<ll>>>> name(i,vector<vector<vector<ll>>>(j,vector<vector<ll>>(k,vector<ll>(l,m))))
#define pb push_back
#define MOD 1000000007
#define MOD2 998244353
#define PI 3.141592653
#define INF 100000000000000 //14
//cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);

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

Measured memory_bytes: 3628
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
 
namespace INPUT{
	const int L=1<<15;
	char _buf[L],*S,*T,c;
	char _gc(){
		if(S==T){
			T=(S=_buf)+fread(_buf,1,L,stdin);
			if(S==T) return EOF;
		}
		return *S++;
	}
	void readi(int &X){
		register bool flag;
		for(c=_gc();(c<'0'||c>'9')&&c!='-';c=_gc());
		if(c=='-') X=0,flag=true; else X=c&15,flag=false;
		for(c=_gc();c>='0'&&c<='9';X=X*10+(c&15),c=_gc());
		if(flag) X=-X;
	}
}
using INPUT::readi;
 
const int Maxn=2E5+5;
 
int N,M,K,V;
int a[Maxn];
int F[Maxn<<1],G[Maxn<<1];
int L[25][Maxn],R[25][Maxn];
char Ans[50],_1[50]={"Possible"},_2[50]={"Impossible"};
//int nxt[Maxn];
 
inline void MIN(int &x,int y){if(x>y)x=y;}
inline void MAX(int &x,int y){if(x<y)x=y;}
 
int main(){
	readi(N),readi(V);
	while(V>>M) ++M;
	for(int i=1;i<=N;++i) readi(a[i]);
	for(int i=0;i<=M;++i){
		L[i][1]=1;
		for(int j=2;j<=N;++j)
			if(a[j]-a[j-1]>(V>>i)) L[i][j]=j;
                        else L[i][j]=L[i][j-1];
		
		R[i][N]=N;
		for(int j=N-1;j>=1;--j)
			if(a[j+1]-a[j]>(V>>i)) R[i][j]=j;
                        else R[i][j]=R[i][j+1];
	}
	G[0]=N+1;
	for(int i=1;i<(1<<M);++i){
		G[i]=N+1;
		for(int j=0;j<M;++j)
			if((i>>j)&1)
				MAX(F[i],R[M-j][min(F[i-(1<<j)]+1,N)]),
				MIN(G[i],L[M-j][max(G[i-(1<<j)]-1,1)]);
	}
	for(int i=1;i<=N;++i)
		K+=(L[0][i]!=L[0][i-1]);
	if(K>20){
		for(int i=1;i<=N;++i)
			puts("Impossible");
		return 0;
	}
	for(int i=1,j;i<=N;++i)
		if(L[0][i]!=L[0][i-1]){
			for(j=0;j<(1<<M);++j)
				if(F[j]>=L[0][i]-1 && G[(1<<M)-1-j]<=R[0][i]+1)
					{memcpy(Ans,_1,sizeof(_1)); break ;}
			if(j==1<<M) memcpy(Ans,_2,sizeof(_2));
			printf("%s\n",Ans);
		}else printf("%s\n",Ans);
/*	memset(nxt,-1,sizeof(nxt));
	for(int i=0;i<(1<<M);++i) MAX(nxt[G[(1<<M)-1-i]],F[i]);
	for(int i=1;i<=N+1;++i) MAX(nxt[i],nxt[i-1]);
	for(int i=1;i<=N;++i)
		if(nxt[R[0][i]+1]>=L[0][i]-1)
			puts("Possible");
		else
			puts("Impossible");*/
	return 0;
}

Measured memory_bytes: 39296
using System;
using System.Collections.Generic;

public class Replacing{
       static int[]strToIntArr(String s){
//          s = s.Substring(1,s.Length-2);
	  string[] strArr = s.Split(new char[]{' '});
	  int len = strArr.Length;
          int[] retArr = new int[len];       
	  for(int i=0;i<len;i++){
	     string sVal = strArr[i];
	     int intVal = int.Parse(sVal);
	     retArr[i] = intVal;
	  }
          return retArr;
       }

  long[]getSums(int n, int q, int[]a, int[]b,int[]c){
      Dictionary<int,int>ctMap = initCtMap(n,a);
      long currS = getSum(n,a);
      long[]sArr = new long[q];
      for(int i=0;i<q;i++){
         if(ctMap.ContainsKey(b[i])){
	    long diff = c[i]-b[i];
	    long offset = diff*ctMap[b[i]];
	    currS += offset;
	    if(ctMap.ContainsKey(c[i])){
	       ctMap[c[i]] += ctMap[b[i]];
	    }else{
	       ctMap[c[i]] = ctMap[b[i]];	       
	    }
	    ctMap[b[i]] = 0;	    
	 }
	 sArr[i] = currS;
      }
      return sArr;
  }

  Dictionary<int,int>initCtMap(int n, int[]a){
  Dictionary<int,int>retD = new Dictionary<int,int>();
     for(int i=0;i<n;i++){
        int el = a[i];
        if(retD.ContainsKey(el)){
	   retD[el]++;
	}else retD[el] = 1;
     }
     return retD;
 }

  long getSum(int n, int[]a){
     long sum = 0L;
     for(int i=0;i<n;i++){
      sum += a[i];
    }
    return sum;
 }
  public static void Main(string[]args){
     string nLn,aLn,qLn;
     Replacing r = new Replacing();
     nLn = Console.ReadLine();
     aLn = Console.ReadLine();
     qLn = Console.ReadLine();
     int n = int.Parse(nLn);
     int q = int.Parse(qLn);
     int[]arr = strToIntArr(aLn);
     int[]b = new int[q];
     int[]c = new int[q];
     for(int i=0;i<q;i++){
        string bcLn = Console.ReadLine();
        int[] bcArr = strToIntArr(bcLn);
	b[i] = bcArr[0];
	c[i] = bcArr[1];
     }
     long[]s = r.getSums(n,q,arr,b,c);
      for(int i=0;i<q;i++){
         Console.WriteLine("{0}",s[i]);
      }
  }
}

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

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

  int H, W, N;
  cin >> H >> W >> N;

  int R, C;
  cin >> R >> C;
  --R, --C;

  string S, T;
  cin >> S >> T;

  vector<tuple<int, int, int>> mov[2];
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < 2; ++j) {
      string &u = j ? T : S;
      int k = u[i] == 'L' || u[i] == 'R';
      if (mov[k].empty() || get<0>(mov[k].back()) != j) {
        mov[k].emplace_back(j, 0, 0);
      }
      if (u[i] == 'L' || u[i] == 'U') --get<1>(mov[k].back());
      else ++get<2>(mov[k].back());
    }
  }

  auto solve = [&]() -> string {
    for (int k = 0; k < 2; ++k) {
      int ltol = k ? -C : -R;
      int rtol = k ? W - 1 - C : H - 1 - R;
      for (int i = 0, ll = 0, rr = 0; i < mov[k].size(); ++i) {
        int t, l, r;
        tie(t, l, r) = mov[k][i];
        if (t == 0) {
          if (rr + l < ltol || rtol < ll + r) return "NO";
          ll += r;
          rr += l;
        } else {
          ll = max(ltol, ll + l);
          rr = min(rtol, rr + r);
        }
        // cout << k << " " << t << " " << l << " " << r << " " << ll << " " << rr << endl;
      }
    }
    return "YES";
  };

  cout << solve() << endl;
  
  return 0;
}


Measured memory_bytes: 6976