akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <iostream>

using namespace std;

int vis[10];
int gs[10] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};

int main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		for (int i=0; i<10; ++i) vis[i] = 0;
		for (int i=9; i>=0; --i) {
			if (n >= gs[i]) {
				vis[i] = 1;
				n -= gs[i];
			}
			if (n <= 0) break;
		}
		int cs = 0;
		for (int i=0; i<10; ++i) {
			if (vis[i]) printf (cs++ ? " %d" : "%d", gs[i]);
		}
		printf ("\n");
	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)
#define VL vector<ll>

int main(){
    ll N, M, X;
    cin >> N >> M >> X;
    VL a(M);
    rep(i,0,M)cin>>a[i];
    
    ll ans=0;
    ll cnta=0, cntb=0;
    for(ll i=X; i<N; i++){
        rep(j,0,M){
            if(a[j]==i)cnta++;
        }
    }
    for(ll i=X; i>=0; i--){
        rep(j,0,M){
            if(a[j]==i)cntb++;
        }
    }
    ans=min(cnta,cntb);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,i,j,x,y,w,hd,s,xlh,g[100010],v[21][21],f[100010][21],sy,mx,ans,pr,sz;
int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&w);
		xlh+=w;
		x--;y--;
		v[x][y]=v[y][x]=w;
	}
	mx=1<<n;
	for(s=1;s<mx;s++){
		for(i=0;i<n;i++)if(s&(1<<i)){
			pr=s^(1<<i);
			sz=0;
			for(j=0;j<n;j++)if((s&(1<<j))&&v[i][j])sz+=v[i][j];
			g[s]=g[pr]+sz;break;
		}
		//printf("%d %d\n",s,g[s]);
	}
	memset(f,172,sizeof(f));
	f[1][0]=0;
	for(s=1;s<mx;s++)
	 for(hd=0;hd<n;hd++)if(f[s][hd]>=0){
	 	for(i=0;i<n;i++)if(!(s&(1<<i))&&v[hd][i]){
	 		f[s|(1<<i)][i]=max(f[s|(1<<i)][i],f[s][hd]+v[hd][i]);
		 }
		sy=(mx-1)^s;
		for(i=sy;i;i=(i-1)&sy)f[s|i][hd]=max(f[s|i][hd],f[s][hd]+g[i|(1<<hd)]);
	 }
	 for(i=1;i<mx;i++)ans=max(ans,f[i][n-1]);
	 printf("%d",xlh-ans);
}

Measured memory_bytes: 8576
#include <bits/stdc++.h>
using namespace std;
#define mod 998244353

long long dp[3010][3010];

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, s; cin >> n >> s;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= s; j++) {
            long long add = 0;
            if (j >= a[i]) add = dp[i][j-a[i]];
            if (j == s) add *=  n-i;
            if (j == a[i]) add *= i+1;
            dp[i+1][j] = (dp[i+1][j] + dp[i][j] + add) % mod;
        }
    }
    cout << dp[n][s] << "\n";
    return 0;
}

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

using namespace std;

typedef long long ll;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    vector<ll> a(n+1);
    for(int i = 0; i < n+1; i++) {
        if (s[i]=='<'){
            a[i+1] = max(a[i+1], a[i]+1);
        }
    }

    for(int i = n; i >=0; i--) {
        if (s[i]=='>'){
            a[i] = max(a[i], a[i+1]+1);
        }
    }
    ll sum=0;
    for(int i = 0; i < n+1; i++) {
        sum += a[i];
    }
    cout << sum << endl;

    return 0;
}

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


int main() {
	set<int>s;
	int a;
	for(int i=0;i<4;i++){
		cin>>a;
		if(a==1||a==9||a==7||a==4){
			s.insert(a);
		}
	}
	if(s.size()==4){
		cout<<"YES"<<endl;
	}else{
		cout<<"NO"<<endl;
	}
		return 0;
}



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

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    double pi[n];
    double ans = 0.0, ansm;
    for (int i = 0; i < n; i++) {
        scanf("%lf", &pi[i]);
    }
    for (int i = 0; i < k; i++) {
        ans += (pi[i] + 1.0) / 2.0;
    }
    ansm = ans;
    if (n > 1) {
        for (int i = 0; i + k < n; i++) {
            ans += -((pi[i] + 1.0) / 2.0) + ((pi[k+i] + 1.0) / 2.0);
            ansm = max(ansm, ans);
        }
    }
    printf("%13.12lf\n", ansm);
}

Measured memory_bytes: 5356
nums = sorted(list(map(int, input().split())))
ans = 0
while nums[0] != nums[-1]:
  if nums[-1] - nums[0] >= 2:
    nums[0] += 2
  else:
    nums[0] += 1
    nums[1] += 1
  nums = sorted(nums)
  ans += 1
print(ans)

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

using namespace std;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
    double ans = 0;
    int n;
    float x;
    cin >> n;
    for(int i=0; i < n; i++)
    {
        cin >> x;
        ans += (1.0/x);
    }
    cout << pow(ans, -1);
	return 0;
}


Measured memory_bytes: 256
import static java.lang.System.*;

import java.util.Arrays;
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner scan = null;
		try{
			scan = new Scanner(System.in);
			int data[] = new int[3];
			for(int i= 0; i < 3;i++){
				data[i] = scan.nextInt();
			}
			Arrays.sort(data);
			out.printf("%d %d %d\n", data[0],data[1],data[2]);
		}finally{
			if(scan !=null)scan.close();
		}

	}
}

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

using namespace std;

#define MAX 45
#define PI acos(-1)
#define INF (1<<29)
typedef pair<double, double> P;

int N, M;
double memo[MAX][MAX][MAX];
vector<double> x, y;

