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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())

// {{{
template<typename T>
void printmatrix(vector<vector<T> > ar){
    for (int i = 0; i < (int)ar.size(); i++) {
        for (int j = 0; j < (int)ar[0].size(); j++) {
            cout << ar[i][j];
        }
        cout << endl;
    }
}

template<typename T>
void printvector(vector<T> vec){
    for (int i = 0; i < (int)vec.size(); i++) {
        cout << vec[i] << endl;
    }
}

template<typename T>
void unique(vector<T>& vec){
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
}

template<typename T>
vector<T> cumsum(vector<T> vec){
    vector<T> newvec((T)vec.size());
    int tmp = 0;
    for (int i = 0; i < (int)vec.size(); i++) {
        tmp += vec[i];
        newvec[i] = tmp;
    }

    return newvec;
}

template<typename T>
T digitsum(T x){
    T y=0;
    while(x){
        y += x % 10;
        x /= 10;
    }

    return y;
}

template<typename T>
T gcd(T x, T y){
    if (x == 0 || y == 0) {
        return 0;
    }

    while (x != y){
        if (x > y) {
            x -= y;
        }else{
            y -= x;
        }
    }
    return x;
}

double log10(double x){
    return log(x) / log(10);
}


// } }}
/* vim:set foldmethod=marker: */

void solve(){
    string s;
    ll k;
    cin >> s >> k;
    k--;
    //
    // ll idx=0;
    // vector<vector<ll>> v((ll)s.length(), vector<ll>(2,0));
    // for (int i = 0; i < (int)s.length(); i++) {
    //     if (s[i] == '1') {
    //         v[i][0] = idx;
    //         v[i][1] = idx;
    //         idx++;
    //     }else{
    //         v[i][0] = idx;
    //         v[i][1] = (ll)pow((ll)atoi(&s[i]), 5*pow(10, 15));
    //         idx = v[i][1] + 1;
    //     }
    // }
    //
    // for (int i = 0; i < (int)s.size(); i++) {
    //     cout << v[i][0] << " " << v[i][1] << endl;
    // }
    // cout << log10(2) << endl;

    char ans='1';
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] != '1' && i <= k) {
            ans = s[i];
            break;
        }
    }

    cout << ans << endl;
    return;
}

int main(int argc, char const* argv[])
{
    solve();
    return 0;
}

// sortの仕方
// int a[N];
// array<int,N> ar;
// vector<int> v;
//
// sort(a, a+N); // 配列
// sort(ar.begin(), ar.end()); // array
// sort(v.begin(), v.end()); // vector 昇順
// sort(v.begin(), v.end(), greater<int>()); // 降順

// Template
// template <class T>
// T foomax(T x, T y){
//   if (x > y){
//     return x;
//   }else{
//     return y;
//   }
// }

// string を int に変換 stoi("1010")
// int を string に変換 to_string(1010)


// map の key, value を全て抜き出す。
// for (auto itr = mp.begin(); itr != mp.end(); itr++) {
//     cout << "key" << itr->first << " value" << itr->second << endl;
// }

// 文字列の検索
// string s="abc";
// if (s.find('d') == string::npos){
//     cout << "find" << endl;
// }else{
//     cout << "not find" << endl;
// }


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define sz(x) (int)x.size()
#define end "\n"
#define all(x) (x).begin(), (x).end()
#define Red ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i, n) for(int i =0 ; i < n; ++i)
#define Rep(i,a,b) for(int i=a;i<=b;i++)
#define pii pair < int, int >
typedef vector<int> vi;
typedef  long long ll;
const int inf = int(1e9);
const int mod =1e9+7;
const int N = (int)2e5 + 5;


