akhauriyash/Code-Regression huggingface dataset:
public class
Main
{
  private static int
  evaluate (
    final int[ ] a,
    final int    k
    )
  {
    int res = 0;
    int t;
    int i;

    t = 1;
    for ( i = 0; i < a.length; ++i )
    {
      if ( i >= k )
        t /= a[ i - k ];
      t *= a[ i ];
      res = Math.max ( res, t );
    }

    return ( res );
  }

  public void
  run (
    final java.util.Scanner sc,
    final java.io.PrintStream out
    )
  {
    int i, j;

    for ( ; ; )
    {
      int[ ] a;
      int n, k;
      int r1, r2 = 0;

      n = sc.nextInt ( );
      k = sc.nextInt ( );
      if ( n == 0 || k == 0 ) break ;
      a = new int[ n ];
      for ( i = 0; i < a.length; ++i )
        a[ i ] = sc.nextInt ( );

      r1 = evaluate ( a, k );
      for ( i = 0; i < a.length; ++i )
      for ( j = i + 1; j < a.length; ++j )
      {
        int t;

        t = a[ i ]; a[ i ] = a[ j ]; a[ j ] = t;
        r2 = Math.max ( r2, evaluate ( a, k ) );
        t = a[ i ]; a[ i ] = a[ j ]; a[ j ] = t;
      }

      out.println ( r2 < r1 ? "NO GAME" : r2 - r1 );
    }
  }

  public static void
  main (
    final String[ ] args
    )
  {
    ( new Main ( ) ).run ( new java.util.Scanner ( System.in ), System.out );
  }
}

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

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n = 5;
    int a[5];
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        if(x == 0) cout <<i + 1 << "\n";
    }

    return 0;
}


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

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

Measured memory_bytes: 256
N,A,B=map(int,input().split())

cnt_blue = 0
total_tmp = 0

try:
    pre_cnt = N // (A+B)
    total_tmp = pre_cnt * (A+B)
    total_tmp += A
    if N <= total_tmp:
        cnt_blue = N -  (pre_cnt * B)
    else:
        cnt_blue = (pre_cnt * A) + A
    print(cnt_blue)
except Exception as e:
    print(0)

Measured memory_bytes: 9080
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cstdint>
using namespace std;

const uint64_t kP = 1000000007;

uint64_t mmul(uint64_t a, uint64_t b, uint64_t p) {
  return ((a % p) * (b % p)) % p;
}

uint64_t mpow(uint64_t a, uint64_t e, uint64_t p) {
  uint64_t ret = 1;
  uint64_t m = a % p;
  while (e) {
    if (e & 1) {
      ret = (ret * m) % p;
    }
    m = (m * m) % p;
    e >>= 1;
  }
  return ret;
}

uint64_t mdiv(uint64_t a, uint64_t b, uint64_t p) {
  return ((a % p) * mpow(b % p, p - 2, p)) % p;
}

int main()
{
  uint64_t n, k;

  cin >> n >> k;
  vector<uint64_t> v;
  vector<uint64_t> w;
  v.resize(n + 1);
  w.resize(n + 1);
  v[0] = w[0] = 1;
  for (uint64_t i = 1; i <= n; ++i) {
    v[i] = mmul(i, v[i-1], kP);
    w[i] = mdiv(w[i-1], i, kP);
  }
  for (uint64_t i = 1; i <= k; ++i) {
    if (n - k + 1 < i) {
      cout << 0 << endl;
    } else {
      uint64_t ans = mmul(v[k-1], v[n - k + 1], kP);
      ans = mmul(ans, w[i - 1], kP);
      ans = mmul(ans, w[k - i], kP);
      ans = mmul(ans, w[i], kP);
      ans = mmul(ans, w[n - k + 1 - i], kP);
      cout << ans << endl;
    }
  }

  return 0;
}




Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <numeric>

typedef long long ll;


using namespace std;
int main() {
    ll n, m;
    cin >> n >> m;
    vector<pair<int, int> > vc;
    for (int i=0; i<n; ++i){
        ll a, b;
        cin >> a >> b;
        pair<int, int> p = make_pair(a,b);
        vc.push_back(p);
    }
    sort(vc.begin(), vc.end(), [](auto it, auto jt){return it.first < jt.first;});
    ll ret = 0LL;
    ll ct = 0LL;
    for (auto it=vc.begin(); it!=vc.end(); ++it){
        auto a = it->first;
        auto b = it->second;
        if(ct+b >= m){
            ret += (m - ct)*a;
            break;
        }
        ret += b*a;
        ct += b;
    }
    cout << ret << endl;
    return 0;
}


Measured memory_bytes: 1400
/*------------------------------------
........Bismillahir Rahmanir Rahim....
..........created by Abdul Aziz.......
------------------------------------*/
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <queue>
#define   mod  998244353
#define   int  long long 
#define   ld   long double
#define   pb   push_back
#define   vi  vector<int> 
#define   dbg(x)  cerr << #x << " = " << x << '\n'
#define   sz(x)  (int)x.size()
#define   all(a) (a.begin(),a.end())
#define   ff   first
#define   ss   second
#define   pii  pair<int,int> 
#define   lcm(a,b) (a*b)/__gcd(a,b) 
using namespace std;

inline void solve(){ 
    int  r, g, b, n, ans = 0 ; 
    cin >> r >> g >> b >> n ; 
    for (int i=0;i<=n/r;i++){
        int s=i*r;
        for (int j=0;j<=n/g;j++){
            int rem = n - (s+j*g);
            if (rem%b==0 and rem>=0) ans++;
            else continue;
           // cout << i << " " << j << " " << rem/b << endl;
        }
    }
    cout << ans << endl; 
} 

signed main()
{
    int n=1; // cin>>n;
    while (n--) solve();
    return 0;
}


Measured memory_bytes: 3636
#F
from operator import mul
from functools import reduce

r1, c1, r2, c2 = [int(i) for i in input().split()]
mod = 10**9 + 7

