akhauriyash/Code-Regression huggingface dataset:
N, M = map(int, input().split(' '))
H = list(map(int, input().split(' ')))
table = [1 for _ in range(N)]

for _ in range(M):
    A, B = map(int, input().split(' '))
    Ah, Bh = H[A - 1], H[B - 1]

    if Ah >= Bh:
        table[B - 1] = 0
    if Ah <= Bh:
        table[A - 1] = 0

ans = table.count(1)

print(ans)

Measured memory_bytes: 91988
#include <stdio.h>
int main() {
	char s[4];
	scanf("%s", s);
	int flag = 1;
	for (int i = 0; i < 3; i++) {
		if (s[i] == s[i + 1]) {
			printf("Bad");
			flag = 0;
			break;
		}
	}
	if (flag) 
		printf("Good");
	return 0;
}


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

#define int long long int
#define pb push_back
#define mp make_pair

int32_t main()
{
     
     int n,m;
     
     cin>>n>>m;
     
  if(n==1)
  {
    cout<<m;
    return 0;
  }
  
     for(int i=1e8;i>=1;i--)
     {
          int left=m-(i*n);
          
          if(left>=0)
          {
               if(left%i==0)
               {
                    cout<<i;
                    return 0;
               }
          }
     }
     
     return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		new Main().run();
	}

	private void run() {
		Scanner scanner = new Scanner(System.in);
		while (true) {
			int n = scanner.nextInt();
			if (n == 0)
				break;
			int[] k = new int[n + 1];
			for (int i = 0; i <= n; i++)
				k[i] = scanner.nextInt();
			loop: for (int i = 0; i <= n; i++) {
				int[] ktmp = new int[n];
				int p = 0;
				for (int j = 0; j < i; j++)
					ktmp[p++] = k[j];
				for (int j = i + 1; j <= n; j++)
					ktmp[p++] = k[j];
				for (int j = 2; j < n; j++)
					if (ktmp[j] - ktmp[j - 1] != ktmp[j - 1] - ktmp[j - 2])
						continue loop;
				System.out.println(k[i]);
				break;
			}
		}
	}
}

Measured memory_bytes: 37612
N, M = map(int, input().split())
H = list(map(int, input().split()))
NA = []
eq = []
for i in range(M):
  A, B = map(int, input().split())
  if H[A-1] > H[B-1]:
    NA.append(B)
  elif H[A-1] < H[B-1]:
    NA.append(A)
  elif H[A-1] == H[B-1]:
    eq.append(A)
    eq.append(B)

MM = NA + eq
MMM = set(MM)
NNA = list(set(NA))
NNAA = len(MMM)
print(N - NNAA)

Measured memory_bytes: 22568
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef long double ld;
const double E = 1e-7;
const ll INF = 1e17;
#define forn(i, s, f) for (int i = s; i < f; ++i)
#define ft first                                                 
#define sec second
#define fora(i, n) for (auto i : n)
#define sz(a) (int)(a).size()
#define sort_(a) sort(a.begin(), a.end())
#define pb push_back
#define mp make_pair
#define rsort_(a) sort(a.begin(), a.end()); reverse(a.begin(), a.end())
#define fast_ cin.tie(0), ios_base::sync_with_stdio(false)
// ____________________________________________________________
#define cina(a) forn(i,0,sz(a)) cin >> a[i]
#define cinpr(a) cin >> a.ft >> a.sec 
//--------------------------------------------------------------
 
int main() {
    ll n, d, ans = 0;
    cin >> n >> d;
    forn(i,0,n) {
        ll x, y;
        cin >> x >> y;
        if (x * x + y * y <= d * d) ans++;
    }
    cout << ans;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
int main()
{
   int n,cnt,i,sum=0,t;
   cin>>n;
   for(i=1;i<=n;i++)
   {
       cnt=0;
       t=i;
      while(t!=0)
      {
          t/=10;
          cnt++;

      }
      if(cnt%2==1)
      {
          sum++;
      }
   }
   cout<<sum<<endl;

    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
int n;
string s;
map<string, int> mp;
int tot;
int main() {
	cin>>n;
	for (int i=1;i<=n;++i) {
		cin>>s;
		if (!mp.count(s)) {
			mp[s]=1;
			++tot;
		}
	}
	printf("%d\n",tot);
	return 0;
}

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



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

    ll N;
    cin >> N;
    if(N % 2 == 1){
        cout << 0 << endl;
        return 0;
    }
    ll answer = 0;
    ll tmp = N;
    tmp /= 2;
    while(tmp > 0){
        tmp /= 5;
        answer += tmp;
    }
    cout << answer << endl;
    return 0;
}



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

using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define debug(x)  do{cerr<<#x<<": "<<x<<"\n";}while(0)
#define debugv(x) do{cerr<<#x<<": ";for(auto&e: (x))cerr<<e<<" ";cerr<<"\n";}while(0)
#define all(x) (x).begin(), (x).end()
#define fori(i, n) for (int i = 0; i < (int)(n); ++i)
#define ford(i, n, e) for (int i = (int)(n); i >= (int)(e); --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
template<typename T> bool mmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template<typename T> bool mmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; }
#define RETURN(x) do{cout << (x) << '\n'; return 0;}while(0)

const int MOD = 1e9+7;
const int MAXN = 5e5+3;
const int INF = 1e9;


int main(int argc, char **argv) {
#ifdef OJ
    freopen("input.txt", "rt", stdin);
    //freopen("output.txt", "wt", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);

    string s; cin >> s;
    int ok = 0;
    for(char c: s) ok |= c == '7';
    cout << (ok? "Yes\n" : "No\n");
    
    return 0;
}


Measured memory_bytes: 3652
#include <stdio.h>

#define rep(i, n) for (int i = 0; i < n; i = i + 1)
#define MAX 10010
#define MAX_INT 9223372036854775807

int main() {
  int N, a[105];

  scanf("%d", &N);

  rep(i, N) {
    scanf("%d", a + i);
  }

  int ans = 0;

  rep(i, N) {
    // 偶数判定
    if ((i + 1) % 2 == 0) {
      continue;
    }
    if (a[i] % 2 == 0) {
      continue;
    }
    ans += 1;
  }

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

  return 0;
}


Measured memory_bytes: 1680
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int count = 0;

		int chair[][] = new int[n][2];

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

			for (int j = 0; j < 2; j++) {
				chair[i][j] = sc.nextInt();
			}

			count += chair[i][1] - chair[i][0] + 1;
		}
		System.out.println(count);

	}

}


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

