akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin>>s;
    int n = s.size();
    unordered_map<int,int> m;
    m[0]++;
    int sum = 0;
    ll ans = 0;
    ll aux = 1;
    for(int i=n-1;i>=0;i--){
        int d = (int) s[i]-'0';
        sum = (sum + d*aux)%2019;
        aux = (aux * 10)%2019;
        ans +=  m[sum];
        m[sum]++;
    }
    cout<<ans<<"\n";
    return 0;

}




Measured memory_bytes: 3792
#include <bits/stdc++.h>
using namespace std;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
 
typedef long long ll;
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define forr(i, a, b) for(int i = (a); i < (int) (b); i++)
#define forn(i, n) forr(i, 0, n)
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define DBG(x) cerr << #x << " = " << (x) << endl
#define DBGV(v,n) forn(i,n) cout << v[i] << " "; cout << endl
#define esta(x,c) ((c).find(x) != (c).end())
#define RAYA cerr << "===============================" << endl
#define MAXN 2005
#define INF 1000000007
 
 
int main()
{ 
	FIN;
	
	#ifdef input
		//freopen("test1.txt", "r", stdin);
	#endif
	
	vector <int> v(5);
	forn(i,5) cin >> v[i];
	int ans = -1;
	forn(i,5) if(v[i]==0) ans=i+1;
	cout << ans << endl;
	
	
	
	return 0;
}

Measured memory_bytes: 3652
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

typedef long long int ll;

#define FOR(i,n,m) for(ll i=(ll)(m);i<(ll)(n);++i)
#define REP(i,n) FOR(i,n,0)
#define IREP(i,n) for(ll i=(ll)(n);i>=0;--i)

const ll MOD = 1000000007;

using namespace std;

int a[100005] = {};

int main()
{
	int N;
	cin >> N;
	REP(i, N)
	{
		cin >> a[i];
	}

	sort(a, a + N);

	int ans = 0;
	int n = a[0], num = 0;
	REP(i, N)
	{
		if (n == a[i])
		{
			num++;
			continue;
		}
		if (num != n)
		{
			ans += (num > n ? num - n : num);
		}
		n = a[i];
		num = 1;
	}
	if (num != n)
	{
		ans += (num > n ? num - n : num);
	}
	cout << ans;
	return 0;
}

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

using namespace std;

int main(void) {
  int x, y;
  cin >>x >> y;
  if (4 * x < y || 2 * x > y) {
    cout << "No" << endl;
  } else if (y % 2 == 0 || y % 6 == 0) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 3624
import java.io.IOException;

import java.io.BufferedReader;
import java.io.InputStreamReader;

import java.io.PrintWriter;

import java.util.HashMap;

@SuppressWarnings("unchecked")
public class Main {
    static final int INF = 1000000007;
    static int MAX_EXP = 0;
    static int[] FCT;
    static int[] INV;

    // 素因数分解
    static void primeFactor(HashMap<Integer, Integer> pf, int n) {
        int a = 2;

        // JDK 1.8 Map.merge
        // map value increment
        while (a * a <= n) {
            if (n % a == 0) {
                pf.merge(a, 1, Integer::sum);
                MAX_EXP = Math.max(MAX_EXP, pf.get(a));
                n = n / a;
            } else a++;
        }

        if (n != 1) {
            pf.merge(n, 1, Integer::sum);
            MAX_EXP = Math.max(MAX_EXP, pf.get(n));
        }
    }

    static void factorial(int x) {
        if (x == 0) return;

        FCT = new int[x + 1];
        FCT[0] = 1;
        FCT[1] = 1;
        for (int i = 2; i <= x; i++)
            FCT[i] = modmulti(FCT[i - 1], i);
    }

    static void inverse(int x) {
        if (x == 0) return;

        INV = new int[x + 1];
        INV[0] = 1;
        INV[1] = 1;
        INV[x] = modcalc(FCT[x], INF - 2);
        for (int i = x - 1; 2 <= i; i--)
            INV[i] = modmulti(INV[i + 1], i + 1);
    }

    // Combination WH
    // nCk
    static int combination(int a, int b) {
        int tmp = modmulti(FCT[a], INV[a - b]);
        return modmulti(tmp, INV[b]);
    }

    // aのb乗をpで割った余りを計算する(a ^ b mod p)
    static int modcalc(int a, int b) {
        // O(log b)
        int d = 0;
        if (b == 0) {
            return 1;
        } else if ((b & 1) == 0) {
            // 偶数 bを半分にできる
            d = modcalc(a, b / 2);
            return modmulti(d, d);
        } else {
            // 奇数 -1乗から1乗をかける
            return modmulti(a, modcalc(a, b - 1));
        }
    }

    // aとbを掛けた値をmodする(a * b mod p)
    static int modmulti(int a, int b) {
        int res = 0;
        int mod = a % INF;
        while (b > 0) {
            if ((b & 1) == 1) {
                res += mod;
                if (res > INF) {
                    res -= INF;
                }
            }
            mod <<= 1;
            if (mod > INF) {
                mod -= INF;
            }
            b >>= 1;
        }
        return res;
    }

    public static void main(String[] args) throws IOException {
        final String s;

        try (BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in))) {
            s = reader.readLine();
        }

        PrintWriter out = new PrintWriter(System.out);

        final String[] sl = s.split(" ");
        int N = Integer.parseInt(sl[0]);
        int M = Integer.parseInt(sl[1]);

        HashMap<Integer, Integer> pf = new HashMap<>();

        primeFactor(pf, M);

        factorial(N + MAX_EXP - 1);

        inverse(N + MAX_EXP - 1);

        int ans = 1;

        for (Integer i : pf.values())
            // (特定の素因数の要素数 + N - 1)C(特定の素因数の要素数)
            ans = modmulti(ans, combination(i + N - 1, i));

        out.println(ans);

        out.flush();
    }
}