#pre-caluculation of the factorial
num = 10**6*2+3
fact=[0] * num
fact[0]=1
for i in range(1, num):
    fact[i] = (fact[i-1] * i) % mod

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

def f(rr,cc):
    #(0,0)~(r,c)までのコンビネーションの累積和
    #print(rr+cc+2, cc+1)
    #print(combinations_count(rr+cc+2, cc+1))
    #return combinations_count(rr+cc+2, cc+1) - 1
    return (fact[rr+cc+2]%mod * pow(fact[rr+1]*fact[cc+1], mod-2, mod)) % mod -1

ans = f(r2, c2) - f(r2, c1-1) - f(r1-1, c2) + f(r1-1, c1-1)
print(ans % mod)

Measured memory_bytes: 82660
#include <bits/stdc++.h>
using namespace std;
int main()
{
	char a1,b1,c1,d1;
	int ans,a,b,c,d;
	cin>>a1>>b1>>c1>>d1;
	a=a1-'0';b=b1-'0';c=c1-'0';d=d1-'0';
	for(char i='+';i<='-';i++)
		for(char j='+';j<='-';j++)
			for(char k='+';k<='-';k++)
			{
				ans=a;
				if(i=='+') ans+=b;
				else if(i=='-') ans-=b;
				if(j=='+') ans+=c;
				else if(j=='-') ans-=c;
				if(k=='+') ans+=d;
				else if(k=='-') ans-=d;
				if(ans==7)
				{
					cout<<a<<i<<b<<j<<c<<k<<d<<"="<<ans<<"\n";
					return 0;
				}
			}
}

Measured memory_bytes: 256
import scala.io.StdIn.{readInt,readLine}

object Main extends App {
  println {
    Iterator.continually(readInt).takeWhile(_!=0).map { n =>
      { for(i<-1 to n) yield {
          val t = readLine.split(" ")
          (t(0),t(1).toInt*3 + t(3).toInt*1)
        }
      }.sortWith( _._2 > _._2).map{ e => e._1 + "," + e._2 }.mkString("\n")
    }.mkString("\n\n")
  }
}

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

int main() {
	int cnt=0, cnt1=0;
	string s;
	cin>>s;
	for(int i=0; i<s.size(); i++)
    {
        if(i%2==0 && s[i]=='0') cnt++;
        else if(i%2 && s[i]=='1') cnt++;
        if(i%2==0 && s[i]=='1') cnt1++;
        else if(i%2 && s[i]=='0') cnt1++;
    }

	cout<<min(cnt, cnt1)<<endl;

	return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[105];

int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	sort(a+1,a+1+n);
	int ans=0;
	for(int i=1;i<=n;++i){
		for(int j=i+1;j<=n;++j){
			if(a[i]==a[j])continue;
			for(int k=j+1;k<=n;++k){
				if(a[k]==a[i] || a[k]==a[j])continue;
				if(a[i]+a[j]>a[k] && a[i]+a[k]>a[j] && a[k]+a[j]>a[i])ans++;
			}
		}
	}
	printf("%d\n",ans);
	return 0; 
}

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

int main(){
  string s;
  cin >> s;
  if(s == "Sunny") cout << "Cloudy" << endl;
  if(s == "Cloudy") cout << "Rainy" << endl;
  if(s == "Rainy") cout << "Sunny" << endl;
  return 0;
}

Measured memory_bytes: 256
from collections import defaultdict


def main():
    n, t = map(int, input().split())
    a = list(map(int, input().split()))
    profit = defaultdict(int)
    now_min = a[0]
    for i in range(1, n):
        profit[a[i] - now_min] += 1
        now_min = min(now_min, a[i])
    profit = list(profit.items())
    profit.sort(key=lambda x: x[0], reverse=True)
    print(profit[0][1])


if __name__ == '__main__':
    main()


Measured memory_bytes: 28980
import scala.io.StdIn.readLine

object Main extends App {

  val t     = readLine()
  val lines = Iterator.continually(readLine()).takeWhile { _ != "END_OF_TEXT" }

  val allWords = for {
    line <- lines
    words = line.split(" ")
    word <- words
  } yield word.toLowerCase

  val cnt = allWords.count { _ == t }
  println(cnt)
}



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

int main(){
  int n,d;
  cin >> n >> d;
  vector<long long int> x(n),y(n); //intだと大きい数でうまくいかない
  int ans = 0;
  for(int i=0;i<n;i++){
    cin >> x.at(i) >> y.at(i);
    if(sqrt(x.at(i)*x.at(i)+y.at(i)*y.at(i))<=d){
      ans++;
    }
  }
  
  cout << ans << endl;
  
}

Measured memory_bytes: 6488
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

