akhauriyash/Code-Regression huggingface dataset:
import java.math.*

fun main(args: Array<String>) {
    val cnt = IntArray(13)
    readInputLine()
    readInputLine().split(" ").forEach { cnt[it.toInt()]++ }
    cnt[0]++

    if (cnt[0] >= 2 || cnt[12] >= 2) {
        println(0)
        return
    }

    for (i in 1..11) {
        if (cnt[i] >= 3) {
            println(0)
            return
        }
    }

    var l = false

    val times = mutableListOf<Int>(24)

    for (i in 0..12) {
        when (cnt[i]) {
            1 -> {
                if (l) {
                    times.add(24 - i)
                } else {
                    times.add(i)
                }
                l = !l
            }
            2 -> {
                times.add(24 - i)
                times.add(i)
            }
        }
    }

    val timesArr = times.toIntArray()

    var ans = Int.MAX_VALUE

    for (i in timesArr.indices) {
        for (j in i + 1 until timesArr.size) {
            ans = Math.min(ans, Math.abs(timesArr[i] - timesArr[j]))
        }
    }

    println(ans)
}

fun readInputLine(): String {
    return readLine()!!
}


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

using namespace std;

int main()
{
  string w;
  bool a = true;
  cin >> w;
  sort(w.begin(), w.end());

  if (w.size() % 2 == 0)
  {
    for (int i = 0; i < w.size() / 2; i += 2)
    {
      if (w[i] == w[i + 1])
      {
        continue;
      }
      else
      {
        a = false;
      }
    }
  }
  else
  {
    a = false;
  }

  cout << (a ? "Yes" : "No");
}

Measured memory_bytes: 256
#pragma GCC optimize "trapv"
#include<iostream>
#include <bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define ld long double
#define mp make_pair
#define pii pair<int,int>
#define mod 1000000007
#define rep(i,n) for(int i=0;i<n;i++)
#define repp(i,a,n) for(int i=a;i<n;i++)
#define all(v) v.begin(),v.end()
#define input(arr,n) for(ll i1=0;i1<n;i1++ )cin>>arr[i1]
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>//s.order_of_key(val) *s.find_by_order(ind)
unsigned long long power(unsigned long long x, 
                         int y, int p) 
{ 
    unsigned long long res = 1; // Initialize result 
  
    x = x % p; // Update x if it is more than or 
    // equal to p 
  
    while (y > 0) { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = (res * x) % p; 
  
        // y must be even now 
        y = y >> 1; // y = y/2 
        x = (x * x) % p; 
    } 
    return res; 
} 
  
// Returns n^(-1) mod p 
unsigned long long modInverse(unsigned long long n, int p) 
{ 
    return power(n, p - 2, p); 
} 
  
// Returns nCr % p using Fermat's little 
// theorem. 
unsigned long long nCrModPFermat(unsigned long long n, 
                                 int r, int p) 
{ 
    // Base case 
    if (r == 0) 
        return 1; 
  
    // Fill factorial array so that we 
    // can find all factorial of r, n 
    // and n-r 
    unsigned long long fac[n + 1]; 
    fac[0] = 1; 
    for (int i = 1; i <= n; i++) 
        fac[i] = (fac[i - 1] * i) % p; 
  
    return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p; 
} 
int main()
{
    fio;
    int t=1;
    //cin>>t;
    while(t--)
    {
        ll s;
        cin>>s;
        ll n=s/3;
        ll sum=0;
        for(int i=1;i<=n;i++)
        {
            sum=((sum%mod)+(nCrModPFermat(s-i*3+i-1,i-1,(int)1e9+7)))%mod;
        }
        cout<<sum<<endl;
    }
}

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

int main() {
    int n;
    cin >> n;
    cout << 111 + 999 - n << endl;
    return 0;
}

/*
やっほい！
　　　　　　　やほほい！
　　　　+　　 　*
　　　 ∧∧　　. ∧∞∧　*
*　ヽ(=´ω｀)人(´ω｀*)ﾉ
　.～（ O x.） （ 　 O)～　+
。*　 　∪　　　　∪
*/

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

int main()
{
  int64_t K;
  cin >> K;
  cout << 50 << endl;
  vector<int64_t> A(50, 49 + K / 50);
  for (int i = 0; i < K % 50; i++)
  {
    A[i] += 50;
    for (int j = 0; j < 50; j++)
    {
      if (i != j)
        A[j]--;
    }
  }
  for (int i = 0; i < 50; i++)
  {
    cout << A[i];
    if (i != 49)
      cout << ' ';
  }
  cout << endl;
}

Measured memory_bytes: 3624
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;

constexpr char newl = '\n';
constexpr double eps = 1e-10;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = ((b)-1); i >=(a); i--)
#define RF0(i,b) RFO(i,0,b)
#define fi first
#define se second
#define debug(x) cout << #x << ": " << x << '\n';
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()

template<typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
template<class T> void Print(vector<T> v) {
  F0R(i, v.size()) {
    cout << v[i] << ' ';
  }
  cout << newl;
}

#if 1


// INSERT ABOVE HERE
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N;
  cin >> N;
  vector<int> as(N);
  F0R(i, N) {
    cin >> as[i];
  }

  auto kau = [&](int day, i64 &yen, i64 &kabu) {
    i64 n = yen / as[day];
    yen -= as[day] * n;
    kabu += n;
    //cout << "kau " << a << "\n";
  };
  auto uru = [&](int day, i64& yen, i64& kabu) {
    yen += as[day] * kabu;
    kabu = 0;
    //cout << "uru " << a << "\n";
  };

  vector<i64> yms(N, 0);
  vector<pair<i64, i64>> kms(N);

  i64 result = 0;
  auto dfs = [&](auto dfs, int day, i64 yen, i64 kabu)->void {

    if (day == N) {
      chmax(result, yen);
      return;
    }

    bool updated = false;
    if (yen > yms[day]) {
      yms[day] = yen;
      updated = true;
    }
    if (kabu > kms[day].first) {
      kms[day] = { kabu,yen };
      updated = true;
    }
    else if (kabu == kms[day].first && yen > kms[day].second) {
      kms[day] = { kabu,yen };
      updated = true;
    }
    if (!updated) return;


    if (day == N - 1) {
      uru(day, yen, kabu);
      dfs(dfs, day + 1, yen, kabu);
    }
    else {
      // なにもしない
      dfs(dfs, day + 1, yen, kabu);

      if (kabu) {
        if (as[day - 1] < as[day]) {
          uru(day, yen, kabu);
          dfs(dfs, day + 1, yen, kabu);
        }
      }
      else {
        if (day == 0 || as[day - 1] > as[day]) {
          kau(day, yen, kabu);
          dfs(dfs, day + 1, yen, kabu);
        }
      }
    }

  };
  dfs(dfs, 0, 1000, 0);

  cout << result;
}
#endif


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

