akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <cmath>
#include <ctime>
#include <iostream>
#include <list>
#include <map>
#include <math.h>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <stdio.h>
#include <string>
#include <vector>
#define rep(i,n) for(int i = 0; i < (n); i++)
#define all(a) a.begin(),a.end()
using namespace std;
using ll = long long;
using P = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;

int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

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

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






#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i>b;i--)
#define vint vector<int> 
#define vvint vector<vint>
#define CST(x) cout<<fixed<<setprecision(x)//小数点以下の桁数指定
#define ct(a) cout<<a<<endl
static const double pi = 3.141592653589793;
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const int INF = 1e9+7;
const int mod= 1e9 + 7;

ll RepeatedSquaring(ll N, ll P, ll M) {
  if(P==0) return 1;
  if(P%2==0) {
    ll t = RepeatedSquaring(N, P/2, M);
    return t*t % M;
  }
  return N*RepeatedSquaring(N, P-1, M);
}



ll modre(ll num) {
  num %= MOD;
  if(num < 0) num += MOD;
  return num;
}

ll mod_pow(ll x,ll n) {
	if (n == 0) return 1;
	ll res = mod_pow(x*x % mod, n / 2);
	if (n & 1) res = res * x % mod;
	return res;
}
 

 
ll comb(ll n, ll x) {
	ll ret = 1,k=1;
	rep(i,x)ret = (ret * (n - i))%mod;
	rep(i,x)k = (k * (x-i))%mod;
	// k = RepeatedSquaring(k, MOD-2, MOD);
	k = mod_pow(k, mod - 2);
	ret = (ret*k + mod) % mod;
	return ret;
}
  
int main() {
  ll a,b,n;
  cin >> n >> a >> b;
  ll ans = RepeatedSquaring(2, n, MOD) - 1;
  a = comb(n,a);
  b = comb(n,b);
  cout << modre(ans - a - b) << endl;
}






Measured memory_bytes: 1016
//============================================================================
// Name        : A-Shrinking.cpp
// Author      : tt
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <string>
using namespace std;

std::string str = "";
int maxDist[27] = {0};

void solve(){
	std::cin >> str;
	maxDist[0] = {0};

	int i;
	for(i=0; i<26; i++) maxDist[i] = -1;

	int strind;
	int alpind;

	for(alpind=0; alpind < 26; alpind++){
		int distCount = 0;
		for(strind = 0; strind< str.length(); strind++){
				if(str[strind] == (char)('a'+alpind) ){
					if(maxDist[alpind] < distCount) maxDist[alpind] = distCount;
					distCount = 0;
				}else	distCount++;
		}
		if(maxDist[alpind] < distCount) maxDist[alpind] = distCount;
	}

	int minDist = 10000;
	for(alpind=0; alpind < 26; alpind++){
		if(minDist > maxDist[alpind] && maxDist[alpind] >=0) minDist = maxDist[alpind];
	}

	printf("%d\n", minDist);

}

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


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

int main()
{
    string s;
    cin >> s;
    stack<char> st;
    for (int i = 0; i < s.size(); i++)
    {
        st.push(s[i]);
        if (2 <= st.size())
        {
            char a = st.top();
            st.pop();
            char b = st.top();
            st.pop();
            if (!((a == '1' && b == '0') || (a == '0' && b == '1')))
            {
                st.push(b);
                st.push(a);
            }
        }
    }
    cout << s.size() - st.size() << endl;
    return 0;
}

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

int main(void){
    string s; cin >> s;
    ll ans = 0;
    for(int i=1;i<s.length();i++){
        if(s[i] != s[i-1]) ans++;
    }
    cout << ans << endl;
    return 0;
}

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

int n;
int t[100010];
int x[100010];
int y[100010];

int main(){
  cin >> n;
  for(int i = 1; i <= n; ++i){
    cin >> t[i] >> x[i] >> y[i];
  }
  t[0] = 0;
  x[0] = 0;
  y[0] = 0;
  string res = "Yes";
  for(int i = 1; i <= n; ++i){
    if((t[i] - t[i-1]) < (abs(x[i] - x[i-1]) + abs(y[i] - y[i-1]))){
      res = "No";
    }
    if((t[i] - t[i-1]) % 2 != (abs(x[i] - x[i-1]) + abs(y[i] - y[i-1])) % 2){
      res = "No";
    }
  }
  cout << res << endl;
}

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


long long solve(int h, int w) {
  if (h > w) return -1;

  long long minV = 922337203685477580;

  // 3 piece
  if (h % 3 == 0) {
    minV = min(minV, 0LL);
  } else {
    minV = min(minV, w * 1LL);
  }

  if (w % 3 == 0) {
    minV = min(minV, 0LL);
  } else {
    minV = min(minV, h * 1LL);
  }
  // complex
  for (int x = 0; x < w; x++) {
    for (int y = max(h / 2 - 1, 0); y < h / 2 + 1 && y < h; y++) {
    // for (int y = 0; y < h; y++) {
      long long vertical = 1LL * h * (x + 1);
      long long horizontalUp = 1LL * ((w - 1) - x) * (y + 1);
      long long horizontalDown = 1LL * ((w - 1) - x) * ((h - 1) - y);

      long long s = min(vertical, min(horizontalUp, horizontalDown));
      long long m = max(vertical, max(horizontalUp, horizontalDown));

      minV = min(minV, m - s);
    }
  }
  for (int y = 0; y < h; y++) {
    for (int x = max(w / 2 - 1, 0); x < w / 2 + 1 && x < w; x++) {
    // for (int y = 0; y < h; y++) {
      long long horizontal = 1LL * w * (y + 1);
      long long verticalLeft = 1LL * ((h - 1) - y) * (x + 1);
      long long verticalRight = 1LL * ((h - 1) - y) * ((w - 1) - x);

      long long s = min(horizontal, min(verticalLeft, verticalRight));
      long long m = max(horizontal, max(verticalLeft, verticalRight));

      minV = min(minV, m - s);
    }
  }

  return minV;
}