#define endl '\n'

void io(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(15);
}
const int MAXN = 1e5 + 5 ;
int A[MAXN] ;
int n ;
int main(int argc,char* argv[]) { 
    io() ;
    cin >> n ;
    bool ok = 1 ;
    int f0 = 0 ;
    int f1 = 0 ;
    int fe = 0 ;
    for(int i = 1; i <= n; i++){
        cin >> A[i] ;
        if(abs(A[i] - A[1]) > 1){
            ok = 0 ;
        }
        if(A[i] == A[1] - 1){
            f0 += 1 ;
        }
        if(A[i] == A[1] + 1){
            f1 += 1 ;
        }
        if(A[i] == A[1]){
            fe += 1 ;
        }
    }
    if(!ok || (f0 && f1)){
        cout << "No\n" ;
        return 0 ;
    }
    if(f0){
        int frq1 = f0 ;
        int frq2 = A[1] - frq1 ;
        if(2*frq2 < fe){
            cout << "No\n";
        }
        else if( (frq1 + 2*frq2) <= n){
            cout << "Yes\n" ;
        }
        else{
            cout << "No\n" ;
        }
    }
    else if(f1){
        int frq1 = fe ;
        int frq2 = A[1] + 1 - frq1 ;
        if(2*frq2 < f1){
            cout <<"No\n" ;
        }
        else if( (frq1 + 2*frq2) <= n){
            cout << "Yes\n" ;
        }
        else{
            cout << "No\n" ;
        }
    }
    else{
        if(2*A[1] <= n || A[1] == n - 1){
            cout << "Yes\n" ;
        }
        else{
            cout <<"No\n";
        }
    }
    return 0 ; 
}

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

using namespace std;

vector<pair<string, int>> ans(int n){
    if(n == 1) return vector<pair<string, int>>(1, make_pair("a", 1));
    auto sub = ans(n - 1);
    vector<pair<string, int>> ret;
    for(auto itr = sub.begin(); itr != sub.end(); itr++){
        for(int i = 0; i < itr->second; i++){
            ret.push_back(*itr);
            ret.rbegin()->first.push_back('a' + i);
        }
        ret.push_back(*itr);
        ret.rbegin()->first.push_back('a' + itr->second);
        ret.rbegin()->second++;
    }
    return ret;
}

int main(void){
    int N;
    cin >> N;
    auto r = ans(N);
    for(auto itr = r.begin(); itr != r.end(); itr++){
        cout << itr->first << endl;
    }
    return 0;
}


Measured memory_bytes: 10080
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
using namespace std;
typedef long long ll;

int N;

int main(){
    cin>>N;

    int n=N;
    int sum=0;
    rep(i,log10(N)+1){
        sum+=n%10;
        n/=10;
    }

    if(N%sum==0){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int INF = 1e9+7;
int mod = 1e9+7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
signed main() {
    int H,W;
    cin >> H >> W;
    vector<vector<int>>a(H,vector<int>(W));
    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            cin >> a[i][j];
        }
    }
    vector<pair<P,P>>ans;
    int nx = 0,ny = 0;
    while(true) {
        int ox = nx,oy = ny;
        bool ok = false;
        if(a[nx][ny]%2 == 1) {
            ok = true;
        }
        if(nx%2 == 0) {
            if(ny+1 == W) {
                nx++;
            }
            else {
                ny++;
            }
        }
        else {
            if(ny-1 == -1) {
                nx++;
            }
            else {
                ny--;
            }
        }
        if(nx == H) {
            break;
        }
        if(ok) {
            ans.push_back({{ox+1,oy+1},{nx+1,ny+1}});
            a[nx][ny]++;
        }
    }
    cout << ans.size() << endl;
    for(int i = 0; i < ans.size(); i++) {
        cout << ans[i].first.first << " " << ans[i].first.second << " " << ans[i].second.first << " " << ans[i].second.second << endl;
    }
}

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

using namespace std;

using ll = long long;
using ld = long double;

const double PI = 3.1415926535897932384626433832795;
const ll MOD = 1000000007;

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

int gcd(int x, int y) { return y ? gcd(y, x % y) : abs(x); }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : abs(x); }
int lcm(int x, int y) { return x / gcd(x, y) * y; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

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

	int n;
	cin >> n;

	vector<int> x(n), y(n);
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> y[i];
	}

	multiset<pair<int, int>> g;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i == j) continue;
			g.emplace(x[j] - x[i], y[j] - y[i]);
		}
	}

	int bonus = 0;
	for (auto e : g) {
		bonus = max(bonus, (int)g.count(e));
	}

	cout << n - bonus << endl;
	return 0;
}


Measured memory_bytes: 384
/* Author - thiolhub */

#include <bits/stdc++.h>

using namespace std;

