akhauriyash/Code-Regression huggingface dataset:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))
import itertools
import math

def calc_distance(x1, y1, x2, y2):
    return math.sqrt((x1 - x2)**2 + (y1 - y2)**2)

def main():
    N = int(input())
    matrix = []
    for i in range(N):
        x, y = input_nums()
        matrix.append((x, y))
    total = 0
    count = 0
    for cmb in itertools.permutations(range(N), N):
        count += 1
        sumv = 0
        for i in range(len(cmb)-1):
            x1 = matrix[cmb[i]][0]
            y1 = matrix[cmb[i]][1]
            x2 = matrix[cmb[i+1]][0]
            y2 = matrix[cmb[i+1]][1]
            sumv += calc_distance(x1, y1, x2, y2)
        total += sumv
    print(total/count)


if __name__ == '__main__':
    main()

Measured memory_bytes: 39664
#include <algorithm>
#include <iostream>

int main(int argc, char *argv[]) {
  int n;
  std::cin >> n;
  long long a[1001];
  for (int i = 0; i < n; ++i)
    std::cin >> a[i];
  int q;
  std::cin >> q;
  for (int i = 0; i < q; ++i) {
    int b, e, k;
    std::cin >> b >> e >> k;
    std::cout << std::count(a + b, a + e, k) << std::endl;
  }
}



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

int main(){
	int N, K, c = 0;
	cin >> N >> K;
	int A[N] = {0};
	for(int i = 0; i < N; i++){
		int a;
		cin >> a;
		A[a]++;
	}
	sort(A,A+N);
	reverse(A,A+N);
	for(int i = 0; i < K; i++)
		c += A[i];
	cout << N-c << endl;
	return 0;
}

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

void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int main()
 {
	fast();
	    int n;
	    cin>>n;
	    
	    int res=0;
	    if(n%1000==0)
	    res=0;
	    else
	    {
	        res=1000-(n%1000);
	    }
	    cout<<res<<endl;
	
	
}

Measured memory_bytes: 3636
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/STACK:108777216")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <ctime>
using namespace std;
 
int const MAX_N = 128 * 1024;
 
int main() {
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
 
    int n,a;
	cin>>n>>a;
	for (int b=0; b*500<=n; b++)
		if (n-b*500 <= a) {
			cout<<"Yes";
			return 0;
		}
	cout<<"No";
    return 0;
}  


Measured memory_bytes: 384
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<cstdlib>
#include<ctime>
#include<climits>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define inf 0x3f3f3f3f
#define N 100010
#define M 
using namespace std;

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

struct Edge{
  int to,next;
}e[N<<1];

int ne,n,m,head[N],vis[N],val[N],x,y,tot;
map<int,int> mp;

void ins(int u,int v){
  ne++;
  e[ne].to=v;
  e[ne].next=head[u];
  head[u]=ne;
}

void insert(int u,int v){
  ins(u,v);ins(v,u);
}

void dfs(int x,int c){
  vis[x]=1;val[x]=tot;mp[tot]=x;
  for(int i=head[x];i;i=e[i].next){
    if(vis[e[i].to]) continue;
    tot+=c;
    dfs(e[i].to,c);
    break;
  }
}

int main(){
  n=read();m=read();
  memset(val,0x3f,sizeof(val));
  rep(i,1,m){
    int u=read(),v=read();
    insert(u,v);
    x=u;y=v;
  }
  vis[x]=1;vis[y]=1;
  tot=1;
  dfs(x,1);
  tot=0;
  dfs(y,-1);
  //  rep(i,1,n) printf("%d ",val[i]);
  //  printf("\n");
  sort(val+1,val+1+n);
  rep(i,1,n+1) if(val[i]==inf){
    printf("%d\n",i-1);
    break;
  }
  rep(i,1,n){
    if(val[i]==inf) break;
    printf("%d ",mp[val[i]]);
  }
  return 0;
}


Measured memory_bytes: 7936
R, C, K = map(int, input().split())
item = [[0 for _ in range(C + 1)] for _ in range(R + 1)]
for _ in range(K):
    r, c, v = map(int, input().split())
    item[r][c] = v

# 多次元配列を生成する際、使いたい引数を逆順で書くと上手くいく

# dp = [[[0 for _ in range(4)] for _ in range(C + 1)] for _ in range(R + 1)]
# とするとTLEだった。(R+1)*4(C+1)だと通るみたいだが、あまり本質的ではない気がする。
# 以下ではdp0,dp1,dp2,dp3という4つの配列を作ることにする。

dp0 = [[0 for _ in range(C + 1)]for _ in range(R + 1)]
dp1 = [[0 for _ in range(C + 1)]for _ in range(R + 1)]
dp2 = [[0 for _ in range(C + 1)]for _ in range(R + 1)]
dp3 = [[0 for _ in range(C + 1)]for _ in range(R + 1)]

for i in range(R + 1):
    for j in range(C + 1):
        # 何度も使うので変数に格納しておく
        # 以下を省略し、毎回配列を見に行く書き方をしたら少し遅くなった(400ms程度)
        now0 = dp0[i][j]
        now1 = dp1[i][j]
        now2 = dp2[i][j]
        now3 = dp3[i][j]

        # 下に移動する場合、アイテムの個数はリセットされる
        if i <= R - 1:
            # 移動先のアイテムを取らない場合
            dp0[i + 1][j] = max(dp0[i + 1][j],
                                now0,
                                now1,
                                now2,
                                now3)

            # 移動先のアイテムを取る場合
            dp1[i + 1][j] = max(dp1[i + 1][j],
                                now0 + item[i + 1][j],
                                now1 + item[i + 1][j],
                                now2 + item[i + 1][j],
                                now3 + item[i + 1][j])

        # 右に移動する場合、アイテムの個数は維持される
        if j <= C - 1:
            # 移動先のアイテムを取らない場合
            dp0[i][j + 1] = max(dp0[i][j + 1],
                                now0)
            dp1[i][j + 1] = max(dp1[i][j + 1],
                                now1)
            dp2[i][j + 1] = max(dp2[i][j + 1],
                                now2)
            dp3[i][j + 1] = max(dp3[i][j + 1],
                                now3)

            # 移動先のアイテムを取る場合
            dp1[i][j + 1] = max(dp1[i][j + 1],
                                now0 + item[i][j + 1])
            dp2[i][j + 1] = max(dp2[i][j + 1],
                                now1 + item[i][j + 1])
            dp3[i][j + 1] = max(dp3[i][j + 1],
                                now2 + item[i][j + 1])