int main()
{
    ll n, c;
    cin >> n >> c;
    ll x[100007], v[100007];
    for(int i = 1; i <= n; i++){
        cin >> x[i] >> v[i];
    }
    x[0] = 0, v[0] = 0;
    ll leftret[100007] {0};
    ll left[100007] {0};
    ll rightret[100007] {0};
    ll right[100007] {0};
    ll get = 0;
    for(int i = 1; i <= n; i++){
        get += v[i];
        leftret[i] = max(leftret[i - 1], get - x[i] * 2);
        left[i] = max(left[i - 1], get - x[i]);
    }
    get = 0;
    for(int i = 1; i <= n; i++){
        get += v[n + 1 - i];
        rightret[i] = max(rightret[i - 1], get - (c - x[n + 1 - i]) * 2);
        right[i] = max(right[i - 1], get - (c - x[n + 1 - i]));
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        ans = max(ans, left[i] + rightret[n - i]);
    }
    for(int i = 1; i <= n; i++){
        ans = max(ans, right[i] + leftret[n - i]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 4992
#include <iostream>
#include <cstdio>
#include <map>
#include <cstring>

using namespace std;

const int maxn = 505;
int c[maxn],s[maxn],f[maxn];
int main()
{
    int n;
    scanf("%d",&n);

    for(int i=1; i<n; i++)
    {
        scanf("%d%d%d",&c[i],&s[i],&f[i]);
    }
    for(int i=1; i<=n-1; i++)
    {   int ans = 0;
        for(int j=i; j<=n-1; j++)
        {
            if(ans<s[j])
                ans = s[j];
            if(ans%f[j]!=0)
                ans+=f[j]-ans%f[j];
            ans +=+ c[j];
        }
        //ans +=
        printf("%d\n",ans);

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

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

int main(void) {
    while (true) {
        int x,y;cin>>x>>y;
        if (x == 0 && y == 0) break;
        if (x > y) swap(x, y);
        cout << x << " " << y << endl;
    }
    return 0;
}


Measured memory_bytes: 3072
import java.util.*;
public class Main{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    if(a%2==0){
      System.out.println(a);   
    }else{
      System.out.println(a*2);   
    }   
  } 
}

Measured memory_bytes: 25556
n,m = map(int, input().split())
num_cnts = []
al = list(map(int, input().split()))
for a in al:
    num_cnts.append((a,1))

for _ in range(m):
    b,c = map(int, input().split())
    num_cnts.append((c,b))

num_cnts.sort(reverse=True)
ans = 0
curr_cnt = 0
for num,cnt in num_cnts:
    if curr_cnt + cnt <= n:
        ans += num*cnt
        curr_cnt += cnt
    else:
        rem = n-curr_cnt
        ans += rem*num
        break

print(ans)

Measured memory_bytes: 95332
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Convert;
using static System.Math;
//using Debug;
//using static System.Globalization.CultureInfo;
using System.Text;
class Program
{
    static void Main(string[] args)
    {
        Solve();
        //WriteLine(Solve());
    }
    static void Solve()
    {
        var nk = Input.ar;
        if (nk[0] > nk[1]) { WriteLine(0); return; }
        var comb = new Modulo.Combination(nk[1] + 1);
        WriteLine(Modulo.Div(comb.fac(nk[1]),comb.fac(nk[1] - nk[0])));
    }
}

public class Input
{
    public static string read => ReadLine();
    public  static int[] ar => Array.ConvertAll(read.Split(' '), int.Parse);
    public  static int num => ToInt32(read);
    public static long[] arL => Array.ConvertAll(read.Split(' '), long.Parse);
    public  static long numL => ToInt64(read);
    public static char[][] gred(int h) 
        => Enumerable.Repeat(0, h).Select(v => read.ToCharArray()).ToArray();
    public static int[][] ar2D(int num)
        => Enumerable.Repeat(0, num).Select(v => ar).ToArray();
    public static long[][] arL2D(int num)
        => Enumerable.Repeat(0, num).Select(v => arL).ToArray();
    public static T getValue<T>(string g)
    {
        var t = typeof(T);
        if (t == typeof(int))
            return (T)(object)int.Parse(g);
        if (t == typeof(long))
            return (T)(object)long.Parse(g);
        if (t == typeof(string))
            return (T)(object)g;
        if (t == typeof(char))
            return (T)(object)char.Parse(g);
        if (t == typeof(double))
            return (T)(object)double.Parse(g);
        if (t == typeof(bool))
            return (T)(object)bool.Parse(g);
        return default(T);
    }
    public const long Inf = (long)1e18;
    public const double eps = 1e-6;
    public  const string alfa = "abcdefghijklmnopqrstuvwxyz";
    public  const int MOD = 1000000007;
}

public class Modulo
{
    private static int Multiple(int num1, int num2)
        => (int)(BigMul(num1, num2) % Input.MOD);

    public static int Pow(int m, int n)
    {
        if (n == 0) return 1;
        if (n % 2 == 0) return Pow(Multiple(m, m), n / 2);
        else return Multiple(Pow(Multiple(m, m), n / 2), m);
    }

    public static int Div(int a, int b)
        => Multiple(a, Pow(b, Input.MOD - 2));

    public class Combination
    {
        private int[] _fac;
        public Combination(int num)//階乗をメモ化
        {
            _fac = new int[num + 1];
            _fac[0] = 1;
            for (var i = 1; i <= num; i++)
                _fac[i] = Multiple(_fac[i - 1], i);
        }
        public int Comb(int n, int r)
        {
            if (n < r) return 0;
            if (n == r) return 1;
            var calc = _fac[n];
            calc = Div(calc, _fac[r]);
            calc = Div(calc, _fac[n - r]);
            return calc;
        }
        public int fac(int num)
            => _fac[num];
    }

}



Measured memory_bytes: 17968
n=int(input())
xl=[];ul=[]
for i in range(n):
  x,u=map(str,input().split())
  #print(x)
  xl.append(float(x))
  ul.append(u)
#print(xl)
btc=380000.0
ans=0.0
for i in range(n):
  if ul[i]=="BTC":
    ans+=xl[i]*btc
  else:
    ans+=xl[i]
print('{:.7f}'.format(ans))

Measured memory_bytes: 3064
// This amazing code is by Eric Sunli Chen.
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>
using namespace std;
template<typename T> void get_int(T &x)
{
	char t=getchar();
	bool neg=false;
	x=0;
	for(; (t>'9'||t<'0')&&t!='-'; t=getchar());
	if(t=='-')neg=true,t=getchar();
	for(; t<='9'&&t>='0'; t=getchar())x=x*10+t-'0';
	if(neg)x=-x;
}
template<typename T> void print_int(T x)
{
	if(x<0)putchar('-'),x=-x;
	short a[20]= {},sz=0;
	while(x>0)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1; i>=0; i--)putchar('0'+a[i]);
}
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define get1(a) get_int(a)
#define get2(a,b) get1(a),get1(b)
#define get3(a,b,c) get1(a),get2(b,c)
#define printendl(a) print_int(a),puts("")
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const LL Linf=1ll<<61;
const double pi=acos(-1.0);

int n,x[1111],y[1111],r[1111];
double dis[1111][1111],dist[1111];
bool vis[1111];
void dijkstra(int s)
{
	for(int i=1;i<=n;i++)dist[i]=1e100;
	dist[s]=0.0;
	for(int _=1;_<=n;_++)
	{
		int x=0;for(int i=1;i<=n;i++)if(!vis[i]&&(x==0||dist[i]<dist[x]))x=i;
		if(x==0)break;
		vis[x]=1;
		for(int i=1;i<=n;i++)dist[i]=min(dist[i],dist[x]+dis[x][i]);
	}
}
int main()
{
	get2(x[1],y[1]);get2(x[2],y[2]);get1(n);
	for(int i=3;i<=n+2;i++)get3(x[i],y[i],r[i]);n+=2;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(1ll*(x[i]-x[j])*(x[i]-x[j])+1ll*(y[i]-y[j])*(y[i]-y[j])<=1ll*(r[i]+r[j])*(r[i]+r[j]))dis[i][j]=0.0;
			else dis[i][j]=sqrt(1ll*(x[i]-x[j])*(x[i]-x[j])+1ll*(y[i]-y[j])*(y[i]-y[j]))-r[i]-r[j];
		}
	}
	dijkstra(1);
	printf("%.10lf\n",dist[2]);
	return 0;
}

Measured memory_bytes: 8960
// lcmとか__builtin_popcountとかはg++ -std=c++17 default.cppみたいなかんじで

#include <bits/stdc++.h>
#define mod 1000000007
#define INF LLONG_MAX
#define ll long long
#define ln cout<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define YES cout<<"YES"<<endl
#define No cout<<"No"<<endl
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
using namespace std;
ll dx[4]={1,0,-1,0};
ll dy[4]={0,1,0,-1};

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

    ll  a,b,c,d,e,n,k,maxi=0,f=0,mini=INF,sum=0,q;
	string str,stra,straa;
    ll x,y,z;
    char ca,cb,cc;
    cin>>n;
    if(n==25) cout<<"Christmas";
    else if(n==24) cout<<"Christmas Eve";
    else if(n==23) cout<<"Christmas Eve Eve";
    else if(n==22) cout<<"Christmas Eve Eve Eve";


    

    return 0;
}