Measured memory_bytes: 26448
loop do
  h, w = gets.split.map(&:to_i)
  break if h == 0 && w == 0
  line = "#." * (w / 2 + 1)

  toggle = true
  h.times do |i|
    puts line[0, w] if toggle
    puts line[1, w] if !toggle
    toggle = !toggle
  end
  puts
end

Measured memory_bytes: 8620
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <climits>
//#include "h.h"
using namespace std;

#define MOD1097 1000000007

#define ll long long
#define pint pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define pm(first, second) pb(mp(first, second))
#define SPACE " "
#define fpf first.first
#define fps first.second
#define spf second.first
#define sps second.second

#define all(X) (X).begin(), (X).end()

int main(){

	int N, K;
	cin >> N >> K;
	if(K == 1)cout << 0 << endl;
	else cout << N - K << endl;

//"Hiroakimm0415"
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

//1000.1.1=590*333=196470

int main(void){
	int n,y,m,d,i,l,j;
	long ans;
	
	scanf("%d",&n);
	
	for(;n>0;n--){
		scanf("%d %d %d",&y,&m,&d);
		ans=0;
		while(y>3){
			y-=3;
			ans+=590;
		}
		if(y==2)ans+=195;
		else if(y==3)ans+=390;
		
		ans+=(m-1)*19+d+(m-1)/2;
		if(m%2==1)ans--;
		if(y==3)ans+=(m-1)/2;
		j=590*333;
		printf("%ld\n",j-ans);
		
	}
	
	return 0;
}
		
			
		
		
	

Measured memory_bytes: 0
s = gets.chomp

b = 0 # start with black(0)
w = 0 # start with white(1)

s.each_char.map(&:to_i).each_with_index do |c,i|
    if i%2 == 0
        # b->0, w->1
        if c == 0
            w += 1 
        else
            b += 1
        end
    else
        if c == 0
            b += 1
        else
            w += 1
        end
    end
end

puts [b,w].min


Measured memory_bytes: 2812
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll a[N],x=1000000000000000000;
long long ans=1;
int main(){
     int n,f=0;
  	 scanf("%d",&n);
  	 for(int i=1;i<=n;i++){
	    scanf("%lld",&a[i]);
	    if(!a[i]) f=1;
		}
  	 if(f) puts("0"),exit(0);
  	 for(int i=1;i<=n;i++){
         if(a[i]>(x/ans)){
         	puts("-1");
         	exit(0);
		 }
         else ans*=a[i];
     }
    printf("%lld\n",ans);
  return 0;
}


Measured memory_bytes: 4400
from sys import stdin
import fractions

A, B, K = [int(x) for x in stdin.readline().rstrip().split()]

num_list = []

for i in range(1, fractions.gcd(A,B)+1):
    if A % i == 0 and B % i == 0:
        num_list.append(i)

print(num_list[-(K)])

Measured memory_bytes: 65388
abc = list(map(int, input().split()))
cnt1 = abc.count(abc[0])
cnt2 = abc.count(abc[1])
cnt3 = abc.count(abc[2])

if cnt1 == 2 or cnt2 == 2 or cnt3 == 2:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 2940
a = int(input())
b = int(input())
c = int(input())
x = int(input())
count = 0
for a_n in range(a+1):
    for b_n in range(b+1):
        for c_n in range(c+1):
            if a_n * 500 + b_n * 100 + c_n * 50 == x:
                count += 1

print(count)

Measured memory_bytes: 3060
tochi=input()
s=[]
I=[]

sum=0
n=len(tochi)
for i in range(n):
    if tochi[i] == "\\":
        s.append(i)
    elif tochi[i] == "/" and s:
        j = s.pop()
        a = i - j
        sum += a
	
        while I and I[-1][0] > j:
            a += I.pop()[1]
        I.append([j, a])

print(sum)
print(len(I), *(a for j, a in I))
    



Measured memory_bytes: 6512
def main():
    #input data
    import sys
    input = lambda:sys.stdin.readline().strip()

    H,W,K = map(int,input().split())
    map_input = [list(input()) for _ in range(H)]

    #solve
    ans = [[-1]*W for i in range(H)]
    queue = []
    strawberry_idx = 0
    
    for i in range(H):
        strawberry_idx+=1
        flag = True
        if all(j=='.' for j in map_input[i]):
            strawberry_idx-=1
            queue.append(i)
            continue
        else:
            for j in range(W):
                if map_input[i][j]=='#':
                    if flag:
                        flag = False
                    else:
                        strawberry_idx+=1
                ans[i][j] = strawberry_idx
            if queue:
                for q in queue:
                    ans[q] = ans[i]
                queue = []
    if queue:
        for q in queue:
            ans[q] = ans[min(queue)-1]
    for a in ans:
        print(*a) 

if __name__=='__main__':
    main()

Measured memory_bytes: 73408
#include <bits/stdc++.h>
#define MOD 1000000007
#define int long long
#define pb push_back
#define bw(i,r,l) for (int i=r-1;i>=l;i--)
#define fw(i,l,r) for (int i=l;i<r;i++)
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
int ans=0,n,f[100001],sz[100001],tmp=1; priority_queue<iii,vector<iii>,greater<iii>> edge;
struct point {int x,y,og;} p[100001];
bool cmp(point &a,point &b) {return a.x<b.x;}
bool cmp2(point &a,point &b) {return a.y<b.y;}
int getf(int u) {
	if (u==f[u]) return u;
	else return f[u]=getf(f[u]);
}
void joint(int u,int v) {
	if (sz[u]>sz[v]) {
		f[v]=u;
		sz[u]+=sz[v];
	} else {
		f[u]=v;
		sz[v]+=sz[u];
	}
}
signed main() {
	//freopen("233220.inp","r",stdin);
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n;
	fw (i,0,n) {cin>>p[i].x>>p[i].y; p[i].og=i; f[i]=i;}
	sort(p,p+n,cmp);
	fw (i,0,n-1) edge.push(iii(min(p[i+1].x-p[i].x,abs(p[i+1].y-p[i].y)),ii(p[i].og,p[i+1].og)));
	sort(p,p+n,cmp2);
	fw (i,0,n-1) edge.push(iii(min(p[i+1].y-p[i].y,abs(p[i+1].x-p[i].x)),ii(p[i].og,p[i+1].og)));
	while (!edge.empty()) {
		if (tmp==n) break;
		iii temp=edge.top(); edge.pop(); int cost=temp.first,u=temp.second.first,v=temp.second.second;
		int pu=getf(u),pv=getf(v);
		if (pu!=pv) {
			tmp++;
			ans+=cost;
			joint(pu,pv);
		}
	}
	cout<<ans;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod (ll)(1e9+7)
#define int ll

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

signed main() {
  int n, a[200001];
  bitset<20> bs;
  cin >> n;
  rep(i, 0, n) cin >> a[i];

  int ans = 0;

  int r = 0, l = 0;
  rep(i, 0, n) {
    r++;
    int f = 0, h[20] = {};
    rep(j, 0, 20) {
      if(1 & a[i] >> j && bs[j]) {
        f++;
        h[j] = 1;
      }
    }
    if(f) {
      while(f) {
        rep(j, 0, 20) {
          if(1 & a[l] >> j) {
            bs[j] = 0;
            if(h[j]) h[j] = 0, f--;
          }
        }
        l++;
        r--;
      }
    }
    rep(j, 0, 20) if(1 & a[i] >> j) bs[j] = true;
    ans += r;
  }

  cout << ans << endl;
}


Measured memory_bytes: 1792
#include<iostream>
#include<cstdlib>
#include<stack>
using namespace std;

int main(){
    stack<int> S;
    int a, b, x;
    string s;

    while(cin >> s){
        if(s[0] == '+'){
            a = S.top();
            S.pop();
            b = S.top();
            S.pop();
            S.push(a + b);
        }else if(s[0] == '-'){
            b = S.top();
            S.pop();
            a = S.top();
            S.pop();
            S.push(a - b);
        }else if(s[0] == '*'){
            a = S.top();
            S.pop();
            b = S.top();
            S.pop();
            S.push(a * b);
        }else{
            S.push(atoi(s.c_str()));
        }
    }

    cout << S.top() << endl;

    return 0;
}


Measured memory_bytes: 3220
#include<stdio.h>

int main(void)
{
    int n, sum=0;
    scanf("%d", &n);
    int a[n], b[n], c[n-1]; 
    for(int i=0; i<n; i++)
    {
    	scanf("%d",&a[i]);
    }
  
  	for(int i=0; i<n; i++)
    {
    	scanf("%d",&b[i]);
    }
  
  	for(int i=0; i<n-1; i++)
    {
    	scanf("%d",&c[i]);
    }

  for(int i=0; i<n; i++)
  {
   	sum += b[a[i]-1];
    if(a[i] == a[i-1] + 1) sum += c[a[i-1]-1];
    }
  
  printf("%d", sum);
  
  return 0;
}

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

const double EPS = 1e-10;

struct P{
  int x,y;
  double tim;
  P(int a,int b,double X){
    x=a;
    y=b;
    tim=X;
  }
  bool operator<(const P& a) const {
    return tim<a.tim;
  }
};

vector<P>v;
int n;
double x[222],y[222],z[222],vx[222],vy[222],vz[222],r[222],vr[222];

double get(int a,int b,double mid){
  double ax=x[a]+vx[a]*mid;
  double ay=y[a]+vy[a]*mid;
  double az=z[a]+vz[a]*mid;
  double bx=x[b]+vx[b]*mid;
  double by=y[b]+vy[b]*mid;
  double bz=z[b]+vz[b]*mid;
  double ar=r[a]-vr[a]*mid;
  double br=r[b]-vr[b]*mid;
  double dist=sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by)+(az-bz)*(az-bz));
  return dist-ar-br;
}