# 最終的にR行で取るアイテムの個数についてそれぞれ調べる、3個が最適とは限らない
ans = max(dp0[-1][-1],
          dp1[-1][-1],
          dp2[-1][-1],
          dp3[-1][-1])

print(ans)


Measured memory_bytes: 473140
#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    long n,i;
    cin>>n;
    long A[n];
    for(i=0;i<n;i++)
        cin>>A[i];
 	long long dp[n];
    //dp[0]=0;
    dp[0]=0;
  	dp[1]=abs(A[1]-A[0]);
    for(i=3;i<=n;i++)
        dp[i-1]=min(dp[i-2]+abs(A[i-1]-A[i-2]),dp[i-3]+abs(A[i-1]-A[i-3]));
    cout<<dp[n-1]<<endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>

#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)

typedef long long int64;

using namespace std;

double calc(double a, double b, double alpha) {
    if (alpha < 45) {
	    
	}
}

int main() {
	ios_base::sync_with_stdio(0);
    double a, b, x;
	double pi = 4 * atan(1.0);
	cin >> a >> b >> x;
	double h = x / (a * a);
	double s = h * a;
	cout.precision(10);
	double ans;
	if (s < a * b / 2) {
	    double x = (2 * s / b);
		ans = pi / 2 - atan(x / b);
	} else {
		s -= a * b / 2;
		double x = 2 * (a * b / 2 - s) / a;
		ans = atan(x / a);
	}
	cout << ans / pi  * 180;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#define debug(x) cout<<"***"<<x<<"***"<<endl;
using namespace std;
int a[55];
int main()
{
	int sum=0,n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=n-1;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			sum+=a[i]*a[j];
		}
	}
	cout<<sum;
	return 0;
}