Measured memory_bytes: 3624
#include<iostream>
using namespace std;
int main() {
	long int a;
	int N; cin >> N;
	double count = 0;
	for (int i = 0; i < N; i++) {
		cin >> a;
		if (a % 4 == 0)count++;
		if (a % 2 == 0 && a % 4 != 0)count += 0.5;
	}
	if (count >= N / 2)cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

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

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

int main() {
    int x,a;cin>>x>>a;
    if(x < a)cout<<0<<endl;
    else cout<<10<<endl;
	return 0;
}

Measured memory_bytes: 3612
//85DTG
//07082020
#include<bits/stdc++.h>
using namespace std;
#define bolt ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define lb lower_bound
#define ub upper_bound
#define vi vector <int>
typedef long long ll;
typedef long double ld;
const ld pi=3.1415926535897932384626433;
const ll mod = 998244353;
const ll inf = 1e18;

ll k;
bool check(ll x,vector <ll> a)
{

   ll cnt=0;
   for (ll i=0;i<a.size();i++)
   {
      if (a[i]>x)
      {
         cnt+=ceil(1.0*a[i]/x);
         cnt--;
      }
   }
   if (cnt<=k)
      return true;
   return false;
}
int main ()
{
   bolt;
   ll n;
   cin>>n;
   vector <ll> a(n);



   cin>>k;
   for (ll i=0;i<n;i++)
   {
      cin>>a[i];
   }
   ll ans=a[n-1];
   sort (a.begin(),a.end());
   ll lo=1;
   ll hi=a[n-1];
   while (lo<=hi)
   {
      ll mid=(lo+hi)/2;

      if (check(mid,a))
      {
         ans=mid;
         hi=mid-1;
      }
      else
      {
         lo=mid+1;
      }
   }
   cout<<ans;
}


Measured memory_bytes: 6292
//https://atcoder.jp/contests/abc143/tasks/abc143_b
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
int main(){
    int n;
    int ans=0;
    cin >> n;
    vector<int> d(n);
    rep(i,n) cin >>d.at(i);

    for(int i=0; i<n-1; i++){
        for(int j=i+1; j<n; j++){
            ans += d.at(i)* d.at(j);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
inline int read(){int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}
inline void write(int x){if (x<0) putchar('-'),x=-x; if (x>=10) write(x/10); putchar(x%10+'0');}
inline void writeln(int x){write(x); puts("");}
const int maxn=100005;
int a[maxn],n,l,t,d;
inline void init(){
	n=read(); l=read(); t=read();
	for (int i=1;i<=n;i++){
		int x=read(),opt=read();
		if (opt==1){
			int temp=t;
			if (l-x<=temp){
				temp-=(l-x);
				++d; 
				x=0;
			}
			x+=temp; d+=temp/l; x%=l;
		}else{
			int temp=t;
			if (x+1<=temp){
				temp-=(x+1);
				--d; 
				x=l-1;
			}
			x-=temp; d-=temp/l; x%=l;
			if (x<0) x+=l;
		}
		a[i]=x; d%=n;
	}
}
inline int pre(int x){
	return x==1?n:x-1;
}
inline int nex(int x){
	return x==n?1:x+1;
} 
inline void solve(){
	int pos=1; d%=n;
	while (d<0) pos=pre(pos),++d;
	while (d>0) pos=nex(pos),--d;
	sort(a+1,a+1+n);
	for (int i=pos;i<=n;i++) writeln(a[i]);
	for (int i=1;i<pos;i++) writeln(a[i]);
}
int main(){
	init();
	solve();
	return 0;
}

Measured memory_bytes: 1536
#include<bits/stdc++.h>
#define lli long long int
#define uli unsigned long long int
#define inf 999999999999999999
#define rep(i,m,n) for(lli i = m;i < n;i++)
#define per(i,m,n) for(lli i=m-1;i>=n;i--)
#define st(n) sort(n.begin(), n.end())
#define rev(n) reverse(n.begin(),n.end())
#define ou(S) cout << S << endl
using namespace std;
int main(){
  int i,j,k;
  lli n,a,b,x,y,ans;
  string s,t,r;
  cin>>x>>y;
  ans=x*y;
  a=max(x,y);
  b=min(x,y);
  n=a%b;
  while(n!=0){
    a=b;
    b=n;
    n=a%b;
  }
  cout<<ans/b<<endl;
}

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

using ll = long long;
using namespace std;

constexpr static ll MOD = 1000000007ll;
constexpr static int INF = 1 << 28; // for x <= 10^9
constexpr static ll INFL = 1ll << 60; // for x <= 10^19
constexpr static double EPS = 1e-10;

int n, d;
int distance(int a[], int b[]) {
    int ret = 0;
    for (int i = 0; i < d; i++) {
        ret += (a[i] - b[i]) * (a[i] - b[i]);
    }

    return ret;
}

int main() {
    cin >> n >> d;
    int xs[n][d];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < d; j++) {
            cin >> xs[i][j];
        }
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int dis2 = distance(xs[i], xs[j]);
            for (int k = 0; k <= dis2; k++) {
                if (k * k == dis2) {
                    ans++;
                    break;
                }
            }
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
n, m = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n)]
C = [list(map(int,input().split())) for i in range(m)]

for i in range(n):
    ans = 0
    dis = float("inf")
    for j in range(m):
        mnh = abs(A[i][0]-C[j][0]) + abs(A[i][1]-C[j][1])
        if mnh < dis:
            #print(dis, "d")
            dis = mnh
            ans = j
    print(ans+1)


Measured memory_bytes: 39280
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MOD=(int)1e9+7;
const int INF=(int)1e9;
const ll LINF=(ll)1e18;

int main(){
    int n,x;
    cin>>n>>x;
    int s[n];
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    sort(s,s+n);
    ll dp[2][100001];
    for(int i=0;i<=100000;i++){
        dp[1][i]=i;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<=100000;j++){
            dp[i%2][j]=(dp[(i+1)%2][j%s[i]]+i*dp[(i+1)%2][j])%MOD;
        }
    }
    cout<<dp[(n-1)%2][x]<<endl;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#include<cstring>
using namespace std;
//#define num 1000000007
#define num 998244353
#define REP(i,a,n) for(ll i=a;i<n;i++)
#define up(a,b) (((a)%(b)==0)?((a)/(b)):((a)/(b))+1)
#define inarr(i,a,n,A) for(ll i=a;i<n;i++) { cin>>A[i]; }
#define vll vector<long long>
#define pii pair <int,int>
#define pll pair<long long, long long>
#define vpii vector< pair <int,int>>
#define vpll vector< pair<long long, long long>>
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a>b)?b:a)
#define max3(a,b,c) (a>b)?(a>c)?a:c:(b>c)?b:c
#define min3(a,b,c) (a<b)?(a<c)?a:c:(b<c)?b:c
#define avg(a,b) ((a)+(b))/2
#define push push_back
#define pop pop_back
#define mp make_pair
#define sf int flag=0     //Remember semicolon
#define assmin(a,b) if(b<=a) { a=b; }
#define assmax(a,b) if(b>=a) { a=b; }
#define fi first
#define s second
#define fix(f,n) std::fixed<<std::setprecision(n)<<f
typedef long long ll;
 