void solve(){
	int a[3];
	cin>>a[0]>>a[1]>>a[2];
	sort(a,a+3);
	if(a[0]==5 && a[1]==5 && a[2]==7)cout<<"YES";
	else cout<<"NO";
}
int main(){
	Red;
	int t=1;
	//cin>>t;
	while(t--)
	solve();
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define mp make_pair
#define fast ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define ff first
#define ss second
#define INF (ll) 1e9
#define tt ll testcase; cin>>testcase; while(testcase--)
 
int main(){
	fast;
	ll n;
	cin>>n;
	ll h[n];
	for(ll i=0; i<n; i++){
		cin>>h[i];
	}
	ll dp[n];
	dp[0]=0;
	dp[1]=abs(h[1]-h[0]);
	for(ll i=2 ;i<n; i++){
		dp[i] = min(dp[i-1] + abs(h[i]-h[i-1]), dp[i-2] + abs(h[i]-h[i-2]));
		//cout<<dp[i]<<"  ";
	}
	cout<<dp[n-1];
}

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

int F(ll A, ll B)
{
  int countA = 0, countB = 0;
  while(A > 0){
    A /= 10;
    countA++;
  }
  while(B > 0){
    B /= 10;
    countB++;
  }
  return max(countA, countB);
}

int main()
{
  ll N; cin >> N;
  int n = sqrt(N);
  int ans = 12;
  rep(i,n){
    if(N % i == 0)
    {
      ll j = N / i;
      ans = min(F(i,j),ans);
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<set>
#define long long ll
using namespace std;


int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	int t1=(a+d-1)/d,t2=(c+b-1)/b;
	if(t1>=t2)cout<<"Yes";
	else cout<<"No";
    return 0;
}



Measured memory_bytes: 3636
#include <bits/stdc++.h>
// #include <boost/multiprecision/cpp_int.hpp>
#define ll long long
#define llu unsigned long long
#define ld long double
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define PI 3.14159265
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define deb(x) cerr << ">> " << #x << " : " << x << "\n"
#define endl '\n'
#define ff first
#define ss second
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * b) / __gcd(a, b)
#define DESYNC ios::sync_with_stdio(0); cin.tie(0);
#define print(a) for(auto x : a) cout << x << " "; cout << endl;

using namespace std;


const ll inf = 1e9 + 42;

const ll M = 998244353;

ll power(ll x, ll y) {
	if (y == 0) return 1;
	if (y & 1) return (x * power(x, y - 1));
	ll t = power(x, y / 2);
	return (t * t);
}

const ll MAX = 1e5 + 5;

// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

ll dp[MAX];

void ahShitHereWeGoAgain()
{
	ll n, k;
	cin >> n >> k;
	vector<ll> a(n);
	for(ll i = 0; i < n; i++)
		cin >> a[i];
	memset(dp, inf, sizeof(dp));

	dp[0] = 0;
	dp[1] = abs(a[1] - a[0]); 
	deb(dp[1]);

	for(ll i = 2; i < n; i++)
	{
		for(ll j = 1; j <= min(i, k); j++)
		{
			dp[i] = min(dp[i - j] + abs(a[i] - a[i - j]), dp[i]);
		}
	}
	deb(dp[2]);
	cout << dp[n - 1] << endl;
}

int main()
{
	DESYNC	
	ll t = 1;
	// cin >> t;
	while (t--)
		ahShitHereWeGoAgain();
	return 0;
}



Measured memory_bytes: 1792
#include<string>
#include<iostream>
#include <algorithm>
#include<vector>
#include<functional>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <numeric>
#include <math.h>
#define ll long long 
#define PI 3.14159265358979323846
#define rep(i,n) for(ll i=0;i<(ll)n;i++)
using namespace std;



int main() {
    string S;
    cin >> S;
    vector<char> A(3);
    rep(i, 3) A[i] = S[i];
    rep(i, 3) cout << A[i];
    cout << endl;
    return 0;
 }


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

#define IO ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define m(a,b) memset(a,b,sizeof(a))
#define rep(i,n) for(int i=1;i<=n;i++)
typedef long long ll;
const int MAXN=1e4+10;

int main(){
	IO;
	int n,m,x;
	cin>>n>>m>>x;
	int a[105],vis[105];
	m(vis,0);
	for(int i=1;i<=m;i++) cin>>a[i],vis[a[i]]=1;
	int ans1=0,ans2=0;
	for(int i=x;i<=n;i++)
		if (vis[i]) ans1++;
	for(int i=x;i>=0;i--)
		if (vis[i]) ans2++;
	cout<<min(ans1,ans2)<<'\n';
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 4333;
int n,m,a[N],b[N],fa[N],dep[N],dl[N],dr[N],num;Vi e[N];
bool vis[N];
struct Line{
	int s,t,lca;Vi pos;//x -x
}c[N];int len;
int LCA(int u, int v){
	while(u!=v){
		if(dep[u]<dep[v])swap(u,v);u=fa[u];
	}
	return u;
}
void rev(Line &a){
	swap(a.s,a.t);//reverse(a.pos.begin(),a.pos.end());
	Vi x;per(i,SZ(a.pos)-1,0)x.pb(-a.pos[i]);
	a.pos=x;
}
Line merge(Line a, Line b, int u){
	if(!(dl[u]<=dl[b.s]&&dr[u]>=dl[b.s]))rev(b);
	if((dl[u]<=dl[a.s]&&dr[u]>=dl[a.s]))rev(a);
	Line c;c.s=a.s;c.t=b.t;c.lca=LCA(c.s,c.t);
	rep(i,0,SZ(a.pos)-1)c.pos.pb(a.pos[i]);
	rep(i,0,SZ(b.pos)-1)c.pos.pb(b.pos[i]);
	return c;
}
void dfs1(int u, int Fa, int Dep){
	dl[u]=++num;fa[u]=Fa;dep[u]=Dep;
	rep(i,0,SZ(e[u])-1)if(e[u][i]!=Fa)
		dfs1(e[u][i],u,Dep+1);
	dr[u]=num;
}
bool isin(int x, int a, int b){
	return dl[x]<=dl[a]&&dr[x]>=dl[a]&&dl[b]<=dl[x]&&dr[b]>=dl[x];
}
bool isin(int x, Line &a){
	if(!a.lca)a.lca=LCA(a.s,a.t);
	return isin(x,a.s,a.lca)||isin(x,a.t,a.lca);
}
void dfs(int u){
	rep(i,0,SZ(e[u])-1)if(e[u][i]!=fa[u])dfs(e[u][i]);
	Vi b;rep(i,1,len)if(!vis[u]&&isin(u,c[i])&&isin(fa[u],c[i]))b.pb(i);
	if(!vis[u]&&fa[u]&&SZ(b)>=2){
		rep(i,1,n)if(i&&fa[i]&&!vis[i]&&isin(i,c[b[0]])&&isin(i,c[b[1]])&&isin(fa[i],c[b[0]])&&isin(fa[i],c[b[1]]))
			vis[i]=1;
		c[b[0]]=merge(c[b[0]],c[b[1]],u);rep(i,b[1]+1,len)c[i-1]=c[i];len--;
	}
}
int getans(){
	int res=0;
	static Line q[N];rep(j,1,m)q[j].s=a[j],q[j].t=b[j];
	rep(i,1,n)if(fa[i]){
		int cnt=0;
		rep(j,1,m){
			cnt+=isin(i,q[j])&&isin(fa[i],q[j]);
		}
		res+=min(cnt,2);
	}
	return res;
}
int main() {
	read(n);read(m);
	rep(i,1,n-1){
		int u,v;read(u);read(v);e[u].pb(v);e[v].pb(u);
	}
	rep(i,1,m)read(a[i]),read(b[i]);len=m;
	cerr<<"OwO\n"<<endl;
	rep(i,1,m)c[i].s=a[i],c[i].t=b[i],c[i].pos.pb(i);
	cerr<<"OwO\n"<<endl;
	dfs1(1,0,0);dfs(1);
	cerr<<"OwO\n"<<endl;
	printf("%d\n",getans());
	cerr<<"OwO\n"<<endl;
	rep(i,1,len)rep(j,0,SZ(c[i].pos)-1)if(c[i].pos[j]<0){int x=-c[i].pos[j];swap(a[x],b[x]);}
	rep(i,1,m)printf("%d %d\n",a[i],b[i]);
	return 0;
}


Measured memory_bytes: 1280
#include <stdio.h>

int main(void){
  int i,j,n,x,count;

  while(1)
  {
    count=0;
    scanf("%d%d",&n,&x);
    if(n+x == 0) break;

    for(i=1;i<=n;i++)
      for(j=i+1;j<=n;j++)
        if(j < x-i-j && x-i-j <= n)
          count++;

    printf("%d\n", count);
  }

  return 0;
}



Measured memory_bytes: 2032
#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  
#include <chrono>
#include <random>
#include <time.h>
#include <fstream>
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define endl "\n"
#define all(c) begin(c),end(c)
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}


#define LLINF 1e18+7
#define N 250000
ll MOD=998244353;

main(){
    int n=in();
    double l;cin>>l;
    double pi=3.1415926535898;
    vector<double> t;
    rep(i,n){
        double d;cin>>d;
        t.pb(d);
    }
    double re=0.0,im=0.0;
    double p=(double)6.0/(double)(n-1)/(double)n/(double)(n-2);
    rep(i,n){
        rep2(j,i+1,n-1){
            double c=(t[i]+t[j])*pi/(double)l;
            int k=n-1-j+i;
            re+=p*cos(c)*(double)(k);
            im+=p*sin(c)*(double)(k);
            c=c+pi;
            re+=p*cos(c)*(double)(n-2-k);
            im+=p*sin(c)*(double)(n-2-k);
            //cout<<c<<" "<<re<<endl;
        }
    }
    printf("%.15f %.15f\n",re,im);
    return 0;
}

Measured memory_bytes: 640
//In The Name Of Allah
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)(x.size())
#define double long double 
#define fi first
#define se second
#define pii pair<int, int>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
  int n, k;
  cin >> n >> k;
  int a[n + 1];
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  int ls[n + 1];
  ls[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (a[i - 1] < a[i]) {
      ls[i] = ls[i - 1] + 1;
    } else {
      ls[i] = 1;
    }
  }
  int ans = 0;
  for (int i = k; i <= n; i++) {
    if (ls[i] >= k) ans = 1;
  }
  set<int> st;
  for (int i = 1; i <= k; i++) {
    st.insert(a[i]);
  }
  if (ls[k] < k) ans++;
  for (int i = k + 1; i <= n; i++) {
    bool mn = (a[i - k] == *st.begin());
    st.erase(a[i - k]);
    if (a[i] < *st.rbegin()) {
      ans++;
    } else if (ls[i] < k && !mn) {
      ans++;
    }
    st.insert(a[i]);
  }
  cout << ans << "\n";
}