#define Fast cin.tie(0), ios::sync_with_stdio(0)
#define All(x) x.begin(), x.end()
#define louisfghbvc int t; cin >> t; while(t--)
#define sz(x) (int)(x).size()
using namespace std;
typedef long long LL;
typedef pair<LL, LL> ii;
typedef vector<LL> vi;

template<typename T> istream& operator>>(istream &is, vector<T> &v) { for(auto &it : v) is >> it; return is; }
template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep = ""; for(const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }

void dbg_out() { cerr << "\n"; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }

const int mod = 1e9+7;
const int N = 2005;

LL s;
LL dp[N];
LL dfs(LL sum){
    if(sum >= s) return sum == s;
    if(dp[sum] != -1) return dp[sum];
    LL res = 0;
    for(int i = 3; sum+i <= s; ++i){
        res = (res+dfs(sum+i))%mod;
    }
    return dp[sum] = res;
}

void solve(){
    cin >> s;
    memset(dp, -1, sizeof dp);
    cout << dfs(0) << "\n";
}

int main()
{
    Fast;
    //louisfghbvc{
        solve();
    //}
    return 0;
}


Measured memory_bytes: 3672
//# pragma GCC optimize("Ofast,no-stack-protector")
//# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
# pragma GCC optimize("Ofast")
# pragma GCC optimization ("unroll-loops")
# include "bits/stdc++.h"
/*
# include <ext/pb_ds/tree_policy.hpp>
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/rope>
*/
std::pair<int,int> DR[] = {{-1,0},{0,1},{1,0},{0,-1},{-1,1},{-1,-1},{1,1},{1,-1}};
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define rcg(s) cout << s;exit(0)
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define all(s) s.begin(),s.end()
# define sz(x) (int)((x).size())
//# define int ll
using namespace std;

/*
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
Tree<int>tr;
*/

// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# define LOCAL
# define sim template < class c
# define ris return * this
# define dor > debug & operator <<
# define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define show(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
int gcd(int a, int b)
{
if(b) return gcd(b,a%b);
return a;
}mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

int n,a[100],b[100],c[100],sum;

int32_t main(){_
	//freopen("input","r",stdin);
	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> a[i];
	}
	for(int i = 1;i <= n;i++){
		cin >> b[i];
	}
	for(int i = 1;i < n;i++) cin >> c[i];
	for(int i = 1;i <= n;i++){
		sum += b[a[i]];
		if(a[i - 1] == a[i] - 1) sum += c[a[i] - 1];
	}
	rc(sum);
	return 0;
}











Measured memory_bytes: 256
n,a,b = map(int, input().split())
mod = 10 ** 9 + 7
ans = pow(2,n,mod) - 1
MIN = min(a,b)
MAX = max(a,b)
min_c = 1
max_c = 1
child = 1
mother = 1
for i in range(MIN):
  child = (child * (n-i)) % mod
  mother = (mother * (i+1)) % mod
min_c = (child * pow(mother,mod-2,mod)) % mod
for i in range(MIN,MAX):
  child = (child * (n-i)) % mod
  mother = (mother * (i+1)) % mod
max_c = (child * pow(mother,mod-2,mod)) % mod
ans = (ans - min_c - max_c) % mod
print(ans)


Measured memory_bytes: 3064
//#pragma Gbb optimize("Ofast") 
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<fstream>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<time.h>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;

int a[2020][2020], ans[2020];

int main()
{
	ios::sync_with_stdio(false);
	int n, x, y;
	cin >> n >> x >> y;
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++)
			if ((i <= x) && (j >= y)) a[i][j] = (j - i - 1) - (y - x - 1), ans[a[i][j]]++;
			else if ((i > x) && (i < y) && (j >= y)) a[i][j] = min(i - x + j - y, j - i - 1), ans[a[i][j]]++;
			else if ((j > x) && (j < y) && (i <= x)) a[i][j] = min(x - i + y - j, j - i - 1), ans[a[i][j]]++;
			else if ((j > x) && (j < y) && (i > x) && (i < y)) a[i][j] = min(i - x + y - j, j - i - 1), ans[a[i][j]]++;
			else a[i][j] = j - i - 1, ans[a[i][j]]++;
	for (int i = 0; i <= n - 2; i++) cout << ans[i] << endl;
	return 0;
}


Measured memory_bytes: 15360
/* Fairy dandy tickling the fancy of his lady friend */

#include <iostream>

#include <vector>

#include <algorithm>

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

#define rep(i,a,b) for(int i=int(a); i<int(b); i++)

#define rip(i,a,b) for(int i=(int)a; i>=(int)b; i--)

#define pb push_back

#define mp make_pair

#define fst first

#define snd second

#define sz(x) int(x.size())

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

#define trace(x) cerr << #x << ": " << x <<endl;



using namespace std;



typedef long long int lli;

typedef pair<lli, lli> ii;

typedef vector<int> vi;

typedef vector<ii> vii;


int mat[20][20];
int n, d; 

bool go(int i, int j){
	int val=0;
	rep(k,0,d)
		val+=(mat[i][k]-mat[j][k])*(mat[i][k]-mat[j][k]);
	int lo=1, hi=500;
	int mid;
	while(lo<=hi){
		mid=(lo+hi)>>1;
		if(mid*mid==val) return 1;
		else if(mid*mid<val) lo=mid+1;
		else hi=mid-1;
	}
	return 0;
}