#define ll              long long int
#define ld              long double
#define db              double
#define pi              3.1415926535897932384626
#define PI              acos(-1.0)
#define endl            "\n"
#define mod             1000000007
#define mk              make_pair
#define pb              push_back
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define ps(x,y)         fixed<<setprecision(y)<<x
#define w(t)            ll t; cin>>t; while(t--)
#define sc(a)	        scanf("%lld",&a);
#define pr(a)	        printf("%lld\n",a)
#define f(i,a,n)		for(ll i=a;i<n;i++)
#define m(a)		    memset(a,0,sizeof(a))
#define FastIO          ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0)



int main(){ FastIO;

int n,i,j,k;cin>>n;
int a[n]; for(i=0;i<n;i++) cin>>a[i];
int dp[n+1];
for(i=0;i<n;i++) dp[i]=INT_MAX;
dp[0]=0;
for(i=0;i<n-1;i++)
{
	dp[i+1]=min(abs(a[i+1]-a[i])+dp[i],dp[i+1]);
	dp[i+2]=min(abs(a[i+2]-a[i])+dp[i],dp[i+2]);
}
cout<<dp[n-1];

return 0;
}


Measured memory_bytes: 1024
import os
import sys
from io import BytesIO

sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))

n, k = map(int, sys.stdin.readline().split())
a = map(int, sys.stdin.readline().split())
f = map(int, sys.stdin.readline().split())
a.sort()
f.sort(reverse=True)

'''
n, k = 100000, 0
a = range(n)
f = range(n)
a.sort()
f.sort(reverse=True)

print n, k

for i in range(n):
	print 1,
print

for i in range(n):
	print 1,
print
'''


def val(p):
	r = 0
	for i in range(n):
		t = 0 if a[i] * f[i] <= p else a[i] - p // f[i]
		r += t
	return r
		
def bin(l, r):
	if l == r:
		return l
	if l + 1 == r:
		if val(l) <= k:
			return l
		else:
			return r
	t = (l + r) // 2
	if val(t) <= k:
		return bin(l, t)
	else:
		return bin(t, r)
		
R = bin(0, 1000000000000)
print(R)

Measured memory_bytes: 72680
#include "bits/stdc++.h"
#include <string>
 
typedef long long ll;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
 
using namespace std;
 
 
int main(){
    int n,m,t;
    cin>>n>>m>>t;
    ll sum=0;
    vector<int> a(n);
    rep(i,n){
        cin>>a[i];
    }
    
    sum+=max(0,a[0]-m);
    sum+=max(t-(a[n-1]+m),0);
    
    
    rep(i,n-1){
        int tmp = a[i+1]-a[i]-2*m;
        if(tmp<=0)continue;
        sum+=tmp;
    }
    
    cout<<sum<<endl;
}

Measured memory_bytes: 3064
#define M 1<<21
char*s,T[M],*r=T;H[M][27],h,U[M],V[M],n,k;main(i){for(;gets(r+1);++n)for(k=0;*++r&=31;)U[r-T]=k|=!!n<<*r;for(;--i+2;)for(k=0,s=r;--s>T;k=H[k][*s]=*s?H[k][*s]?:++h:0)n+=i*__builtin_popcount(U[s-T]&(V[k]|=!s[-1]<<*s));printf("%d",1-n);}

Measured memory_bytes: 115596
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
	Scanner sc = new Scanner (System.in);


	int d = sc.nextInt();
	int t = sc.nextInt();
	int s = sc.nextInt();

	if(t*s >= d) {
		System.out.println("Yes");
	}else {
		System.out.println("No");
	}
}
}


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

typedef double dbl;

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		dbl x[2], y[2], r[2];
		for (int j = 0; j < 2; j++) {
			cin >> x[j] >> y[j] >> r[j];
		}
		dbl d = sqrt(pow(x[1] - x[0], 2) + pow(y[1] - y[0], 2));
		if (d < fabs(r[0] - r[1])) {
			if (r[0] > r[1]) {
				cout << 2 << endl;
			}
			else {
				cout << -2 << endl;
			}
		}
		else if (d > r[0] + r[1]) {
			cout << 0 << endl;
		}
		else cout << 1 << endl;
	}
}


Measured memory_bytes: 3144
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int  N = sc.nextInt();
		String S = sc.next();
		int K = sc.nextInt();
		
		String s = "";
		
		for(int i = 0; i < S.length(); i++) {
			if(S.charAt(i) == S.charAt(K-1)) {
				s += S.charAt(i);
			}else {
				s += '*';
			}
		}
		System.out.println(s);
	}
}


Measured memory_bytes: 23252
#include <stdio.h>
#include <string.h>
#define Max 50+5
int main(int argc, char *argv[])
{
	char S[50+5];
	while(scanf("%s",S)!=EOF)
	{
		int len=strlen(S);
		if(len>9)
		{
			printf("NO\n");
			continue;
		}
		int flag=1;
		int temp=0;
		for(int i=0;i<len;i++)
		{
			if(temp==0&&S[i]=='K')
			{
				temp=1;
			}
			else if(temp==1&&S[i]=='I')
			{
				temp=2;
			}
			else if(temp==2&&S[i]=='H')
			{
				temp=3;
			}
			else if(temp==3&&S[i]=='B')
			{
				temp=4;
			}
			else if(temp==4&&S[i]=='R')
			{
				temp=5;
			}
		}
		if(temp!=5)
		{
			printf("NO\n");
			continue;
		}
		for(int i=0;i<len;i++)
		{
			if(S[i]=='K'&&i>1)
			{
				flag=0;
				break;
			}
			if(S[i]=='K'&&S[i+1]!='I')
			{
				flag=0;
				break;
			}
			else if(S[i]=='I'&&S[i+1]!='H')
			{
				flag=0;
				break;
			}
			else if(S[i]=='H'&&((S[i+1]!='B'&&S[i+2]!='B')||(S[i+2]=='B'&&S[i+1]!='A')))
			{
				flag=0;
				break;
			}
			else if(S[i]=='B'&&((S[i+1]!='R'&&S[i+2]!='R')||(S[i+2]=='R'&&S[i+1]!='A')))
			{
				flag=0;
				break;
			}
			else if(S[i]=='R'&&i<len-2)
			{
				flag=0;
				break;
			}
		}
		if(flag==0)
			printf("NO\n");
		else
			printf("YES\n");		
	}
	return 0;
}