Measured memory_bytes: 12800
import math


def f(a, b):
    keta_a = int(math.log10(a)) + 1
    keta_b = int(math.log10(b)) + 1
    return max(keta_a, keta_b)

n = int(input())
res = 0
for i in range(1, int(n ** 0.5) + 1):
    if (n % i == 0):
        res = i
print(f(res,n/res))

Measured memory_bytes: 3060
#include <cstdio>
#define MOD 1000000007
typedef long long ll;
const int mx = 2e6;
inline ll quick_pow(ll a, int n)
{
	ll res = 1;
	while (n)
	{
		if (n & 1)
			res = res * a % MOD;
		a = a * a % MOD;
		n >>= 1;
	}
	return res;
}
struct
{
	int x1, x2, y1, y2;
} a, b, c;
ll fact[2000005], inv[2000005];
inline ll func(int x, int y)
{
	return fact[x + y] * inv[x] % MOD * inv[y] % MOD;
}
inline ll calc(int x1, int y1, int x2, int y2)
{
	return (func(x2 + 1, y2 + 1) - func(x2 + 1, y1) - func(x1, y2 + 1) + func(x1, y1)) % MOD;
}
int main()
{
	// freopen("AGC018-E.in", "r", stdin);
	fact[0] = inv[0] = 1;
	for (int i = 1; i <= mx; i++)
		fact[i] = fact[i - 1] * i % MOD;
	inv[mx] = quick_pow(fact[mx], MOD - 2);
	for (int i = mx; i; i--)
		inv[i - 1] = inv[i] * i % MOD;
	scanf("%d%d%d%d%d%d", &a.x1, &a.x2, &b.x1, &b.x2, &c.x1, &c.x2);
	scanf("%d%d%d%d%d%d", &a.y1, &a.y2, &b.y1, &b.y2, &c.y1, &c.y2);
	ll ans = 0;
	for (int i = b.x1; i <= b.x2; i++)
	{
		(ans -= calc(i - a.x2, b.y1 - a.y2 - 1, i - a.x1, b.y1 - a.y1 - 1)
				* calc(c.x1 - i, c.y1 - b.y1, c.x2 - i, c.y2 - b.y1) % MOD * (i + b.y1)) %= MOD;
		(ans += calc(i - a.x2, b.y2 - a.y2, i - a.x1, b.y2 - a.y1)
				* calc(c.x1 - i, c.y1 - b.y2 - 1, c.x2 - i, c.y2 - b.y2 - 1) % MOD * (i + b.y2 + 1)) %= MOD;
	}
	for (int i = b.y1; i <= b.y2; i++)
	{
		(ans -= calc(b.x1 - a.x2 - 1, i - a.y2, b.x1 - a.x1 - 1, i - a.y1)
				* calc(c.x1 - b.x1, c.y1 - i, c.x2 - b.x1, c.y2 - i) % MOD * (i + b.x1)) %= MOD;
		(ans += calc(b.x2 - a.x2, i - a.y2, b.x2 - a.x1, i - a.y1)
				* calc(c.x1 - b.x2 - 1, c.y1 - i, c.x2 - b.x2 - 1, c.y2 - i) % MOD * (i + b.x2 + 1)) %= MOD;
	}
	printf("%lld\n", (ans + MOD) % MOD);
	return 0;
}


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