int main(){

    fastio;

	cin>>n>>d;
	rep(i,0,n)
		rep(j,0,d) cin>>mat[i][j];
	int cont=0;
	rep(i,0,n)
		rep(j,i+1,n)
			if(go(i,j)) cont++;
	cout<<cont<<endl;

    return 0;

}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#define _USE_MATH_DEFINENS
#include <cmath>
using namespace std;

#define p(x) cout << x << endl;
#define el cout << endl;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, a, b;
    cin >> n >> a >> b;
    int c = n * a;
    cout << min(c, b) << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <cstdio>
#include <queue>
#include <set>
#include <algorithm>

int main(){
  
  // read input
  int N, K;
  long long int tmp;
  std::vector<long long int> h;
  
  scanf("%d", &N);
  scanf("%d", &K);
  for(int i = 0; i < N; i++){
    scanf("%lld", &tmp);
    h.push_back(tmp);
  }
  
  // sort h
  std::sort(h.begin(), h.end());
  //for(int i = 0; i < N; i++){
  //  printf("%lld\n", h[i]);
  //}
  
  // solve problem
  long long int ans = h[K-1]-h[0];
  for(int i = 0; i <= N-K; i++){
    if(h[K+i-1] - h[i] < ans){
      ans = h[K+i-1] - h[i];
    }
  }
  printf("%lld", ans);
  
  return 0;
}


Measured memory_bytes: 1400
#include<iostream>
using namespace std;
main()
{
  int n,m;
  cin>>n>>m;
  int a[n],c=0;
  for(int i=0;i<m;i++)
  {
    cin>>a[i];
    c+=a[i];
  }
  if(n-c>=0)
    cout<<n-c;
  else
    cout<<-1;
}

Measured memory_bytes: 3680
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
using namespace std;

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

int main(int argc, char ** argv) {
    int a, b;
    while (~scanf("%d%d", &a, &b)){
        int g = gcd(a, b);
        int l = a / g*b;
        printf("%d %d\n",g,l);
    }
}

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

using namespace std;

int main() {
	long a[111], n, x;
	cin >> n >> x;
	a[0] = 0;
	for (int i = 0; i < n; i++)
		cin >> a[i + 1];
	sort(a + 1, a + n + 1);
	for (int i = 0; i < n; i++)
		a[i + 1] += a[i];
	int k = upper_bound(a, a + n + 1, x) - a;
	if (k == n + 1 && a[k - 1] != x)
		k--;
	cout << k - 1 << endl;
	return 0;
}


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

int main()
{
    int n;
    cin >> n;
    double sum = 0;
    for(int i = 0; i < n; i++){
        double y;
        string s;
        cin >> y >> s;
        if(s[0] == 'J'){
            sum += y;
        }else{
            sum += y * 380000.0;
        }
    }
    cout << sum;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>/
// #include <ext/pb_ds/tree_policy.hpp>

#define pb push_back
#define mp make_pair
#define PI ( acos(-1.0) )
#define mod 1000000007LL
#define IN freopen("nocross.in","r",stdin)
#define OUT freopen("nocross.out","w",stdout)
#define FOR(i,a,b) for(i=a ; i<=b ; i++)
#define DBG printf("Hi\n")
#define INF 2000000000000000000LL
#define i64 long long int
#define eps (1e-8)
#define xx first
#define yy second
#define ln 17
#define off 2
#define SZ(z) ((int)z.size())

#define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL)


// using namespace __gnu_pbds;
using namespace std ;

// typedef tree< i64, null_type, less<i64>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

#define maxn 300005

int dp[3005][3005][2] ;

int main()
{
    int n , m ;

    scanf("%d %d",&n,&m) ;

    for(int i=0 ; i<=n ; i++) dp[0][i][0] = 1 ;

    for(int i=1 ; i<=m ; i++)
    {
        for(int r=0 ; r<=n ; r++)
        {
            for(int fl=0 ; fl<2 ; fl++)
            {
                int b = n-r ;

                int nfl ;

                if(r!=0)
                {
                    nfl = fl ;
                    if(r==1) nfl = 0 ;
                    dp[i][r][fl] = (dp[i-1][r-1][nfl] + dp[i-1][r][nfl])%mod ;
                }
                if( b!=0 )
                {
                    nfl = fl ;
                    if(r==0) nfl = 0 ;
                    dp[i][r][fl] = ( dp[i][r][fl] + dp[i-1][r][nfl])%mod ;
                    dp[i][r][fl] = ( dp[i][r][fl] + dp[i-1][r+1][nfl])%mod ;
                }
            }
        }
    }

    int ans = 0 ;

    for(int i=0 ; i<=n ; i++) ans = ( ans + dp[m][i][1] )%mod ;

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

    return 0 ;
}


Measured memory_bytes: 70656
#include<stdio.h>
int main(){
  int a,b,c;
  scanf("%d%d",&a,&b);
  c=a*b;
  if((a>=1)&&(a<=20)&&(b>=1)&&(b<=20)){
    if((a<10)&&(b<10)){
      printf("%d",c);
    }
    else
      printf("-1");
  }
  else
    printf("-1");
}

Measured memory_bytes: 128
#include<iostream>
#include<string.h>
#include<ctype.h>
#include<string>
#include<math.h>
#define pi 3.141592653589
#include<iomanip>
using namespace std;

int main(){
     
    int a,b;
    char op;
    
    cin>>a>>op>>b;
    if(op=='+')cout<<a+b<<endl;
    else cout<<a-b<<endl;
     
    return 0;
}
 

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

int k[5] = { 5,7,5,7,7 };
int main() {
	int a;
	while (cin >> a, a) {
		int b[40];
		for (int c = 0; c < a; c++) {
			string d; cin >> d;
			b[c] = d.length();
		}
		for (int i = 0; i < a; i++) {
			int x = 0, y = 0;
			for (int j = i; j < a; j++) {
				if (y + b[j] > k[x])break;
				else if (y + b[j] < k[x])y += b[j];
				else { 
					x++; y = 0;
				if (x == 5) { cout << i + 1 << endl; goto l; }
				}
			}
		}
	l:;
	}
}

Measured memory_bytes: 3132
#include<cstdio>
#include<iostream>
#include<array>
using namespace std;
array<pair<int,int>,1001> pairs;
array<array<pair<int,int>,1001>,1001> m;
int main(){
  for(int caseNo=0;;caseNo++){
    int w; scanf("%d",&w);
    if(w==0) break;
    int n; scanf("%d",&n);
    for(int i=1;i<=n;i++){
      scanf("%d,%d",&pairs[i].first,&pairs[i].second);
    }
    for(int j=0;j<=w;j++){
      m[0][j].first=0;
      m[0][j].second=0;
    }
    for(int i=1;i<=n;i++){
      for(int j=0;j<=w;j++){
	if(pairs[i].second<=j){
	  if(m[i-1][j].first>m[i-1][j-pairs[i].second].first+pairs[i].first){
	    m[i][j].first=m[i-1][j].first;
	    m[i][j].second=m[i-1][j].second;
	  }else{
	    m[i][j].first=m[i-1][j-pairs[i].second].first+pairs[i].first;
	    m[i][j].second=m[i-1][j-pairs[i].second].second+pairs[i].second;
	  }
	}else{
	  m[i][j].first=m[i-1][j].first;
	  m[i][j].second=m[i-1][j].second;
	}
      }
    }
    printf("Case %d:\n%d\n%d\n",caseNo+1,m[n][w].first,m[n][w].second);
  }
}

Measured memory_bytes: 9008
N,K = [int(i) for i in input().split()]
H = [int(i) for i in input().split()]

dp = [0]*N
dp[1] = abs(H[1]-H[0])

for i in range(2,N):
    tmp = 10**9
    for j in range(1,min(i,K)+1):
        tmp = min(tmp,abs(H[i]-H[i-j])+dp[i-j])
    dp[i] = tmp

print(dp[-1])


Measured memory_bytes: 52448
def split(a): 
    return [char for char in a]    
pred=input()
real=input()
x=split(pred)
y=split(real)
c=0
if x[0]==y[0]:
    c+=1
if x[1]==y[1]:
    c+=1
if x[2]==y[2]:
    c+=1
print(c)

Measured memory_bytes: 9124
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll LINF=1LL<<60;
const int INF=1<<30;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
	string s;cin>>s;
	if (s == "ABC"){
		cout << "ARC" << endl;
	}
	else{
		cout << "ABC" << endl;
	}
	return 0;
}