Measured memory_bytes: 764
//ACになるコード
#include <iostream>
#include <vector>
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> vec(1);
  int a = -1, b = -1, c = -1;
  int acount = 0, bcount = 0, ccount = 0;
  for(int i=0; i<n; i++){
    int num;
    cin >> num;
    if(i == 0) a = num;
    else if(a != num && b == -1) b = num;
    else if(a != num && b != num && c == -1) c = num;
    else if(a != num && b != num && c != num){
      cout << "No" << endl;
      return 0;
    }
    if(a == num) acount++;
    if(b == num) bcount++;
    if(c == num) ccount++;
  }
  if(a != -1 && b != -1 && c != -1 && acount == n/3 && bcount == n/3 && ccount == n/3 && (a ^ b) == c){
    cout << "Yes" << endl;
    return 0;
  }else if(c == -1 && ((a == 0 && bcount - acount == acount) || (b == 0 && acount - bcount == bcount))){
    cout << "Yes" << endl;
    return 0;
  }else if(a == 0 && b == -1 && c == -1){
    cout << "Yes" << endl;
    return 0;
  }else{
    cout << "No" << endl;
    return 0;
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#define DIM 200005
using namespace std;
int n, i, st, dr, ii, j, mid;
long long sol;
int ind[DIM];
struct sir{
    string s, s2;
    int m, m2;
};
sir v[DIM];
int cmp(int a, int b){
    for(int i = 0; i < min(v[a].m2, v[b].m2); i++){
        if(v[a].s2[i] != v[b].s2[i]){
            return v[a].s2[i] < v[b].s2[i];
        }
    }
    if(v[a].m2 != v[b].m2){
        return v[a].m2 < v[b].m2;
    }
    return v[a].m < v[b].m;
}
int egal(int a, int b){
    if(v[a].m2 > v[b].m2){
        return 0;
    }
    for(int i = 0; i < v[a].m2; i++){
        if(v[a].s2[i] != v[b].s2[i]){
            return 0;
        }
    }
    return 1;
}
int main(){
    cin>> n;
    for(i = 1; i <= n; i++){
        cin>> v[i].s;
        v[i].m = v[i].s.size();
        for(j = 0; j < v[i].m; j++){
            v[i].s2 += v[i].s[  v[i].m - j - 1 ];
        }
    }
    for(ii = 'a'; ii <= 'z'; ii++){
        for(i = 1; i <= n; i++){
            for(j = 0; j < v[i].m; j++){
                if(v[i].s[j] == ii){
                    break;
                }
            }
            v[i].m2 = v[i].m - j - 1;
            ind[i] = i;
        }
        sort(ind + 1, ind + n + 1, cmp);
        for(i = 1; i <= n; i++){
            if(v[ ind[i] ].s[0] == ii){
                st = i + 1;
                dr = n;
                while(st <= dr){
                    mid = (st + dr) / 2;
                    if(egal(ind[i], ind[ mid ])){
                        st = mid + 1;
                    }
                    else{
                        dr = mid - 1;
                    }
                }
                sol += dr - i;
            }
        }
    }
    cout<< sol;
}

Measured memory_bytes: 21436
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string>
#include <vector>
#include <cstdio>
#include <iomanip>
#define ll long long
#define rep2(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define rep3(i,a,b) for(int i=a;i>=b;i--)
#define REP(e,v) for(auto e:v)
#define queint queue<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue<int>//大きい順
#define pqg priority_queue<int,vec,greater<int>>//小さい順
#define pb push_back
#define vec vector<int>
#define vecvec vector<vector<int>>
#define vecll vector<ll>
#define vecvecll vector<vector<ll>>
#define bs binary_search
#define All(c) (c).begin(),(c).end()
#define mp make_pair
using namespace std;
int in(){int x;scanf("%d",&x);return x;}
string stin(){string s;cin>>s;return s;}
ll lin(){ll x;scanf("%lld",&x);return x;}
int main(){
    int n=in(),a=in();
    vec p(n);
    rep(i,n)p[i]=in();
    vector<vecll> x(n+1,vecll(50*n+1));
    x[0][0]=1;
    rep(i,n)rep3(j,n,1)rep2(k,p[i],50*n)x[j][k]+=x[j-1][k-p[i]];
    ll ans=0;
    rep2(i,1,n)ans+=x[i][a*i];
    cout<<ans<<endl;
}


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

int a, b, q;
const long long INF = 1ull << 60;

int main()
{
	cin >> a >> b >> q;

	vector<long long> s(a), t(b);

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

	for (int i = 0; i < b; i++)
		cin >> t[i];

	for (int i = 0; i < q; i++) {
		long long x, m = 0;
		long long r[4] = { INF, INF, INF, INF };

		cin >> x;

		vector<long long>::iterator j = lower_bound(s.begin(), s.end(), x), 
			k = lower_bound(t.begin(), t.end(), x);

		if (j != s.begin() && k != t.begin())
			r[0] = x - min(*(j - 1), *(k - 1));

		if (j != s.end() && k != t.end())
			r[1] = max(*j, *k) - x;

		if (j != s.begin() && k != t.end())
			r[2] = min(x + *k - *(j - 1) * 2, *k * 2 - x - *(j - 1));

		if (j != s.end() && k != t.begin())
			r[3] = min(x + *j - *(k - 1) * 2, *j * 2 - x - *(k - 1));

		m = min({ r[0], r[1], r[2], r[3] });

		cout << m << endl;
	}

	return 0;
}

Measured memory_bytes: 2944
//メモリ数確認したか?
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
#include<cstdlib>
using namespace std;
typedef long long int ll;

int main()
{
    int W,H,N;
	scanf("%d%d%d",&W,&H,&N);
	int X[1000],Y[1000];
	for(int i=0;i<N;i++){
		scanf("%d%d",&X[i],&Y[i]);
	}
	int ans=0;
	for(int i=0;i<N-1;i++){
		if((X[i]-X[i+1])*(Y[i]-Y[i+1])>=0){
			ans+=max(abs(X[i]-X[i+1]),abs(Y[i]-Y[i+1]));
		}
		else ans+=abs(X[i]-X[i+1])+abs(Y[i]-Y[i+1]);

	}
	printf("%d\n",ans);
    return 0;
}
//メモリ数確認したか?

Measured memory_bytes: 1196
#include<iostream>
#include<queue>
#include<vector>
#define INF 1000
using namespace std;

typedef pair<int,int> P;

int H,W;
int mindep;				//最小手数		
char MAP[12][12];		//可変マップデータ( 外側番兵 )
char has[4] = "RGB";

//領域の面積を戻り値とする
int BFS( char color ){
	queue<P> que;
	P now;
	char map11 = MAP[1][1];
	int i;
	int dx[4] = {0,1,0,-1};
	int dy[4] = {1,0,-1,0};
	int ret = 0;

	que.push( P(1,1) );
	while( !que.empty() ){
		now = que.front();
		que.pop();
		if( MAP[ now.first ][ now.second ] != map11 )
			continue;
		ret++;
		MAP[ now.first ][ now.second ] = color;
		for( i = 0;i < 4;i++ )
			que.push( P( now.first + dy[i], now.second + dx[i] ) );
	}
	return ret;
}

//depth=操作回数,maxcount1=最多の色ブロックの個数(操作前)
int draw( int depth,int maxcount1 )
{
	char color = MAP[1][1];			//1行1列の色(文字)
	char map[12][12] = {0};			//今のマップデータ
	//int cnt[3] = {0};				//R,G,Bブロックの数
	int maxcount2;					//今の最多の色ブロックの個数(操作前)
	int i,j;

	if( mindep <= depth )
		return INF;

	for( i = 1;i < H+1;i++ ){
		for( j = 1;j < W+1;j++ ){
			map[i][j] = MAP[i][j];
			/*if( MAP[i][j] == 'R' )
				cnt[0]++;
			if( MAP[i][j] == 'B' )
				cnt[1]++;
			if( MAP[i][j] == 'G' )
				cnt[2]++;*/
		}
	}
	//cout << cnt[0] << " " << cnt[1] << " " << cnt[2] << endl;

	int ret[3] = {1000,1000,1000};	//戻り値

	for( i = 0;i < 3;i++ ){
		if( has[i] == color )
			continue;
		//MAP[1][1]と同じ色の1つの領域をhas[i]色にする.
		maxcount2 = BFS( has[i] );
		if( maxcount2 == H*W )
			return depth;
		if( maxcount1 >= maxcount2 )
		{
			continue;
		}
		ret[i] = draw( depth+1,maxcount2 );
		//MAPの内容をもとに戻す
		for( j = 1;j < H+1;j++ ){
			for( int k = 1;k < W+1;k++ ){
				MAP[j][k] = map[j][k];
			}
		}
	}
	mindep = min( mindep, min( ret[0], min(ret[1],ret[2]) ) );
	return min( ret[0], min(ret[1],ret[2]) );
}

int main()
{
	int i,j,k;
	int cnt[3] = {0};		//R,B,Gブロックの数
	int ans[1000] = {0};

	for( i = 0; cin >> W >> H; i++ ){
		if( W == 0 && H == 0 )
			break;
		mindep = INF;
		for( j = 0;j < H+2;j++ ){
			for( k = 0;k < W+2;k++ ){
				MAP[j][k] = 0;
			}
		}

		for( j = 1;j < H+1;j++ ){
			for( k = 1;k < W+1;k++ ){
				cin >> MAP[j][k];
				if( MAP[j][k] == '\n' || MAP[j][k] == '\r' ){
					k--;
					continue;
				}
			}
		}
		ans[i] = draw( 0,0 );
		cout << ans[i] << endl;
	}

	/*for( j = 0;j < i;j++ ){
		cout << ans[j] << endl;
	}*/
	return 0;
}

Measured memory_bytes: 1220
/*
ID: rchalam1
LANG: C++14
TASK:
*/
// For train.usaco.org, fill the template above.

// Competitive Coding Template

// GCC OPTIMIAZTION FLAGS
#ifdef ONLINE_JUDGE
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#endif

#include <bits/stdc++.h>

/*
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
*/
// All Includes for Competitive Coding Template

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

using vi = std::vector<int>;
using vll = std::vector<long long>;
using vull = std::vector<unsigned long long>;

#define FOR(i, a, b) for (auto i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (auto i = (a); i >= (b); --i)
#define R0F(i, a) ROF(i, a, 0)
#define ITR(a, x) for (auto& a: x)

#define FSRT(set) sort((set).begin(),(set).end())
#define RSRT(set) sort((set).rbegin(),(set).rend())
#define CSRT(set, function) sort((set).begin(),(set).end(), (function))
#define TRS(set) sort((set).begin(),(set).end(), greater<>())
#define REV(set) reverse((set).begin(),(set).end());

#define ALL(set) (set).begin(), (set).end()

#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

// For stdio, call setIO() or setIO("").
void setIO(std::ifstream &readFile, std::ofstream &writeFile, const std::string &name = "", bool stdIO = false)
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	if(!name.empty() && !stdIO)
	{
		readFile.open(name + ".in");
		if(readFile.fail()) return;
		writeFile.open(name + ".out");
		std::cin.rdbuf(readFile.rdbuf());
		std::cout.rdbuf(writeFile.rdbuf());
	}
}