int a, b;

int main(){
//	cin.tie(0);
//	ios::sync_with_stdio(false);
	cin >> a >> b;
	if(a <= 8 && b <= 8) cout << "Yay!\n";
	else cout << ":(\n";
}

Measured memory_bytes: 256
lst_1 = input().split()

N = lst_1[0]
K = int(lst_1[1])

lst_N = list(N)

lst_hate = input().split()

flg = True

while 1:

    for i in range(len(lst_N)):

        for j in range(len(lst_hate)):

            if lst_N[i] == lst_hate[j]:
                flg = False
                break

    if flg == True:
        break

    N = ''.join(lst_N)
    N = int(N)
    N += 1
    lst_N = list(str(N))

    flg = True

N = ''.join(lst_N)
print(N)

Measured memory_bytes: 3064
package main

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

var sc = bufio.NewScanner(os.Stdin)

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

func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(next(), 64)
	return f
}

func nextInts(n int) []int {
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i] = nextInt()
	}
	return slice
}

func main() {
	sc.Split(bufio.ScanWords)
	n := nextInt()

	// 4の倍数の個数, 奇数の個数
	x, y := 0, 0
	for i := 0; i < n; i++ {
		a := nextInt()
		if a%4 == 0 {
			x++
		} else if a%2 == 1 {
			y++
		}
	}

	if x >= n/2 {
		fmt.Println("Yes")
	} else if x >= y {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


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

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

    int x, a, b;
    cin >> x >> a >> b;
    if (abs(x-a) > abs(x-b))
        cout << 'B' << endl;
    else
        cout << 'A' << endl;
} 

Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
string s;
bool check(int i){
	if(i%2==1&&s[i]=='R')return 1;
	if(i%2==0&&s[i]=='L')return 1;
	return 0;
}
int main(void){
	cin>>s;
	for(int i=0;i<s.size();i++)
		if(check(i)){cout<<"No";return 0;}
	cout<<"Yes";
	return 0;
}

Measured memory_bytes: 256
N, M = list(map(int, input().split()))
F = []
for i in range(N):
    F.append(input())
W = [[0] * M for _ in range(N)]
for i in range(N):
    if F[i][0] == "#":
        break
    W[i][0] = 1
for i in range(M):
    if F[0][i] == "#":
        break
    W[0][i] = 1       
for i in range(1, N):
    for j in range(1, M):
        if F[i][j] != "#":
            W[i][j] += W[i-1][j]
            W[i][j] += W[i][j-1]
print(W[-1][-1] % (10**9+7))  


Measured memory_bytes: 157528
flag = True
numbers = {}
for i in range(3):
    tmp = list(int(i) for i in input().split())
    if tmp[0] in numbers:
        numbers[tmp[0]] += 1
        if numbers[tmp[0]] > 2:
            flag = False
            break
    else:
        numbers[tmp[0]] = 1
    if tmp[1] in numbers:
        numbers[tmp[1]] += 1
        if numbers[tmp[1]] > 2:
            flag = False
            break
    else:
        numbers[tmp[1]] = 1

for i in range(4):
    if not i+1 in numbers:
        flag = False
        break

if flag:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 3064
T = list(input())

for i in range(len(T) - 1):
    if T[i] == "?":
        if i > 0 and T[i - 1] == "P":
            T[i] = "D"
        else:
            if T[i + 1] == "P":
                T[i] = "D"
            elif T[i + 1] == "D":
                T[i] = "P"
            else:
                T[i] = "P"
                T[i + 1] = "D"

if T[-1] == "?":
    T[-1] = "D"
print("".join(T), sep="")


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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef vector<vector<long long>> VVL;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define LB(a,x) lower_bound((a).begin(), (a).end(), x) - (a).begin()
#define UB(a,x) upper_bound((a).begin(), (a).end(), x) - (a).begin()

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

#define en "\n"

constexpr double EPS = 1e-9;
constexpr double PI  = 3.141592653589793238462643383279;
constexpr int INF = 2147483647;
constexpr long long LINF = 1LL<<60;
constexpr long long MOD = 1000000007; // 998244353

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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; }

int main(void){
    int N; cin >> N;
    VI A(N); REP(i,N) cin >> A[i];
    ll ans = A[0]-1;
    int mx = 1;
    FOR(i,1,N){
        if(A[i] <= mx) continue;
        else if(A[i] == mx+1){
            mx++;
            continue;
        }
        ans += (A[i]-1) / (mx+1);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    string s;
    int w;
    cin>>s>>w;
//    vector<char>ans;
//    for(int i=0;i!=s.size();i++)
//    {
//        if((i+1)%w==1)
//            ans.push_back(s[i]);
//    }
//    for(int i=0;i<ans.size();i++)
//        cout<<ans[i];
    for(int i=0;i<s.size();i+=w)
        cout<<s[i];
    cout<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <algorithm>
#include <functional>
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
 
int main () {
  int m, n;
  cin >> n >> m;
  int a[n];
  int sum = 0;
  for (int i = 0; i < n; i++){
    cin >> a[i];
    sum += a[i];
  }
  sort(a, a+n, greater<int>());
  if (a[m-1] >= ceil((double)sum/(double)(4*m))){
    cout << "Yes";
  }else{
    cout <<"No";
  }
  return 0;
}

Measured memory_bytes: 256
package main

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

func main() {
	sc := NewScanner()
	A, B, _ := sc.NextInt(), sc.NextInt(), sc.NextInt()
	fmt.Println(A * B / 2)
}

type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner() *Scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1000)
	return &Scanner{r: rdr}
}
func (s *Scanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *Scanner) NextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *Scanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}
func (s *Scanner) NextInt64() int64 {
	v, _ := strconv.ParseInt(s.Next(), 10, 64)
	return v
}