Measured memory_bytes: 3624
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<int, P> P1;

//#define int long long

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i, x) for (int i = 0; i < x; i++)
#define rep1(i, x) for (int i = 1; i <= x; i++)
#define rrep(i, x) for (int i = x - 1; i >= 0; i--)
#define rrep1(i, x) for (int i = x; i > 0; i--)
#define sor(v) sort(v.begin(), v.end())
#define rev(s) reverse(s.begin(), s.end())
#define lb(vec, a) lower_bound(vec.begin(), vec.end(), a)
#define ub(vec, a) upper_bound(vec.begin(), vec.end(), a)
#define uniq(vec) vec.erase(unique(vec.begin(), vec.end()), vec.end())
#define mp1(a, b, c) P1(a, P(b, c))

const int INF = 100000000;
const int M = 100000000;
const int dir_4[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const int dir_8[8][2] = {{1, 0},  {1, 1},   {0, 1},  {-1, 1},
                         {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};

/*----------------------------------------------/
/- char         : %c  | char *       : %s  | short        : %hd
/- int          : %d  | long         : %ld | long long    : %lld
/- unsigned short:%hu | unsigned int : %u  | unsigned long: %lu
/- u_long long  : %llu| (octal)      : %o  | (hexadecimal): %x
/- float        : %f  | double       : %lf |
/----------------------------------------------*/

/*----------------------------------------------/
/- INT_MAX, LONG_MAX   : 1<<15 = 2.1*pow(10, 9)       (= 2147483647)
/- UINT_MAX, ULONG_MAX : 1<<16 = 4.2*pow(10, 9)       (= 4294967295)
/- LLONG_MAX           : 1<<63 = 9.2*pow(10, 18)      (= 9223372036854775807)
/- ULLONG_MAX          : 1<<64 = 1.8*pow(10, 19)      (= 18446744073709551615)
/----------------------------------------------*/

int main() {
    int n, q;
    char s[100010];
    int l[100010], r[100010];
    cin >> n >> q;
    cin >> s;
    rep(i, q) cin >> l[i] >> r[i];

    int map[100010];
    rep(i, n) {
        if (i == 0) {
            map[i] = 0;
        } else {
            if (s[i] == 'C' && s[i - 1] == 'A') {
                map[i] = map[i - 1] + 1;
            } else {
                map[i] = map[i - 1];
            }
        }
    }
    rep(i, q) {
        int ret = map[r[i] - 1] - map[l[i] - 1];
        cout << ret << endl;
    }

    return 0;
}

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

int main() {
	int N;
  	cin>>N;
  	vector<string> a(N);
  	int max=1;
  	int count=0;
  
  	for(int i=0;i<N;i++){
     	 cin>>a.at(i);
    }
  
  	sort(a.begin(),a.end());
  	
  
  	for(int i=0;i<N-1;i++){
      	if(a.at(i)==a.at(i+1)){
         	count++; 
        }
      	else{
         	count=0; 
        }
      	
      	if(max<=count){
         	max=count+1;
        }
     	 
    }
      	
  	count=0;
  
  	if(max!=1){
  		for(int i=0;i<N-1;i++){
           if(a.at(i)==a.at(i+1)){
          		count++; 
         	}
      	 	else{
          		count=0; 
         	}
      	
      		if(max==count+1){
         		cout<<a.at(i)<<endl;
        	}
    	}
    }
  	else{
     	for(int i=0;i<N;i++){
         	cout<<a.at(i)<<endl; 
        }
    }
  
  	
}


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

int main(){
    long long N; cin >> N;
    long long ans = (1LL << 50);
    for(int i = 1; i <= sqrt(N); ++i){
        if(N % i == 0){
            ans = min(ans, N / i + i - 2);
        }
    }
    cout << ans << endl;
}


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

signed main(){
  lint N; cin >> N;
  vector<lint> a(N), sum(N, 0);
  for(lint i = 0; i < N; i++){
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  for(lint i = 0; i < N; i++){
    if(i == 0) sum[i] = a[i];
    else sum[i] = sum[i - 1] + a[i];
  }
  lint ans = N;
  for(lint i = N - 1; i >= 1; i--){
    if(a[i] > 2 * sum[i - 1]){
      ans = N - i; break;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 1792
n, x = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
total = sum(a)
ans = 0
if x == total:
    ans = n
elif x > total:
    ans = n - 1
else:
    for v in a:
        x -= v
        if x < 0:
            break
        ans += 1
print(ans)

Measured memory_bytes: 3064
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 210
#define INF 0x3FFFFFFF
using namespace std;
vector<int> a[MAXN],rev[MAXN],r[MAXN];
int n,m,s,t,d[MAXN],g[MAXN];
int dfs(int x,int f){
    if(x==t)
	    return f;
    for(int i=0;i<a[x].size();i++)
        if(r[x][i]>0&&d[a[x][i]]+1==d[x]){
            int res=dfs(a[x][i],min(f,r[x][i]));
            if(res>0){
	            r[x][i]-=res;
	            r[a[x][i]][rev[x][i]]+=res;
            	return res;
        	}
        }
    int les=MAXN;
    g[d[x]]--;
    if(g[d[x]]==0){
        d[s]=n;
        return 0;
    }
    for(int i=0;i<a[x].size();i++)
        if(r[x][i]>0)
            les=min(les,d[a[x][i]]);
    d[x]=les+1;
    g[d[x]]++;
    return 0;
}
int isap(){
    int res=0;
    g[0]=n;
    while(d[s]<n){
	    res+=dfs(s,INF);
    }
    return res;
}
int u,v,w;
int xa[MAXN],xb[MAXN],ya[MAXN],yb[MAXN];
void addlink(int x,int y,int val){
	a[x].push_back(y);
	a[y].push_back(x);
	rev[x].push_back(a[y].size()-1);
	rev[y].push_back(a[x].size()-1);
	r[x].push_back(val);
	r[y].push_back(0);
}
int main(){
    SF("%d",&n);
	for(int i=0;i<n;i++)
		SF("%d%d",&xa[i],&ya[i]);
	for(int i=0;i<n;i++)
		SF("%d%d",&xb[i],&yb[i]);
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			if(xa[i]<xb[j]&&ya[i]<yb[j])
				addlink(i,j+n,1);
    s=2*n;
    t=2*n+1;
    for(int i=0;i<n;i++){
    	addlink(s,i,1);
    	addlink(i+n,t,1);
    }
	n=2*n+1;
    PF("%d",isap());
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

ll gcd(ll x, ll y) {
  if(x > y)
    return gcd(y, x);
  else if(x == 0)
    return y;
  else
    return gcd(y % x, x);
}

map<ll, int> res;
void factorization(ll N) {
  if(N == 1 || N == 0) return;
  ll n = N;
  ll i = 2;
  while(n >= i * i) {
    while(n % i == 0) {
      if(res.count(i)) res[i]++;
      else res[i] = 1;
      n /= i;
    }
    if(i > 2) i += 2;
    else i++;
  }
  if(n != 1) res[n] = 1;
}

int main() {
  ll A, B;
  cin >> A >> B;
  ll g = gcd(A, B);
  factorization(g);
  cout << res.size()+1 << endl;
  return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a[10];
bool ha[1100000];
void DFS(int x)
{
    if(x<100000)    ha[x]=true;
    else return ;
    for(int i=0;i<=9;i++)   if(!a[i])   DFS(x*10+i);
}

int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=0;i<k;i++){
        int x;cin>>x;
        a[x]++;
    }
    for(int i=1;i<=9;i++){
        if(!a[i])    DFS(i);
    }
    for(int i=n;;i++){
        if(ha[i]){
            cout<<i<<endl;
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n; cin>>n;
  int a[n];
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  long long int ans=0;
  long long int step=0;
  for(int i=0;i<n-1;i++){
    if(step+a[i]>a[i+1]){
      step=-a[i+1]+step+a[i];
      ans+=step;
    }
    else{
      step=0;
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 4320
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

N = int(input())
SN = sum(int(x) for x in str(N))
if N % SN:
    print("No")
else:
    print("Yes")


Measured memory_bytes: 7848
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
int main(){
  string s,fr,en;
  int tf=1,q;
  cin>>s>>q;
  rep(i,q){
    int t,f;
    char c;
    cin>>t;
    if(t==1){
      tf*=-1;
    }
    else{
      cin>>f>>c;
      (f==1?f=1:f=-1);
      (tf*f==1?fr=c+fr:en=en+c);
    }
  }
  if(tf==-1){
    reverse(s.begin(),s.end());
    reverse(fr.begin(),fr.end());
    reverse(en.begin(),en.end());
    cout<<en<<s<<fr<<endl;
  }else
  cout<<fr<<s<<en<<endl;
}

Measured memory_bytes: 1160
def union_find():
    # グラフの連結していないグループの数をunion_findで求める
    def get_parent(node):
        if par[node] == -1:
            return node
        else:
            par[node] = get_parent(par[node])
            return par[node]

    def merge(i, j):
        i = get_parent(i)
        j = get_parent(j)
        if i != j:
            par[j] = i
        return

    n, m = map(int, input().split())
    xyz = [list(map(int, input().split())) for _ in range(m)]
    par = [-1] * n
    for x, y, z in xyz:
        merge(x-1, y-1)
    print(par.count(-1))

union_find()

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

namespace AtCoder.Contest.A
{
	static class Program
	{
		public static void Main(string[] args)
		{
			var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
			Console.SetOut(sw);

			var cin = new Scanner();

			var s = cin.ArrayInt(3);
			Array.Sort(s);
			var t = new int[] { 5, 5, 7 };
			bool ok = true;
            for (int i = 0; i < 3; i++)
            {
				if (s[i] != t[i]) ok = false;
            }
            if (ok) Console.WriteLine("YES");
            else Console.WriteLine("NO");

			Console.Out.Flush();
		}
	}

	class Scanner
	{
		string[] s;
		int i;

		char[] cs = new char[] { ' ' };

		public Scanner()
		{
			s = new string[0];
			i = 0;
		}

		public string Next()
		{
			if (i < s.Length) return s[i++];
			string st = Console.ReadLine();
			while (st == "") st = Console.ReadLine();
			s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
			if (s.Length == 0) return Next();
			i = 0;
			return s[i++];
		}

		public int NextInt()
		{
			return int.Parse(Next());
		}

		public int[] ArrayInt(int N, int add = 0)
		{
			int[] Array = new int[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = NextInt() + add;
			}
			return Array;
		}

		public long NextLong()
		{
			return long.Parse(Next());
		}

		public long[] ArrayLong(int N, long add = 0)
		{
			long[] Array = new long[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = NextLong() + add;
			}
			return Array;
		}

		public double NextDouble()
		{
			return double.Parse(Next());
		}

		public double[] ArrayDouble(int N, double add = 0)
		{
			double[] Array = new double[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = NextDouble() + add;
			}
			return Array;
		}
	}
}

Measured memory_bytes: 11220
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPS(i,n) for(int i=1, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
using namespace std;
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; }
template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val) { std::fill( (T*)array, (T*)(array+N), val ); }
#define INF 1e9
#define PI (acos(-1))
#define mod (int)1e9+7
int main() {
    int n;
    cin>>n;
    vector<int> a(n);
    REP(i,n)cin>>a[i];
    bool f=true;
    REP(i,n){
        if(a[i]%2==0){
            if(a[i]%3!=0&&a[i]%5!=0){
                f=false;
                break;
            }
        }
    }
    if(f)cout<<"APPROVED\n";
    else cout<<"DENIED\n";
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
typedef long long ll;
int main(){
	ll n,m;
	cin>>n>>m;
	if(n==1||m==1)
		cout<<"1";
	else if(n%2==0)
		cout<<n*m/2;
	else
		cout<<(n-1)*m/2+(m+1)/2;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

/*

??´?§?????§???¢
3????????£?????´??°?????\?????????????????????????????????3?????¨??????????§???¢?????´?§?????§???¢??§????????´????????? YES ??????????????´????????? NO ??¨????????????????????°?????????????????????????????????

Input
?????°?????????????????????????????????????????????1?????????????????????????????°??? N ?????????????????????????¶??????? N ????????\?????????????????????????????????3????????´??°???1????????????????????§????????????????????????????????????

Constraints
1 ? 1???????????? ? 1,000
N ? 1,000
Output
??????????????????????????¨??????YES ????????? NO ???1??????????????????????????????

*/


int main( void )
{
	int a, b, c, w, num, i;
	
	scanf( "%d", &num );
	
	for ( i = 0 ; i < num ; i++) {
		scanf( "%d %d %d", &a, &b, &c );
		if ( a < b ) {
			w = a;
			a = b;
			b = w;
		}
		
		if ( a < c ) {
			w = a;
			a = c;
			c = w;
		}
		
		if ( ( a * a ) == ( ( b * b ) + ( c * c ) ) ) {
			printf( "YES\n" );
		}
		else {
			printf( "NO\n" );
		}
	}
	
	return 0;
}

Measured memory_bytes: 580
#include<iostream>
#include<algorithm>
#include<set>

using namespace std;

struct S{
  int g[4][4];
  int y,x;
  bool operator<(S s)const{
    return lexicographical_compare(g[0],g[4],s.g[0],s.g[4]);
  }
};

int main(){
  for(int N;cin>>N,N;){
    set<S> d[366];
    S s{{},1,1};
    d[0].insert(s);
    for(int i=0;i<N;i++){
      int s[16];
      for(int j=0;j<16;j++){
	cin>>s[j];
      }
      for(auto e:d[i]){
	for(int k=0;k<3;k++){
	  for(int l=0;l<3;l++){
	    if(k!=e.y&&l!=e.x||i==0&&(k!=1||l!=1))continue;
	    auto cs=e;
	    cs.y=k;
	    cs.x=l;
	    for(int m=0;m<4;m++){
	      for(int n=0;n<4;n++){
		cs.g[m][n]++;
	      }
	    }
	    for(int m=0;m<2;m++){
	      for(int n=0;n<2;n++){
		int y=k+m;
		int x=l+n;
		cs.g[y][x]=0;
		if(s[y*4+x])goto next;
	      }
	    }
	    if(*max_element(cs.g[0],cs.g[4])>=7)goto next;
	    d[i+1].insert(cs);
	  next:
	    ;
	  }
	}
      }
    }
    cout<<!d[N].empty()<<endl;
  }
}

      

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

int main() {
  int n,k;
  int r,s,p;
  string t;
  cin>>n>>k>>r>>s>>p>>t;
  vector<char> vec(n);
for (int i = 0; i < n; i++) {
  if(t.at(i)=='r'){
    vec.at(i)='p';
  }
  else if(t.at(i)=='s'){
    vec.at(i)='r';
}
  else{vec.at(i)='s';
      }
}
  for (int i = 0; i < n-k; i++) {
    if(vec.at(i)==vec.at(i+k)){
      vec.at(i+k)='q';
    }
  }
  
  int ans =0;
  cin >>ans;
  for (int i = 0; i < n; i++) {
    if(vec.at(i)=='p'){
      ans+=p;
    }
    else if(vec.at(i)=='r'){
      ans+=r;
    }
    else if(vec.at(i)=='s'){
      ans+=s;
    }
  }
  cout<<ans<<endl;
 
}

    
    
    
  
  



Measured memory_bytes: 512
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, m, n) for(int i=(m); i<(n); ++i)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define Cout(x) cout << (x) << endl
#define dump(x) cerr << #x << " = " << (x) << endl;
typedef long long LL;
typedef vector<int> VI;
typedef vector<long long> VL;
typedef vector<string> VS;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
const int inf = (int)1e9;
const long long mod = (long long)1e9 + 7;
const double pi = acos(-1.0);

template <class T>void Sort(vector<T> & a) { sort(a.begin(), a.end()); }
template <class T>void ReSort(vector<T>& a) { sort(a.rbegin(), a.rend()); }
template <class T>void Reverse(vector<T>& a) { reverse(a.begin(), a.end()); }
template <class T>void Unique(vector<T>& a) { a.erase(unique(a.begin(), a.end()), a.end()); }
template <class T>T Sum(vector<T> a, T init = 0) { return accumulate(a.begin(), a.end(), init); }

//INPUT//
void CINPUT() {}
template<class H, class ...T> void CINPUT(H&& h, T&& ...t) { cin >> h; CINPUT(forward<T>(t)...); }
#define in(...) int __VA_ARGS__; CINPUT(__VA_ARGS__);
#define In(T,...) T __VA_ARGS__; CINPUT(__VA_ARGS__);
#define Vin(T,name,n) int n; cin>>n; vector<T> name(n); rep(i,n)cin>>name[i];
#define VIn(T,name,n) vector<T> name(n); rep(i,n)cin>>name[i];

//OUTPUT//
void print() { cout << endl; }
template <class H> void print(H&& h) { cout << h << endl; }
template <class H, class... T> void print(H&& h, T&& ... t) { cout << h << " "; print(forward<T>(t)...); }
template<class T>void out(T n) { cout << n << endl; }
template<class T>void out(vector<T> a, string sep = " ", string end = "\n") { for (int i = 0; i < (int)a.size(); ++i)cout << a[i] << (i == (int)a.size() - 1 ? end : sep); }
void yes(bool f) { puts(f ? "yes" : "no"); }
void Yes(bool f) { puts(f ? "Yes" : "No"); }
void YES(bool f) { puts(f ? "YES" : "NO"); }
void poss(bool f) { puts(f ? "possible" : "impossible"); }
void Poss(bool f) { puts(f ? "Possible" : "Impossible"); }
void POSS(bool f) { puts(f ? "POSSIBLE" : "IMPOSSIBLE"); }

int main() {
	Vin(char, s, n);
	Sort(s);
	Unique(s);
	puts(sz(s) == 3 ? "Three" : "Four");
}

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

int main(){
    int n, m;
    cin >> n;
    m = n;

    int sum = 0;
    while(1){
        sum += m % 10;
        m /= 10;
        if(m < 1) break;
    }

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

    return 0;

}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod=1e9+7;
int n,m,dp[3010][3010];
void DP(int n){
	memset(dp,0,sizeof(dp));
	for(int i=0;i<=n;i++)
		dp[0][i]=1;
	for(int i=0;i<m;i++){
		for(int j=0;j<=n;j++){
			if(j<n){
				dp[i+1][j+1]+=dp[i][j];
				if(dp[i+1][j+1]>=mod)
					dp[i+1][j+1]-=mod;
				dp[i+1][j]+=dp[i][j];
				if(dp[i+1][j]>=mod)
					dp[i+1][j]-=mod;
			}
			if(j>0){
				dp[i+1][j-1]+=dp[i][j];
				if(dp[i+1][j-1]>=mod)
					dp[i+1][j-1]-=mod;
				dp[i+1][j]+=dp[i][j];
				if(dp[i+1][j]>=mod)
					dp[i+1][j]-=mod;
			}
		}
	}
	return;
}
int getans(){
	DP(n);
	int ret=0;
	for(int i=0;i<=n;i++){
		ret+=dp[m][i];
		if(ret>=mod)
			ret-=mod;
	}
	DP(n-1);
	for(int i=0;i<n;i++){
		ret-=dp[m][i];
		if(ret<0)
			ret+=mod;
	}
	return ret;
}
int main(){
	scanf("%d%d",&n,&m);
	printf("%d",getans());
	return 0;
}

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


void solve(long long N, long long M, long long C, std::vector<long long> B, std::vector<std::vector<long long>> A){
	int ans = 0;
	for(int i = 0;i < N;++i){
		int cnt = C;
		for(int q = 0;q < M;++q){
			cnt += A[i][q] * B[q];
		}
		if(cnt > 0) ans++;
	}
	cout << ans << endl;
	return;
}

// Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    long long C;
    scanf("%lld",&C);
    std::vector<long long> B(M);
    for(int i = 0 ; i < M ; i++){
        scanf("%lld",&B[i]);
    }
    std::vector<std::vector<long long>> A(N, std::vector<long long>(M));
    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j < M ; j++){
            scanf("%lld",&A[i][j]);
        }
    }
    solve(N, M, C, std::move(B), std::move(A));
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;

/*
<url:https://code-festival-2017-qualc.contest.atcoder.jp/tasks/code_festival_2017_qualc_c>
問題文============================================================
 問題文
 英小文字のみからなる文字列 s があります。
 すぬけ君は、次の操作を繰り返し行うことができます。
 
 s の任意の位置 (先頭および末尾を含む) をひとつ選び、英小文字 x をひとつ挿入する。
 すぬけ君の目標は、s を回文にすることです。
 すぬけ君の目標が達成可能か判定し、達成可能ならば必要な操作回数の最小値を求めてください。
 
 注釈
 回文とは、前後を反転しても変わらない文字列のことです。
 例えば、a, aa, abba, abcba は回文ですが、ab, abab, abcda は回文ではありません。
 
 制約
 1≤|s|≤10^5
 s は英小文字のみからなる。
=================================================================

解説=============================================================

 x は自由に挿入可能だが、それ以外の文字は挿入することができない
 
 よって、 x を無視した文字列がすでに回文になっていなければ文字列を回文にすることができない
 
 よって、xを無視して回文かどうかを調べればいい
 
 あとは、いくつ x を挿入すればいいかに関しては、
 今度は x を無視せずに調べていき、 xが出てきてかつ、そのxがすでに回文の一部でなければ
 xを挿入 => 操作回数＋１
 して行けばいい
 
================================================================
*/
ll solve(){
    string s; cin >> s;
    ll ret = 0;
    
    ll l = 0, r = s.length()-1;
    while(l <= r){
        if(s[l] == s[r]){
            l++; r--;
        }else{
            if(s[l] == 'x'){
                l++; ret++;
                continue;
            }
            if(s[r] == 'x'){
                r--; ret++;
                continue;
            }
            return -1;
        }
    }
    return ret;
}
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    cout << solve() << endl;
	return 0;
}


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

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
    out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

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

    ll n;
    cin >> n;
    vector<ll> v(n), c(n);
    REP(i, n) cin >> v[i];
    REP(i, n) cin >> c[i];

    ll ret = 0;
    REP(i, n) {
        if(v[i] > c[i]) ret += v[i] - c[i];
    }
    cout << ret << endl;

    return 0;
}


Measured memory_bytes: 256
N, M = map(int, input().split())
xyz = []
for i in range(N):
    tmp = list(map(int, input().split()))
    xyz.append(tmp)
    
ans = 0
for i in range(6):
    tmp_xyz = xyz
    sum_x = 0
    sum_y = 0
    sum_z = 0
    if i == 0:
        tmp_xyz = sorted(tmp_xyz, reverse=True, key=lambda x: x[0] + x[1] + x[2])
        for j in range(M):
            sum_x += tmp_xyz[j][0]
            sum_y += tmp_xyz[j][1]
            sum_z += tmp_xyz[j][2]
        tmp_ans = abs(sum_x) + abs(sum_y) + abs(sum_z)
        ans = max(ans, tmp_ans)
    elif i == 1:
        tmp_xyz = sorted(tmp_xyz, reverse=True, key=lambda x: (-1)*x[0] + x[1] + x[2])
        for j in range(M):
            sum_x += tmp_xyz[j][0]
            sum_y += tmp_xyz[j][1]
            sum_z += tmp_xyz[j][2]
        tmp_ans = abs(sum_x) + abs(sum_y) + abs(sum_z)
        ans = max(ans, tmp_ans)
    elif i == 2:
        tmp_xyz = sorted(tmp_xyz, reverse=True, key=lambda x: x[0] + (-1)*x[1] + x[2])
        for j in range(M):
            sum_x += tmp_xyz[j][0]
            sum_y += tmp_xyz[j][1]
            sum_z += tmp_xyz[j][2]
        tmp_ans = abs(sum_x) + abs(sum_y) + abs(sum_z)
        ans = max(ans, tmp_ans)
    elif i == 3:
        tmp_xyz = sorted(tmp_xyz, reverse=True, key=lambda x: x[0] + x[1] + (-1)*x[2])
        for j in range(M):
            sum_x += tmp_xyz[j][0]
            sum_y += tmp_xyz[j][1]
            sum_z += tmp_xyz[j][2]
        tmp_ans = abs(sum_x) + abs(sum_y) + abs(sum_z)
        ans = max(ans, tmp_ans)
    elif i == 4:
        tmp_xyz = sorted(tmp_xyz, reverse=True, key=lambda x: (-1)*x[0] + (-1)*x[1] + x[2])
        for j in range(M):
            sum_x += tmp_xyz[j][0]
            sum_y += tmp_xyz[j][1]
            sum_z += tmp_xyz[j][2]
        tmp_ans = abs(sum_x) + abs(sum_y) + abs(sum_z)
        ans = max(ans, tmp_ans)
    elif i == 5:
        tmp_xyz = sorted(tmp_xyz, reverse=True, key=lambda x: (-1)*x[0] + x[1] + (-1)*x[2])
        for j in range(M):
            sum_x += tmp_xyz[j][0]
            sum_y += tmp_xyz[j][1]
            sum_z += tmp_xyz[j][2]
        tmp_ans = abs(sum_x) + abs(sum_y) + abs(sum_z)
        ans = max(ans, tmp_ans)
    elif i == 6:
        tmp_xyz = sorted(tmp_xyz, reverse=True, key=lambda x: x[0] + (-1)*x[1] + (-1)*x[2])
        for j in range(M):
            sum_x += tmp_xyz[j][0]
            sum_y += tmp_xyz[j][1]
            sum_z += tmp_xyz[j][2]
        tmp_ans = abs(sum_x) + abs(sum_y) + abs(sum_z)
        ans = max(ans, tmp_ans)
    elif i == 7:
        tmp_xyz = sorted(tmp_xyz, reverse=True, key=lambda x: (-1)*x[0] + (-1)*x[1] + (-1)*x[2])
        for j in range(M):
            sum_x += tmp_xyz[j][0]
            sum_y += tmp_xyz[j][1]
            sum_z += tmp_xyz[j][2]
        tmp_ans = abs(sum_x) + abs(sum_y) + abs(sum_z)
        ans = max(ans, tmp_ans)
        
print(ans)

Measured memory_bytes: 3408
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
#define task "tst"
using namespace std;
const ll N = 3e6 + 9;
const ll mod = 1e9 + 7;
typedef pair<ll,ll> LL;
ll n,i,cnt,cnt1;
string s;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        //freopen(task".out", "w", stdout);
    }
    cin>>n>>s;
    s = " " + s;
    for (i = 1;i <= n;i++) if (s[i] == 'R') cnt++;
    for (i = 1;i <= cnt;i++) if (s[i] == 'R') cnt1++;
    cout<<cnt - cnt1;
}



Measured memory_bytes: 3876
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <vector>

static const int IINF = 1 << 30;
static const long long LINF = 1LL << 60;
static const long long MOD = 1.0e+9 + 7;

template <typename T> std::vector<T> vectors(std::size_t n, T val) {
  return std::vector<T>(n, val);
}

template <typename T, typename... Args>
auto vectors(std::size_t n, Args... args) {
  return std::vector<decltype(vectors<T>(args...))>(n, vectors<T>(args...));
}

template <class T> inline bool chmin(T &a, const T &b) {
  return (a > b) ? a = b, true : false;
}

template <class T> inline bool chmax(T &a, const T &b) {
  return (a < b) ? a = b, true : false;
}

template <class T> inline void chadd(T &a, const T &b) { a += b, a %= MOD; }

int main() {
  // Input
  int A, B;
  std::cin >> A >> B;

  // Main
  int res = 0;
  if (A > B)
    res += A--;
  else
    res += B--;

  if (A > B)
    res += A--;
  else
    res += B--;

  // Output
  std::cout << res << std::endl;

  return 0;
}


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

int main()
{
    string s1,s2;
    int ans=0;
    cin>>s1>>s2;
    for(int i=0;i<3;i++)
        if(s1[i]==s2[i])
            ++ans;
        cout<<ans;
    return 0;
}



Measured memory_bytes: 3544
N = int(input())
a_s = [int(x) for x in input().split()]

a_s.sort()
a_s.reverse()
alice = 0
bob = 0
for i, a in enumerate(a_s):
    if i % 2 == 0:
        alice += a
    else:
        bob += a
ans = alice - bob

print(ans)


Measured memory_bytes: 3060