int main() {
  int H, W;
  cin >> H >> W;

  long long s;
  if (H > W) {
    s = solve(W, H);
  } else {
    s = solve(H, W);
  }
  cout << s << endl;
  return 0;
}


Measured memory_bytes: 256
s = input()
ans = 0
possible = set(["A", "C", "G", "T"])

for i in range(len(s), -1, -1):
  for j in range(len(s)):
    if j + i > len(s):
      break
    else:
      sub = s[j:i+j]
      if set(sub).issubset(possible):
        ans = max(ans, len(sub))

print(ans)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <math.h>
#include<map>
#include<algorithm>
using namespace std;
typedef long long int ll;
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; }
#define all(a)  (a).begin(),(a).end()
#define rep(i, n) for (ll i = 0; i < n; i++)
#define vll vector<ll>
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define cinf(n,x,y) for(int i=0;i<(n);i++) cin >> x[i]>>y[i];
const ll INF =1LL << 62;
int main(){
  int a,b,c,d,e,k;
  cin >> a >> b >> c >> d >> e >> k;
  if(e-a <=k) cout <<"Yay!" << endl;
  else cout << ":(" << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N;
    cin >> N;
    bool ans = false;
    for(int i = 0; i <= N / 4; i++){
        for(int j = 0; j <= N / 7; j++){
            if(4 * i + 7 * j == N){
                ans = true;
            }
        }
    }
    if(ans){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 3636
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(void){
	int n,i,j,e0,w0,e1,w1,c;
	string s;
	cin>>n;
	cin>>s;
	e0=0;
	w0=0;
	for(i=0;i<n;i++){
		if(s[i]=='W'){
			w0++;
		}
		else{
			e0++;
		}
	}
	e1=e0;w1=0;
	c=1000000;
	for(i=0;i<n;i++){
		if(s[i]=='E'){
			e1--;
			c=min(c,e1+w1);
		}
		else{
			w1++;
			c=min(c,e1+w1-1);
		}
	}
	cout<<c<<endl;
	return 0;
}


Measured memory_bytes: 900
def judge(i):
    if i in [1, 3, 5, 7, 8, 10, 12]:
        return 0
    elif i in [4, 6, 9, 11]:
        return 1
    else:
        return 2
x, y = map(int, input().split())
if judge(x) == judge(y):
    print("Yes")
else:
    print("No")

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

// @@ !! LIM()

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  ll n; cin >> n;
  string v;
  while (n >= 1) {
    ll x = (n - 1) % 26;
    v += 'a' + x;
    n = (n - 1) / 26;
  }
  reverse(v.begin(), v.end());
  cout << v << endl;
  

  return 0;
}



Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,x;
  cin>>n>>x;
  int t=n*2;
  int s=n*4;
  if(x%2==0&&x>=t&&x<=s)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
}

Measured memory_bytes: 3620
#include<stdio.h>
int main()
{
    int a,b,c,s;
    scanf("%d %d %d",&a,&b,&c);
    if(a>b)
    {
        s=a;
        a=b;
        b=s;
    }
    if(a>c)
    {
        s=a;
        a=c;
        c=s;
    }
    if(b>c)
    {
        s=b;
        b=c;
        c=s;
    }
    printf("%d\n",c-a);
}


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

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

    string S, T;
    cin >> S >> T;
    cout << (S[0] == T[0]) + (S[1] == T[1]) + (S[2] == T[2]) << '\n';

    return 0;
}

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

using namespace std;


void solve() {
    int n; cin >> n;
    vector<int> res(n+1);
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        res[x] = i;
    }
    for (int i = 1; i <= n; i++) {
        cout << res[i] << ' ';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using mii = map<int, int>;
using mll = map<ll, ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vpi = vector<pii>;
using vl = vector<ll>;
using vll = vector<vl>;
using vpl = vector<pll>;
using vs = vector<string>;

int main()
{
    int n;
    cin >> n;
    double ans = 0;
    if(n%2 == 0) ans = 0.5;
    else ans = (n/2+1) / (double)n;
    cout << ans << endl;

    return 0;
}


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

#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

using namespace std;
using LL = long long;

constexpr int MAXN = 2e5 + 5;

struct node {
    node() = default;
    node(int _id, int _val, int _pop): id(_id), preVal(_val), pop(_pop) {}
    int id, preVal, pop;
};

int n, val[MAXN], ans[MAXN];
vector<int> G[MAXN], vec;
stack<node> s;

void dfs(int cur, int fa) {
    if (cur == 1) vec.emplace_back(val[cur]), s.push(node(0, 0, true));
    else {
        if (val[cur] > vec.back()) vec.emplace_back(val[cur]), s.push(node(0, 0, true));
        else {
            int pos = lower_bound(vec.begin(), vec.end(), val[cur]) - vec.begin();
            s.push(node(pos, vec[pos], false));
            vec[pos] = val[cur];
        }
    }
    ans[cur] = vec.size();
    for (auto &to : G[cur]) {
        if (to == fa) continue;
        dfs(to, cur);
    }
    node tmp = s.top();
    s.pop();
    if (tmp.pop) vec.pop_back();
    else vec[tmp.id] = tmp.preVal;
}

int main() {
    boost;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> val[i];
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        G[u].emplace_back(v), G[v].emplace_back(u);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++)
        cout << ans[i] << endl;
    return 0;
}

Measured memory_bytes: 32196
import io.StdIn._
import scala.math._

object Main extends App {
  val Seq(n, l) = readLine().split(" ").map(_.toInt).toSeq

  require(2 <= n && n <= 200)
  require(-100 <= l && l <= 100)

  val sum = (1 to n).map(l + _ - 1).sum
  val min = (1 to n).map(i => abs(sum - (sum - (l + i - 1)))).min
  (1 to n).find(i => abs(sum - (sum - (l + i - 1))) == min).map(i => println(sum - l - i + 1))
}


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