func (s *Scanner) NextIntArray() []int {
	s.pre()
	start := s.p
	result := []int{}
	for ; s.p < len(s.buf)+1; s.p++ {
		if s.p == len(s.buf) || s.buf[s.p] == ' ' {
			v, _ := strconv.ParseInt(string(s.buf[start:s.p]), 10, 0)
			result = append(result, int(v))
			start = s.p + 1
		}
	}

	return result
}
func (s *Scanner) NextInt64Array() []int64 {
	s.pre()
	start := s.p
	result := []int64{}
	for ; s.p < len(s.buf)+1; s.p++ {
		if s.p == len(s.buf) || s.buf[s.p] == ' ' {
			v, _ := strconv.ParseInt(string(s.buf[start:s.p]), 10, 64)
			result = append(result, v)
			start = s.p + 1
		}
	}
	return result
}

func (s *Scanner) NextMap() map[int]bool {
	s.pre()
	start := s.p
	mp := map[int]bool{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			mp[v] = true
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	mp[v] = true

	return mp
}

func (s *Scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *Scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i, n) for(long long int i = 0; i < n; i++)
#define _rep(i, m, n) for(long long int i = m; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
//const int N = 1000000;
const ll mod = 1000000007;
using Graph = vector<vector<int>>;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
  
ll gcd(ll A, ll B){
    if(B == 0)return A;
    return gcd(B, A % B);
}
ll lcm(ll A, ll B){
    return A * (B / gcd(A, B));
}
  
/*------------------------------------------------------------------*/
  
int main(){
    ll n; cin >> n;
    vector<ll> d(n);
    rep(i, n) cin >> d[i];
    sort(d.begin(), d.end());
    ll m; cin >> m;
    vector<ll> t(m);
    rep(i, m) cin >> t[i];
    sort(t.begin(), t.end());
    
    ll i = 0, j = 0;
    while(i < n){
        if(t[j] == d[i]){
            j++;
            i++;
            if(j == m){
                cout << "YES" << endl;
                return 0;
            }
        }else{
            i++;
        }
    }
    cout << "NO" << endl;
    return 0;
}


Measured memory_bytes: 3328
////////////////////////////////////////////////////////////////////
// This source code is for Visual Studio
////////////////////////////////////////////////////////////////////
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <sstream>
#include <iterator>
#include <stack>
#include <functional>
#include <iomanip>
#include <string>
#include <cstring>
#include <deque>
#include <math.h>
#include <assert.h>

#define	numberof(a)	(sizeof(a) / sizeof(a[0]))
#define	INF32		INT32_MAX
#define	INF64		INT64_MAX
#define Rep(i,n) for(int i = 0; i < (n); ++i )

using namespace std;

typedef vector< vector<int> > MAT;
typedef pair<int, int> PINT;
typedef long long ll;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int32_t s32;
typedef int64_t s64;

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);

// main function
int main()
{
	ll N = 0;
	string u = "";
	double x = 0;
	double ret = 0;
	double yen_per_btc = 380000.0;

	cin >> N;
	Rep(i, N) {
		cin >> x >> u;
		if (u == "JPY") {
			ret += x;
		}
		else {
			ret += x * yen_per_btc;
		}
	}

	cout << ret << endl;

	return 0;
}

Measured memory_bytes: 256
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};
    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, [graph1; $len:expr]) => {{
        let mut g = vec![vec![]; $len];
        let ab = read_value!($next, [(usize1, usize1)]);
        for (a, b) in ab {
            g[a].push(b);
            g[b].push(a);
        }
        g
    }};
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };
    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };
    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };
    ($next:expr, usize1) => (read_value!($next, usize) - 1);
    ($next:expr, [ $t:tt ]) => {{
        let len = read_value!($next, usize);
        read_value!($next, [$t; len])
    }};
    ($next:expr, $t:ty) => ($next().parse::<$t>().expect("Parse error"));
}

#[allow(unused)]
macro_rules! debug {
    ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap());
}
#[allow(unused)]
macro_rules! debugln {
    ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap());
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (let _ = write!(out,$($format)*););
    }
    input! {
        h: usize, w: usize, m: usize,
        xy: [(usize1, usize1); m],
    }
    let mut set = HashSet::new();
    let mut row = vec![0; h];
    let mut col = vec![0; w];
    for &(x, y) in &xy {
        row[x] += 1;
        col[y] += 1;
        set.insert((x, y));
    }
    let &rmax = row.iter().max().unwrap();
    let &cmax = col.iter().max().unwrap();
    let mut diff = 1;
    let rarg = (0..h).filter(|&i| row[i] == rmax).collect::<Vec<_>>();
    let carg = (0..w).filter(|&i| col[i] == cmax).collect::<Vec<_>>();
    'outer:
    for &r in &rarg {
        for &c in &carg {
            if !set.contains(&(r, c)) {
                diff = 0;
                break 'outer;
            }
        }
    }
    puts!("{}\n", rmax + cmax - diff);
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


Measured memory_bytes: 21460
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(){
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }
 
    long long ans = 0;
    int MaxNum = 0;
    for (int i = 0; i < N; i++)
    {
        //MaxNumを使い回すことで計算を抑える
        MaxNum = max(MaxNum, A[i]);
        int Bi = MaxNum;
        ans += Bi - A[i];
    }
 
    cout << ans << endl;
}

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

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

	string s;
	cin >> s;

	int a = 0;
	for(int i = 0; i < s.size(); i++) {
		if(a == 0 && s[i] == 'C') a++;
		else if(a == 1 && s[i] == 'F') a++;
	}

	if(a == 2) cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <array>
#include <vector>
#include <utility>
#include <bitset>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <numeric>

using namespace std;

using ll = long long;
using p = pair<ll, ll>;