// To time program, create object Timer  to start timing, and call Timer.elapsed().
#include <chrono>

class Timer
{
	std::chrono::time_point<std::chrono::high_resolution_clock> m_beg;
public:
	Timer() : m_beg(std::chrono::high_resolution_clock::now())
	{}

	void reset()
	{ m_beg = std::chrono::high_resolution_clock::now(); }

	[[nodiscard]] long double elapsed() const
	{
		return std::chrono::duration_cast<std::chrono::duration<long double, std::ratio<1> >>(
				std::chrono::high_resolution_clock::now() - m_beg).count();
	}
};

// Defines datatype
using dt = int;
// Defines MAXN value
constexpr dt MAXN = 1e5 + 1;
// Defines Modulus
constexpr dt MOD = 1e9 + 7;
// Defines Floating Point Correction
constexpr long double EPS = 1e-9;

//*****
//START CODE BELOW
//*****

int main(int argc, char *argv[])
{
	static std::ifstream readFile;
	static std::ofstream writeFile;
	setIO(readFile, writeFile);
	int n;
	cin >> n;
	vector<int> ps(n);
	for(auto &p : ps) cin >> p;
	int answer = 1, minimum = ps[0];
	for(int i = 1; i < n; ++i)
	{
		answer += (ps[i] <= minimum);
		minimum = min(minimum, ps[i]);
	}
	cout << answer << '\n';
}

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

int main() {
  int n;
  cin >> n;
  vector<int> scores(n);
  int sum = 0;
  rep(i, n) {
    cin >> scores[i];
    sum += scores[i];
  }
  sort(scores.begin(), scores.end());
  if (sum % 10 == 0) {
    for (auto it = scores.begin(); it != scores.end(); it++) {
      if (*it % 10 != 0) {
        sum -= *it;
        break;
      }
    }
  }

  if (sum % 10 == 0) {
    cout << 0 << endl;
  } else {
    cout << sum << endl;
  }

  return 0;
}


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

using namespace std;

int main(){

  long long int n;
  cin>>n;

  long long int l, r;
  cin>>l>>r;

  for(int i=1; i<n; i++){
    long long int t, a;
    cin>>t>>a;
    long long int j=max((l-1)/t, (r-1)/a)+1;
 //   while(j*t<l or j*a<r) j++;
    l=j*t;
    r=j*a;
  }

  cout<<l+r<<endl;
}


Measured memory_bytes: 3644
/*
    ->->->->-> Vora Mahammasasim <-<-<-<-<-
*/
#include<bits/stdc++.h>
#include<stdio.h>
#define Quick std :: ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define pb emplace_back
#define Mod 1000000007
#define all(a) a.begin(),a.end()
#define ps(a) partial_sum(all(a),a.begin())
using namespace std;

signed main(){

    Quick;
    string s;
    cin>>s;
    int ans = 0;
    for(int i=0;i<s.size();i++){
        ans += (s[i]-'0');
    }
    if(ans%9 ==0 ) cout<<"Yes\n";
    else cout<<"No\n";
}


Measured memory_bytes: 3780
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    l = []
    if n%2 == 0:
        for i in range(1,n+1):
            for j in range(i+1,n+1):
                if i == j or i+j == n+1:
                    continue
                else:
                    l.append((i,j))
    else:
        for i in range(1,n+1):
            for j in range(i+1,n+1):
                if i+j == n:
                    continue
                else:
                    l.append((i,j))
    print(len(l))
    for i,j in l:
        print(i,j)
    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 43244
import sys
import functools

def minmaxsum(*t):
    (x,y,z),e=t
    if x > e:
        x=e
    if y < e:
        y = e
    z += e
    return (x,y,z)

input()
m,x,s = functools.reduce(minmaxsum,map(int,input().split()),(1000000,-1000000,0\
))
print(m,x,s)

Measured memory_bytes: 8896
import sys;input=sys.stdin.readline
from collections import deque, defaultdict
def encode(i, j):
    return 2 + K + i*M + j
from heapq import heappush, heappop
class MinCostFlow:
    INF = 10**18

    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def addEdge(self, fr, to, cap, cost):
#        print(fr, to, 10**18-cost)
        forward = [to, cap, cost, None]
        backward = forward[3] = [fr, 0, -cost, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def minCostFlow(self, s, t, f):
        N = self.N; G = self.G
        INF = MinCostFlow.INF

        res = 0
        H = [0]*N
        prv_v = [0]*N
        prv_e = [None]*N

        d0 = [INF]*N
        dist = [INF]*N

        while f:
            dist[:] = d0
            dist[s] = 0
            que = [(0, s)]

            while que:
                c, v = heappop(que)
                if dist[v] < c:
                    continue
                r0 = dist[v] + H[v]
                for e in G[v]:
                    w, cap, cost, _ = e
                    if cap > 0 and r0 + cost - H[w] < dist[w]:
                        dist[w] = r = r0 + cost - H[w]
                        prv_v[w] = v; prv_e[w] = e
                        heappush(que, (r, w))
#            print(dist)
            if dist[t] == INF:
                return None

            for i in range(N):
                H[i] += dist[i]

            d = f; v = t
            while v != s:
                d = min(d, prv_e[v][1])
                v = prv_v[v]
            f -= d
            res += d * H[t]
            v = t
            while v != s:
                e = prv_e[v]
                e[1] -= d
                e[3][1] += d
                v = prv_v[v]
        return res
N, M = map(int, input().split())
B = []
for _ in range(N):
    s = input().strip()
    B.append(s)

ks = []
for i in range(N):
    for j in range(M):
        if B[i][j] == "o":
            ks.append((i, j))
K = len(ks)
mcf = MinCostFlow(2+K+N*M)
for i in range(K):
    mcf.addEdge(0, i+2, 1, 0)

for ki in range(K):
    i, j = ks[ki]
    s = (i, j)
    queue=deque([s])
    vs = set([s])
    dist = defaultdict(int)
    while queue:
        u, v = queue.popleft()
#        print(2+ki, (u,v),encode(u,v), (i,j), dist[(u, v)])
        mcf.addEdge(2+ki, encode(u, v), 1, 10**5-dist[(u, v)])
        for nu, nv in [(u+1, v), (u, v+1)]:
            if (nu, nv) in vs:
                continue
            if nu >= N or nv >= M:
                continue
            if B[nu][nv] == "#":
                continue
            vs.add((nu, nv))
            queue.append((nu, nv))
            dist[(nu, nv)] = dist[(u, v)] + 1

for i in range(N):
    for j in range(M):
        mcf.addEdge(encode(i,j),1,1,0)
#print(mcf.G)
print(K*10**5-mcf.minCostFlow(0, 1, K))


Measured memory_bytes: 103420
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
    int D,N,ans=0;cin>>D>>N;
    int m=pow(100,D);
    REP(i,N)ans+=m;
    if(N==100)ans+=m;
    cout<<ans<<endl;
}