double check(int a,int b){
  double l=0,r=300;
  r(o,100){
    double mid=(l+r)/2;
    double a1=get(a,b,mid);
    double a2=get(a,b,mid+EPS);
    if(a1<0||a1<a2)r=mid;
    else l=mid;
  }
  if(get(a,b,r)-EPS<=0)return l;
  return 1e9;
}

bool used[222];
double ans[222];

int main(){
  while(cin>>n,n){
    memset(used,0,sizeof(used));
    v.clear();
    r(i,n)cin>>x[i]>>y[i]>>z[i]>>vx[i]>>vy[i]>>vz[i]>>r[i]>>vr[i];
    r(i,n){
      r(j,n)if(i<j){
        double X=check(i,j);
        v.push_back(P(i,j,X));
      }
      v.push_back(P(i,i,r[i]/vr[i]));
    }
    sort(v.begin(),v.end());
    r(i,v.size()){
      int a=v[i].x;
      int b=v[i].y;
      if(!(!used[a]&&!used[b]))continue;
      used[a]=1;
      used[b]=1;
      ans[a]=v[i].tim;
      ans[b]=v[i].tim;
    }
    r(i,n)printf("%.10lf\n",ans[i]);
  }
}


Measured memory_bytes: 3616
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf  1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)

int main(){
    int x,y;
    cin >> x >> y;
    cout << x+y/2 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define bit(n) (1<<(n))
#define ii(x) int x; cin >> (x)
#define ii2(x, y) int x, y; cin >> (x) >> (y)
#define ii3(x, y, z) int x, y, z; cin >> (x) >> (y) >> (z)
#define yn(x, ok, ng) cout << ((x)?(ok):(ng)) << endl
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
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;}
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}
int const INF = 1001001001;


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