constexpr ll INF = 1LL << 62;

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

    ll H, W;
    cin >> H >> W;

    vector<vector<ll> > C(10, vector<ll>(10));
    for (ll i = 0; i < 10; i++) {
        for (ll j = 0; j < 10; j++) {
            cin >> C[i][j];
        }
    }

    vector<vector<ll> > A(H, vector<ll>(W));
    for (ll h = 0; h < H; h++) {
        for (ll w = 0; w < W; w++) {
            cin >> A[h][w];
        }
    }

    for (ll k = 0; k < 10; k++) {
        for (ll i = 0; i < 10; i++) {
            for (ll j = 0; j < 10; j++) {
                C[i][j] = min(C[i][j], C[i][k] + C[k][j]);
            }
        }
    }

    ll ans = 0;
    for (ll h = 0; h < H; h++) {
        for (ll w = 0; w < W; w++) {
            if (A[h][w] != -1) {
                ans += C[A[h][w]][1];
            }
        }
    }

    cout << ans << endl;

    return 0;
}




Measured memory_bytes: 640
d = int(input())
for i in range(d):
    n = int(input())
    l = list(map(int, input().split()))
    dis = [l[i+1] - l[i] for i in range(n - 1)]
    M, m = max(dis), min(dis)
    if M > 0 and m > 0:
        print(M, 0)
    elif M < 0 and m < 0:
        print(0, abs(m))
    else:
        print(M, abs(m))

Measured memory_bytes: 6724
#include<bits/stdc++.h>
using namespace std;
int a[10024300];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    sort(a+1,a+n+1);
    cout<<a[n]-a[1];
    return 0;
} 

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

using namespace std;
using ll = long long;

int main(int argc, const char *argv[]) {
  ll n, a, b;
  cin >> n >> a >> b;
  vector<ll> vh(n);
  for (int i = 0; i < n; ++i) {
    cin >> vh[i];
  }

  sort(vh.begin(), vh.end(), greater<ll>());

  ll l = 1, r = pow(10, 9) + 1;
  while (l != r) {
    ll mid = (r + l) / 2;
    ll m = mid;
    for (int i = 0; i < n && m >= 0; ++i) {
      ll hp = vh[i] - mid * b;
      m -= max(0ll, hp / (a - b) + (hp % (a - b) > 0));
    }

    if (m < 0) {
      l = mid + 1;
    } else {
      r = mid;
    }
  }

  cout << r << '\n';
}

Measured memory_bytes: 4028
# DPL_3_B: Largest Rectangle
import sys
H, W = map(int, sys.stdin.readline().strip().split())

C = []
for h in range(H):
    c = list(map(int, sys.stdin.readline().strip().split()))
    C.append(c)

# 列方向のdp
dp = [[0] * (W + 1) for _ in range(H)]
for h in range(H):
    for w in range(W + 1):  # 長方形の面積探査時に一番右端が0だと都合がいい
        if w == W:
            dp[h][w] = 0
            continue
        if C[h][w] == 1:
           dp[h][w] = 0
        elif h == 0:  # 0行目は上の行が存在しないので別処理
           dp[0][w] = 1
        else:
           dp[h][w] = dp[h-1][w] + 1

# 長方形を求める
ans = 0
for h in range(H):
    stack = [(0, 0)]  # [(left, height)]
    for w in range(W + 1):
        if dp[h][w] >= stack[-1][1]:  # まだ長方形が決定されないとき
            stack.append((w, dp[h][w]))
        else:  # 高さが足りずに長方形が決定されるとき
            while stack[-1][1] > dp[h][w]:  # stack[0] = (0, 0) なので、 stack[0]は絶対に取り出されない
                left_pos, height = stack.pop()
                area = height * (w - left_pos)  # 長方形の面積
                ans = max(ans, area)
            stack.append((left_pos, dp[h][w]))

print(ans)



Measured memory_bytes: 63240
n = int(input())
dictionary = []

for i in range(1, n+1):
  s, p = input().split()
  p = int(p)
  dictionary.append([i, s, p])

sortedDict = sorted(dictionary, key=lambda x: (x[1], -x[2]))

for i in range(n):
  print(sortedDict[i][0])

Measured memory_bytes: 3060
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#ifndef FAST_IO
 #define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);
#endif

#define FILE_IO freopen("input.txt","r",stdin)
#define int long long
#define f first
#define s second
#define endl '\n'
#define all(c) c.begin(),c.end()
#define bp __builtin_popcount
#define debug(x) cerr << #x << " = " << x << endl;

const int MOD = 1e9 + 7;
const int INF = 1e18;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>void print(T t){for(auto &it : t)cout<<it<<" ";}
inline int powerexp(int a, int b, int m = MOD){ int res = 1;while(b){if(b&1)res = res * a % m;a = a * a % m,b >>= 1;}return res % m;}
inline int modinv(int a){ return powerexp(a,MOD-2,MOD);}
inline int lcm(int a, int b){ int g = __gcd(a,b);return a/g*b;}
inline int add(int x, int y){ x += y; if (x >= MOD) x -=  MOD; return x;}
inline int mul(int x, int y){ return (x * 1ll * y) % MOD;}
inline int sub(int x, int y){ x -= y; if (x<0) x += MOD; return x ;}

//-------------------< start here >-------------------------// 

void solve(){
   set<int> s;
   int q;
   cin >> q;
   for(int i = 0; i < q; i++){
	  int cmd;
	  cin >> cmd;
	  if (cmd == 0){
		   int val;
		   cin >> val;
		   s.insert(val);
		   cout << (int)s.size() << endl;
		}
      if (cmd == 1){
		  int val;
		  cin >> val;
		  if (s.find(val) == s.end()) cout << 0 << endl;
		  else cout << 1 << endl;  
		}
	  if (cmd == 2){
		  int x;
		  cin >> x;
		  s.erase(x);  
		}   
	}
}