#define d(x) cerr << #x ":" << x << endl;
#define dd(x, y) cerr << "(" #x "," #y "):(" << x << "," << y << ")" << endl
#define rep(i, n) for (int i = (int)(0); i < (int)(n); i++)
#define repp(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define all(v) v.begin(), v.end()
#define dump(v)                  \
    cerr << #v ":[ ";            \
    for (auto macro_vi : v) {    \
        cerr << macro_vi << " "; \
    }                            \
    cerr << "]" << endl;
#define ddump(v)                           \
    cerr << #v ":" << endl;                \
    for (auto macro_row : v) {             \
        cerr << "[";                       \
        for (auto macro__vi : macro_row) { \
            cerr << macro__vi << " ";      \
        }                                  \
        cerr << "]" << endl;               \
    }
using lint       = long long;
const int INF    = 1e9;
const lint LINF  = 1e18;
const lint MOD   = 1e9 + 7;
const double EPS = 1e-10;

int main() {
    int N, W;
    cin >> N >> W;
    vector<int> w(N), v(N);
    rep(i, N) cin >> v[i] >> w[i];

    vector<vector<int>> ma(N + 1, vector<int>(W + 1, -1));
    ma[0][0] = 0;
    // dump(w);
    // dump(v);
    // ddump(ma);

    // 状態 (i,j) : i-1 番目までのアイテムを選んでその重さが j である．
    // ma[i][j] : 状態 (i,j) での価値の最大値．
    // BFS する．ma[i][j] == -1 ならば，その状態は到達不可能．
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= W; j++) {
            if (ma[i][j] == -1) continue;
            ma[i + 1][j] = max(ma[i + 1][j], ma[i][j] + 0);
            if (j + w[i] <= W)
                ma[i + 1][j + w[i]] = max(ma[i + 1][j], ma[i][j] + v[i]);
        }
    }

    // ddump(ma);

    int M = -1;
    for (int j = 0; j <= W; j++) {
        M = max(M, ma[N][j]);
    }

    cout << M << endl;
    return 0;
}



Measured memory_bytes: 6836
#include <bits/stdc++.h>
using namespace std;
#define dhoom ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);  
typedef long long ll;
typedef long double ld;
const ll inf = 1e18;
const int nax = 2e6 + 7;
const ll mod = 1e9 + 7;
//ll tree[4 * nax];
//9uS-22RSwk7gQqh
int main()
{
	string a , b , c;
	cin >> a >> b >> c;
	if(a[a.size()-1] == b[0] && b[b.size()-1] == c[0])
		cout << "YES" << endl;
	else 
		cout << "NO" << endl;
	return 0;
} 




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
ll mod=1000000007;

int main(){
    std::ios::sync_with_stdio(false);
    int ar[5]={0};
    for(int i=0;i<3;i++){
        int a,b;
        cin>>a>>b;
        ar[a]++;ar[b]++;
    }
    if(ar[1]==3||ar[2]==3||ar[3]==3||ar[4]==3)cout<<"NO";
    else cout<<"YES";

    return 0;
}


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

bool isprime(int x)
{
  if(x==2)
    return true;

  if(x<2 || x%2==0)
    return false;

  for(int i=3; i*i<=x; i+=2){
    if(x%i==0)
      return false;
  }

  return true;
}

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

  int cnt = 0;

  for(int i=0; i<n; i++){
    int x;
    cin >> x;

    if(isprime(x)){
      cnt++;
    }
  }

  cout << cnt << endl;

  return 0;
}



Measured memory_bytes: 3092
#include <iostream>
#include <map>
#include <unordered_map>
#include <set>
#include <utility>
#include <stack>
#include <cstdio>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <iterator>
#include <sstream>
#define popcount(x) __builtin_popcount(x)
#define oddparity(x) __builtin_parity(x)
#define clz(x) __builtin_clz(x)
#define ctz(x) __builtin_ctz(x)
#define sf scanf
#define pf printf
#define ll long long int
using namespace std;

int k, s, x, y, z, c;

int main()
{
    sf("%d%d", &k, &s);
    for (x = 0; x <= k; x++) {
        for (y = 0; y <= k; y++) {
            z = s - x - y;
            if (z >= 0 && z <= k && x + y + z == s) c++;
        }
    }
    pf("%d\n", c);
    return 0;
}

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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef map<ll,ll>::iterator itll;
typedef long double ld;
typedef map<ll,ll> mapll;

#define con continue
#define pb push_back
#define fi first
#define se second
#define fr front()
#define INF 1000000000000000000
#define all(vl) vl.begin(),vl.end()
#define m_p make_pair 
#define sz(a) sizeof(a)
#define forn(mp,it) for(it = mp.begin();it!=mp.end();it++)
#define FOR(i,a,n) for(ll i=a;i<n;i++) 
#define FORE(i,a,n) FOR(i,a,n+1)
#define Endl endl
#define eNdl endl
#define enDl endl
#define endL endl

int main()
{
	ll n;
	cin>>n;
	vector<ll> vl(n-1);
	FOR(i,0,n-1)cin>>vl[i];
	ll ans = 0;
	FOR(i,0,n-2)
	{
		ans+=min(vl[i],vl[i+1]);
	}
	ans+=vl[n-2];
	cout<<ans+vl[0]<<endl;
	return 0;
}