string s;
cin >> s;
int n = SZ(s);
vi v;
int cnt = 1;
rep(i,n) {
    if( i+1 == n || s[i] != s[i+1] ) {
        v.push_back(cnt);
        cnt = 1;
    }
    else cnt++;
}

int m = SZ(v);
vi ans;
for(int i = 0; i < m; i = i + 2) {
    int tot = v[i] + v[i+1];
    vi res(tot);
    if(tot % 2 == 0) {
        res[v[i]-1] = tot/2;
        res[v[i]] = tot/2;
        rep(j,tot) ans.push_back(res[j]);
    }
    else {
        if(v[i] % 2 == 1) {
            res[v[i]-1] = tot/2 + 1;
            res[v[i]] = tot/2;
            rep(j,tot) ans.push_back(res[j]);
        }
        if(v[i+1] % 2 == 1) {
            res[v[i]-1] = tot/2;
            res[v[i]] = tot/2 + 1;
            rep(j,tot) ans.push_back(res[j]);
        }
    }
}
rep(i,n) {
    if (i == n - 1) {
      cout << ans[i] << endl;
    } else {
      cout << ans[i] << ' ';
    }
}

return 0;
}

Measured memory_bytes: 1480
#include <bits/stdc++.h>
#define N 200005
using namespace std;
int k,n,a[N];
double cnt,p[1005],ans;
int main(){
	cin>>n>>k;
	for(int i=1;i<=1000;i++)p[i]=i*(i+1)*1.0/2.0/i;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=k;i++)cnt+=p[a[i]];
	ans=cnt;
	for(int i=k+1;i<=n;i++)cnt+=p[a[i]]-p[a[i-k]],ans=max(ans,cnt);
	cout<<fixed<<setprecision(8)<<ans<<endl;
	return 0;
}

Measured memory_bytes: 4540
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()

int main(void){
    ll n;
    cin >> n;
    string s;
    cin >> s;

    ll sum = 0;
    rep(i, 0, 1000){
        string tmp = to_string(i);
        if(i < 10){
            tmp =  '0' + tmp;
            tmp =  '0' + tmp;
        }
        else if(i < 100){
            tmp = '0' + tmp;
        }
        ll c = 0;
        rep(j, 0, n){
            if(tmp[c] == s[j]){
                c++;
            }
        }
        if(c == 3){
            sum++;
        }
    }
    cout << sum << endl;
    return 0;
}


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

int main(){
	
	
	int n;
	cin >> n;
	std::vector<int> v(n);
	for(int i = 0; i < n; ++i){
		cin >> v[i];
	}
	ll ans = 0;
	for(int i = 1; i < n; ++i){
		if(v[i] < v[i - 1]){
			ans += v[i-1] - v[i];
			v[i] = v[i - 1];
		}
	}

	cout << ans;

	return 0;
}

Measured memory_bytes: 3976
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define INF 10000000
#define MOD 1000000007
#define MID (l+r)/2
#define HASHMOD 2305843009213693951
#define ll long long
#define ull unsigned long long
#define F first
#define S second
typedef pair<ll, ll> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef map<int, int> mii;

#define EPS 1e-6

#define T double
typedef complex<T> pt;
#define x real()
#define y imag()
T dot(pt v, pt w) {return (conj(v)*w).x;}
T cross(pt v, pt w) {return (conj(v)*w).y;}
T orient(pt a, pt b, pt c) {return cross(b-a,c-a);}
T dist(pt a, pt b) {return abs(a-b);}

int main(){
	string s;
	cin>>s;
	int n = s.size();
	s = "0" + s;
	bool ok =true;
	vi one;
	for(int i=0;i<=n;i++){
		if(s[i]!=s[n-i]) ok = false;
		if(s[i]=='1') one.push_back(i);
	}
	if(!ok || s[1]=='0'){
		cout<<-1<<endl;
		return 0;
	}

	for(int i=1;i<=one.size();i++) cout<<i<<" "<<i+1<<endl;
	int cnt=one.size()+2;
	for(int i=1;i<one.size();i++){
		for(int j=1;j<one[i]-one[i-1];j++) cout<<i+1<<" "<<cnt++<<endl;
	}
	assert(cnt==n+1);



}


Measured memory_bytes: 3948
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,z,w;
    cin >> n >> z >> w;
    vint a(n);
    REP(i,n){
        cin >> a[i];
    }
    if(n==1){
        cout << abs(w-a[0]) << endl;
        return 0;
    }
    cout << max(abs(w-a[n-1]), abs(a[n-1]-a[n-2])) << endl;;

    return 0;
}

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

int main()
{
    /* ------- 宣言と入力 ------- */

    int A[3][3];

    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            cin >> A[i][j];
        }
    }

    int N;

    cin >> N;

    int b[N];

    for (int i = 0; i < N; i++)
    {
        cin >> b[i];
    }

    /* ------- 計算 ------- */

    bool bingo[3][3] = {false};

    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            for (int k = 0; k < N; k++)
            {
                if (A[i][j] == b[k])
                {
                    bingo[i][j] = true;
                }
            }
        }
    }

    string ans = "No";

    for (int i = 0; i < 3; i++)
    {
        if (bingo[i][0] && bingo[i][1] && bingo[i][2])
        {
            ans = "Yes";
        }
    }

    for (int i = 0; i < 3; i++)
    {
        if (bingo[0][i] && bingo[1][i] && bingo[2][i])
        {
            ans = "Yes";
        }
    }

    if (bingo[0][0] && bingo[1][1] && bingo[2][2])
    {
        ans = "Yes";
    }

    if (bingo[0][2] && bingo[1][1] && bingo[2][0])
    {
        ans = "Yes";
    }

    cout << ans << endl;

    return 0;
}

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

#define INF 1e18
long long DP[5001][5001];