Measured memory_bytes: 256
from sys import stdin

if __name__ == '__main__':
    n, k = [int(x) for x in stdin.readline().rstrip().split()]
    H = [int(x) for x in stdin.readline().rstrip().split()]
    H.sort(reverse=True)
    H = H[k:]
    totalAttack = sum(H)
    print(totalAttack)

Measured memory_bytes: 26764
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <iomanip>
#include <set>
using namespace std;

#define rep(i, s) for (int i = 0; i < s; ++i)
#define all(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define VEC(a, n) vector<int>a(n)
#define PQ(a) priority_queue<int>a
#define PQmin(a) priority_queue< int, :vector<int>, greater<int> >a
#define PAIR pair<int, int>
/*
sort(sp.begin(), sp.end(), [](PAIR l, PAIR r){
        return l.first<r.first || (l.first==r.first && l.second > r.second);
        });
*/

typedef long long  ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))


int main() {
    int n,a,b;
    cin>>n>>a>>b;
    if((b-a)%2==0){
        cout<<"Alice"<<endl;
        return 0;
    }
    else{
        cout<<"Borys"<<endl;
        return 0;
    }

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define rrep(i, n) for(int i=n-1; i>=0; i--)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
template<class T> void puts(T x) { std::cout << x << std::endl; }
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; }

const int MAX_V = 100010;
int V, E;
vector<vector<int>> g;
bool visited[MAX_V];
int disc[MAX_V], low[MAX_V], parent[MAX_V], ap[MAX_V];

void dfs(int u) {
    static int time = 0;
    int children = 0;
    visited[u] = true;
    disc[u] = low[u] = time++;
    for (int v: g[u]) {
        if (!visited[v]) {
            children++;
            parent[v] = u;
            dfs(v);
            low[u] = min(low[u], low[v]);
            if (parent[u] == -1 && children > 1) ap[u] = true;
            if (parent[u] != -1 && low[v] >= disc[u]) ap[u] = true;
        } else if (v != parent[u]) {
            low[u] = min(low[u], disc[v]);
        }
    }
}

int main() {
    cin >> V >> E;
    g.resize(V);
    rep(i, V) parent[i] = -1;
    rep(i, E) {
        int s, t; cin >> s >> t;
        g[s].pb(t);
        g[t].pb(s);
    }

    rep(i, V) {
        if (!visited[i]) dfs(i);
    }
    rep(i, V) {
        if (ap[i]) cout << i << endl;
    }
}



Measured memory_bytes: 4712
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  string s,t;
  cin>>s>>t;
  char a[2*n];
  int k=0;
  for(int i=0;i<n;i++){
  a[k++]=s[i];
    a[k++]=t[i];
  
  }
  a[k]='\0';
  cout<<a<<endl;
}

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
"""
.2分探索を考える
.各kに対してx回以上抜き出せるかという問いを考える
.各数の個数を数えて数iの個数をCiとする
.各数iを抜き出せるのはCiまで
 ⇒各数を抜き出す回数min(Ci,x)
.Σmin(Ci,x)はkx以上でなければいけない(k個x回抜き出すため)
.これを満たすときx回抜き出せる
.このままではO(n^2(logn))なので工夫する
.Σ(min(Ci,x))はk依存でないのでここを工夫する(Σ(min(Ci,x))をSxとする)
.SxはSx-1と比べてx以上のCiの数だけ増える(x以上のCiの数をDxとする)
.Sx := Sx-1 + Dx
.Dxを求める時はCのリストについてbisectを行う。
⇒Ciの個数のリストdを用意してdの累積和を用意しておくとO(n)
.Sx >= k*xとなるxの最大値を2分探索で求める。(O(nlogn))
⇒変形すると,Sx/x >= kであり、各kに対してSx/xは単調減少なのでO(n)
"""
n = I()
a = LI()
cnt = list(Counter(a).values())
d = [0]*(n+1)
for i in cnt:
    d[i] += 1
d = list(accumulate(d))
m = d[-1]
S = [0]*(n+1)
for i in range(1,n+1):
    S[i] = S[i-1] + (m - d[i-1]) 
S2 = [0]*(n+1)
for i in range(1,n+1):
    S2[i] = S[i]//i
tmp = n
for k in range(1,n+1):
    while S2[tmp] < k:
        tmp -= 1
        if tmp <= 0:
            print(0)
            break
    else:
        print(tmp)


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