Measured memory_bytes: 3584
#include<iostream>
#include<cstdio>
#include<cstring>
namespace not_mine
{
	typedef long long ll;
	const int N=55;
	const ll INF=123372036854775801ll;
	ll s[N],ans;
	int n;
	void work()
	{
		int p=0;
		for(int i=1;i<=n;s[i++]++)
			if(s[i]>s[p])p=i;
		s[p]-=n+1;
	}
	bool check()
	{
		for(int i=1;i<=n;i++)
			if(s[i]>=n)return 0;
		return 1;
	}
	ll calc(ll x)
	{
		ll ret=0;
		for(int i=1;i<=n;i++)
			if(s[i]>x)ret+=(s[i]-x)/(n+1);
		return ret;
	}
	void initialize()
	{
		ll tmp=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			scanf("%lld",s+i),tmp+=s[i];
		ll u=INF,d=0,cnt=tmp-(ll)(n-1)*(n-1);
		for(int i=1;i<=n;i++)s[i]+=cnt;

		for(ll mid;u>d;)
		{
			mid=(u+d)>>1;
			if(calc(mid)<=cnt)u=mid;
			else d=mid+1;
		}
		ans=calc(d),cnt-=ans;
		for(int i=1;i<=n;s[i++]-=cnt)
			if(s[i]>d)s[i]-=(n+1)*((s[i]-d)/(n+1));
	}
	void solve()
	{
		initialize();
		for(;!check();ans++)
			work();
		printf("%lld\n",ans);
	}
}
int main()
{
	not_mine::solve();
	return 0;
}


Measured memory_bytes: 256
# AGC025
def get_ketawa(N):
    ans = 0
    while 1:
        if N == 0:
            break
        ans += N % 10
        N //= 10

    return ans
N = int(input())
tmp = get_ketawa(N)
if tmp == 1:
    print(10)
else:
    print(tmp)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define oo 0x3f3f3f3f
#define ooLL 0x3f3f3f3f3f3f3f3f
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL)
const int mod = 1e9+7;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<pair<int,int>> vii;
typedef pair<int,int> pii;

int main(){
    ll x;
    scanf("%lld", &x);
    ll y = 100LL;
    int t = 0;

    while(y < x){
        y=1.01*y;
        t++;
    }

    printf("%d\n", t);
    return 0;
}

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

#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define intll int long long
const intll INF = 1e9;
const int MOD = 1e9 + 7;

int main() {
  int a,b,c ; 
  cin >> a >> b >> c ;
  string s = "No" ;
  
  if((a<c) && (c<b)) s = "Yes" ;
  if((b<c) && (c<a)) s = "Yes" ;
  
  cout << s ;
}


Measured memory_bytes: 3480
N = int(input())
li=[[int(it) for it in input().split()] for i in range(N)]

to,ao,bo=0,0,0
flag = "Yes"
for tn,an,bn in li:
  dt = tn-to
  dr = abs(an-ao)+abs(bn-bo)
  if (dt<dr):
    flag = "No"
  if (dr%2!=dt%2):
    flag = "No"
  to,ao,bo=tn,an,bn
print (flag)

  

Measured memory_bytes: 21052
n = int(input())
h = list(map(int,input().split()))

dp = [float("inf")]*(n)
dp[0] = 0
dp[1] = abs(h[1] - h[0])

for i in range(2,n):
  temp_1 = abs(h[i] - h[i-1]) + dp[i-1]
  temp_2 = abs(h[i] - h[i-2]) + dp[i-2]
  if temp_1 < temp_2:
    dp[i] = temp_1
  elif temp_2 <= temp_1:
    dp[i] = temp_2
  
print(dp[n-1])

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

int main(){
  int a, b, c, k;
  cin >> a >> b >> c >> k;
  if(k<a) cout << k << endl;
  else if(a<=k && k<=a+b) cout << a << endl;
  else cout << a-(k-a-b) << endl;
}

Measured memory_bytes: 3624
#include"bits/stdc++.h"
#define rep(i,n) for(int i=0;i<n;i++)
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Forr(i,a,b) for(int i=a;i>=b;i--)
typedef long long ll;
double PI = 3.14159265;
using namespace std;
using Graph = vector<vector<int>>;
using Field = vector<string>;
using DGraph = vector<vector<pair<int, int>>>;

const long long INF = 1LL << 60;
//---//
int main() {
	string S;
	int K; cin >> K>>S;

	if (S.size() <= K)cout << S << endl;
	else {
		rep(i, K)cout << S[i];
		cout << "...";
		cout << endl;
	}
	return 0;
}


Measured memory_bytes: 3596
n=int(input())
a=[int(j) for j in input().split()]
maxind=a.index(max(a))+1
minind=a.index(min(a))+1
if min(a)>0:
    print(n-1)
    for i in range(1,n):
        print(i,i+1)
else:
    if max(a)<0:
        print(n-1)
        for i in range(1,n)[::-1]:
            print(i+1,i)
    else:
        if max(a)+min(a)>0:
            ans=[]
            for i in range(n):
                if a[i]<0:
                    ans.append(i+1)
            print(len(ans)+n-1)
            for i in ans:
                print(maxind,i)
            for i in range(1,n):
                print(i,i+1)
        else:
            ans=[]
            for i in range(n):
                if a[i]>0:
                    ans.append(i+1)
            print(len(ans)+n-1)
            for i in ans:
                print(minind,i)
            for i in range(1,n)[::-1]:
                print(i+1,i)
            








Measured memory_bytes: 3064
#include "bits/stdc++.h"

using namespace std;

#define int long long

#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)

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

#define debug(x) cerr << #x << ": " << x << endl;

const int MOD = 1e9 + 7;

template <typename T>
T gcd(T m, T n) { return n == 0 ? m : gcd(n, m % n); }
template <typename T>
T lcm(T m, T n) { return n * m / gcd(n, m); }

signed main(void)
{
  int num;
  int n;
  cin >> n;

  num = n - 1;

  for (int i = 2; i <= sqrt(n); ++i)
  {
    if (n % i == 0)
    {
      num = min(num, i - 1 + n / i - 1);
    }
  }
  cout << num << endl;
}