struct Constraint {
	long long H, P;

	Constraint(long long H = 0, long long P = 0):H(H), P(P){}

	bool operator<(const Constraint& r)const {
		return P+H < r.P+r.H;
	}
};

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

	int N; cin >> N;
	vector<Constraint>C(N);
	for (int i = 0; i < N; i++) {
		int P, H; cin >> H >> P;
		C[i] = Constraint(H, P);
	}
	sort(C.begin(), C.end());

	for (int i = 0; i <= N; i++)for (int j = 0; j <= N; j++)DP[i][j] = INF;
	DP[0][0] = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < i + 1; j++) {
			if (DP[i][j] == INF)continue;

			if (DP[i][j] <= C[i].H) {
				DP[i + 1][j + 1] = min(DP[i + 1][j + 1], DP[i][j] + C[i].P);
			}			
			DP[i + 1][j] = min(DP[i + 1][j], DP[i][j]);
		}
	}

	int ans = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (DP[i][j]==0 || DP[i][j] == INF)continue;
			ans = max(ans, j);
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 195712
#include<stdio.h>
#include<math.h>
int main()
{
	double x1, x2, y1, y2, x, y, kyori;

	scanf(" %lf %lf %lf %lf", &x1, &y1, &x2, &y2);

	x = x2 - x1;
	y = y2 - y1;

	x = pow(x,2);
	y = pow(y,2);

	kyori = x + y;

	kyori = sqrt(kyori);

	printf("%f", kyori);

	return 0;
}

Measured memory_bytes: 652
#include<iostream>
#include<bits/stdc++.h>
#define ll long long
#define make_pair
using namespace std;
 
int main()
{
    ll n; cin>>n;
    ll ar[n];
    ll total = 0;
    for(ll i = 0;i < n;i++){ cin>>ar[i]; total = total^ar[i];}
    
    for(ll i = 0;i < n;i++){
        cout<<(total^ar[i])<<" ";
    }

	return 0;
}

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

int main() {
	long a[3];
	cin>>a[0]>>a[1]>>a[2];
	sort(a,a+3);
	if(a[1]-a[0]==a[2]-a[1]) cout<<"YES\n";
	else cout<<"NO\n";
	// your code goes here
	return 0;
}

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

using namespace std;

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15);
  }
} initializer;

class UnionFind {
private:
  int n;
  vector<int> a;
public:
  UnionFind(int n) : n(n), a(n, -1) {}
  int find(int x) {return a[x] < 0 ? x : (a[x] = find(a[x]));}
  bool equal(int x, int y) {return find(x) == find(y);}
  void unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (a[x] > a[y]) swap(x, y);
    a[x] += a[y];
    a[y] = x;
    --n;
  }
  int size() {return n;}
  int size(int x) {return -a[find(x)];}
  bool isRoot(int x) {return find(x) == x;}
  vector<vector<int>> groups() {
    vector<vector<int>> r(a.size()), res;
    for (uint i = 0; i < a.size(); ++i) r[find(i)].emplace_back(i);
    for (auto&& i : r) if (!i.empty()) res.emplace_back(move(i));
    return res;
  }
};

int main() {
  int n, k[2];
  cin >> n >> k[0] >> k[1];
  vector<UnionFind> uf(2, UnionFind(n));
  for (int t = 0; t < 2; ++t) {
    for (int i = 0; i < k[t]; ++i) {
      int p, q;
      cin >> p >> q;
      uf[t].unite(p - 1, q - 1);
    }
  }
  vector<vector<int>> gr[2];
  for (int i = 0; i < 2; ++i) gr[i] = uf[i].groups();
  vector<vector<int>> a(2, vector<int>(n));
  for (int t = 0; t < 2; ++t) {
    for (const auto& g : gr[t]) for (int i : g) a[t][i] = g[0];
  }
  map<pair<int, int>, int> m;
  for (int i = 0; i < n; ++i) ++m[make_pair(a[0][i], a[1][i])];
  for (int i = 0; i < n; ++i) {
    cout << m[make_pair(a[0][i], a[1][i])] << (i != n - 1 ? ' ' : '\n');
  }
}



Measured memory_bytes: 35060
import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue
from decimal import Decimal
# import fractions

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
dl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    A, B = sl()
    A = Decimal(A)
    B = Decimal(B)
    print(int(A*B))


if __name__ == '__main__':
    main()


Measured memory_bytes: 10756
import java.io.IOException;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws IOException {

        int dai = 20 * 10;
        int sho = dai - 5;

        Scanner sc = new Scanner(System.in);

        int num = sc.nextInt();

        for (int i = 0; i < num; i++) {
            int days = 0;
            int year = sc.nextInt();
            int mth = sc.nextInt();
            int day = sc.nextInt();

            if ( 1000 < year || 10 < mth || 20 < day ) {
                break;
            }
            //生まれた年
            if (year % 3 == 0) {
                days += 20 - day + 1;
                for (int j = mth + 1; j <= 10; j++) {
                    days += 20;
                }
            } else {
                if (mth % 2 == 0) {
                    days += 19 - day + 1;
                } else {
                    days += 20 - day + 1;
                }
                for (int j = mth + 1; j <= 10; j++) {
                    if (j % 2 == 0) {
                        days += 19;
                    } else {
                        days += 20;
                    }
                }
            }
            //翌年以降
            for (int j = year + 1; j < 1000; j++) {
                if (j % 3 == 0) {
                    days += dai;
                } else {
                    days += sho;
                }
            }
            System.out.println(days);
        }

        sc.close();
    }
}



Measured memory_bytes: 26320
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> llP;

ll mod(ll a, ll b){
  ll ret=a%b;
  if(ret<0) ret+=b;
  return ret;
}

ll modpow(ll a,ll b,ll c){
  ll res=1;
  while(b>0){
    if(b&1) res=mod(res*a,c);
    a=mod(a*a,c);
    b>>=1;
  }
  return res;
}