Measured memory_bytes: 128
a=list()
for i in range(5):
  a.append(int(input()))
flag=True
count2=0
for i in range(5):
  if a[i]%10==0:
    count2+=a[i]
  else:
    flag=False
if flag==False:
  max=10
  count=0
  for i in range(5):
    if a[i]%10<max and a[i]%10!=0:
      max=a[i]%10
      maxI=i
  for i in range(5):
    if i!=maxI:
      count+=a[i]
      if a[i]%10!=0:
        count+=(10-a[i]%10)
  count+=a[maxI]
  print(count)
else:
  print(count2)
  

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

int main(){
	int n,m,ans = 0;
	cin >> n;
	cin >> m;
	if(n >= 2){
		ans = ans + n*(n-1)/2;
	}
	if(m >= 2){
		ans = ans + m*(m-1)/2;

	}
	cout << ans;

	return 0;
}


Measured memory_bytes: 256
import math

H, W = map(int, input().split())
S = [list(map(lambda x:x == '.', input())) for _ in range(H)]

d = [[math.inf] * (H * W) for _ in range(H * W)]

def node2pos(i):
    h = i // W
    w = i % W
    return h, w

for i in range(H * W):
    for j in range(H * W):
        h1, w1 = node2pos(i)
        h2, w2 = node2pos(j)
        if (abs(h1-h2) == 1 and w1 == w2) or (abs(w1-w2) == 1 and h1 == h2):
            if S[h1][w1] and S[h2][w2]:
                d[i][j] = 1
            if S[h1][w1]:
                d[i][i] = 1

for k in range(H * W):
    for i in range(H * W):
        for j in range(H * W):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ans = 0
for i in range(H * W):
    for j in range(H * W):
        if d[i][j] != math.inf:
            ans = max(ans, d[i][j])

print(ans)


Measured memory_bytes: 77452
/* ---------- STL Libraries ---------- */
// IO library
#include <cstdio>
#include <fstream>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>
#include <cmath>
#include <numeric>
#include <random>
#include <cstring>

// container library
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>
#include <stack>

/* ---------- Namespace ---------- */
using namespace std;

/* ---------- Type ---------- */
using ll = long long;
#define int ll
#define P pair<ll, ll>

/* ---------- Constants  */
const double PI = 3.141592653589793238462643383279;
const ll MOD = 1e9 + 7;
const int INF = 1LL << 55;

/* v-v-v-v-v-v-v-v-v Main Part v-v-v-v-v-v-v-v-v */
signed main() {
    int N, A, B, C, D;
    string str;
    cin >> N >> A >> B >> C >> D >> str;
    A--; B--; C--; D--;

    for (int i = A; i < max(C, D); i++) {
        if (str[i] == '#' && str[i+1] == '#') {
            cout << "No" << endl;
            return 0;
        }
    }

    if (D < C) {
        bool valid = false;
        for (int i = B - 1; i <= D - 1; i++) {
            if (i + 2 >= N) break;

            if (str[i] == '.' && str[i+1] == '.' && str[i+2] == '.') {
                valid = true;
                break;
            }
        }

        if (!valid) {
            cout << "No" << endl;
            return 0;
        }
    }

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

Measured memory_bytes: 640
/**
 *    author:  math2do
 *    created: 21.11.2019 16:2:47
**/

#include <bits/stdc++.h>

using namespace std;

vector <vector <int>> dp;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  #ifdef LOCAL
    freopen("vacation.in", "rt", stdin);
  #endif
  int n;
  cin >> n;
  vector <vector <int>> mat(n, vector <int>(3));
  for (int i = 0; i < n; i++) {
    cin >> mat[i][0] >> mat[i][1] >> mat[i][2];
  }
  
 
  function<int(int idx, int last)> solve = [&](int idx, int last) ->int {
    if (idx == n) return 0;
    if (dp[idx][last] != -1) return dp[idx][last];    
    int ans = 0;
    for (int i = 0; i < 3; i++) {
      if (i == last) continue;
      else {
        ans = max(ans, mat[idx][i] + solve(idx + 1, i));
      } 
    }
    return dp[idx][last] = ans; 
  };
  
  dp.resize(n);
  for (int i = 0; i < n; i++) {
    dp[i].resize(3);
    fill(dp[i].begin(), dp[i].end(), -1);
  } 

  int ans = 0;
  for (int i = 0; i < 3; i++) {
    ans = max(ans, mat[0][i] + solve(1, i));
  } 
  cout << ans << endl;
 
  return 0;
}


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

long long n,arr[200005],counts[200005]={0};
vector<long long>v;

int main()
{
   ios_base::sync_with_stdio(0);cin.tie(0);
   cin>>n;
   long long k,X;
   cin>>k;
   for(int i=1;i<=n;i++) cin>>arr[i];

   long long idx=1,num=1,start;
   while(1)
   {
       if(counts[idx]>0)
       {
           //cout<<"Counts : "<<counts[idx]<<endl;
           if(counts[idx]>k){ cout<<v[k]<<endl; return 0; }
           start=counts[idx];
           X=num-counts[idx];
           start--;
           v.erase(v.begin(),v.begin()+start);
           break;
       }
       counts[idx]=num;
       v.push_back(idx);
       idx=arr[idx];
       num++;
   }
   k-=start;
   X=k%X;
   //cout<<"K : "<<k<<endl;
   //cout<<"X : "<<X<<endl;
   cout<<v[X]<<endl;
}


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