ll mod(ll a, ll b)
{
	if(a%b<0)
	{
		return a%b + b;
	}
	return a%b;
}
 
 
ll mod_exp(ll a, ll b, ll c)
{
	ll res=1;
	a=a%c;
	while(b>0)
	{
		if(b%2==1)
		{
			res=(res*a)%c;
		}
		b/=2;
		a=(a*a)%c;
	}
	return res;
}
ll gcd(ll a, ll b)
{
    if(b==0)
    {
        return a;
    }
    return gcd(b, a%b);
}
bool prime[3001];
void SieveOfEratosthenes() 
{ 
    memset(prime, true, sizeof(prime)); 
    prime[1]=false;
    for (int p=2; p*p<=3000; p++) 
    { 
        if (prime[p] == true) 
        { 
            for (int i=p*p; i<=3000; i += p) 
                prime[i] = false; 
        } 
    } 
}
ll powe[20];
void power()
{
	powe[0]=1;
	REP(i,1,20)
	{
		powe[i]=(powe[i-1]*10)%num;
        if(powe[i]<0)
        powe[i]+=num;
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	ll n;
	cin>>n;
	ll A[n];
	map<ll,ll> count;
	REP(i,0,n)
	{
		cin>>A[i];
		count[A[i]]++;
	}
	ll tot=0;
	for(auto itr=count.begin();itr!=count.end();++itr)
	{
		tot+=((itr->second)*(itr->second-1))/2;
	}
	REP(i,0,n)
	{
		cout<<tot-count[A[i]]+1<<"\n";
	}
	return 0;
}

Measured memory_bytes: 11136
#include <bits/stdc++.h>
#define rep(i, to) for (int i = 0; i < (to); ++i)
#define repf(i, from, to) for (int i = (from); i < (to); ++i)
#define unless(cond) if (!(cond))
using namespace std;
using ll = long long;
template <typename T>
using V = vector<T>;
template <typename T, typename U>
using P = pair<T, U>;

int main() {
  string s;

  cin >> s;

  s[3] = '8';

  cout << s << endl;
}


Measured memory_bytes: 3612
#define _GLIBCXX_DEBUG

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>

#include <cmath>

#define int long long

using namespace std;

signed main() {
  int a;
  string s;

  cin >> a >> s;

  if (a >= 3200) {
    cout << s << endl;
  } else {
    cout << "red" << endl;
  }


  return 0;
}


Measured memory_bytes: 764
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#define int long long
using namespace std;

typedef pair<int, int> Pii;

void readline(int N, vector<int> &a){
    string s;
    for(int i = 0; i < N - 1; i++){
        getline(cin, s, ' ');
        a[i] = atoi(s.c_str());
    }
    getline(cin, s, '\n');
    a[N - 1] = atoi(s.c_str());
}
void readline(int N, vector<double> &a){
    string s;
    for(int i = 0; i < N - 1; i++){
        getline(cin, s, ' ');
        a[i] = atof(s.c_str());
    }
    getline(cin, s, '\n');
    a[N - 1] = atof(s.c_str());
}

signed main(){

    string s;
    cin >> s;

    int ans = 0;
    for(int i = 0; i < 4; i++){
        if(s[i] == '+'){
            ans++;
        }else{
            ans--;
        }
    }

    cout << ans;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/integer/common_factor.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>

using std::string;
using std::vector;
using std::set;
using std::multiset;
using std::unordered_set;
using std::map;
using std::multimap;
using std::unordered_map;
using std::pair;
using std::cin;
using std::cout;

using boost::multiprecision::cpp_int;
using cpp_dec_float_1000 = boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1000, boost::int128_type>>;

typedef uintmax_t    ull;
typedef intmax_t     ll;
typedef uint64_t     ul;
typedef uint32_t     ui;
typedef uint8_t      uc;

constexpr char CRLF  = '\n';
constexpr char SPACE = ' ';
constexpr char VECTOR_COUT_SEPARATOR = SPACE;
constexpr ll INF = 1000'000'007;
constexpr int MOD = 1000'000'007;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> std::ostream& operator<< (std::ostream& os, const std::vector<T>& vc) { for(auto it = vc.begin(); it != vc.end(); ++it) { if (std::next(it) == vc.end()) os << *it; else os << *it << VECTOR_COUT_SEPARATOR; } return os; }
template<class T1, class T2> inline std::ostream & operator<< (std::ostream & os, const std::pair<T1, T2> & p) { return os << p.first << ' ' << p.second; }
template<class T> T modinv(T a, T m) { T b = m, u = 1, v = 0; while (b) { T t = a / b; a -= t * b; boost::swap(a, b); u -= t * v; boost::swap(u, v); } u %= m; if (u < 0) u += m; return u; }
template<class T> inline bool isSosuu(const T& n) { if (n == T(1)) { return false; } for (T i = 2; i*i <= n; ++i) { if (n % i == 0) { return false; } } return true; }
template<class T> vector<vector<T>> split (const vector<T>& S, T delim) { vector<vector<T>> ret{}; vector<T> buff{}; for (auto c : S) { if (c == delim) { if (!buff.empty()) ret.push_back(buff); buff.clear(); } else { buff.push_back(c); } } if (!buff.empty()) ret.push_back(buff); return ret; }
template<class T> inline void printYesNo(const T& t) { cout << (t ? "Yes" : "No") << CRLF; }
template<class T = int64_t> T modpow(T N, T P, T M) { T ret{1}; N %= M; while (P) { if (P & 0x01) { ret *= N; ret %= M; } P >>= 1; N *= N; N %= M; } return ret; }

/** code for assert debug begin */
int gErr = 0;
#define ASSERT(p) if(!(p)){ gErr = 1; }else{ ; }
/** code for assert debug end */

struct Tmp
{
public:
  int N;
  Tmp(int N)
  : N(N)
  {}
};

void solve(void)
{
  string s; cin >> s;

  ll res{};
  int kuro{};
  for (int i = 0; i < s.size(); ++i) {
    if (s[i] == 'W') {
      res += kuro;
    } else {
      ++kuro;
    }
  }
  cout << res << CRLF;
  return;
}

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

  solve();

  return 0;
}


Measured memory_bytes: 720
n, q = map(int, input().split())
s    = input()
            
Q = []
for _ in range(q):
    Q.append(input().split())

s    = '$'+s+'$' 
         
def isRemove(pos, s, Q, target):
    cur  = pos        
            
    for t, d in Q:
        if cur == target:
            break
        
        if s[cur] != t:
            continue
            
        if d == 'L':
            cur -= 1
        else:
            cur += 1
            
    if cur == target:
        return True
    return False
          
l = 0
r = len(s) - 1
            
while r - l > 1:
    md = (r+l) // 2
    if isRemove(md, s, Q, 0):
        l = md
    else:
        r = md
            
mostRight = l
            
l = 0
r = len(s) - 1
            
while r - l > 1:
    md = (r+l) // 2
    if isRemove(md, s, Q, len(s)-1):
        r = md
    else:
        l = md        
            
mostLeft = r

print(mostLeft-mostRight-1) #AABCBDBA

Measured memory_bytes: 41520
#include <iostream>

using namespace std;

int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}