int main() {
  for(int i=1;i<=5;i++){
      int a;
      cin>>a;
      if(a==0) cout<<i<<endl;
  }
  return 0;
}


Measured memory_bytes: 3580
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include<vector>
using namespace std;

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

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

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

    int sum = 0;

    for(int i=0;i<n;i++){
        sum += a[i].second;
        if(sum>a[i].first){
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
    return 0;

}

Measured memory_bytes: 3328
#include<iostream>
#include<vector>
#include<sstream>
#include<string>
#include<numeric>
using namespace std;
int input(){
  int x;
  cin>>x;
  return x;
}
int abs(int x){
  if(x>=0){
    return x;
  }else{
    return -x;
  }
}
int gcd(int x, int y){
	if(x<y){
    return gcd(y,x);
  }
  if(y==0){
    return x;
  }
  return gcd(y,x%y);
}



int main() {
  string S;
  cin>>S;
  if(S.at(0)=='A'){
    int sum=0;
    int x=0;
    for(int i=2;i<S.size()-1;i++){
      if(S.at(i)=='C'){
        sum++;
      }
    }
    for(int i=1;i<S.size();i++){
      if(S.at(i)>='A'&&S.at(i)<='Z'){
        x++;
      }
    }
    if(sum==1&&x==1){
      cout<<"AC"<<endl;
    }else{
      cout<<"WA"<<endl;
    }
    


  }else{
    cout<<"WA"<<endl;
  }


  


  



  
  
  

  


}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<map>
#include<iomanip>
#define rip(i,n) for(int i=0;i<n;i++)
#define ll long long
#define lb long double
#define vec vector<int>
using namespace std;
int main() {
	lb a, b, c, d;
	cin >> a >> b >> c >> d;
	cout << fixed <<setprecision(10)<<sqrt((a - c) * (a - c) + (b - d) * (b - d)) << endl;
}


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

int main() {
   int X, Y;
   cin >> X >> Y;
   bool can = false;
   for (int i = 0; i <= X; i++) {
       int legs = 2*i+4*(X-i);
       if (legs == Y) {
           can = true;
           break;
       }
   }
   if (can) cout << "Yes" << endl;
   else cout << "No" << endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> pii;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define vv(type, c, m, n, i) vector<vector<type>> c(m, vector<type>(n, i))
#define mat(type, c, m, n) vector<vector<type>> c(m, vector<type>(n));for(auto& r:c)for(auto& i:r)cin>>i;
#define rep(i,a,n) for(int i=(a), i##_len=(n); i<i##_len; ++i)
#define rrep(i,a,n) for(int i=(a), i##_len=(n); i>i##_len; --i)
#define each(x,y) for(auto &(x):(y))
#define var(type, ...)type __VA_ARGS__;Scan(__VA_ARGS__);
template<typename T> void Scan(T& t) { cin >> t; }
template<typename First, typename...Rest>void Scan(First& first, Rest&...rest) { cin >> first; Scan(rest...); }
#define vec(type, c, n) vector<type> c(n);for(auto& i:c) cin>>i;
#define len(x) ((int)(x).size())
#define mp make_pair
#define eb emplace_back
#define em emplace
#define pb pop_back
#define fi first
#define se second
#define get(a, i) get<i>(a)
#define bit_count __builtin_popcount
#define mt make_tuple
inline string zero(int a,string s,char c='0'){return string(a-len(s),c)+s;}
inline string zero(int a,int t,char c='0'){return zero(a, to_string(t), c);}
inline string zero(int a,ll t,char c='0'){return zero(a, to_string(t), c);}
#define mini min_element
#define maxi max_element
#define sum accumulate
#define chmax(a,b) if(a<b)a=b
#define chmin(a,b) if(a>b)a=b
template <class T> inline void print(T t){cout << t << '\n';}
template <class H, class... T> inline void print(H h, T... t){cout << h << " ";print(t...);}
int v[510][510];
void solve() {
	var(int, h, w);
	rep(i, 1, h + 1) {
		rep(j, 1, w + 1) {
			cin >> v[i][j];
		}
	}
	vector<vi> ans;
	ans.reserve(250010);
	rep(i, 1, h) {
		rep(j, 1, w + 1) {
			if (v[i][j] & 1) {
				ans.eb(vi{i, j, i + 1, j});
				++v[i + 1][j];
			}
		}
	}
	rep(j, 1, w) {
		if (v[h][j] & 1) {
			ans.eb(vi{h, j, h, j + 1});
			++v[h][j + 1];
		}
	}
	print(len(ans));
	each(a, ans) {
		print(a[0], a[1], a[2], a[3]);
	}
}
int main() {
	solve();
	return 0;
}


Measured memory_bytes: 11776
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()

fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod


inv[n] = pow(fac[n], mod-2, mod)
for j in range(n-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod

def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod




A = LI()
dp = [[0] * (n + 1) for _ in range(k + 1)]
dp[0][0] = 1
for i in range(k):
    for j in range(n + 1):
        for l in range(min(n - j, A[i]) + 1):
            dp[i + 1][j + l] = (dp[i + 1][j + l] + dp[i][j] * comb(n - j, l) % mod
                                * comb(n - l, A[i] - l)) % mod

print(dp[k][n])

Measured memory_bytes: 99020
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define clr(a) memset(a, 0, sizeof(a))
#define sz(x) x.size()
#define printarray(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout<<*it<<" "; cout<<endl;
#define rep(n) for (ll i = 0; i < n; i++)
#define repc(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define DEC(i, x, y) for (int i = x; i >= y; i--)
#define all(v) v.begin(), v.end()
#define min3(a, b, c) min(a, min(b, c))
#define max3(a, b, c) max(a, max(b, c))
#define alla(a, n) a, a + n
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * b)/gcd(a, b)
#define int long long int
#define ull unsigned long long

using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 5;

int fastexpo(int b, int exp){
    if(exp == 0) return 1;
    if(exp == 1) return b;
    int ans = (fastexpo(b,exp/2) % MOD);
    ans *= ans;
    ans %= MOD;
    if(exp % 2 == 1){
        ans *= b;
    }
    ans %= MOD;
    return ans;
}

// int a[n];
// int n, k;

void reduceFraction(int x, int y) { 
    int d; 
    d = __gcd(x, y); 
  
    x = x / d; 
    y = y / d; 
  
    cout << "x = " << x << ", y = " << y << endl; 
} 


int finddiff(string a, string b){
	int cnt = 0;
	for(int i= 0;i<a.size();i++){
		cnt += (a[i]!=b[i]);
	}
	return cnt;
 
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s, t;
    cin>>s>>t;
    int ans = INT_MAX;
    int n= t.size();
    for(int i= 0;i<=s.size()-n;i++){
        string s1 = s.substr(i, n);
        ans = min(ans, finddiff(s1, t));
    }
    cout<<ans<<endl;
    return 0;
}





Measured memory_bytes: 3664
using System;
using System.Linq;

namespace agc008_a
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] x = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int min = 2147483647;
            if (x[0] <= x[1])
            {
                min = Math.Min(min, x[1] - x[0]);
            }
            if (x[0] * -1 <= x[1])
            {
                min = Math.Min(min, x[1] - x[0] * -1 + 1);
            }
            if (x[0] <= x[1] * -1)
            {
                min = Math.Min(min, x[1] * -1 - x[0] + 1);
            }
            if (x[0] * -1 <= x[1] * -1)
            {
                min = Math.Min(min, x[1] * -1 - x[0] * -1 + 2);
            }
            Console.WriteLine(min);
        }
    }
}