int main(){

	string s;
	cin >> s;

	int n = s.size();
	int idx = 0, f1 = 4, f2 = n - 8;
	for (int i = 0; i < n; i++){
		if (i == f1 || i == f2){
			cout<< ' ' << s[idx++];
		}
		else{
			cout << s[idx++];
		}
	}
	cout << '\n';

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;

int N;
vector<ll> A;

bool judge(int tar){
  ll val=A[tar];
  for(int i=0;i<N;i++){
    if(i==tar) continue;
    if(A[i]<=2*val) val+=A[i];
    else return false;
  }
  return true;
}

int main(){
  cin>>N;
  A.resize(N);
  rep(i,N) cin>>A[i];

  sort(A.begin(),A.end());

  int ok=N-1,ng=-1;
  while(ok-ng>1){
    int mid=(ok+ng)/2;
    if(judge(mid)) ok=mid;
    else ng=mid;
  }

  cout<<N-ok<<endl;

  return 0;
}


Measured memory_bytes: 1152
#include<cstdio>
typedef long long ll;
struct edge
{
	int e, nxt;
};
edge a[200200]; int m;
int sp[100100];
int n; ll K;
const ll base = 1'000'000'007;
ll d[100100];
int par[100100];
bool v[100100];
int deg[100100];
int q[100100], hd = 1, tl = 2;
ll cmod[100100];
int main()
{
	scanf("%d%lld", &n, &K);
	cmod[0] = 1;
	for (int i = 1; i <= K-1; i++)
		cmod[i] = (cmod[i - 1] * (K - 1 - i)) % base;
	for (int i = 1; i < n; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		a[++m].e = v; a[m].nxt = sp[u]; sp[u] = m;
		a[++m].e = u; a[m].nxt = sp[v]; sp[v] = m;
	}
	q[1] = 1; v[1] = true;
	while (hd < tl)
	{
		int cur = q[hd++];
		d[cur] = 1;
		for (int j = sp[cur]; j; j = a[j].nxt)
		{
			if (v[a[j].e]) continue;
			v[a[j].e] = true;
			q[tl++] = a[j].e; par[a[j].e] = cur; deg[cur]++;
		}
	}
	for (int i = n; i > 1; i--)
	{
		int cur = q[i];
		d[cur] = (d[cur] * cmod[deg[cur]]) % base;
		d[par[cur]] = (d[par[cur]] * d[cur]) % base;
	}
	for (int i = 0; i <= deg[1]; i++) d[1] = (d[1] * (K - i)) % base;
	printf("%lld\n", d[1]);
	return 0;
}


Measured memory_bytes: 4992
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>

//#include <tuple>

//#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

int main() {
  ll N, M;
  cin >> N >> M;
  // 問題回答済みかどうかの配列
  vector<ll> p(N, 0);
  // wrongの配列
  vector<ll> wa(N, 0);

  ll pn;
  string s;
  for(int i = 0; i < M; i++){
    cin >> pn >> s;
    // ACの場合
    if (s == "AC"){
      p.at(pn-1) = 1;
    } else { // WAの場合
      if (p.at(pn-1) == 0) { // 不正解の場合
        wa.at(pn-1)++;
      }
    }
  }

  ll rp = 0, rw=0;
  // 数える
  for (int i = 0; i < N; i++) {
    rp += p.at(i);
    if (p.at(i) == 1) {
      rw += wa.at(i);
    }
  }
  
  cout << rp << " " << rw << endl;

}


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

#ifdef __GXX_EXPERIMENTAL_CXX0X__
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

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

#ifdef __GXX_EXPERIMENTAL_CXX0X__
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
//#include <bits/stdc++.h>
#define rep(i, z, n) for(int i = z; i < n; i++)
#define all(v) v.begin(), v.end()
typedef long long ll;
const int INF = 1<<29;
//const int MODINF = 1000000007;
using namespace std;

int main(){
    int H, W, K;
    cin >> H >> W >> K;
    vector<vector<char>> c(H, vector<char>(W));
    rep(i, 0, H){
        rep(j, 0, W){
            cin >> c.at(i).at(j);
        }
    }
    
    int ans = 0;
    for (int tmp = 0; tmp < (1 << 6); tmp++){
        if(tmp >= pow(2, H)) continue;
        bitset<6> s(tmp);
        for (int Tmp = 0; Tmp < (1 << 6); Tmp++){
            if(Tmp >= pow(2, W)) continue;
            int count = 0;
            bitset<6> S(Tmp);
            
            
            rep(i, 0, H){
                rep(j, 0, W){
                    if((!s.test(i)) && (!S.test(j)) && (c.at(i).at(j) == '#')){
                        count++;
                    }
                }
            }
            
            if (count == K){
                ans++;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 4072
#include<bits/stdc++.h>
#define REP(x,y,z) for(int x=y;x<=z;x++)
#define MSET(x,y) memset(x,y,sizeof(x))
#define M 100005
#define INF 1000000000
using namespace std;
using T = tuple<int,int,int>;
int n,m,st,ed,dis[M][3];
vector<int> e[M];
priority_queue<T,vector<T>,greater<T>> q;
int main()
{
    while (~scanf("%d %d", &n, &m)) {
        REP(i,0,n) e[i].clear();
        REP(i,1,m) {
            int x,y;
            scanf("%d %d",&x,&y);
            e[x].push_back(y);
        }
        scanf("%d %d", &st,&ed);

        REP(i,1,n)REP(j,0,2) dis[i][j] = INF;
        q.push( T(0,st,0) );
        while (!q.empty()) {
            int d,x,y;
            tie(d,x,y) = q.top();
            q.pop();
            if (dis[x][y] <= d) continue;
            dis[x][y] = d;

            int y2 = (y+1)%3;
            for (int x2:e[x]) if(dis[x2][y2]>dis[x][y]+1) {
                q.push( T(dis[x][y]+1, x2, y2) );
            }
        }

        if (dis[ed][0]==INF) dis[ed][0] = -1;
        else dis[ed][0] /= 3;
        printf("%d\n", dis[ed][0]);
    }
    return 0;
}


Measured memory_bytes: 7796
function Main(input) {
    input = input.split("\n");
    for (j=0; j < input.length-1; j++) {
        var x = String(input[j])
        var i = String(j+1)
        if (x === "0") {
            break;
        } else {
            console.log("Case " + i + ": " + x)
        }
    }
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 22224
def main():
    N = int(input())
    jobs = []
    time = 0
    for _ in range(N):
        A, B = map(int, input().split())
        jobs.append((A, B))

    jobs = sorted(jobs, key=lambda x: x[1])
    for j in jobs:
        time += j[0]
        if time > j[1]:
            print("No")
            return
        
    else:
        print("Yes")


if __name__ == '__main__':
    main()

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

int main(){
   int n,tmp;
   vector<int> l;
   cin >> n;
   for(int i=0;i<n*2;i++) {cin >> tmp; l.insert(l.begin(),tmp);}
   sort(l.begin(), l.end());
   int ans=0;
   for(int i=0;i<2*n;i+=2) {ans += l[i];}
   cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <set>
#include <string>
#include <vector>
#include <iomanip>
#include <map>
#include <deque>

using namespace std;

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

typedef long long ll;
typedef long double ld;

const ll SIZE = 1e6 + 10, S2 = 1e7 * 2, MOD = 1e9 + 7, INF = 1e9 * 1e7 * 100;



int main() {
    fastInp;

    ll a[3];
    for (int i = 0; i < 3; i++) cin >> a[i];

    ll ans = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                if (i != j && j != k && k != i && a[i] % 2 == a[j] % 2 && a[i] % 2 != a[k] % 2) {
                    a[i]++;
                    a[j]++;
                    ans++;
                }
            }
        }
    }

    ll mx = max(a[0], max(a[1], a[2]));
    for (int i = 0; i < 3; i++) {
        ans += ((mx - a[i]) / 2);
    }

    cout << ans;
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <iomanip>

using namespace std;

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

    int A;
    double sum = 0;
    for (int i = 0; i < N; i++) {
        cin >> A;
        sum += 1.0 / A;
    }

    cout << fixed << setprecision(10) << 1.0 / sum << endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
    // スペース区切りの整数の入力
    int a,b,num,tmp,answer;
	cin >> a >> b;
    answer=b-a+1;
  if(a==1){
  	cout << b << endl;
  }else{
  	num=a*2-1;
    for(int i=0;i<num;i++){
        cout << answer << endl;
      	answer++;
    }
  }

    return 0;
}

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

ll n,k;
ll a[5010];
bool sum[5010];
// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}


int main() {
    std::cin >> n>>k;
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    sort(a,a+n);

    ll r = n-1;
    ll l = -1;
    ll i = r;
    while(r-l>1){
        // iだけがいない街
        bool sum[5010][5010];
      	Fill(sum,false);
      	sum[0][0]=true;
        for (int l = 0; l < n; l++) {
            for (int j = 0; j <= k; j++) {
                if(sum[l][j]){
                    sum[l+1][j] = true;
                    if(j+a[l]<=k && i!=l){
                        sum[l+1][j+a[l]]=true;
                    }
                }
            }
        }
      	sum[n][0]=false;
        
        bool flag = false;
      
        for (int c = 1; c <= min(a[i],k); c++) {
            if(sum[n][k-c]){
                flag = true;
                break;
            }
        }
      	flag = flag || a[i] >=k;
      
        if(i==r && !flag){
          cout<<n<<endl;
            return 0;
        }else if(i==r){
            i = (r+l)/2;
        }else{
            (flag ? r : l ) = i;
            i = (r+l)/2;
        }
    }
    std::cout << l+1 << std::endl;
}


Measured memory_bytes: 24832
n=int(input())
ans=0

for i in range(1,n+1):
  cnt=0
  
  for j in range(1,i+1):
    if i % j == 0:
      cnt += 1
      
  if cnt == 8 and i % 2 == 1:
    ans += 1
    
print(ans)

Measured memory_bytes: 2940
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

using namespace std;
using ll = long long;

constexpr ll infl = 10000000000000007LL;
constexpr int inf = 1000000007;

int main() {
    int n;
    cin >> n;
    vector<int> idx(n + 1);
    for (int i = 1; i <= n; ++i) {
        int p;
        cin >> p;
        idx[p] = i;
    }

    multiset<int> mset{0, 0, n + 1, n + 1};
    ll ans = 0;
    for (int i = n; i >= 1; --i) {
        int c = idx[i];
        auto it_d = mset.lower_bound(c);
        ll d = *it_d;
        ll e = *(++it_d);
        ll b = *(----it_d);
        ll a = *(--it_d);

        ans += ((e - d) * (c - b) + (b - a) * (d - c)) * (ll)i;

        mset.insert(c);
    }

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

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

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

int main()
{
	int N, A, B;
	cin >> N >> A >> B;
	int total = 0;
	for (int num = 1; num <= N; ++num)
	{
		int sum = summation(num);
		if (sum >= A && sum <= B) total += num;
	}
	cout << total << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
typedef long long LL;
const int MaxN = 1e5;

int n;
int main()
{
	while(scanf("%d", &n) != EOF)
	{
		printf("ABC%d\n", n);
	}
}

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

int main() {
	int N, K;
	cin >> N >> K;
	int sum = 0;
	int x;
	for (int i = 0; i < N; i++) {
		cin >> x;
		sum += min(x, K - x);
	}
	cout << sum * 2 << endl;
	return 0;
}


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

using namespace std;

typedef long long ll;

inline ll read(){
	char ch=getchar();ll x=0,f=1;
    while(ch<'0' || ch>'9') {
       if(ch=='-') f=-1;
	  	  ch=getchar();
	}
    while(ch<='9' && ch>='0') {
	   x=x*10+ch-'0';
	   ch=getchar();
	}
    return x*f;
}

map<long long,int> a;

int main(){
	int n=read();
	a[0]=1;
	ll sum=0,s=0;
	for(int i=1;i<=n;i++){
		s+=read();
		sum+=a[s];
		a[s]++;
	}
	cout<<sum;

	return 0;
}


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

int nexta(int a, int L){
	stringstream ss;
	string s0;
	int min, max;
	ss << a;
	s0 = ss.str();
	s0.resize(L, '0');
	sort(s0.begin(), s0.end());
	min = atoi(s0.c_str());
	reverse(s0.begin(), s0.end());
	max = atoi(s0.c_str());
	return(max - min);
}



int main()
{
	int a0, L, a[21], i, j;
	bool flag;
	while (cin >> a0 >> L, (a0 || L)){
		a[0] = a0;
		flag = false;
		for (i = 1; i < 21; i++){
			a[i] = nexta(a[i - 1], L);
			for (j = 0; j < i; j++){
				if (a[i] == a[j]){
					flag = true;
					break;
				}
			}
			if (flag){
				cout << j << " " << a[i] << " " << i - j << endl;
				break;
			}
		}

	}
	return 0;
}

Measured memory_bytes: 1252
import java.io.InputStream;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class Main {

  public static void main(String[] args) {
    resolve(System.in, System.out);
  }

  static void resolve(InputStream is, PrintStream pw) {
    Scanner sc = new Scanner(is);
    List<Integer> a = new ArrayList<>();
    Set<Integer> distinctA = new HashSet<>();
    int n = Integer.parseInt(sc.next());
    for (int i = 0; i < n; i++) {
      Integer an = Integer.valueOf(sc.next());
      a.add(an);
      distinctA.add(an);
    }
    pw.println(
      a.size() == distinctA.size() ? "YES" : "NO"
    );
  }
}


Measured memory_bytes: 70732
#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;
typedef vector<lld> vi;
typedef pair<int,int> pi;
#define F first
#define S second
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define rep(i,a,b) for (int i = a; i < b; i++)
static lld r,j,cu=0,x,y,a,nu=0,b,m,n,s,q,i,z,p,k,d,t;string s1,s2,s3,s4;
vi v[100001];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;lld a[n];set<lld>s;
    rep(i,0,n)
    {
      cin>>a[i];
      s.insert(a[i]);
    }
    cout<<s.size();
} 

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

int main(){
    int A, B, C;
    cin >> A >> B >> C;

    priority_queue<int, vector<int>, greater<int>> que;
    que.push(A);que.push(B);que.push(C);

    int count = 0;
    while(true){
        int min_val = que.top(); que.pop();
        int medium_val = que.top(); que.pop();
        int max_val = que.top(); que.pop();

        if(min_val==medium_val && medium_val==max_val){
            break;
        }

        if(min_val == medium_val){
            count += 1;
            que.push(max_val);
            que.push(medium_val+1);
            que.push(min_val+1);
        }else{
            count += 1;
            que.push(max_val);
            que.push(medium_val);
            que.push(min_val+2);
        }

    }

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

Measured memory_bytes: 3580
import math
from collections import Counter

# N = int(input()) # 1行, 単数
# arg = list(map(int, input().split())) # 1行, 配列
# D = Counter(arg) # 出現数カウント

# print('Yes')
# print('No')
# print()

# while True:
  # try:
    # listA=list(map(int,input().split()))
    # listA.append(list(map(int,input().split())))
  # except:
    # break;

S = list(input()) # 1行, 単数
T = list(input()) # 1行, 単数
cnt = 0

for i, s in enumerate(S):
  if S[i] != T[i]:
    cnt = cnt + 1

print(cnt)

Measured memory_bytes: 85068
#include<bits/stdc++.h>
using namespace std;
string S;
int main(){
	while(1){
		cin >> S;
		if(S[0] == '0') break;
		long long ans = 0;
		for(int i=0;i<S.size();i++){
			ans += S[i] - '0';
		}
		cout << ans << endl;
	}



}


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

typedef pair<string, int> P;

signed main() {
	int n, q;
	cin >> n >> q;
	queue<P> que;

	for (int i = 0; i < n; ++i) {
		string name;
		int time;
		cin >> name >> time;
		que.push(make_pair(name, time));
	}

	int cnt = 0;

	while (!que.empty()) {
		if (que.front().second > q) {
			que.front().second -= q;
			que.push(que.front());
			que.pop();
			cnt += q;
		}
		else {
			cnt += que.front().second;
			cout << que.front().first << ' ' << cnt << endl;
			que.pop();
		}
	}
}


Measured memory_bytes: 6340
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < b; i++)
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main()
{
    int n;
    cin >> n;
    string t = "MARCH";
    ll cnt[5] = {};
    rep(i, 0, n) {
        string s;
        cin >> s;
        rep(j, 0, 5) {
            if (s[0] == t[j]) cnt[j]++;
        }
    }

    ll ans = 0;
    rep(i, 0, 5) {
        rep(j, i + 1, 5) {
            rep(k, j + 1, 5) {
                ans += cnt[i] * cnt[j] * cnt[k];
            }
        }
    }

    cout << ans << endl;
    return 0;

}


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

#define rep(i,n) for(ll i=0;i<(n);++i)
using ll = long long;
using pll = pair<ll,ll>;
constexpr ll INF = (1LL<<60);
constexpr ll MOD = (1e9+7);
//constexpr ll MOD = (998244353);
template<class T> bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T> bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}return 0;}
#if loc||debg||local||debug
void dump(){cerr<<endl;}
template<class T,class... Ts> void dump(T&& h, Ts&&... t){cerr<<h<<", ";dump(forward<Ts>(t)...);}
#else
template<class T,class... Ts> void dump(T&& h, Ts&&... t){}
#endif
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T> ostream &operator<<(ostream& os,vector<T>const& v){for(auto const& vi:v)os<<vi<<" ";return os;}
template<class T>vector<T> vec(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto vec(size_t a, Ts... ts){return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...));}
template<class T>vector<T> _vec(size_t a,T v){return vector<T>(a,v);}
template<class T, class... Ts>auto _vec(size_t a, Ts... ts){return vector<decltype(_vec<T>(ts...))>(a, _vec<T>(ts...));}

constexpr ll COM_MAX = (ll)1e6;
vector<ll> fac(COM_MAX),finv(COM_MAX),inv(COM_MAX);
// 前処理
void comb_init(){
  fac[0]=fac[1]=1;
  finv[0]=finv[1]=1;
  inv[1]=1;
  for(int i=2;i<COM_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 comb(ll n,ll k){
  if(n<k)return 0;
  if(n<0||k<0)return 0;
  return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}
// 重複組み合わせ
ll nHk(ll n,ll k){
  return comb(n+k-1,n-1);
}


int main(){

  comb_init();

  ll h,w,a,b;
  cin>>h>>w>>a>>b;

  ll ans = 0ll;
  for(ll i=b+1;i<=w;++i){
    ll x = comb(h-a+i-2,i-1);
    ll y = comb(w-i+a-1,a-1);
    dump(x,y);
    ans += (x*y)%MOD;
    ans %= MOD;
  }
  cout<<(ans)<<endl;

}

Measured memory_bytes: 23680
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>

#include <algorithm>
#include <numeric>
#include <cmath>

using namespace std;
typedef long long ll;
const long double PI = (acos(-1));
const long long MOD = 1000000007;

static const int  MAX_INT = std::numeric_limits<int>::max();
static const long MAX_LONG = std::numeric_limits<long>::max();
static const ll   MAX_LL = std::numeric_limits<long long>::max();

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


///////////////////////////////////////////////////
// ------------------- utils ------------------- //
///////////////////////////////////////////////////
// change min/max
template<class T> inline bool chMin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chMax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

// initalisation of the binominal coefficient
void COMBinit(std::vector<long long>& fac, std::vector<long long>& finv, std::vector<long long>& inv, int n, int MOD) {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < n; 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;
    }
}

// binominal coefficient: nCk
// http://drken1215.hatenablog.com/entry/2018/06/08/210000
long long COMB(int n, int k, int MOD) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    std::vector<long long> fac(n + 1), finv(n + 1), inv(n + 1);
    COMBinit(fac, finv, inv, n + 1, MOD);
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

///////////////////////////////////////////////////
// ------------------- main -------------------- //
///////////////////////////////////////////////////
void Main() {
    ll S; cin >> S;
    if (S < 3) {
        cout << 0 << endl;
        return;
    }
    
    // combination: O(N)
    // for each number of elements, count the possible configurations of extra elements
    //ll maxN = S / 3;
    //ll cnt = 1;
    //for (ll i = 2; i <= maxN; ++i) {
    //    ll slot = S - 3 * i;
    //    cnt = (cnt + COMB(slot + i - 1, i - 1, MOD)) % MOD;
    //}
    //cout << cnt << endl;

    // dp : O(N)
    // https://www.youtube.com/watch?v=yLkJZXkB6D0&feature=youtu.be
    vector<ll> dp(S+1, 0);
    dp[0] = 1;
    for (ll i = 3; i <= S; ++i) {
        for (ll j = 0; j <= i - 3; ++j) {
            //dp[i] += dp[j];
            //dp[i] %= MOD;
            dp[i] = (dp[i] + dp[j]) % MOD;
        }
    }
    cout << dp[S] << endl;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout << std::fixed << std::setprecision(15);
    Main();

    double tmp;
    cin >> tmp;

    return 0;
}


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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& x : a)
        cin >> x;
    sort(a.begin(), a.end());
    vector<int> visited(1000001);

    for (int i = 0; i < n; i++) {
        if (visited[a[i]] == 0) {
            for (int j = 2 * a[i]; j <= 1000000; j += a[i]) {
                visited[j]++;
            }
            if (i+1 < n && a[i] == a[i+1])
                visited[a[i]]++;
        }
    }
    int ans=0;
    for (int x : a) {
        if (!visited[x])
            ans++;
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 7936
while(s=?/+gets.gsub(/\d+/){|k|?1*k.to_i})!~/#/
n=s.size-s.rindex(?/)-1
a,b,c,d=gets.split.map &:to_i
s[n*a-n+b]=?1
s[n*c-n+d]=?b
$><<s[1..-1].gsub(/1+/,&:size)
end

Measured memory_bytes: 8728
#!/usr/bin/env python3

MOD = 10**9
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

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

m = K-A[len(A)-1] + A[0]

index = 0

for i in range(len(A)-1):
    d = A[i+1]-A[i]
    if m < d:
        m = d
        index = i

ans = K - m
print(ans)



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

int main()
{

    int n,x;

    int i,j,k;

    int count;
 while(1){
   count = 0;
    cin >> n >> x;
    if(n == 0 && x == 0){ break;
    }
    
    else {
    
    for(i = 1;i <= n;i++){

      for(j = i+1;j <= n;j++){

	for(k = j+1;k <= n;k++){

	  if(i + j + k == x){

	    count++;
	  }
	}
      }
    }

    }
    cout << count << "\n";
  }
}

Measured memory_bytes: 1160