int main(){
    int a, b, k;
    cin >> a >> b >> k;
    int score = gcd(a, b);
    int cnt = 0;
    for(int i = score; i > 0; i--){
        if(score % i == 0){
            cnt++;
            if(cnt == k){
                cout << i << "\n";
                return 0;
            }
        }
    }
}

Measured memory_bytes: 256
n = int(input())
li = []
for i in range(n):
    a = input()
    li.append(a)
for i in range(n-1):
    if li[i][-1] != li[i+1][0]:
        print("No")
        exit()
if len(li) == len(set(li)):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3060
#include <vector>
#include <iostream>
#include <cmath>
#include <map>
#include <algorithm>
#include <fstream>
#include <unistd.h>
#include <string>
#include <numeric>
#include <queue>
#include <deque>
#include <sstream>
#include <iomanip>
#include <set>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef vector<P> vp;
typedef vector<PL> vpl;
typedef vector<vector<P>> vvp;
typedef vector<vector<PL>> vvpl;
const int INF = 1001001001;
const ll LINF = 1e18;
const double pi = 3.1415926535897932;
const string endstr = "\n";
#define FOR(i, a, b) for(ll i = (a); i < b; i++)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define FORMAP(it, m) for(auto it = m.begin(); it != m.end(); it++)
#define ff first
#define ss second
#define pb push_back

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

bool p_comp_fs(const PL p1, const PL p2){ return p1.first < p2.first;};
bool p_comp_fg(const PL p1, const PL p2){ return p1.first > p2.first;};
bool p_comp_ss(const PL p1, const PL p2){ return p1.second < p2.second;};
bool p_comp_sg(const PL p1, const PL p2){ return p1.second > p2.second;};
template <typename T>
vector<T> uniquen(vector<T> vec){
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    return vec;
}