Measured memory_bytes: 2776
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<string, pair<int,int> > P;

vector<P> v;

bool cmp(const P &a, const P &b){
  if (a.first != b .first) return a.first < b.first;
  return a.second.first < b.second.first;
}

int main() {
  int N;
  cin >> N;
  rep(i,N){
 	string s;
    int a;
    cin >> s >> a;
    v.push_back(make_pair(s, make_pair(-a,i+1)));
  }
  sort(v.begin(), v.end(), cmp);
  rep(i,N) {
    cout << v[i].second.second << endl;
  }
}

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

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef pair<LL, LL> PLL;
typedef vector<LL> VL;
typedef vector<VL> VVL;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort((c).begin(),(c).end())

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

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

LL dp[2][101][256];
LL fact[101];
int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  fact[0] = 1;
  REP(i,100) fact[i+1] = fact[i] * (i+1) % MOD;
  
  int N, K; cin >> N >> K;
  VI xs(N);
  REP(i,N) cin >> xs[i];
  SORT(xs);

  int crt = 0, nxt = 1;
  dp[crt][0][0] = 1;
  REP(i,N){
	fill((LL*)dp[nxt], (LL*)dp[nxt]+101*256, 0);
	REP(j,i+1){
	  REP(b,256){
		(dp[nxt][j][b] += dp[crt][j][b]) %= MOD;
		(dp[nxt][j+1][b] += dp[crt][j][b^xs[i]]) %= MOD;
	  }
	}
	swap(crt, nxt);
  }

  LL ans = 0;
  REP(i,N+1)
	(ans += dp[crt][i][K] * fact[i]) %= MOD;
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 640
import java.util.*;
 
public class Main
{
    private final static int MOD = 1_000_000_007;
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
	String[] temp = in.nextLine().split(" ");
	int N = Integer.parseInt(temp[0]);
	int K = Integer.parseInt(temp[1]);
	int[] arr = new int[N];
	temp = in.nextLine().split(" ");
	for (int i = 0; i < N; i++) {
	    arr[i] = Integer.parseInt(temp[i]);
	}
	long[][] dp = new long[N+1][K+1];
	dp[0][0] = 1;
	for (int i = 1; i <= N; i++) {
	    dp[i][0] = 1;
	    for (int j = 0; j < K; j++) {
		dp[i][j+1] = dp[i][j] + dp[i-1][j+1];
		dp[i][j+1] %= MOD;
		if (j - arr[i-1] >= 0) {
		    dp[i][j+1] = dp[i][j+1]-dp[i-1][j-arr[i-1]] + MOD;
		    dp[i][j+1] %= MOD;
		}
	    }
	}
	System.out.println(dp[N][K] % MOD);
	in.close();
    }
}


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

using namespace std;

const int N=1e5+5;
int n,a[N];
long long m,s[N];