int main() {
    int n,k;cin>>n>>k;
    long a[n],ans;
    for(int i=0;i<n;++i){
        cin>>a[i];
    }
    sort(a,a+n,greater<long>());
    ans=a[0]-a[k-1];
    for(int i=1;i<=n-k;++i){
        ans=min(ans,a[i]-a[i+k-1]);
    }
    cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;
public class Main {

	static void solve() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String s = sc.next();
		int res = 0;
		for (int i = 0; i<n-2; i++) {
			if(s.charAt(i)=='A'&&s.charAt(i+1)=='B'&&s.charAt(i+2)=='C') 
				res++;
		}
		sc.close();
		System.out.println(res);
	}
	public static void main(String[] args) {
		solve();

	}

}


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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reps(i,s,n) for(int (i)=(s);(i)<(n);(i)++)
#define repr(i,n) for(int (i)=(n)-1;(i)>=0;(i)--)
#define forin(x,n) for(auto& (x) : n)
#define all(v) (v).begin(),(v).end()
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define mp make_pair
#define pb push_back
#define MOD 1000000007
#define inf 1000000000
#define llinf 1000000000000000
#define MAX 1000000


typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef pair<int,int> pint;
typedef pair<ll,ll> pll;
typedef vector<pint> vpint;
typedef pair<int,pint> P;


int main(){
    int n,m;
    cin>>n>>m;
    vint l(m),r(m);
    rep(i,m){
        cin>>l[i]>>r[i];
    }
    int minnum=0,maxnum=n+1;
    rep(i,m){
        minnum=max(minnum,l[i]);
        maxnum=min(maxnum,r[i]);
    }
    cout<<max(0,maxnum-minnum+1)<<endl;

}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<(int)n;i++)
using namespace std;
int main ()
{
	int n,m;
	while(cin>>n>>m&&n)
	{
		vector<pair<int,int > >a;
		pair<int,int> x;
		rep(i,n){
			cin>>x.second>>x.first;
			a.push_back(x);
		}
		sort(a.begin(),a.end());
		reverse(a.begin(),a.end());
		int ans=0;
		rep(i,n)
		{
			m-=a[i].second;
			a[i].second=0;
			if(m<0)
			{
				a[i].second-=m;
				break;
			}
		}
		rep(i,n)
		{
			ans+=a[i].first*a[i].second;
			
		}
		cout<<ans<<endl;
		
		
	}
	
}

Measured memory_bytes: 1328
import java.util.Scanner;

public class Main {

	static Scanner sc = new Scanner(System.in);
	static int[] DR = { 0, 1, 0, -1 };
	static int[] DC = { -1, 0, 1, 0 };

	public static void main(String[] args) throws Exception {
		while (true) {
			int N = sc.nextInt();
			if (N == 0) break;
			int l = 0;
			int r = 0;
			int b = 0;
			int t = 0;
			int[] row = new int[N];
			int[] col = new int[N];
			for (int i = 1; i < N; ++i) {
				int n = sc.nextInt();
				int d = sc.nextInt();
				row[i] = row[n] + DR[d];
				col[i] = col[n] + DC[d];
				l = Math.min(l, col[i]);
				r = Math.max(r, col[i]);
				t = Math.min(t, row[i]);
				b = Math.max(b, row[i]);
			}
			System.out.println((r - l + 1) + " " + (b - t + 1));
		}
	}

}

Measured memory_bytes: 34800
/*
 _____ _             _              _           _ 
|_   _| |__   ___   / \   _ __  ___| |__  _   _| |
  | | | '_ \ / _ \ / _ \ | '_ \/ __| '_ \| | | | |
  | | | | | |  __// ___ \| | | \__ \ | | | |_| | |
  |_| |_| |_|\___/_/   \_\_| |_|___/_| |_|\__,_|_|                                                

*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
#define ll          long long
#define pb          push_back
#define ppb         pop_back
#define	endl		'\n'
#define mii         map<ll,ll>
#define msi         map<string,ll>
#define mis         map<ll, string>
#define rep(i,a,b)    for(ll i=a;i<b;i++)
#define repr(i,a,b) for(ll i=b-1;i>=a;i--)
#define trav(a, x) 	for(auto& a : x)
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define vii         vector<pair<ll, ll>>
#define vs          vector<string>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll)x.size()
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define max(a,b)	(a>b?a:b)
#define min(a,b)	(a<b?a:b)

/*	For Debugging	*/
#define DEBUG 		cerr<<"\n>>>I'm Here<<<\n"<<endl;
#define display(x) trav(a,x) cout<<a<<" ";cout<<endl;
#define what_is(x)  cerr << #x << " is " << x << endl;

std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define TIME        cerr << "\nTime elapsed: " << setprecision(5) <<1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
#define DECIMAL(n)  cout << fixed ; cout << setprecision(n);
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace __gnu_pbds;
using namespace std;
#define PI 3.141592653589793
#define N  100005
long double dp[305][305][305];
ll n;
long double fun(ll a,ll b,ll c)
{
	if(a==0 && b==0 && c==0)
		return 0;
	if(dp[a][b][c]!=-1)
		return dp[a][b][c];
	long double ext=(n*1.0)/(a+b+c);
	long double ans=0.0;
	if(a!=0)
	{
		ans+=((a*1.0)/n)*fun(a-1,b,c);
	}
	if(b!=0)
	{
		ans+=((b*1.0)/n)*fun(a+1,b-1,c);
	}
	if(c!=0)
	{
		ans+=((c*1.0)/n)*fun(a,b+1,c-1);
	}
	ans=(ans+1)*ext;
	dp[a][b][c]=ans;
	return ans;
}

void solve()
{
	cin>>n;
	ll x;
	vi f(3,0);
	rep(i,0,n)
	{
		cin>>x;
		x--;
		f[x]++;
	}
	rep(i,0,305)
	{
		rep(j,0,305)
		{
			rep(k,0,305)
			dp[i][j][k]=-1.0;
		}
	}
	cout<<fun(f[0],f[1],f[2])<<endl;
	return;
}
int main()
{
	DECIMAL(10);
	FAST
	int TESTS=1;
//	cin>>TESTS;
	while(TESTS--)
	{
		solve();
	}
	TIME
	return 0;
}

Measured memory_bytes: 443776
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}



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

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

  
  rep(i,N){
    ll inp;cin >> inp;
    A.pb(inp);
  }
  rep(i,N){
    ll inp; cin >> inp;
    B.pb(inp);
  }

  ll suma = 0;
  ll sumb = 0;

  rep(i,N){
    suma += A[i];
    sumb += B[i];
  }
  
  ll times = sumb - suma;
  ll at = 0 ,bt = 0;
  
  rep(i,N){
    if(A[i] < B[i]){
      at += ((B[i]-A[i])/2 + ((B[i]-A[i])%2));
      if((B[i]-A[i]) %2) bt ++;
    }
    else
      bt += A[i]-B[i];
  }
  
  
  
  if( at >= bt && at <= times && bt <= times ) cout << "Yes" << endl;
  else cout <<"No" << endl;
  

  
  //cout << fixed << setprecision(16) << ans << endl;
  return 0;
}