struct UnionFind{
    vl par;
    vl rank;
    map<ll, ll> size;
    UnionFind(ll N) : par(N, 0), rank(N, 0){
        for(int i = 0; i < N; i++){
            par[i] = i; size[i] = 1;
        }
    }
    
    ll root(ll x){
        if(par[x] == x) return x;
        else{
            par[x] = root(par[x]); // compression
            return par[x];
        }
    }
    
    void unite(ll x, ll y){
        ll rx = root(x); ll ry = root(y);
        if(rx == ry) return;
        if(rank[rx] < rank[ry]) swap(rx, ry);
        if(rank[rx] == rank[ry]) ++rank[rx];
        par[ry] = rx;
//        if(rx != ry) size[rx] = size[rx] + size[ry];
//        else{
//            size[rx] = max(size[rx], size[ry]);
//        }
    }
    
    ll get_size(ll x){
        return size[root(x)];
    }
    
    bool same(ll x, ll y){
        return root(x) == root(y);
    }
};


int main(){
    ll N, M; cin >> N >> M;
    auto uf = new UnionFind(N);
    vl ps(N, 0); REP(i, N){ ll p; cin >> p; ps[i] = p-1;};
    REP(i, M){
        ll x, y; cin >> x >> y;
        uf->unite(x-1, y-1);
    }
    map<ll, vector<ll>> m1, m2;
    REP(i, N){
        ll root = uf->root(ps[i]);
        if(m1[root].size()==0) m1[root].reserve(1024*128);
        m1[root].pb(i);
    }
    
    ll ret = 0;
    for(auto it : m1){
        for(auto v : it.ss){
            if(binary_search(it.ss.begin(), it.ss.end(), ps[v])) ret++;
        }
    }
    cout << ret << endstr;
    return 0;
}


Measured memory_bytes: 417152
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int k,a,b;
    cin>>k>>a>>b;
    for(int i=a;i<=b;i++)
    {
    if(i%k==0)
    {
    cout<<"OK"<<endl;
    return 0;
    }
    }
    cout<<"NG"<<endl;
    return 0;
    
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vc = vector<char>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;

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

    if (K % 2 == 0 || K % 5 == 0)
    {
        cout << -1 << endl;
        return 0;
    }

    long long int L = 7%K;
    for (int i = 1; i < 10e7; i++)
    {
        if (L == 0)
        {
            cout << i << endl;
            return 0;
        }
        L = L*10+7;
        L %= K;
    }

    return 0;
}

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

int main(){
  int mat[3][3];
  int res[3][3];
  for(int i=0; i<3; i++){
    for(int j=0; j<3; j++){
      res[i][j] = 0;
    }
  }
  for(int i=0; i<3; i++){
    for(int j=0; j<3; j++){
      int num;
      cin >> num;
      mat[i][j] = num;
    }
  }
  int n;
  cin >> n;
  for(int i=0; i<n; i++){
    int num;
    cin >> num;
    for(int j=0; j<3; j++){
      for(int k=0; k<3; k++){
        if(mat[j][k] == num) res[j][k] = 1;
      }
    }
  }
  bool bingo = false;
  if((res[0][0] && res[0][1] && res[0][2])
    || (res[1][0] && res[1][1] && res[1][2])
    || (res[2][0] && res[2][1] && res[2][2])
    || (res[0][0] && res[1][0] && res[2][0])
    || (res[0][1] && res[1][1] && res[2][1])
    || (res[0][2] && res[1][2] && res[2][2])
    || (res[0][0] && res[1][1] && res[2][2])
    || (res[2][0] && res[1][1] && res[0][2])
     ) bingo = true;
  if(bingo) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

const mod = 1000000007
var sc = bufio.NewScanner(os.Stdin)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)

	n := nextInt()
	c := 0
	for i := 1; i <= n; i++ {
		f, l := getFirst(i), getLast(i)
		if f == 0 || l == 0 {
			continue
		}
		// 1桁
		if f == l && f <= n {
			c++
		}
		// 2桁
		if l * 10 + f <= n {
			c++
		}
		// 3桁
		mm := l*100+f
		m := min(l * 100 + 90 + f, n)
		if mm < m {
			c += (m-mm)/10 + 1
		}
		// 4桁
		mm = l*1000+f
		m = min(l * 1000 + 990 + f, n)
		if mm < m {
			c += (m-mm)/10 + 1
		}
		// 5桁
		mm = l*10000+f
		m = min(l * 10000 + 9990 + f, n)
		if mm < m {
			c += (m-mm)/10 + 1
		}
		// 6桁
		mm = l*100000+f
		m = min(l * 100000 + 99990 + f, n)
		if mm < m {
			c += (m-mm)/10 + 1
		}
	}

	fmt.Println(c)
}

func getFirst(x int) int {
	for x > 9 {
		x /= 10
	}
	return x
}