long long calc(int lim)
{
    long long res=0;
    for(int i=1;i<=n;i++)
    {
        int v=lower_bound(a+1,a+n+1,lim-a[i])-a;
        res+=n-v+1;
    }
    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
    int l=1,r=2e5,lim;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(calc(mid)>=m)
        {
            lim=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    long long need=m-calc(lim+1);
    long long res=need*lim;
    lim++;
    for(int i=1;i<=n;i++)
    {
        ///a[i]+a[j]>=lim;
        int v=lower_bound(a+1,a+n+1,lim-a[i])-a;
        res+=1ll*a[i]*(n-v+1)+s[n]-s[v-1];
    }
    cout<<res;
}


Measured memory_bytes: 1408
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iomanip>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#define REP(i, n) for(long long i = 0; i < n; i++)
#define SHOWVEC(v, n) for(int _i = 0; _i < n; _i++) cerr << v[_i] << ' '; cerr << endl;

using namespace std;

int main()
{
  int A, B;
  cin >> A >> B;
  int ans = A + B;
  ans = max(ans, A - B);
  ans = max(ans, A * B);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#ifdef DEMETRIO
#define deb(...) fprintf(stderr,__VA_ARGS__)
#define deb1(x) cerr << #x << " = " << x << endl
#else
#define deb(...) 0
#define deb1(x) 0
#endif
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
#define SZ(x) ((int)(x).size())
#define mset(a,v) memset(a,v,sizeof(a))
#define mcpy(a,b) memcpy(a,b,sizeof(a))
using namespace std;
typedef long long ll;

int n;
int h[100005];
int f[100005];

int main(){
	scanf("%d",&n);
	fore(i,0,n)scanf("%d",h+i);
	f[n-1]=0;f[n-2]=abs(h[n-2]-h[n-1]);
	for(int i=n-3;i>=0;--i)f[i]=min(abs(h[i]-h[i+1])+f[i+1],abs(h[i]-h[i+2])+f[i+2]);
	printf("%d\n",f[0]);
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int a,b,c,k;
    int max = 0;
    cin >> a >> b >> c >> k;
    if(a >= k) max = k;
    else {
        k -= a;
        // cout << k << endl;
        max += a;
        k -= b;
        // cout << k << endl;
        if(k > 0){
            max -= min(c,k);
            // cout << min(c,k) << endl;
        }
    }
    cout << max << endl;
}


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

vector<int> Z_algorithm(string S){
  // cerr << S << endl;
  int c = 0, n = S.length();
  vector<int> Z(n,0);
  for(int i = 1; i < n; ++i){
    int l = i - c;
    if(i + Z[l] < c + Z[c]){
      Z[i] = Z[l];
    }else{
      int j = max(0, c + Z[c] - i);
      while(i + j < n && S[j] == S[i+j]) ++j;
      Z[i] = j;
      c = i;
    }
  }
  return Z;
}

string min_cycle(string S){
  vector<int> Z = Z_algorithm(S+S);
  int L = S.length();
  // for(auto e : Z) cerr << e << " ";
  // cerr << endl;
  for(int i = 1; i < L; ++i){
    if(Z[i] >= L){
      return S.substr(0,i);
    }
  }
  return S;
}

int main(){
  string S, T;
  cin >> S >> T;
  {
    string sc = min_cycle(T), st = min_cycle(S);
    cerr << sc << " " << st << endl;
    if(sc.length() == st.length()){
      string sc_ = sc + sc;
      vector<int> Z = Z_algorithm(st+"#"+sc_);
      // for(auto e : Z)
      //   cerr << e << " ";
      // cerr << endl;
      for(size_t i = st.length(); i < Z.size(); ++i){
        if(Z[i] >= (int)st.length()){
          // cerr << i << " " << Z[i] << endl;
          cout << -1 << endl;
          return 0;
        }
      }
    }
  }
  string S_ = S;
  while(S.length() <= T.length()) S += S_;
  S += S;
  S += S;
  string U = T + "#" + S;
  vector<int> Z = Z_algorithm(U);
  int N = Z.size(), M = T.length();
  vector<int> dp(N+1,0);
  int ans = 0;
  for(int i = M+1; i < N; ++i){
    ans = max(ans,dp[i]);
    if(Z[i] >= M) dp[i+M] = dp[i]+1;
    ans = max(ans,dp[i+1]);
  }
  cout << ans << endl;
}


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


main() {
  int n;cin >> n;
  if(n==2){
    cout << 1 << endl;
    return 0;
  }
  int ans=0;
  for(int i=1;i<n;i++){
    ans+=(n-1)/i;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3524
n = int(input())
s = input()

ans = 0
for i in range(n):
    d1, d2 = {}, {}
    for j in range(i):
        d1[s[j]] = 0
    for j in range(i, n):
        if s[j] in d1 and s[j] not in d2:
            d2[s[j]] = 0
    ans = max(ans, len(d2))

print(ans)




Measured memory_bytes: 9152
s=input()
s=s[::-1]
t=""
i=0
while i<=len(s)-5:
    if s[i:i+5]=="maerd":
        t+="maerd"
        i+=5
    elif s[i:i+5]=="esare":
        t+="esare"
        i+=5
    elif s[i:i+6]=="resare":
        t+="resare"
        i+=6
    elif s[i:i+7]=="remaerd":
        t+="remaerd"
        i+=7
    else:
        print("NO")
        exit()
if t==s:
    print("YES")
else:
    print("NO")


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

int main() {
    int n,k,d,A;
    cin >> n >> k;

    vector<int> vec(n);

    for (int i = 0; i < k; i++){
        cin >> d;
        for (int j = 0; j < d; j++){
            cin >> A;
            vec.at(A - 1)++;
        }
    }

    int ans = 0;
    for (int i = 0; i < n; i++){
        if(vec.at(i) == 0){
            ans++;
        }
    }

    cout << ans << endl;

    return 0;
}



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

using namespace std;
typedef long long ll;


int n;
int a[1010];

int main()
{
    cin >> n;
    double mul = 1, sum = 0;;
    for (int i = 0 ; i < n; ++i)
        cin >> a[i], mul *= a[i];
    for (int i = 0; i < n ; ++i)
    {
        sum += mul / a[i];
    }
    cout << fixed << setprecision(9) << mul / sum << endl;
    return 0;
}


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

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

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

 
int main() {
  VI A(4);
  bool ans=true;
  string S;
  cin >> S;
  REP(i,4) {
    REP(j,4) {
      if (S.at(i) == S.at(j)) {
        A.at(i)++;
      }
    }
  }
  REP(i,4) {
    if(A.at(i) != 2) ans = false;
  }
  if(ans) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

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

using namespace std;

#define all(x) begin(x), end(x)

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;

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

    string s;
    cin >> s;

    bool valid = s[2] == s[3] and s[4] == s[5];
    cout << (valid ? "Yes" : "No") << '\n';
    
    return 0;
}


Measured memory_bytes: 256