Measured memory_bytes: 512
S = str(input())
T = str(input())

dict_S_to_T = {}
dict_T_to_S = {}

for s, t in zip(S, T):
    if s not in dict_S_to_T.keys():
        dict_S_to_T[s] = t
    else:
        if dict_S_to_T[s] != t:
            print('No')
            exit()
    if t not in dict_T_to_S.keys():
        dict_T_to_S[t] = s
    else:
        if dict_T_to_S[t] != s:
            print('No')
            exit()

print('Yes')


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

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  
  if ( A + B > C + D ) {
    cout << "Left" << endl;
  }
  
  else if ( A + B == C + D ) {
    cout << "Balanced" << endl;
  }
  
  else if ( A + B < C + D ){
    cout << "Right" << endl;
  }
}

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

using namespace std;

typedef long long LL;
#define N 300000

LL n,m,p,q[N],f[N],a[N],ans[N];

void ins(LL x,LL k){
	LL y=lower_bound(q+1,q+p+1,x)-q-1;
	if (y==0){
		ans[x]+=k;
		return;
	}
	f[y]+=k*(x/q[y]);
	ins(x%q[y],k);
}

int main(){
	scanf("%lld%lld",&n,&m);
	q[p=1]=n;
	for (LL i=1;i<=m;++i){
		LL x; scanf("%lld",&x);
		for (;p&&x<=q[p];--p);
		q[++p]=x;
	}
	f[p]=1;
	for (LL i=p;i;--i){
		ins(q[i],f[i]);
	}
	for (LL i=n;i;--i) ans[i]+=ans[i+1];
	for (LL i=1;i<=n;++i) printf("%lld\n",ans[i]);
	
	return 0;
}
			