Measured memory_bytes: 256
//第8回シンデレラガール総選挙は是非本田未央ちゃんに投票をお願いします！
//ファンのことも他のアイドルの子たちのことも本当に大事にしてて、今まで周りに色んなものを与えてくれました。
//今度は私たちが未央ちゃんにお返しをする番です。みんなでガラスの靴を履かせてあげましょう！
// #本田未央を一番星に #本田未央を令和のシンデレラガールに #第8回シンデレラガール総選挙
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define N 190
#define M 20
short dp[N][N][N][M];
int sum[N][N];
string ma[N];
int h,W;
int num(int lx,int hx,int ly,int hy){
	return sum[hx][hy]-sum[hx][ly]-sum[lx][hy]+sum[lx][ly];
}
int cal(int x,int y,int z,int w){
	if(dp[x][y][z][w]>=0) return dp[x][y][z][w];
	if(w==0){
		int lo=z,hi=W;
			if(x==0 && y==3 && z==0 && w==0){
				//cout<<lo<<hi<<endl;
			}
		while(hi>lo){
			int mi=(hi+lo+1)/2;
			if(num(x,y,z,mi)==0 || num(x,y,z,mi)==(y-x)*(mi-z)) lo=mi;
			else hi=mi-1;
		}
		//cout<<x<<' '<<y<<' '<<z<<' '<<w<<' '<<lo<<endl;
		return dp[x][y][z][w]=lo;
	}
	int ret=cal(x,y,cal(x,y,z,w-1),w-1),lo=x+1,hi=y-1;
	if(hi>=lo){
		while(hi>lo){
			int mi=(hi+lo+1)/2;
			if(cal(x,mi,z,w-1)<cal(mi,y,z,w-1)) hi=mi-1;else lo=mi;
		}
		ret=max(ret,min(cal(x,lo,z,w-1),cal(lo,y,z,w-1)));
		if(lo<y-1) ret=max(ret,min(cal(x,lo+1,z,w-1),cal(lo+1,y,z,w-1)));
	}
	//cout<<x<<' '<<y<<' '<<z<<' '<<w<<' '<<ret<<endl;
	return dp[x][y][z][w]=ret;
}
int main()
{
	cin>>h>>W;
	rep(i,h) cin>>ma[i];
	memset(sum,0,sizeof(sum));
	rep(i,h) rep(j,W){
		sum[i+1][j+1]=sum[i+1][j]+sum[i][j+1]-sum[i][j];
		if(ma[i][j]=='#') sum[i+1][j+1]++;
	}
	memset(dp,-1,sizeof(dp));
	//cout<<cal(0,3,0,1)<<endl;
	//cout<<cal(1,3,1,0)<<endl;
	rep(i,M){
		if(cal(0,h,0,i)>=W){
			cout<<i<<endl;return 0;
		}
	}
}


Measured memory_bytes: 268416
#include <iostream>
using namespace std;
int main () {
int a,b,c,d;
cin>>a;
for(int i=0;i<2;i++){
cin>>b;
if(a>b){
a=b;
}}
cin>>c>>d;
if(c>d){
c=d;
}
cout<<a+c-50<<endl;
return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<string>
#define ll long long
using namespace std;

int main(){
    string s, keyence = "keyence";
    cin >> s;

    if(s.substr(0,7) == keyence || s.substr((int)s.length()-8,7) == keyence){
        cout << "YES" << endl;
        return 0;
    }

    for(int j=0;j<7;j++){
        if(s[j]!=keyence[j]){
            if(s.substr((int)s.length()-(7-j),7-j) == keyence.substr(j,7-j)){
                cout << "YES" << endl;
                return 0;
            }else{break;}
        } 
    }
    cout << "NO" << endl;
}


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

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

const int mod = 1000000007;
const int inf = 1000000007;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  int cnt = 0;
  rep(i, n) {
    if ((i + 1) % 2 && a[i] % 2) cnt++;
  }
  cout << cnt << endl;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
string s,t;
int m,n;
vector<vector<int>> dp(3000,vector<int>(3000));
int calc(int i,int j){
    if(i==m||j==n){
        return 0;
    }
    if(dp[i][j]!=-1){
        return dp[i][j];
    }
    int ans;
    if(s[i]==t[j]){
        ans=1+calc(i+1,j+1);    
    }
    else{
        ans=max(calc(i+1,j),calc(i,j+1));
    }
    return dp[i][j]=ans;
}
void solve(){
    cin>>s>>t;
    m=s.length(),n=t.length();
    dp.assign(m,vector<int>(n,-1));
    int lcs=calc(0,0);
    string res="";
    int sl=0,st=0;
    while(sl<m && st<n){
        if(s[sl]==t[st]){
            res+=s[sl];
            sl++,st++;
        }
        else if(calc(sl+1,st)>calc(sl,st+1)){
            sl++;    
        }
        else{
            st++;
        }
    }
    cout<<res<<'\n';
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}


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

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

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

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

ll A, B, C;

signed main()
{
    cin >> A >> B >> C;
    for(ll i = 1; i < 1000; ++i) {
        ll cand = A * i;
        if( (A * i) % B == C ) {
            printf("YES\n");
            return 0;
        }
    }
    printf("NO\n");
    return 0;
}


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

int main() {
  string s;
  cin >> s;
  int n = s.size();
  int start, end;
  for (int i = 0; i < n; i++) {
    if (s[i] == 'A') {
      start = i;
      break;
    }
  }
  for (int i = n - 1; i >= 0; i--) {
    if (s[i] == 'Z') {
      end = i;
      break;
    }
  }
  cout << end - start + 1 << endl;
}

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

using namespace std;

int main(){
  int n;
  int num = 0;
  int tmp;
  cin >> n;
  for(int i=1; i<=n; i++){
    tmp = log10(i) + 1;
    tmp = tmp % 2;
    if(tmp==1){
      num++;
    }
  }
  cout << num << endl;  
}

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

template<typename T>
vector<T> Dijkstra(vector<vector<T>> &G, int s, T inf) {
    vector<T> dist(G.size(),inf);
    vector<bool> used(G.size(),false);

    dist[s] = 0;
    while (true) {
        used[s] = true;
        int u = -1;
        T d = inf;
        for (int v = 0; v < G.size(); ++v) {
            if (used[v]) continue;
            if (dist[v] > dist[s] + G[s][v]) dist[v] = dist[s] + G[s][v];
            if (d > dist[v]) {
                d = dist[v];
                u = v;
            }
        }
        if (u == -1) break;
        s = u;
    }

    return dist;
}

///////////////////////////////////////////////////////////////////////////////

const ll inf = numeric_limits<ll>::max() / 2;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N; cin >> N;
    vector<vector<ll>> G(N, vector<ll>(N,inf));
    for (int i = 0; i < N; ++i) {
        int u,k; cin >> u >> k;
        for (int j = 0; j < k; ++j) {
            ll v,c; cin >> v >> c;
            G[u][v] = c;
        }
    }

    auto dist = Dijkstra(G,0,inf);
    for (int i = 0; i < N; ++i) {
        cout << i << " " << dist[i] << endl;
    }
}