//-----------------------------
//comment from here for TOPCODER 
int32_t main(){
   IOS;
   solve();
   //find();
   #ifdef LOCAL_DEFINE
   cerr << "time elapsed " << (double)clock()/CLOCKS_PER_SEC << endl;
   #endif
}



Measured memory_bytes: 12508
#include <bits/stdc++.h>
using namespace std;
const int MAXn = 5 + 4, MAXx = (1<<5);
typedef long long ll;
#define int ll
string s = "MARCH";
int ar[MAXn], n, ans;
int32_t main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		string t;
		cin >> t;
		for (int j = 0; j < 5; j++)
			if (t[0] == s[j])
				ar[j]++;
	}
	for (int i = 0; i < MAXx; i++)
		if (__builtin_popcount(i) == 3) {
			int tmp = 1;
			for (int j = 0; j < 5; j++)
				if ((i>>j) & 1)
					tmp *= ar[j];
			ans += tmp;
		}
	cout << ans;
}


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

using namespace std;
using llong = long long;
using ldbl = long double;
using lpair = pair<llong, llong>;

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

constexpr llong mod = 1e9+7;
constexpr llong inf = mod * mod;

int main() {
  llong D, T, S;
  cin >> D >> T >> S;

  cout << (S*T < D ? "No": "Yes") << endl;

  return 0;
}

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

int main(){
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  int sum = 0;
  rep(i, n){
    cin >> a[i];
    sum += a[i];
  }
  sort(a.begin(), a.end(), greater<int>());
  bool can = false;
  if(a[m-1] >= (sum+4*m-1)/(4*m)) can = true;
  
  if(can) cout << "Yes" << endl;
  else cout << "No" << endl;
    
    return 0;
}



Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define sz(a) (int)a.size()
#define de(a) cout<<#a<<" = "<<a<<endl
#define dd(a) cout<<#a<<" = "<<a<<" "
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef vector<int> vi;
//----
int n, m;
const int N=410;
ll sum[N][N], pre[N][N], dp[N][N];
const int MOD=1e9+7;
int a[N], b[N];
int main(){
	rep(i, 0, N)pre[i][0]=1;
	rep(i, 1, N)rep(j, 1, N)pre[i][j]=pre[i][j-1]*i%MOD;
	rep(i, 0, N)rep(j, 1, N)sum[i][j]=(sum[i][j-1]+pre[j][i])%MOD;
	scanf("%d%d", &n, &m);
	rep(i, 0, n)scanf("%d", a+i);
	rep(i, 0, n)scanf("%d", b+i);
	dp[0][0]=1;
	rep(i, 1, n+1)rep(j, 0, m+1)rep(k, 0, j+1){
		dp[i][j]=(dp[i][j]+dp[i-1][k]*(sum[j-k][b[i-1]]-sum[j-k][a[i-1]-1]+MOD)%MOD)%MOD;
	}
	printf("%lld\n", dp[n][m]);
	return 0;
}
/*
2 3
1 1
1 1

1 2
1
3
*/

Measured memory_bytes: 4096
n, a, b = map(int, input().split())
v = list(map(int, input().split()))

# dp[i] := i個選ぶときの価値の最大値
# dq[i] := i個選ぶときの価値の最大値の個数
dp = [0] * (n + 1)
dq = [0] * (n + 1)

dq[0] = 1

for i in range(n):
    val = v[i]
    # i番目を選ぶとき
    for j in range(n)[::-1]:
        if dp[j + 1] == dp[j] + val:
            dq[j + 1] += dq[j]
        if dp[j + 1] < dp[j] + val:
            dp[j + 1] = dp[j] + val
            dq[j + 1] = dq[j]
        else:
            continue

max_ans = 0
max_cnt = 10 ** 30
for i in range(a, b + 1):
    if max_cnt * dp[i] > max_ans * i:
        max_ans = dp[i]
        max_cnt = i

ans = 0
for i in range(a, b + 1):
    if max_cnt * dp[i] == max_ans * i:
        ans += dq[i]

print(max_ans / max_cnt)
print(ans)


Measured memory_bytes: 39408
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
    int N,K;
    cin>>N>>K;
    vector<long long int>v;
    long long int tree;
    for(int i=0;i<N;i++){
        cin>>tree;
        v.push_back(tree);
    }
    sort(v.begin(),v.end());
    long long int min=10*10*10*10*10*10*10*10*10;
    for(int i=0; i<=N-K; i++){
        if(min>v[i+K-1]-v[i]){
            min = v[i+K-1]-v[i];
            //cout << v[i+K-1] <<" "<<v[i]<<endl;
        }
    }
    cout << min << endl;
    return 0;
}


Measured memory_bytes: 1400
#include <iostream>
#include <list>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
typedef long long lli;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<vector<lli> > mat;
typedef vector<vector<bool> > matb;
typedef vector<string> vst;
typedef pair<lli,lli> pll;
typedef pair<double,double> pdd;

vll x(9);
lli y;

set<vll> vis;
queue<vll> q;
queue<lli> d;

vll ans{1,2,3,4,5,6,7,8,0};