Measured memory_bytes: 6528
#include<bits/stdc++.h>
using namespace std;
int main(){
  string S;
  cin >>S;
  if(S.at(5)=='0' && (S.at(6)=='1'||S.at(6)=='2'||S.at(6)=='3'||S.at(6)=='4')){
  cout<<"Heisei"<<endl;
  }
  else{cout<<"TBD"<<endl;}
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <functional>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long
struct mint {
    int x;
    mint(int 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(int t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    mint inv() const {
        return pow(mod - 2);
    }
    mint& operator/=(const mint a) {
        return *this *= a.inv();
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res /= a;
    }
};
mint dp[110][200020];
int N, K;
int a[110];

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    cin >> N >> K;
    
    rep(i, N) cin >> a[i];
    dp[0][K + 1] = 1;
    rep(i, 100010) dp[0][K + i + 1] = 1;
    rep(i, N) {
        rep(j, K + 1) {
            dp[i + 1][j + 1] = dp[i][j + a[i] + 1] - dp[i][j];
        }
        rep(j, 200010) dp[i + 1][j + 1] += dp[i + 1][j];
    }

    cout << dp[N][1].x << endl;

    return 0;
}


Measured memory_bytes: 175508
import java.util.*;
 
public class Main{
	public static void main(String[] args){
		Scanner scanner = new Scanner(System.in);
		int x1 = scanner.nextInt();
        int y1 = scanner.nextInt();
        int x2 = scanner.nextInt();
        int y2 = scanner.nextInt();
        
        int xx = x2 - x1;
        int yy = y2 - y1;
        
        int x3 = x2 - yy;
        int x4 = x1 - yy;
        int y3 = y2 + xx;
        int y4 = y1 + xx;
        
        System.out.println(x3 + " " + y3 + " " + x4 + " " + y4);
	}
}

Measured memory_bytes: 21716
# D - String Formation
s = input()
q = int(input())

f = b = ''
odd = 0
for i in range(q):
    t,*fc = input().split()
    if t=='1': odd ^= 1 #t1
    else: #t2
        if odd: #odd:reverse
            if fc[0]=='1': b += fc[1] #f1
            else: f += fc[1] #f2
        else: #even
            if fc[0]=='1': f += fc[1] #f1
            else: b += fc[1] #f2

if odd: print(b[::-1] + s[::-1] + f)
else: print(f[::-1] + s + b)

Measured memory_bytes: 4468
#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
long long s,a1,a2,a3,b1,b2,b3;
signed main(){
	cin >> s;
	a1 = b1 = 0;
	a2 = 1e9;
	b2 = 1;
	b3 = (s-1)/a2 + 1;
	a3 = b3*a2 - s;
	cout << a1 <<  " " << b1 << " " << a2 << " " << b2  << " " << a3 << " "  << b3;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define mod 1000000007
ll x = 0,y = 0,z;
int main(){
	int n; cin >> n >> z;
	rep(i,n){
		ll a; cin >> a;
		x = __gcd(x,a);
		y = max(y,a);
	}
	if(y>=z && z%x == 0) puts("POSSIBLE");
	else puts("IMPOSSIBLE");
}

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


main() {
  int N, M;
  int T[MAX_N], P[MAX_M], X[MAX_M];
  cin >> N;
  rep(i, N) cin >> T[i];
  cin >> M;
  rep(i, M) {
    cin >> P[i] >> X[i];
    P[i]--;
  }
  rep(i, M) {
    int sum {};
    rep(j, N) {
      if (j == P[i]) {
        sum += X[i];
      } else {
        sum += T[j];
      }
    }
    cout << sum << endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long  N,A,B;
  cin >> N >> A >> B;
  long long count = 0;
  for(long long i = (N-2)*A; i <= (N-2)*B; i++){
    count++;
  }

cout << count <<endl;
}

Measured memory_bytes: 256
import java.util.*;

class Main{
    static String mark;
    static int[][] crys;
    static int n;
    static int[] findMark;
    static double[] distA;
    static double[][] distY;

    public static void main(String[] args){
	Scanner sc = new Scanner(System.in);

	n = sc.nextInt();
	int hx = sc.nextInt();
	int hy = sc.nextInt();
	int dx = sc.nextInt();
	int dy = sc.nextInt();

	while(n!=0){
	    crys = new int[n][2];
	    distA = new double[n];
	    for(int i=0; i<n; i++){
		crys[i][0] = sc.nextInt();
		crys[i][1] = sc.nextInt();
		distA[i] = getDistance(dx,dy,i);
	    }

	    distY = new double[n+1][n];
	    for(int i=1; i<=n; i++){
		distY[0][i-1] = getDistance(hx,hy,i-1);
		for(int j=0; j<n; j++){
		    distY[i][j] = getDistance(crys[i-1][0],crys[i-1][1],j);
		}
	    }

	    findMark = new int[n];
	    mark = "NO";
	    solve(-1,0,0.0);
	    System.out.println(mark);

	    n = sc.nextInt();
	    hx = sc.nextInt();
	    hy = sc.nextInt();
	    dx = sc.nextInt();
	    dy = sc.nextInt();
	}
    }

    public static void solve(int pos, int findNum, double radius){
	if(mark.equals("YES")){return;}
	if(findNum==n){mark = "YES"; return;}

	for(int i=0; i<findMark.length; i++){
	    if(findMark[i]==0 && distY[pos+1][i] >= distA[i]-radius){return;}
	}

	for(int i=0; i<findMark.length; i++){
	    if(findMark[i]==0){
		if(distY[pos+1][i]<distA[i]-radius){
		    findMark[i] = 1;	
		    solve(i,findNum+1,distY[pos+1][i]+radius);
		    if(mark=="YES")break;
		    findMark[i] = 0;
		}else return;
	    }
	}
    }

    public static double getDistance(int x, int y, int i){
	return  Math.sqrt((x-crys[i][0])*(x-crys[i][0])+(y-crys[i][1])*(y-crys[i][1]));
    }
}

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

int c[3][3];

bool ok() {
  int b1 = c[0][0], b2 = c[0][1], b3 = c[0][2];
  int a2 = c[1][0] - c[0][0];
  if(a2 + b2 != c[1][1] || a2 + b3 != c[1][2]) return false;
  int a3 = c[2][0] - c[0][0];
  if(a3 + b2 != c[2][1] || a3 + b3 != c[2][2]) return false;
  return true;
}

int main () {
  rep(i,3)rep(j,3) {
    cin >> c[i][j];
  }

  cout << (ok() ? "Yes" : "No") << endl;
  return 0;
}


Measured memory_bytes: 256
//組の練習？

#include <bits/stdc++.h>
#define rep(i,N) for (int i = 0; i < (N); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main(void){
  int x, y;
  cin >> x >> y;

  vector <int> vec = {0, 1, 3, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 2};
  if (vec.at(x) == vec.at(y)) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 3600
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]

# 
# a, b
# s = input()

N = int(input())
H = [0] + list(map(int, input().split()))

ans = 0
cnt = 0
pre = H[1]
for i in range(2, N+1):
    now = H[i]
    if now > pre:
        ans = max(ans, cnt)
        cnt = 0
        pre = now
    else:
        pre = now
        cnt += 1

ans = max(ans, cnt)
print(ans)



Measured memory_bytes: 14252
#include <stdio.h>
typedef long long ll;
ll a, b, c, aa, bb, cc;
int cnt;
bool Pass(){
	if(a&1) return 0;
	if(b&1) return 0;
	if(c&1) return 0;
	return 1;
}
int main(){
	scanf("%lld%lld%lld", &a, &b, &c);
	while(Pass()){
		aa = a >> 1;
		bb = b >> 1;
		cc = c >> 1;
		a = bb + cc;
		b = aa + cc;
		c = aa + bb;
	//	printf("a = %lld  b = %lld  c = %lld", a, b, c);
		cnt++; if(cnt > 100000000) {
			puts("-1"); return 0;
		}
	}
	printf("%d\n", cnt);
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
using namespace std;
int main(){
int a,b;
cin>>a>>b;
if (a*b>=a-b && a*b>=a+b ){
    cout<<a*b<<endl;
}
else if (a-b>=a*b && a-b>=a+b){
    cout<<a-b<<endl;
}
else if (a+b>=a*b && a+b>=a-b){
    cout<<a+b<<endl;
}
    return 0;
}



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

struct Closed_Section {
    bool valid;
    int64_t begin;
    int64_t end;
    Closed_Section(bool _valid, int64_t _begin, int64_t _end) {
        valid = _valid; begin = _begin; end = _end;
    }
    Closed_Section() {
        valid = false, begin = 0; end = -1; //配列を定義するためにデフォルトコンストラクタが必要。
    }
    int64_t size() { return valid ? end - begin + 1 : 0; }
    Closed_Section operator*(const Closed_Section &r) const {
        if (!valid) { return Closed_Section(valid, begin, end); }
        if (!r.valid) { return r; }
        if (end < r.begin) { return Closed_Section(false, 0, -1); }
        if (r.end < begin) { return Closed_Section(false, 0, -1); }
        return Closed_Section(true, std::max(begin, r.begin), std::min(end, r.end));
    }
    void dump() { std::cout << "valid:" << valid << " begin:" << begin << " end:" << end << std::endl; }
};

// end of template

int64_t N;

const int64_t MAX_N = 1e5 + 10;
const int64_t MOD = 1e9 + 7;

int64_t T[MAX_N] = {};
int64_t A[MAX_N] = {};
Closed_Section Ts[MAX_N];
Closed_Section As[MAX_N];

int main(int argc, char **argv) {
    std::cin >> N;
    for (int i = 1; i <= N; i++) {
        std::cin >> T[i];
    }
    for (int i = 1; i <= N; i++) {
        std::cin >> A[i];
    }
    for (int i = 1; i <= N; i++) {
        if (T[i-1] < T[i]) {
            Ts[i] = Closed_Section(true, T[i], T[i]);
        } else {
            Ts[i] = Closed_Section(true, 1, T[i]);
        }
    }
    for (int i = N; 1 <= i; i--) {
        if (A[i+1] < A[i]) {
            As[i] = Closed_Section(true, A[i], A[i]);
        } else {
            As[i] = Closed_Section(true, 1, A[i]);
        }
    }

    int64_t ret = 1;
    for (int i = 1; i <= N; i++) {
        ret *= (Ts[i]*As[i]).size();
        ret %= MOD;
    }
    std::cout << ret << std::endl;
}

Measured memory_bytes: 6528