double area(int a, int b, int c)
{
    vector<P> p(3);
    p[0] = P(x[a], y[a]);
    p[1] = P(x[b], y[b]);
    p[2] = P(x[c], y[c]);   
    
    double res = 0;
    for (int i = 1; i < 4; i++) {
	res += (p[i%3].first - p[i-1].first) * (p[i%3].second + p[i-1].second);
    }
    res /= 2.0;
    return abs(res);
}

double get_max_area(int L, int R, int m)
{
    if (m == M) {
        return 0;
    }    
    double &res = memo[L][R][m];
    if (res != -1) {
        return res;
    }
    for (int i = R+1; i < N; i++) {
        res = max(res, get_max_area(L, i, m+1) + area(L, R, i));
    }
    return res;
}

int main()
{
    double p;
    while (cin >> N >> M, N) {
        x.clear(); y.clear();
        x.resize(N); y.resize(N);
        for (int i = 0; i < N; i++) {
            cin >> p;
            p *= (2.0 * PI);
            x[i] = cos(p); y[i] = sin(p);
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) {
                    memo[i][j][k] = -1;
                }
            }
        }

        double mx = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i+1; j < N; j++) {
                for (int k = j+1; k < N; k++) {
                    mx = max(mx, get_max_area(i, k, 3) + area(i, j, k));
                }
            }
        }
        printf("%.6f\n", mx);
    }
    return 0;
}

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

int n;
int a[210];

int main(){
  cin >> n;
  for(int i=0;i<n;i++) cin >> a[i];
  
  int res = 0;
  
  while(true){
    bool exist_odd = false;
    for (int i=0;i<n;i++){
      if(a[i]%2 != 0) exist_odd = true;
    }
    
    if(exist_odd) break;
         
    for(int i=0;i<n;i++){
      a[i] /= 2;
    }
    res++;
  }
         
  cout << res << endl;
}


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

int main(){
  int64_t N = 0;
  int64_t K = 0;
  std::cin >> N >> K;
  
  int64_t answer = N % K;
  if(std::abs(answer-K) < answer){
    answer = std::abs(answer-K);
  }
  
  
  std::cout << answer << std::endl;

  
  return 0;
}

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

int main()
{
   int a,b,i,j,ans=0;
   cin>>a>>b;
   for(i=a;i<=b;i++)
   {
       if(i%10==(i/10000)%10&&(i/10)%10==(i/1000)%10) ans++;
   }cout<<ans<<endl;
    return 0;
}


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

#define ll long long
#define ull unsigned long long
#define openfiles ifstream cin("input10.txt"); ofstream cout("output10.txt");

using namespace std;

ll dp[200][200000];
ll w[200], c[200];
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> w[i] >> c[i];
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j < w[i]; j++)
        {
            dp[i][j] = dp[i-1][j];
        }
        for(int j = w[i]; j <= m; j++)
        {
            dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + c[i]);
        }
    }
    cout << dp[n][m];
}


Measured memory_bytes: 156416
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

int main()
{
    long long k;
    cin >> k;

    int n = 50;
    vector<long long> a(n, 0);
    for(int i=0; i<n; ++i)
        a[i] = k / n + (n - 2);
    ++ a[n-1];
    for(int i=0; i<k%n; ++i){
        a[0] += n;
        for(int j=1; j<n; ++j)
            -- a[j];
        rotate(a.begin(), a.begin()+1, a.end());
    }

    cout << n << endl;
    cout << a[0];
    for(int i=1; i<n; ++i)
        cout << ' ' << a[i];
    cout << endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int a=Integer.parseInt(sc.next());
int b=Integer.parseInt(sc.next());
if(a>b)System.out.println("a > b");
if(a==b)System.out.println("a == b");
if(a<b)System.out.println("a < b");
}
}


Measured memory_bytes: 26028
#include<stdio.h>

int main(){
   int A,B,C,D;
   int x;
   int y;
   scanf("%d %d %d %d",&A,&B,&C,&D);
   x=(C+B-1)/B;
   y=(A+D-1)/D;
   if(x<=y){
      printf("Yes");
   }
   if(x>y){
      printf("No");
   }
   return 0;
}


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

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


    if( a == 'H' ){
        cout << b << endl;
    } else {
        if( b == 'H' ) cout << 'D' << endl;
        else cout << 'H' << endl;
    }


    return 0;
}


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

public class Hello
{
    public static void Main()
    {
        var hs = new HashSet<int>();
        string[] line = Console.ReadLine().Trim().Split(' ');
        var a = int.Parse(line[0]);
        var b = int.Parse(line[1]);
        var c = int.Parse(line[2]);
        var i = 0;
        while (true)
        {
            var t = b * (i++) + c;
            if (t % a == 0) { Console.WriteLine("YES"); break; }
            else if (!hs.Add(t % a)) { Console.WriteLine("NO"); break; }
        }
    }
}

Measured memory_bytes: 13268
#include<stdio.h>
#include<stdlib.h>
#define MAX 255

int Parent(int i){
  return i/2;
}

int Left(int i){
  return 2*i;
}

int Right(int i){
  return (2*i)+1;
}

main(){
  int heap[MAX],i,size,left,right;

  scanf("%d",&size);
  for(i=1 ; i<=size ; i++){
    scanf("%d",&heap[i]);
  }

  for(i=1 ; i<=size ; i++){
    printf("node %d: key = %d, ",i,heap[i]);
    if(i>=2) printf("parent key = %d, ",heap[Parent(i)]);

    left=Left(i);
    right=Right(i);
    if(left<=size) printf("left key = %d, ",heap[left]);
    if(right<=size) printf("right key = %d, ",heap[right]);

    printf("\n");
  }
  return 0;
}

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

int D;