func getLast(x int) int {
	return x % 10
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int main()
{
    ll a[5],n,t;
    cin>>n;
    for(int i=0; i<5; i++)
        cin>>a[i];
    sort(a,a+5);
   if(n>a[0])
   {
       if(n%a[0]==0)
        t=n/a[0];
        else
            t=n/a[0]+1;

   }
   else if(n<=a[0])
    t=1;
    cout<<t+4;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int main(){
  const int N = 9;
  const int S = 1001;
  const int M = 101;
  ll dp[N + 1][M + 1][S + 1] = {}; // num, last, sum
  dp[0][0][0] = 1;
  for(int i = 0; i < N; i++){
    for(int j = 0; j < M; j++){
      for(int k = 0; k < S; k++){
        for(int l = j; l < M && k + l < S; l++){
          dp[i + 1][l + 1][k + l] += dp[i][j][k];
        }
      }
    }
  }
  int n, s;
  while(cin >> n >> s && n){
    ll res = 0;
    for(int i = 0; i < M + 1; i++){
      res += dp[n][i][s];
    }
    cout << res << endl;
  }
  return 0;
}

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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define ALL(a) (a).begin(), (a).end()
#define rALL(a) (a).rbegin(), (a).rend()
#define SZ(x) ((int)(x).size())
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1 << 28;
const ll INF64 = 1ll << 55;
const int mod = 1000000007;
//const int mod = 998244353;

template <class T>inline bool chmin(T &a, const T b)
{
  if (a > b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>inline bool chmax(T &a, const T b)
{
  if (a < b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>inline void line_out(const vector<T> vec) {
  int n = SZ(vec);
  rep(i, n) {
    cout << vec[i];
    if(i < n-1) cout << " ";
  }
  cout << endl;
  return;
}

struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a)
  {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const
  {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const
  {
    mint res(*this);
    return res -= a;
  }
  mint &operator++()
  {
    if ((x += 1) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator--()
  {
    if ((x += mod - 1) >= mod)
      x -= mod;
    return *this;
  }
  mint operator*(const mint a) const
  {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};
struct edge {int to; ll cost;};

int main()
{
  int n; cin >> n;
  vector<vector<edge>> g(n+1);
  rep(i, n-1) {
    int a, b;
    ll c;
    cin >> a >> b >> c;
    g[a].push_back(edge{b, c});
    g[b].push_back(edge{a, c});
  }
  int q, k;
  cin >> q >> k;
  vector<int> x(q), y(q);
  rep(i, q) cin >> x[i] >> y[i];

  vector<ll> dist(n+1, INF64);
  dist[k] = 0;
  queue<int> qu;
  qu.push(k);

  while(!qu.empty()) {
    int now = qu.front(); qu.pop();

    for(auto next : g[now]) {
      if(dist[next.to] == INF64) {
        dist[next.to] = dist[now]+next.cost;
        qu.push(next.to);
      }
    }
  }
  rep(i, q) cout << dist[x[i]]+dist[y[i]] << endl;
}

Measured memory_bytes: 12392
/* Author : Pranav Deshmukh
            PICT,Pune
   Stay Focused!
*/

#include<bits/stdc++.h>
using namespace std;

// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")

#define int             long long
#define float           double
#define ms(s, n) 		memset(s, n, sizeof(s))
#define dip(type,var)   type var; cin>>var;
#define dipi(x)         int x; cin>>x;
#define dipi2(x,y)      int x,y; cin>>x>>y;
#define w(x)            int x; cin>>x; while(x--)
#define mka(type,arr,n) type *arr=new type[n];
#define fo(i,n)         for(int i=0;i<n;i++)
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mod             1000000007
#define inf             1e18
#define pi              3.141592653589793238
#define endl            "\n"
#define f               first
#define s               second
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >

// void c_p_c()
// {
// 	ios_base::sync_with_stdio(0);
// 	cin.tie(0);
// 	cin.tie(0);
// #ifndef ONLINE_JUDGE

// 	freopen("input.txt", "r", stdin);
// 	freopen("output.txt", "w", stdout);
// #endif
// }

int32_t main() {
	// c_p_c();
	int count = 0;
	dipi(n);
	mka(int, arr, n);
	fo(i, n) {
		cin >> arr[i];
	}
	for (int i = 0; i < n - 2; i++) {
		for (int j = i + 1; j < n - 1; j++) {
			for (int k = j + 1; k < n; k++) {
				if (arr[i] + arr[j] > arr[k] && arr[j] + arr[k] > arr[i] && arr[i] + arr[k] > arr[j] && arr[i] != arr[j] && arr[j] != arr[k] && arr[i] != arr[k]) {
					count++;
				}
			}
		}
	}
	cout << count << endl;
	cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
	return 0;
}


Measured memory_bytes: 3788
#include <iostream>
using namespace std;
template<class Type> class Queue
{
    struct Node
    {
        Type num;
        Node *back;
    };
    Node *head, *tail;
    int sz;
    public:
        Queue()
        {
            head = tail = new Node;
            sz = 0;
        }
        void push(Type x)
        {
            Node *n = new Node;
            n->num = x;
            tail->back = n;
            tail = n;
            if(empty()) head = tail;
            sz++;
        }
        Type pop()
        {
            Type ret = head->num;
            Node *_head = head;
            head = head->back;
            delete _head;
            sz--;
            return ret;
        }
        Type front()
        {
            if(not empty()) return head->num;
        }
        bool empty()
        {
            return sz == 0;
        }
};
struct P
{
    string name;
    int val;
};
int main()
{
    int n, t;
    cin >> n >> t;
    Queue<P> que;
    for(int i = 0; i < n; i++)
    {
        P info;
        cin >> info.name >> info.val;
        que.push(info);
    }
    int sum = 0;
    while(!que.empty())
    {
        P tmp = que.front(); que.pop();
        if(tmp.val - t <= 0) 
        {
            sum += tmp.val;
            cout << tmp.name << " " << sum << "\n";
        }
        else
        {
            tmp.val -= t;
            sum += t;
            que.push(tmp);
        }
    }
    return 0;
}


Measured memory_bytes: 7120
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
#define RF(x) freopen(x,"r",stdin)
#define WF(x) freopen(x,"w",stdout)
typedef long long LL;
using namespace std;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
const LL MOD = 1e9+7;
const int SIZE = 1e7+5;
const int INF = 1LL<<30;
const double eps = 1e-4;
const double PI=3.1415926535897932;

char s[100009];
int v[100009];

int main(){
	DRI(n);RS(s);
	REP(v1,2){//0=sheep, 1 =wolf
		REP(v2,2){
			bool legit=1;
			v[0]=v1,v[1]=v2;
			REPP(i,2,n){
				int xv=s[i-1]=='x';
				v[i]=v[i-2]^v[i-1]^xv;
			}
			REP(i,n){
				int xv=s[i]=='x';
				if(v[i]!=(v[(i-1+n)%n]^v[(i+1)%n]^xv)){
					legit=0;
				}
			}
			if(legit){
				REP(i,n){
					printf("%c",v[i]?'W':'S');
				}
				return 0;
			}
		}
	}puts("-1");
}


Measured memory_bytes: 768