int main(){
    for(lli i = 0;i < 9;i++) cin >> x[i];
    q.push(x);
    d.push(0);
    while(!q.empty()){
        x = q.front();
        y = d.front();
        q.pop();
        d.pop();
        if(vis.count(x)) continue;
        vis.insert(x);
        if(x == ans){
            cout << y << endl;
            return 0;
        }
        for(lli i = 0;i < 9;i++){
            if(x[i] == 0){
                if(i+3 < 9){
                    swap(x[i],x[i+3]);
                    q.push(x);
                    d.push(y+1);
                    swap(x[i],x[i+3]);
                }
                if(i-3 >= 0){
                    swap(x[i],x[i-3]);
                    q.push(x);
                    d.push(y+1);
                    swap(x[i],x[i-3]);
                }
                if(i%3 != 0){
                    swap(x[i],x[i-1]);
                    q.push(x);
                    d.push(y+1);
                    swap(x[i],x[i-1]);
                }
                if(i%3 != 2){
                    swap(x[i],x[i+1]);
                    q.push(x);
                    d.push(y+1);
                    swap(x[i],x[i+1]);
                }
                break;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 31344
#include "bits/stdc++.h"

using namespace std;
using ll = long long;
#define endl '\n'
#define all(v) v.begin(), v.end()

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    for (auto& v : p) cin >> v;
    sort(all(p));
    ll ans = 0;
    for (int i = 0; i < k; i++)
        ans += p[i];
    cout << ans << endl;
}


Measured memory_bytes: 3588
#include <bits/stdc++.h>
#define INT long long int
#define MOD 1000000007
#define oo (1e18)
using namespace std;
INT n, a[200020], d[200020], ans;
map<INT, INT> b;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i = 1 ; i <= n ; i++ )
    {
        cin>>a[i];
        d[i] = d[i-1]+a[i];
        if( !d[i] ) ans++;
        ans += b[d[i]];
        b[d[i]]++;
    }
    cout<<ans<<endl;
    return 0;
}




Measured memory_bytes: 15872
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(long i = 0; i < n; i++)
#define erep(i, n) for(long i = 1; i <= n; i++)
// const long MOD = 1000000007;
#define all(a) a.begin(), a.end()
#define eall(a) a.begin()+1, a.end()
#define show(ans)  cout << ans << endl;

const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(){long n;
cin >> n;
vector<long> a(n+1);
erep(i, n) cin >> a[i];
vector<long> b = a;
sort(eall(b));
long x = b[n];
long tmp = x;
long y = 0;
erep(i, n){
  if(abs(a[i]*2-x) < tmp){
    tmp = abs(a[i]*2-x);
    y = a[i];
  }
}
cout << x << ' ' << y << endl;

return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
//author wjl

using namespace std;
#define LL long long
#define Rint register int
#define U unsigned
#define forn(i,a,b) for(int i = a;i <= b;++i)
#define nfor(i,a,b) for(int i = a;i >= b;--i)
#define pii pair<int ,int>
#define MS0(X) memset(X,0,sizeof(X))
#define MSf(X) memset(X,false,sizeof(X))
#define MS1(X) memset(X,-1,sizeof(X))
#define BR printf("--------------------\n")
#define pb push_back
#define rep(i,a,b) for(Rint i=a;i<=b;++i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const double PI=atan(1.)*4.;
const int maxn=1e6+5;
const int inf = 0x3f3f3f3f;
const int mod=1e9+7;
const double e=2.71828182845904523536;
int dirx[8]={1,0,-1,0,1,-1,-1,1};
int diry[8]={0,1,0,-1,1,1,-1,-1};
int n,t;
struct node
{
    int a,b;
}st[maxn];

bool cmp(node a,node b)
{
    return a.a<b.a;
}

int dp[3005][6005];
int mx[3005];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>t;
    for(int i=1;i<=n;i++)
    {
        cin>>st[i].a>>st[i].b;
    }
    sort(st+1,st+n+1,cmp);
    /*for(int i=n;i>=1;i--)
    {
        mx[i]=max(mx[i+1],st[i].b);
    }*/
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=t+st[i].a-1;j>=st[i].a;--j)
        {
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-st[i].a]+st[i].b);
            ans=max(ans,dp[i][j]);
        }
        for(int j=st[i].a-1;j>=0;--j)
        {
            dp[i][j]=dp[i-1][j];
            ans=max(ans,dp[i][j]);
        }
        /*for(int j=t-1;j>=0;j--)
        {
            dp[i][j]=dp[i-1][j];
            if(j>=st[i].a)
                dp[i][j]=max(dp[i][j],dp[i-1][j-st[i].a]+st[i].b);
        }
        ans=max(ans,dp[i][t-1]+mx[i+1]);*/
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 71936
#include<bits/stdc++.h>
using namespace std;
int main()
{

    long long m,n,res=0,ans=0,i,j,c=1;
    cin>>m>>n;
    res=m;
    for(i=m;; i++)
    {
        res=res*2;
        if(res<=n)
        {
            c++;
            //cout<<res<<" ";
        }
        else
        {
            break;
        }

    }
    cout<<c<<endl;

    return 0;

}


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

int main()
{
    string s[12];
    int h,w,k;
    cin>>h>>w>>k;
    for(int i=0;i<h;i++)
        cin>>s[i];
    int ans=1e9;
    for(int u=0;u<(1<<(h-1));u++){//枚举横向切割的所有情况
        int x=__builtin_popcount(u);//横向切割的刀数
        int r[x+1]={0};//切x刀后横向看被分成x+1块
        int flag=1;//记录每一块是否达标
        int cnt=x;//记录此种分法的答案
        for(int j=0;j<w;j++){//纵切
            int c[x+1]={0};//记录纵切后x+1块所含的1的数量
            int p=0;//记数
            int mx=0;//记录x+1块中包含1数量最大的那块
            for(int i=0;i<h;i++){//记录纵切一刀时x+1块的情况
                c[p]+=s[i][j]-'0';
                mx=max(mx,c[p]);
                if(u&(1<<i)) p++;//如果横向切了一刀标记加加
            }
            if(mx>k) {flag=0;break;}//如果此时最大块包含的1大于k，那么证明横向切割没有最优，跳到下一组横向切割的情况
            mx=0;
            for(int i=0;i<=x;i++){//符合条件就横向判断
                mx=max(mx,r[i]+c[i]);
            }
            if(mx>k) {memset(r,0,sizeof(r));cnt++;}//横向的某一块的1的数量大于k就要切一刀
            for(int i=0;i<=x;i++) r[i]+=c[i];
        }
        if(flag) ans=min(ans,cnt);//更新答案
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256