/*
  verified on 2020/02/04
  http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_B&lang=ja
*/


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

using ll = long long;
#define int long long
using P = pair<int, int>;

#define LOG(variable) cout << #variable":\t" << (variable) << endl
#define LOGCON(i, container) for(int (i) = 0; (i) < (container).size(); ++(i)) cout << (i) << ":\t" << (container)[(i)] << endl
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(i, r, n) for (int i = (r); i < (n); ++i)
#define REPR(i, n) for(int i = (n); i >= 0; --i) // from n to 0
#define REPRS(i, n, r) for(int i = (n); i >= (r); --i) // from n to r
#define REPOBJ(itr, obj) for(auto itr = (obj).begin(); itr != (obj).end() ; ++itr)
#define REPROBJ(itr, obj) for(auto itr = (obj).rbegin(), e = (obj).rend(); itr != e; ++itr)
#define COUTB(x) cout << (x) << "\n"
#define COUTS(x) cout << (x) << " "
#define PB push_back
#define SORT(obj) sort((obj).begin(), (obj).end())
#define SORTR(obj) sort((obj).begin(), (obj).end(), greater<>())
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define PI (acos(-1))
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%MOD+MOD)%MOD){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += MOD-a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= MOD; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime MOD
  mint inv() const { return pow(MOD-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
template<typename T = int>
T in() {T a; cin >> a; return a;}
/***** MAIN *****/
signed main() {
  int a = in();
  int b = in();
  int c = in();
  int ans = b/a;
  cout << min(c, ans);
  cout << "\n";
  return 0;
}
/***** MAIN *****/


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void play(char *sa, char *sb, char *sc) {
  int lena, lenb, lenc;
  lena = strlen(sa);
  lenb = strlen(sb);
  lenc = strlen(sc);
  char next = 'a';  //最初はAさんのターンから
  while (lena >= 0 && lenb >= 0 &&
         lenc >= 0) {  //一枚も持っておらず自分のターンが来た人が勝つ
    // aさんから最初のカードをみる->減らす->次の人を変更する
    switch (next) {
      case 'a':
        next = *sa++;
        lena--;
        break;
      case 'b':
        next = *sb++;
        lenb--;
        break;
      case 'c':
        next = *sc++;
        lenc--;
        break;
      default:
        break;
    }
  }
  if (lena == -1)
    printf("A\n");
  else if (lenb == -1)
    printf("B\n");
  else
    printf("C\n");
}

int main(void) {
  char *sa, *sb, *sc;  // charでポインタの時はメモリを確保する
  sa = (char *)malloc(sizeof(char) * 100);
  sb = (char *)malloc(sizeof(char) * 100);
  sc = (char *)malloc(sizeof(char) * 100);
  scanf("%s", sa);
  scanf("%s", sb);
  scanf("%s", sc);
  play(sa, sb, sc);
  return 0;
}

Measured memory_bytes: 128
main :: IO ()                                                                                                              
main = do                                                                                                                  
  [n,t] <- ((map read . words) <$> getLine) :: IO [Int]                                                                    
  [c0,t0] <- (foldr (g t) [1001,1001]) <$> (sequence $ replicate n ((map read . words) <$> getLine :: IO [Int]))           
  if t0 <= t                                                                                                               
    then putStrLn $ show c0                                                                                                
    else putStrLn "TLE"                                                                                                    
  where                                                                                                                    
    g :: Int -> [Int] -> [Int] -> [Int]                                                                                    
    g t [a0,b0] [a1,b1] = if a0 <= a1 && b0 <= t                                                                           
                        then [a0,b0]                                                                                       
                        else [a1,b1]

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


int main(void)
{
    while (1)
    {
        string line;
        getline(cin, line);
        if (line == "0") break;

        int sum = 0;
        for (char ch : line)
        {
            sum += ch - '0';
        }
        cout << sum << endl;
    }

    return 0;
}

Measured memory_bytes: 3204
using System;
using System.Linq;
using System.Collections.Generic;

public class Hello{
    public static void Main(){
        string InputNum;
        int Num;
        List<int> Primes = new List<int>();
        bool[] PrimeCheck = Enumerable.Repeat<bool>(true, Consts.MAXNUM).ToArray();
        
        while((InputNum = Console.ReadLine()) != null){
            Num = int.Parse(InputNum);

            if(Primes.Count == 0){
                for(int i = 0; i < Consts.MAXNUM; i++){
                    if(i == 0 || i == 1){
                        PrimeCheck[i] = false;
                        continue;
                    }
                    else if(PrimeCheck[i] == false){
                        continue;
                    }
                    else{
                        Primes.Add(i);
                        for(int n = i * 2; n < Consts.MAXNUM; n += i){
                            PrimeCheck[n] = false;
                        }
                    }
                }
            }
            
            for(int i = 0; i < Primes.Count; i++){
                if(Num < Primes[i]){
                    System.Console.WriteLine(i);
                    break;
                }
                if(i == Primes.Count -1){
                    System.Console.WriteLine(Primes.Count);
                }
            }
        }
    }
}

public static class Consts{
    public static int MAXNUM = 999999;
}

Measured memory_bytes: 12580
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#define MOD 1000000007
#define MOD2 998244353
#define int long long
#define double long double
#define EPS 1e-9
//#define PI 3.14159265358979

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

using namespace std;

template < typename T >
ostream &operator<<(ostream &os, const vector< T > &A) {
	for (int i = 0; i < A.size(); i++)
		os << A[i] << " ";
	os << endl;
	return os;
}
template <>
ostream &operator<<(ostream &os, const vector< vector< int > > &A) {
	int N = A.size();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < A[i].size(); j++)
			os << A[i][j] << " ";
		os << endl;
	}
	return os;
}

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

struct edge {
	int from, to, d, c;
	edge(int _from = 0, int _to = 0, int _d = 0, int _c = 0) {
		from = _from;
		to = _to;
		d = _d;
		c = _c;
	}
	bool operator<(const edge &rhs) const {
		return (d == rhs.d) ? (c < rhs.c) : (d < rhs.d);
	}
};
struct aabb {
	int x1, y1, x2, y2;
	aabb(int x1, int y1, int x2, int y2) : x1(x1), y1(y1), x2(x2), y2(y2) {}
};

typedef vector< edge > edges;
typedef vector< edges > graph;
struct flow {
	int to, cap, rev, cost;
	flow(int to = 0, int cap = 0, int rev = 0, int cost = 0) : to(to), cap(cap), rev(rev), cost(cost) {}
};
typedef vector< vector< flow > > flows;

const int di[4] = {0, -1, 0, 1};
const int dj[4] = {-1, 0, 1, 0};
const int ci[5] = {0, 0, -1, 0, 1};
const int cj[5] = {0, -1, 0, 1, 0};
const ll LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const double PI = acos(-1);

int pow2(int n) { return 1LL << n; }
template < typename T, typename U >
bool chmin(T &x, const U &y) {
	if (x > y) {
		x = y;
		return true;
	}
	return false;
}
template < typename T, typename U >
bool chmax(T &x, const U &y) {
	if (x < y) {
		x = y;
		return true;
	}
	return false;
}

struct initializer {
	initializer() {
		cout << fixed << setprecision(20);
	}
};
initializer _____;

int N, M, K, T, Q, H, W;
signed main() {
	string S;
	cin >> S;
	cout << S[0] << S[1] << S[2] << endl;
	return 0;
}

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

int main() {
int H,W;
cin >> H>>W;
vector<string> a(H);
  for (int i =0;i<W+2;i++){
    cout <<"#";
  }
	cout <<endl;
  for (int i =0;i<H;i++) {
	cin >>a.at(i);
    cout <<"#"<<a.at(i)<<"#"<<endl;
  }

  for (int i =0;i<W+2;i++){
    cout <<"#";
  }
  cout<<endl;
}
  

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define arep(a,i,n) for(ll i=(a);i<(n);i++)
#define rep(i,n) for(ll i=0;i<(n);i++)
#define cinf(x,n) for(ll i=0;i<(n);i++)cin>>x[i];
#define coutf(x,n) for(ll i=0;i<(n);i++)cout<<x[i]<<endl;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using namespace std;

int main(){
	int h,w;
	cin >> h >> w;
	char a[h][w];
	rep(i,h)rep(j,w)cin>>a[i][j];
	rep(i,w+2)cout<<'#';cout<<endl;
	rep(i,h){
		cout<<'#';
		rep(j,w){
			cout << a[i][j];
		}
		cout << '#' << endl;
	}
	rep(i,w+2)cout<<'#';cout<<endl;
}

Measured memory_bytes: 3564
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
ll a,b;
string s, t;
ll gcd(ll a, ll b){
	while(b){
		a %= b;
		swap(a,b);
	}
	return a;
}
int main(){
	scanf("%lld%lld", &a, &b);
	printf("%lld\n", a*b/gcd(a,b));
}

Measured memory_bytes: 256
from math import factorial
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = {False: 'No', True: 'Yes'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


# show_flg = False
show_flg = True

g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

# MOD 組み合わせ
def cmb(n, r, mod):
    if r < 0 or r > n:
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


def g(r, c):
    return cmb(r+c+2, r+1, MOD)


def main():
    M = 10 ** 6
    r1, c1, r2, c2 = MI()
    r1 -= 1
    c1 -= 1

    for i in range(2, 3 * M):
        g1.append((g1[-1] * i) % MOD)
        inverse.append((-inverse[MOD % i] * (MOD//i)) % MOD)
        g2.append((g2[-1] * inverse[-1]) % MOD)

    ans = g(r2, c2)
    ans -= g(r2, c1)
    ans -= g(r1, c2)
    ans += g(r1, c1)
    print(ans % MOD)


if __name__ == '__main__':
    main()


Measured memory_bytes: 172472
#include <iostream>
#include <iomanip>
#include <cstdio>
 
using namespace std;
 
int main(){
  int a, b, c, d, e, f;
  while(true){
    if(!(cin >> a >> b >> c >> d >> e >> f)) return 0;
    double det = a*e - b*d;
    double x = (e*c-b*f)/det;
    double y = (-d*c+a*f)/det;
    printf("%.3f %.3f\n", (int)(x*1000)/1000.0, (int)(y*1000)/1000.0 );
  }
}


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

int main(){
  ll r=0,g=0,b=0;
  int n;
  string s;
  cin >> n >> s;

  rep(i,n) {
    if(s.at(i) == 'R') r++;
    if(s.at(i) == 'G') g++;
    if(s.at(i) == 'B') b++;
  }

  ll ans = r*g*b;

  rep(i,n){
    for(int j = i+1; j < n; j++) {
      int k = 2*j - i;
      if(k >= n) continue;
      if(s.at(i) != s.at(j) && s.at(j) != s.at(k) && s.at(i) != s.at(k)) ans--;
    }
  }

  cout << ans << endl;
}



Measured memory_bytes: 3612
N=int(input())
A=list(map(int, input().split()))
clist=[0]*N
loscount=0
count=1
for i in range(0,N):
    if A[i]%2==1:
        clist[i]=3
    elif A[i]%2==0:
        clist[i]=3
        loscount=loscount+1
for i in range (0,N):
    count=count*clist[i]
print(count-2**loscount)

Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<limits.h>
#include<cmath>
#include<queue>
#include<stack>

#include<stdio.h>
#include<stdlib.h>

#define rep(i,n) for(ll i = 0; i < (ll)n; i++)
#define swap(a,b) a^=b;b^=a;a^=b;
#define chmax(a,b) {if(a < b) a = b;}
#define chmin(a,b) {if(a > b) a = b;}

using namespace std;
typedef long long ll;
ll gcd(ll, ll);
vector<bool> to_binary(int);
ll nCr(ll n, ll r);

const ll INF = 1LL << 60;

typedef tuple<ll, ll> mtupl;

/*

bool mycomp(mtupl x, mtupl y) {
	return get<1>(x) < get<1>(y);
}

int vsum(vector<int> v) {
	int res = 0;
	for (auto it = v.begin(); it != v.end(); it++)
		res += *it;
	return res;
}

int vmin(vector<int> v) {
	int min = INT32_MAX;
	for (auto it = v.begin(); it != v.end(); it++)
		min = std::min(min, *it);
	return min;
}

int vmax(vector<int> v) {
	int max = INT32_MIN;
	for (auto it = v.begin(); it != v.end(); it++)
		max = std::max(max, *it);
	return max;
}

ll gcd(ll A, ll B) {
	if (A == 0 || B == 0) return max(A, B);
	int r = A % B;
	while (r != 0) {
		A = B;
		B = r;
		r = A % B;
	}
	return B;
}

vector<ll> prime_factor(int64_t n) {
	//map< ll, ll > ret;
	vector<ll> ret;
	for (ll i = 2; i * i <= n; i++) {
		while (n % i == 0) {
			//ret[i]++;
			ret.push_back(i);
			n /= i;
		}
	}
	if (n != 1)ret.push_back(n);// ret[n] = 1;
	return ret;
}

const int MAX = 1000000;
const int MOD = 1000000007;
ll fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}
ll COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

struct edge {
	ll to;
	ll cost;
};

*/

int get_dig(ll x) {
	int ret = 0;
	while (x != 0) {
		ret += x % 10;
		x /= 10;
	}
	return ret;
}

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//Program Start	

	ll N,A,B;
	cin >> N >> A >> B;

	ll sum = 0;
	for (int i = 1; i <= N; i++) {
		int d = get_dig(i);
		if (A <= d && d <= B) sum += i;
	}

	cout << sum << endl;




ProgramEndPointLabel:;

	//Program End
#ifndef DEBUG
	system("pause");
#endif // !DEBUG


	return 0;
}




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

using namespace std;
using llong = long long;
using ullong = unsigned long long;
int main(){
  int n;
  cin >> n;
  vector<int> v(n);
  map<int,int> odd,even;
  for(int i=0;i<n;++i){
    int x;
    cin >> x;
    if(i%2){
      odd[x]++;
    }else{
      even[x]++;
    }
  }

  pair<int,int> emax(-1,0),emax2(-1,0);
  for(auto e:even){
    if(emax.second < e.second){
      emax = e;
    }
  }
  for(auto e:even){
    if(emax2.second < e.second && e.first != emax.first ){
      emax2 = e;
    }
  }

  pair<int,int> omax(-1,0),omax2(-1,0);
  for(auto o:odd){
    if(omax.second < o.second){
      omax = o;
    }
  }
  for(auto o:odd){
    if(omax2.second < o.second && o.first != omax.first ){ 
      omax2 = o;
    }
  }

  if( omax.first != emax.first ){
    cout << ( n/2 - omax.second) + ( n/2 - emax.second ) << endl;
  }else{
    cout << min((n/2-emax2.second)+(n/2-omax.second),
                (n/2-omax2.second)+(n/2-emax.second)) << endl;
  }
}

Measured memory_bytes: 5376
// #define STOPIT
#include<bits/stdc++.h>
#define rep(i,n,m) for(int i = (n); i <(m); i++)
#define rrep(i,n,m) for(int i = (n) - 1; i >=(m); i--)
using namespace std;
using ll = long long;

void debug_impl() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_impl(Head head, Tail... tail) { cerr << " " << head; debug_impl(tail...); }
#ifndef STOPIT
    #define debug(...)\
    do {\
        cerr << boolalpha << "[" << #__VA_ARGS__ << "]:";\
        debug_impl(__VA_ARGS__);\
        cerr << std::noboolalpha;\
    } while (false)
#else
    #define debug(...) {}
#endif

template < typename Container, typename Value = typename Container::value_type, enable_if_t<!is_same< Container, string >::value, nullptr_t> = nullptr>
istream& operator>> (istream& is, Container& v)
  { for (auto & x : v) { is >> x; } return is; }

template < typename Container, typename Value = typename Container::value_type, enable_if_t<!is_same< Container, string >::value, nullptr_t> = nullptr >
ostream& operator<< (ostream& os, Container const& v) {
  os << "{";
  for (auto it = v.begin(); it != v.end(); it++)
    {os << (it != v.begin() ? "," : "") << *it;}
  return os << "}";
}
using ll = long long;
const ll MOD = 1000000007;

ll power_mod(ll n, ll m)
{
    ll res = 1;
    ll base = n;
    while (m > 0)
    {
        if (m&1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        m >>= 1;
    }
    return res;
}

ll inv_mod(ll n)
{
    return power_mod(n, MOD-2);
}
// x_inv =(MOD % x) ^ -1 * (- MOD / x) ???

ll comb(ll n, ll m)
{
    m = min(m, n-m);
    ll res = 1;
    rep(i, 0, m)
    {
        res *= n;
        res %= MOD;
        --n;
    }
    rep(i,1,m+1)
    {
        res *= inv_mod(i);
        res %= MOD;
    }
    return res;
}

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

    ll ans = power_mod(2, n) - 1;
    ans -= comb(n, a);
    if (ans <0) ans += MOD;
    if (a!= b)
        ans -= comb(n, b);
    if (ans < 0) ans += MOD;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256