int main(void) {
    cin >> D;
    switch (D) {
        case 25:
        cout << "Christmas" << endl;
        break;
        case 24:
        cout << "Christmas Eve" << endl;
        break;
        case 23:
        cout << "Christmas Eve Eve" << endl;
        break;
        default:
        cout << "Christmas Eve Eve Eve" << endl;
        break;
    }
    return 0;
}


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

using namespace std;

//int dirs[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
//int dirs[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};


int main()
{
    ios::sync_with_stdio(false);
    //freopen("inp.in","r",stdin);
    //freopen("outp.out","w",stdout);
    int m1, d1, m2, d2;
    cin >> m1 >> d1;
    cin >> m2 >> d2;
    if(m2==m1+1)
    {
        cout << 1 << endl;
    }
    else
    {
        cout << 0 << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<cmath>
#include<iomanip>
#include<functional>
using namespace std;

int INF = 1e9 + 7;

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

int main() {
	ll x;
	cin >> x;

	ll ans = (x / 11) * 2;
	if (x % 11 == 0);
	else if (x % 11 <= 6) ans += 1;
	else ans += 2;
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <algorithm>
#include <array>
#include <complex>
#include <utility>
#include <map>

//enum { OCEAN = 0, LAND = 1 };

int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };
void search(std::vector<std::string> &grid, int r, int c) {
    if (!(0 <= r && r < 12 && 0 <= c && c < 12))
        return;

    if (grid[r][c] == '0') {
        return;
    }
    grid[r][c] = '0';
    for (int i = 0; i<4; i++) {
        int newr = r + dx[i], newc = c + dy[i];
        if (!(0 <= newr && newr < 12 && 0 <= newc && newc < 12))
            continue;

        if (grid[newr][newc] == '0') {
            continue;
        }

        search(grid, newr, newc);
    }
}
int count_land(std::vector<std::string> &grid) {
    int res = 0;
    for (int i = 0; i<12; i++) {
        for (int j = 0; j<12; j++) {
            if (grid[i][j] == '1') {
                ++res;
                search(grid, i, j);
            }
        }
    }
    return res;
}
int main(void) {
    std::vector<std::string> grid(12);
    int input = 0;
    
    while (std::cin>>grid[0],std::cin){
        for (int i = 1; i < 12; i++) {
            std::cin >> grid[i];
        }
    std::cout << count_land(grid) << std::endl;
    
    }
    
    return 0;
}


Measured memory_bytes: 3060
N,K = map( int, input().split())
#a = [0 for in range(K)]
l = [0]
if N>=K:
  l[0] = N-K+1
now = K-1
cnt = 2
while now>=1:
  nx = now // 2
  if N > now:
    a = now-nx
  elif now >= N > nx:
    a = N - nx
  else:
    a = 0
  l.append(a)
  now = nx
  cnt *= 2
#print( N, win, win/N )
#print(l)
ll = len(l)
pp = 1
for i in range(ll):
  l[ll-i-1] *= pp
  pp *= 2
#print(l)
suml = sum(l)
print( suml/(pp/2)/N)


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

#define ll long long
#define fw(p) for(int w=0;w<(p);w++)
#define fx(p) for(int x=0;x<(p);x++)
#define fy(p) for(int y=0;y<(p);y++)
#define fz(p) for(int z=0;z<(p);z++)
#define fyg(p,g) for(int y=(g);y<(p);y++)
#define fzg(p,g) for(int z=(g);z<(p);z++)
#define ce(d) cout<<d<<endl;
#define vecp(p) int aa;cin>>aa;(p).push_back(aa);
#define vecpl(p) long long aa;cin>>aa;(p).push_back(aa);
#define vecps(p) string aa;cin>>aa;(p).push_back(aa);
#define vecp2(p) cin>>aa;(p).push_back(aa);
#define vecpl2(p) long long a	b;cin>>ab;(p).push_back(ab);
#define vecps2(p) string ab;cin>>ab;(p).push_back(ab);
#define sorts(c) sort((c).begin(),(c).end());
#define reverses(c) reverse((c).begin(),(c).end());
#define vec(b) vector<int> (b);
#define vecl(b) vector<long long> (b);
#define vecs(b) vector<string> (b);
#define pb(b,a) (b).push_back((a));
#define doublece(a,b) cout<<(a)<<' '<<(b)<<endl;
#define pairs(s) vector<pair<int,int>> (s);
#define pairsp(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define MOD 1000000007
#define cey ce("Yes")
#define cen ce("No")
#define ceY ce("YES")
#define ceN ce("NO")

int main()
{
	double L;
	cin >> L;
	L /= 3;
	cout << fixed << setprecision(10) << L*L*L << endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long N, a, b;
    cin >> N >> a >> b;
    if((b - a) % 2 == 1){
        cout << min(a + (b - a - 1) / 2, N - b + 1 + (b - a - 1) / 2);
    }
    else cout << (b - a) / 2 << endl;
}

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

int main() {
	string S;
	cin >> S;
	int cnt = 0;
	for (int i = 0; i < S.length(); i++) {
		if (S[i] == 'x')cnt++;
	}
	if (cnt < 8)cout << "YES" << endl;
	else cout << "NO" << endl;

	return 0;
}

Measured memory_bytes: 256
//abc147_b.cpp
//Sun Dec  8 21:01:37 2019

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

int main(){
	string s;
	cin >> s;

	int max = s.length()/2;

	int ans = 0;
	for (int i=0;i<max;i++){
		if (s[i]!=s[s.length()-1-i]){
			ans++;
		}
	}

	cout << ans << endl;
//	printf("%.4f\n",ans);
}

Measured memory_bytes: 256
# AGC040
# A
# ><
import itertools

s_list = input()

n = len(s_list) + 1
a_list = [0]*n
tmp_list = [0]*n

gr = itertools.groupby(s_list)

idx = 0
_tmp = 0
for key, group in gr:
    _num = sum(1 for _ in group)
    if key == "<":
        a_list[idx:idx+_num+1] = list(range(_num+1))
    else:
        a_list[idx] = max(_tmp,_num)
        a_list[idx+1:idx+_num] = list(range(_num-1,0,-1))
        tmp_list[idx] = _num
    idx += _num
    _tmp = _num

# print(a_list)
# print(tmp_list)
print(sum(a_list))    

Measured memory_bytes: 35720
A1, A2, A3 = map(int, input().split())
a = []
a.append(abs(A2 - A1) + abs(A3 - A2))
a.append(abs(A2 - A3) + abs(A1 - A2))
a.append(abs(A1 - A2) + abs(A3 - A1))
a.append(abs(A1 - A3) + abs(A2 - A1))
a.append(abs(A3 - A1) + abs(A2 - A3))
a.append(abs(A3 - A2) + abs(A1 - A3))
print(min(a))

Measured memory_bytes: 9180
#include "bits/stdc++.h"
#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 pii pair<int,int>
#define tii tuple<int,int,int>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
ll int MOD=1e9+7;
#define INF 2*1e9
#define N 310000
 
using namespace std;
string alphabet("abcdefghijklmnopqrstuvwxyz");

main(){
    int n;
    cin>>n;
    vector<pii> v;
    rep(i,n){
        int a;cin>>a;
        v.pb({a,0});
    }
    rep(i,n){
        int a;cin>>a;
        v.pb({a,1});
    }
    sort(v.begin(),v.end());
    int t=0,s;
    ll ans=1;
    rep(i,2*n){
        s=v[i].second;t=1;
        while(t){
            i++;
            if(v[i].second==s){
                t++;
            }
            else{
                ans=ans*t%MOD;
                t--;
            }
        }
    }
    cout<<ans;
}



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

using namespace std;

int main() {
  string s, t;
  cin >> s >> t;
  int ans = 0;
  for (int i = 0; i < s.size(); i++)
    ans += !(s[i] ^ t[i]);
  cout << s.size() - ans;
  return 0;
}


Measured memory_bytes: 3896
import math
n,k=map(int,input().split())
size=math.floor(n/k)
cnt=size*(size-1)*(size-2)+size*(size-1)*3+size
if k%2==0:
    size=math.floor(2*n/k)-size
    cnt+=size*(size-1)*(size-2)+size*(size-1)*3+size

print(cnt)

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

const int mod = 1e9 + 7;

class BinomialCoefficients{
  int max;
  int mod;
  long long *factorial;
  long long *factorial_inverse;
  long long *inverse;

public:
  int get(int n, int k){
    if(n < 0 || k < 0 || k > n) return 0;
    else return factorial[n] * (factorial_inverse[k] * factorial_inverse[n - k] % mod) % mod;
  }

  BinomialCoefficients(int max = 1000000, int mod = 1000000007) : max(max), mod(mod){
    factorial = new long long[max + 1];
    factorial_inverse = new long long[max + 1];
    inverse = new long long[max + 1];

    factorial[0] = factorial[1] = 1;
    factorial_inverse[0] = factorial_inverse[1] = 1;
    inverse[1] = 1;

    for(int k = 2; k <= max; k++){
      factorial[k] = factorial[k - 1] * k % mod;
      inverse[k] = mod - inverse[mod % k] * (mod / k) % mod;
      factorial_inverse[k] = factorial_inverse[k - 1] * inverse[k] % mod;
    }
  }

  ~BinomialCoefficients(){
    delete [] factorial;
    delete [] factorial_inverse;
    delete [] inverse;
  }
};

using namespace std;

int main(){
  int S;
  cin >> S;
  
  BinomialCoefficients binom;
  
  long long ans = 0;
  for(int i = 1; i <= S; i++){
    long long sum = S - i * 3;
    ans += binom.get(sum + i - 1, i - 1);
    ans %= mod;
  }
  
  cout << (ans + mod) % mod << endl;
  
  return 0;
}

Measured memory_bytes: 26760
#include <iostream>
#include <string>
using namespace std;
int main() {
	int h,w,a,b;
	for(;;){
		cin>>h>>w;
		if(h==0 && w==0){
			return 0;
		}
		a=h;
		b=w;
		for(h=a;h>0;h=h-1){
			for(w=b;w>0;w=w-1){
				cout<<"#";
			}
			cout<<endl;	
		}
		cout<<endl;
	}
}



Measured memory_bytes: 3116
import numpy as np

N, M = map(int, input().split())
A = []
for i in range(N):
    S = input()
    A.append([S[i] for i in range(len(S))])
A = np.array(A)
B = []
for i in range(M):
    S = input()
    B.append([S[i] for i in range(len(S))])
for i_raw in range(N - M + 1):
    for j_col in range(N - M + 1):
        if (A[i_raw : i_raw + M, j_col : j_col + M] == B).all():
            print("Yes")
            exit()
print("No")


Measured memory_bytes: 12488
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Program
{
    static void Main(string[] args)
    {
        var dance = Console.ReadLine();

        var ret = Check(dance) ? "Yes" : "No";


        Console.WriteLine(ret);
    }

    public static bool Check(string dance)
    {
        for (int i = 0; i < dance.Length; i++)
        {
            if (i == 0)
            {
                if (dance[i].ToString() == "L")
                {
                    return false;
                }
            }
            else
            {
                if (i % 2 == 1)
                {
                    if (dance[i].ToString() == "R")
                    {
                        return false;
                    }
                }
                else
                {
                    if (dance[i].ToString() == "L")
                    {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}


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

// @author: pashka

int n, m, q;
vector<int> a, b, c, d;
vector<int> p;
int res = 0;

void bt() {
    if (p.size() == n) {
        int score = 0;
        for (int i = 0; i < q; i++) {
            if (p[b[i]] - p[a[i]] == c[i]) {
                score += d[i];
            }
        }
        res = max(res, score);
        return;
    }
    for (int x = 1; x <= m; x++) {
        if (!p.empty() && x < p.back()) continue;
        p.push_back(x);
        bt();
        p.pop_back();
    }
}

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

    cin >> n >> m >> q;
    a.resize(q);
    b.resize(q);
    c.resize(q);
    d.resize(q);
    for (int i = 0; i < q; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--; b[i]--;
    }
    bt();
    cout << res << "\n";

    return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
#define INCANT cin.tie(0), cout.tie(0), ios::sync_with_stdio(0), cout << fixed << setprecision(20);
#define int long long
const int INF = 1e18, MOD = 1e9 + 7;
int n, m, q;
int a[55], b[55], c[55], d[55];

int score(vector<int> A) {
    int ret = 0;
    for (int i = 0; i < q; i++) {
        if (A[b[i]] - A[a[i]] == c[i]) ret += d[i];
    }
    return ret;
}

int dfs(vector<int> A, int last) {
    if (A.size() >= n) {
        return score(A);
    }
    int mx = -INF;
    for (int i = last; i <= m; i++) {
        A.push_back(i);
        mx = max(mx, dfs(A, i));
        A.pop_back();
    }
    return mx;
}

signed main() {
    cin>>n>>m>>q;
    
    for (int i = 0; i < q; i++) {
        cin>>a[i]>>b[i]>>c[i]>>d[i];
        a[i]--;
        b[i]--;
    }
    vector<int> A;
    cout<<dfs(A, 1)<<endl;
}

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

#define MOD 1000000007
#define int long long
//#define PI 3.14159265358979

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

using namespace std;

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

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

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

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

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

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

struct initializer {
	initializer() {
		cout << fixed << setprecision(11);
	}
};
initializer _____;
int abs(int a, int b) {
	int ret = a - b;
	if (ret >= 0)
		return ret;
	else
		return -ret;
}

int N, M, K, T, Q;
signed main() {
	int N, Z, W;
	cin >> N >> Z >> W;
	vector< int > A(N);
	rep(i, N) cin >> A[i];
	int ans = abs(A[N - 1] - W);
	if (N > 1)
		chmax(ans, abs(A[N - 1], A[N - 2]));
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#define ll long long
using namespace std;

ll getNumberOfWays(vector<int> limits,int n,int k) {
	ll out=0;
	vector<ll> dp(k+1,0);
	dp[0]=1;
	for(int children=1;children<=n;children++) {
		vector<ll> stepSum(k+2,0);
		for(int iter=k;iter>=0;iter--) {
			if(iter+1<=min(iter+limits[children-1],k)) {
				stepSum[iter+1]+=dp[iter];
				stepSum[iter+1]%=(ll)1e9+7;
				stepSum[min(iter+limits[children-1],k)+1]-=dp[iter];
				stepSum[min(iter+limits[children-1],k)+1]%=(ll)1e9+7;
			}
		}
		ll inc=0;
		for(int i=0;i<k+1;i++) {
			inc+=stepSum[i];
			dp[i]+=inc;
          	dp[i]%=(ll)(1e9+7);
		}
	}
	/*
	for(ll val:dp) {
		cout<<val<<" ";
	}cout<<endl;
	*/
	out=dp[k];
	return out%(ll)(1e9+7);
}

int main() {
	int n=0,k=0;
	cin>>n>>k;
	vector<int> limits(n,0);
	for(int i=0;i<n;i++)cin>>limits[i];
	cout<<getNumberOfWays(limits,n,k)<<endl;
	return 0;
}


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

using namespace std;
using ll=long long;

int n,m;
vector<vector<int>>adj;
vector<int>in_dig,s_path;
queue<int>Q;

void bfs(){
    while(!Q.empty()){
        auto node=Q.front();Q.pop();
        for(auto child:adj[node]){
            s_path[child]=max(s_path[child], s_path[node]+1);
            in_dig[child]--;
            if(!in_dig[child]){
                Q.push(child);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    cin>>n>>m;
    adj.resize(n+1);
    in_dig.resize(n+1);
    s_path.resize(n+1);
    // vis.resize(n+1);
    for(int i=0; i<m; i++){
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        in_dig[b]++;
    }

    for(int node=1; node<=n; node++){
        if(in_dig[node]==0)Q.push(node);
    }

    bfs();

    int ans=0;
    for(int node=1; node<=n; node++)ans=max(ans,s_path[node]);
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 9360
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

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

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

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

    int N;
    u64 A;
    u64 remain = 0;
    u64 ans = 0;

    cin >> N;
    rep (i, N)
    {
        cin >> A;
        ans += MIN(A, remain);
        A -= MIN(A, remain);
        ans += A / 2;
        remain = A % 2;
    }
    cout << ans << "\n";
    return 0;
}



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

using namespace std;
 
#define PB(x)	push_back(x)
#define ALL(x)	(x).begin(), (x).end()
#define ALLR(x)	(x).rbegin(), (x).rend()
#define MP(x)	make_pair(x)
 
#define debug(_x)		cerr << #_x << '=' << _x << endl;
#define debug2(_x, _y)	cerr << #_x << '=' << _x << ' ' << #_y << '=' << _y << endl;
#define debugn(_a)		cerr << #_a << ": "; for (const auto _x: _a) cerr << _x << ' '; cerr << endl;

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

#define int long long int

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef unsigned long long ull;

const int INF = LONG_LONG_MAX;
const int NINF = LONG_LONG_MIN/2;

int32_t main() {
	FAST_IO;
	
	int r;
	cin >> r;
	
	printf("%.9f\n", 4.0*acos(0.0)*r);
}

// g++ -Wall -Wextra -Wshadow -fsanitize=undefined


Measured memory_bytes: 3772
// C++ 14
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long ilong
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#define N 3
#define NN (N*N)

vector<Int> dx = {0, 0, -1, 1};
vector<Int> dy = {-1, 1, 0, 0};
vector<char> dirs = {'u', 'd', 'l', 'r'};


struct Puzzle {
  vector<Int> vec;
  Int blank;
  string path;
  
  Puzzle(): vec(NN, -1), blank(-1), path("") {
  }
  
  Puzzle(vector<Int> &vec, Int blank, string path) {
    this->vec = vec;
    this->blank = blank;
    this->path = path;
  }
  
  bool operator == (const Puzzle &other) const { 
    loop(n,0,NN) {
      if (vec[n] != other.vec[n]) return false;
    }
    
    return true;
  }
  
  Puzzle move(Int dir) {
    // i = h * N + w
    Int sx = blank % N;
    Int sy = blank / N;
    Int tx, ty;
    
    switch (dir) {
      case 0: 
      case 1:
      case 2:
      case 3:
        tx = sx + dx[dir];
        ty = sy + dy[dir];
        break;
      default:
        cout << "Invalid dir: " << dir << endl;
        exit(1);
        break;
    }
    
    Puzzle p;
    if (tx < 0 || N <= tx || ty < 0 || N <= ty) {
      return p;
    }
    
    p = *this;
    swap(p.vec[sy * N + sx], p.vec[ty * N + tx]);
    p.blank = ty * N + tx;
    p.path += dirs[dir];
    return p;
  }
  
  void dump() {
    loop(n,0,NN) cout << vec[n] << ' '; cout << endl;
  }
  
  void dump2() {
    loop(h,0,N) {
      loop(w,0,N) {
        cout << vec[h * N + w] << ' ';
      }
      cout << endl;
    }
  }
};

namespace std {

  template <>
  struct hash<Puzzle>
  {
    std::size_t operator()(const Puzzle& p) const
    {
      std::size_t seed = p.vec.size();
      for(auto& i : p.vec) {
        seed ^= i + 0x9e3779b9 + (seed << 6) + (seed >> 2);
      }
      return seed;
    }
  };
}


vector<Int> targetVec = {1, 2, 3, 4, 5, 6, 7, 8, 0};
Puzzle target(targetVec, 8, "");
Puzzle source;


Int bfs() {
  queue<Puzzle> Q;
  unordered_map<Puzzle, bool> DONE;
  
  Q.push(source);
  DONE[source] = true;
  
  while (!Q.empty()) {
    Puzzle top = Q.front(); Q.pop();
    if (top == target) return top.path.length();
    
    loop(dir,0,dirs.size()) {
      Puzzle p = top.move(dir);
      if (p.blank== -1) continue; // Invalid board
      if (DONE[p]) continue;
      Q.push(p);
      DONE[p] = true;
    }
  }
  
  cout << "No solution" << endl;
  return -1;
}

void input() {
  vector<Int> vec(NN, -1);
  Int blank = -1;
  loop(h,0,N) {
    loop(w,0,N) {
      cin >> vec[h*N + w];
      if (vec[h*N + w] == 0) blank = h * N + w;
    }
  }
  source.vec = vec;
  source.blank = blank;
}

void solve() {
  cout << bfs() << endl;
}


int main() {
  input();
  solve();
}


Measured memory_bytes: 41252
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

template <typename T>
void print(T x) {
    cout << x << "\n";
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REVFOR(i, m, n) for (int i = (n - 1); i >= (m); --i)
#define REP(i, n) FOR(i, 0, n)
#define REVREP(i, n) REVFOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;

void chmax(ll& x, ll y) {
    if (x < y) x = y;
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    ll n; cin >> n;

    print(n * (n - 1) / 2);
}

Measured memory_bytes: 3572
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>

char A[105];
char B[105];
char C[105];
int cur_a = 0;
int cur_b = 0;
int cur_c = 0;
int len_a = 0;
int len_b = 0;
int len_c = 0;

int main () {
    scanf("%s%s%s", A, B, C);
    len_a = strlen(A);
    len_b = strlen(B);
    len_c = strlen(C);
    char next = A[0];
    cur_a++;
    char flag;
    while(true) {
        if(next == 'a') {
            if(cur_a >= len_a) {
                flag = 'A';
                break;
            }
            next = A[cur_a++];
        }
        else if(next == 'b') {
            if(cur_b >= len_b) {
                flag = 'B';
                break;
            }
            next = B[cur_b++];
        }
        else if(next == 'c') {
            if(cur_c >= len_c) {
                flag = 'C';
                break;
            }
            next = C[cur_c++];
        }
    }
    printf("%c ", flag);
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdbool.h>
int main(){
	bool fl[200][3]={};
	int a,b,c,d,i,f,g[200]={0};
	int x[200][3]={0};
	scanf("%d",&a);
	for(i=0;i<a;i++)
	{
		for(f=0;f<3;f++)
		{
			scanf("%d",&x[i][f]);
		}
	}
	for(i=0;i<3;i++)
	{
		for(f=0;f<a;f++)
		{
			for(d=f+1;d<a;d++)
			{
				if(x[f][i]==x[d][i])
				{
					fl[f][i]=true;
					fl[d][i]=true;
				}
			}
		}
	}
	
	for(i=0;i<a;i++)
	{
		for(f=0;f<3;f++)
		{
			if(!fl[i][f])
				{
					g[i]+=x[i][f];
				}
		}
	}
	for(i=0;i<a;i++)
	{
		printf("%d\n",g[i]);
	}
	return 0;
	}


Measured memory_bytes: 2048
#include <iostream>

using namespace std;

int main() {
	int bingo[3][3];
	int n;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> bingo[i][j];
		}
	}
	cin >> n;
	for (int b = 0; b < n; b++) {
		int cur;
		bool found = false;
		cin >> cur;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				if (cur == bingo[i][j]) {
					bingo[i][j] = 0;
					found = true;
					break;
				}
			}
			if (found) break;
		}
	}
	bool success = false;
	bool allzero;
	for (int i = 0; i < 3; i++) {
		allzero = true;
		for (int j = 0; j < 3; j++) {
			if (bingo[i][j] != 0) {
				allzero = false;
				break;
			}
		}
		if (allzero) success = true;
	}
	for (int j = 0; j < 3; j++) {
		if (success) break;
		allzero = true;
		for (int i = 0; i < 3; i++) {
			if (bingo[i][j] != 0) {
				allzero = false;
				break;
			}
		}
		if (allzero) success = true;
	}
	allzero = true;
	for (int i = 0; i < 3; i++) {
		if (success) break;
		if (bingo[i][i] != 0) {
			allzero = false;
			break;
		}
	}
	if (allzero) success = true;
	allzero = true;
	for (int i = 0; i < 3; i++) {
		if (success) break;
		if (bingo[i][2-i] != 0) {
			allzero = false;
			break;
		}
	}
	if (allzero) success = true;
	if (success) cout << "Yes";
	else cout << "No";
	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(c) (c).begin(), (c).end()
#define pb push_back
#define eb emplace_back
using namespace std;
const long long INF = 1LL<<60; // 仮想的な無限大の値;
using ll = long long;
using P  = pair<int, int>;
#define vi vector<int>
#define vll vector<ll>
#define vs vector<string>
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; }

int main()
{
    int N;
    cin >> N;
    vi A(N), B(N);
    int cnt = 0;
    rep(i, N)
    {
        int a, b;
        cin >> a >> b;
        if(a==b) ++cnt;
        else cnt = 0;
        if(cnt >= 3){
            cout << "Yes" << endl;return 0;
        }
       
        
    }
     cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> Pii;

ll N, K;

ll gcd(ll a, ll b) {
    ll large = max(a, b);
    ll small = min(a, b);
    if (small == 0) return large;
    else return gcd(small, large % small);
}

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

    ll tmp = N % K;
    
    cout << min(tmp, K-tmp) << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define print(x) cout << (x) << endl;
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    N = N * 3;
    vector<int> a(N);
    long long sum = 0;
    for (int i = 0; i < N; i++) {
        cin >> a.at(i);
    }
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
    for (int i = 0; i < N / 3 * 2; i+=2) {
        sum += a.at(i+1);
    }
    cout << sum << endl;
}

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

using vi=vector<int>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;

const int INF=1e9;
const int SIZE=6002;
const int OFFSET=3001;

void cmin(int &lhs,int rhs){
    lhs=min(lhs,rhs);
}
int main(){
    int N,K;
    cin>>N>>K;
    vector<int> a(N),r(K),b(K);
    for(int i=0;i<N;i++) cin>>a[i];
    for(int i=0;i<K;i++) cin>>r[i];
    for(int i=0;i<K;i++) cin>>b[i];

    sort(a.begin(),a.end());
    sort(r.begin(),r.end());
    sort(b.begin(),b.end());
    vi rsum(K+1),bsum(K+1);
    for(int i=0;i<K;i++) rsum[i+1]=rsum[i]+r[i];
    for(int i=0;i<K;i++) bsum[i+1]=bsum[i]+b[i];
    vi asum(N+1);
    for(int i=0;i<=N;i++) asum[i+1]=asum[i]+a[i];
    auto sumR=[&](int l,int r){
        return rsum[r]-rsum[l];
    };
    auto sumB=[&](int l,int r){
        return bsum[r]-bsum[l];
    };
    auto sumA=[&](int l,int r){
        return asum[r]-asum[l];
    };

    vvvi dp(K+1,vvi(K+1,vi(SIZE+1,INF)));
    dp[0][0][OFFSET]=0;
    for(int i=0;i<=K;i++){
        for(int j=0;j<=K;j++){
            for(int X=0;X<=SIZE;X++){
                int k=N-(i+j)-1;
                if(k==-1) continue;
                int Y=sumR(K-i,K)+sumB(K-j,K)-sumA(N-(i+j),N)-(X-OFFSET);
                if(i==1 && j==1 && X==OFFSET+3){
                    
                }
                if(i+1<=K){
                    int toX=X-a[k]+r[K-i-1];
                    if(0<=toX && toX<=SIZE){
                        cmin(dp[i+1][j][toX],dp[i][j][X]+max(0,X-toX));
                    }
                }
                if(j+1<=K){
                    int toY=Y-a[k]+b[K-j-1];
                    cmin(dp[i][j+1][X]  ,dp[i][j][X]+max(0,Y-toY));
                }
            }
        }
    }
    int res=INF;
    for(int i=0;i<=K;i++){
        for(int j=0;j<=K;j++){
            for(int X=0;X<=SIZE;X++){
                int Y=sumR(K-i,K)+sumB(K-j,K)-sumA(N-(i+j),N)-(X-OFFSET);
                if(sumR(0,K-i)+X-OFFSET>=0 && sumB(0,K-j)+Y>=0 && i+j==N){
                    cmin(res,dp[i][j][X]);
                }
            }
        }
    }
    // cerr<<dp[0][1][OFFSET]<<endl;
    // cerr<<dp[1][1][OFFSET+3]<<endl;
    // cout<<dp[2][1][OFFSET]<<endl;
    cout<<(res==INF ? -1 : res)<<endl;
    
    return 0;
}


Measured memory_bytes: 91844
#include<iostream>
#include<algorithm>
using namespace std;
long long inf=1e12;
int n;
long long a[200005],sum[200005],ans;
long long check(int f,int s,int t){
	if(!f||f>s||t<=s||t==n){
		return inf;
	}
	long long x1=sum[f],x2=sum[s]-sum[f],x3=sum[t]-sum[s],x4=sum[n]-sum[t];
	return max(max(x1,x2),max(x3,x4))-min(min(x1,x2),min(x3,x4));
}
int main(){
	cin>>n;
	ans=inf;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
	for(int i=2,l,r;i<=n-2;i++){
		l=upper_bound(sum,sum+n+1,sum[i]/2)-sum;
		if(l==0) l++;
		if(l==n+1) l--;
		r=upper_bound(sum,sum+n+1,sum[i]+(sum[n]-sum[i])/2)-sum;
		if(r==0) l++;
		if(r==n+1) r--;
		for(int j=l-1;j<=l;j++){
			for(int k=r-1;k<=r;k++){
				ans=min(ans,check(j,i,k));
			}
		}
	}
	cout<<ans;
}

Measured memory_bytes: 6652
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
 
using namespace std;
 
const int M = 2e5 + 5;
int k, n, t[M], mx; 

int main () {
	cin >> k >> n;
	for (int i = 0; i < n; i++) {
		cin >> t[i];
		if (i) mx = max(mx, t[i]-t[i-1]);
	}
	mx = max(mx, t[0]+k-t[n-1]);
	cout << k - mx << endl;
}

Measured memory_bytes: 1024
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;

namespace MyProject
{
    class Program
    {
        static void Main(string[] args)
        {
#if Local
            var sw = new Stopwatch();
            sw.Start();
            Console.SetIn(new StreamReader("input.in"));
#endif

            var solver = new Solver();
            solver.Solve();
#if Local
            Console.WriteLine($"{sw.ElapsedMilliseconds}ms");
#endif
        }
    }

    class Solver
    {
        public void Solve()
        {
            var items1 = Console.ReadLine().Split();
            var S = items1[0];
            var T = items1[1];

            var items2 = Console.ReadLine().Split().Select(elem => int.Parse(elem)).ToArray();
            var A = items2[0];
            var B = items2[1];

            var U = Console.ReadLine();

            if (U == S)
            {
                A -= 1;
            }
            else
            {
                B -= 1;
            }

            Console.WriteLine($"{A} {B}");
        }
    }
}


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

int main(){
	string s;
	cin>>s;
	int y=(s[5]-'0')*10+s[6]-'0';	
	if(y<=4){
		cout<<"Heisei"<<endl;
	}else{
		cout<<"TBD"<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
mod io{
    use std::io::*;
    pub fn read<T: ::std::str::FromStr>()->T{
        let stdin=stdin();
        let ret=stdin.lock().bytes().map(|c|c.unwrap()as char)
        .skip_while(|c|c.is_whitespace())
        .take_while(|c|!c.is_whitespace())
        .collect::<String>().parse().ok().unwrap();
        ret
    }
}
use io::read;
fn main(){
    let (mut a,mut b)=(0,0);
    for c in read::<String>().chars(){
        a=a*10+c as i32-48;
        b+=c as i32-48;
    }
    println!("{}",if a%b<1{"Yes"}else{"No"})
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
int n;
int p[2][105];
int main(){
    cin >> n;
    for(int b = 0; b < 2; b++){
        for(int i = 1; i <= n; i++){
            cin >> p[b][i];
            p[b][i] += p[b][i-1];
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        ans = max(ans, p[0][i] + p[1][n] - p[1][i-1]);
    }
    cout << ans << '\n';
}

Measured memory_bytes: 256
//#######################     Starting_with_name_of_ALLAH     ##############################
//#######################     Bismillahir_rahmair_raheem      ##############################
 
//                      coded in 2020
//
//                   Shamim Ahammad Rasel
//                  Begum Rokeya University
//                 shamim.brur.cse@gmail.com
//                    I love your thinking 


#include<bits/stdc++.h>
#include<bitset>
#include<iostream>
#define tc()         int tc;cin>>tc;while(tc--)

using namespace std;


bitset<1000001> prime;


void shomoy();

void seive(){
    // o prime
    // 1 not prime
    prime[1] = 1;
    prime[2] = 0;
    for(int i=3;i*i<1000009;i+=2){
        if(prime[i]==0){
            for(int j=i+i;j<1000009;j+=i){
                prime[j] = 1;
            }
        }
    }
}

long long fact(int n){
    long long mul = 1;
    for(int i=1;i<=n;i++){
        mul *= i;
    }
    return mul;
}



int npr(int n,int r){
    int mul=1;
    int temp =0;
    for(int i=0;i<r;i++){
        mul *= (n-i);
    }
    return mul;
}

int main(){
	ios::sync_with_stdio();
	cin.tie();
    int  i,j,k,x,y,a,b,n,s,p,total=0,index,count,sum,temp,len,t,temp1,count1,count2,mn;
    
    char line[1001];
    cin>>line;
    len = strlen(line);
    if(line[len-1]=='s'){
    	cout<<line<<"es"<<endl;
    }
    else{
    	cout<<line<<"s"<<endl;
    }
	    

    

   


shomoy();
return 0;
}




void shomoy(){
    #ifndef ONLINE_JUDGE
        cerr<<"---------END OF OUTPUT---------------\n";
        cerr<<"---------Time  :"<<1.0*clock()/CLOCKS_PER_SEC<<"s------------\n";
        
    #endif
 
}


Measured memory_bytes: 3636