akhauriyash/Code-Regression huggingface dataset:
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    private static List<String> l = new ArrayList<>();
    private static int N;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = Integer.parseInt(sc.next());
        rec(0);
        int res = 0;
        for (String s : l) {
            boolean b3 = false;
            boolean b5 = false;
            boolean b7 = false;
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c == '3') {
                    b3 = true;
                } else if (c == '5') {
                    b5 = true;
                } else {
                    b7 = true;
                }
                if (b3 && b5 && b7) {
                    res++;
                    break;
                }
            }
        }
        System.out.println(res);
    }

    private static void rec(long n) {
        long n3 = n * 10 + 3;
        long n5 = n * 10 + 5;
        long n7 = n * 10 + 7;
        if (n3 <= N) {
            l.add(String.valueOf(n3));
            rec(n3);
        }
        if (n5 <= N) {
            l.add(String.valueOf(n5));
            rec(n5);
        }
        if (n7 <= N) {
            l.add(String.valueOf(n7));
            rec(n7);
        }
        return;
    }
}


Measured memory_bytes: 27092
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#include<stdio.h>
#include <string.h>
#include<algorithm>
#include <queue>
#include<vector>
typedef long long ll;
const int mod=1e9+7;
const int maxn=2e6+16;
const ll INF=100000000000005;
const double eps=1e-11;
using namespace std;
ll n,m,p;
map<ll,ll>mp;
ll sum[maxn];
ll num[maxn];
int main()
{
    ll res=0;//记录最终答案
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&num[i]);
        sum[i]=sum[i-1]+num[i];
    }
    for(int i=1;i<=n;i++)
        sum[i]=(sum[i]-i%m+m)%m;//预处理前缀和
   // for(int i=0;i<=n;i++)
   //     printf("%lld ",sum[i]);
  //  printf("\n");
    ll low=min(m-1,n);
    for(int i=0;i<=low;i++)
    {
        res+=mp[sum[i]];
        mp[sum[i]]++;
    }
   // printf("%lld\n",res);
    for(int i=low+1;i<=n;i++)
    {
        mp[sum[i-m]]--;
        res+=mp[sum[i]];
        mp[sum[i]]++;
    }
    printf("%lld\n",res);
    return 0;
}





Measured memory_bytes: 18432
import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        FastScanner sc = new FastScanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int[] cnt = new int[26];
        char[] s = sc.next().toCharArray();
        int len = s.length;
        for(int i = 0; i < len; i++){
            cnt[s[i]-'a']++;
        }
        long ans = (long)len*(long)(len-1)/2;
        for(int c : cnt){
            long cl = c;
            ans -= cl*(cl-1)/2;
        }
        pw.println(ans+1);
        pw.flush();
    }

    static class GeekInteger {
        public static void save_sort(int[] array) {
            shuffle(array);
            Arrays.sort(array);
        }
 
        public static int[] shuffle(int[] array) {
            int n = array.length;
            Random random = new Random();
            for (int i = 0, j; i < n; i++) {
                j = i + random.nextInt(n - i);
                int randomElement = array[j];
                array[j] = array[i];
                array[i] = randomElement;
            }
            return array;
        }
 
    }
}

class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;
    public FastScanner(InputStream in) {
        reader = new BufferedReader(new InputStreamReader(in));
        tokenizer = null;
    }

    public String next() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public String nextLine() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken("\n");
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public double nextDouble() {
         return Double.parseDouble(next());
    }
    
    public String[] nextArray(int n) {
        String[] a = new String[n];
        for (int i = 0; i < n; i++)
            a[i] = next();
        return a;
    }

    public int[] nextIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = nextInt();
        return a;
    }

    public long[] nextLongArray(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++)
            a[i] = nextLong();
        return a;
    } 
}


Measured memory_bytes: 29972
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c,x,ans=0;
	cin >> a >> b >> c >> x;
	x /= 50;
	for(int i=0;i <= a;i++)
		for(int j=0;j <= b;j++)
			if(x-i*10-j*2 >= 0 && x-i*10-j*2 <= c) 
				ans++;
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <iostream>
#include <set>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define PRIME1 99999883
#define PRIME2 99999893
#define EPS 0.00000001
using namespace std;

struct Info{
	char from[11],to[11];
	int from_len,to_len;
};

struct Data{
	char words[11];
	int count,length;
};

bool strCmp(char* base, char* comp){
	int length1 = 0,length2 = 0;
	for(int i=0;base[i] != '\0'; i++)length1++;
	for(int i=0;comp[i] != '\0'; i++)length2++;
	if(length1 != length2)return false;

	for(int i=0;base[i] != '\0'; i++){
		if(base[i] != comp[i])return false;
	}
	return true;
}

void strcpy(char* to,char* str){
	for(int i=0;str[i] != '\0';i++){
		to[i] = str[i];
		to[i+1] = '\0';
	}
}


void func(int N){

	char first[11],last[11];
	Info info[N];
	int length,last_length;

	for(int i = 0; i < N; i++){
		scanf("%s %s",info[i].from,info[i].to);

		for(length = 0;info[i].from[length] != '\0';length++);
		info[i].from_len = length;
		for(length = 0;info[i].to[length] != '\0';length++);
		info[i].to_len = length;
	}
	scanf("%s",first);
	for(length = 0;first[length] != '\0';length++);

	scanf("%s",last);

	Data data;
	strcpy(data.words,first);
	data.count = 0;
	data.length = length;
	int ans = -1;

	for(length = 0;last[length] != '\0';length++);
	last_length = length;

	queue<Data> Q;
	Q.push(data);

	char work[111],tmp_work[11];
	int count,work_index;

	while(!Q.empty()){

		if(strCmp(last,Q.front().words)){
			ans = Q.front().count;
			break;
		}

		for(int i = 0; i < N; i++){
			count = 0;
			work_index = 0;
			for(int k = 0; k <= Q.front().length-info[i].from_len;){

				for(int p = 0; p < info[i].from_len;p++){
					tmp_work[p] = Q.front().words[k+p];
					tmp_work[p+1] = '\0';
				}

				if(strCmp(info[i].from,tmp_work)){
					for(int p = 0; p < info[i].to_len;p++){
						work[work_index++] = info[i].to[p];
						work[work_index] = '\0';
					}
					k+=info[i].from_len;
					count++;
					if(k > Q.front().length-info[i].from_len){
						for(int p = k; p < Q.front().length;p++){
							work[work_index++] = Q.front().words[p];
							work[work_index] = '\0';
						}
					}
				}else{
					if(k < Q.front().length-info[i].from_len){
						work[work_index++] = Q.front().words[k];
						work[work_index] = '\0';
						k++;
					}else{
						for(int p = k; p < Q.front().length;p++){
							work[work_index++] = Q.front().words[p];
							work[work_index] = '\0';
						}
						k++;
					}
				}
			}
			if(count > 0){
				for(length = 0;work[length] != '\0';length++);
				if(length <= last_length){
					Data new_data;
					strcpy(new_data.words,work);
					new_data.length = length;
					new_data.count = Q.front().count+1;
					Q.push(new_data);
				}
			}
		}

		Q.pop();
	}


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


int main(){

	int N;

	while(true){
		scanf("%d",&N);
		if(N == 0)break;

		func(N);
	}

    return 0;
}

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

using namespace std;

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

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

constexpr int MOD = 1e9 + 7;

int sum(int a, int b, int mod=MOD) {
    int c = a + b;
    if (c >= mod) {
        c -= mod;
    }

    return c;
}

inline int prod(int a, int b, int mod=MOD) {
    return (1LL * a * b) % mod;
}

int modpow(int base, int exp, int mod=MOD) {
    int res = 1;
    int cur = base;
    for (int p = 1; p <= exp; p <<= 1) {
        if (p & exp) {
            res = prod(res, cur, mod);
        }

        cur = prod(cur, cur, mod);
    }

    return res;
}

constexpr int MAXN = 404;
int n;
// dp[i][j] = sum of f distributing j candies over last i students
int lo[MAXN], hi[MAXN];
int bs[MAXN][MAXN];
int dp[MAXN][MAXN];

int solve(int idx, int k) {
    if (idx == n) {
        return k == 0;
    }

    int& res = dp[idx][k];
    if (res != -1) {
        return res;
    }

    res = 0;
    // solve(k) = sum_i solve(k - i) sum_b b^i
    // need to quickly compute sum_b b^i 
    for (int i = 0; i <= k; ++i) {
        int nxt = solve(idx + 1, k - i);
        int bsum = sum(bs[i][hi[idx]], MOD - bs[i][lo[idx] - 1]);
        res = sum(res, prod(bsum, nxt));
        /*
        for (int b = lo[idx]; b <= hi[idx]; ++b) {
            res = sum(res, prod(modpow(b, i), nxt));
        }
        */
    }

    return res;
}

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

    for (int i = 0; i < MAXN; ++i) {
        for (int j = 0; j < MAXN; ++j) {
            bs[i][j] = modpow(j, i);
        }

        for (int j = 1; j < MAXN; ++j) {
            bs[i][j] = sum(bs[i][j - 1], bs[i][j]);
        }
    }

    int c;
    cin >> n >> c;
    for (int i = 0; i < n; ++i) {
        cin >> lo[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> hi[i];
    }

    memset(dp, -1, sizeof(dp));
    cout << solve(0, c) << '\n';
    
    return 0;
}


Measured memory_bytes: 1664
#include<stdio.h>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
 
 
using namespace std;
 
//conversion
//------------------------------------------
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();}
 
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}
 
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
 
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
 
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
 
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
 
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
 
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//pair sort
bool compare_by_b(pair<LL, LL> a, pair<LL, LL> b) {
    if(a.second != b.second) return a.second < b.second;
    else return a.first < b.first;
}
std::uint32_t euclidean_gcd(std::uint32_t a, std::uint32_t b){return b != 0 ? euclidean_gcd(b, a % b) : a;}


void solve(long long a, long long b, long long h){
    cout<<(a+b)*h/2<<endl;
}

int main(){
    long long a;
    scanf("%lld",&a);
    long long b;
    scanf("%lld",&b);
    long long h;
    scanf("%lld",&h);
    solve(a, b, h);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int a, b, c;
int main(void) {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin >> a >> b >> c) {
        if(a == b) cout << c << endl;
        else if(a == c) cout << b << endl;
        else if(b == c) cout << a << endl;
    }
}

Measured memory_bytes: 256
#include<algorithm>
#include <iostream>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<string>
using namespace std;
int main(){
   
    int n;
    cin>>n;
    
    int x,y;
    x=800*n;
    y=200*(n/15);
    
    cout<<x-y<<endl;
    
    
    return 0;
}






Measured memory_bytes: 256
// --------------
// Tejas Pandey  |
// 19 - 06 - 20  |
// Atcoder BC 171|
// --------------

#include <bits/stdc++.h>
using namespace std;
     
#define mod 1000000007
#define vi vector<int>
typedef long long int ll;
     
int main (void){
  //freopen("in.txt","r",stdin);
  //freopen("out.txt","w",stdout);
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n,k;
  cin >> n >> k;
  int a[n];
  for(int i = 0;i < n;i++) cin >> a[i];
  sort(a,a+n);
  int ans = 0;
  for(int i = 0;i < k;i++) ans += a[i];
  cout << ans;
  return 0;
}


Measured memory_bytes: 3584
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define SIZE 2005

enum Type{
	NOT,
	USED,
};

struct Info{

	bool operator<(const struct Info &arg) const{

		return R+T > arg.R+arg.T;
	}

	int R,A,W,T;
};

int N;
int dp[SIZE][SIZE][2];
Info info[SIZE];

int main(){

	scanf("%d",&N);

	for(int i = 0; i < N; i++){

		scanf("%d %d %d %d",&info[i].R,&info[i].A,&info[i].W,&info[i].T);
	}

	sort(info,info+N);

	for(int i = 0; i <= N; i++){
		for(int k = 0; k <= 2000; k++){
			dp[i][k][NOT] = -BIG_NUM;
			dp[i][k][USED] = -BIG_NUM;
		}
	}

	dp[0][2000][0] = 0;

	for(int i = 0; i < N; i++){

		dp[i][info[i].T][USED] = max(dp[i][info[i].T][USED],info[i].A);

		for(int rest = 2000; rest > 0; rest--){

			dp[i+1][rest][NOT] = max(dp[i][rest][NOT],dp[i][rest][USED]);

			int next = min(rest-info[i].R,info[i].T);

			if(next >= 0){

				dp[i][next][USED] = max(dp[i][next][USED],max(dp[i][rest][NOT]+info[i].A,dp[i][rest][USED]+info[i].W));
			}
		}
	}

	int ans = 0;
	for(int i = 1; i <= 2000; i++){

		ans = max(ans,dp[N][i][NOT]);
	}

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

	return 0;
}



Measured memory_bytes: 34600
def main():
    N = int(input())
    C = input()
    
    ANS = 0
    while 1 == 1:
        i = C.find('W')
        j = C.rfind('R')
        if i == -1 or j == -1:
            break
        if i >= j:
            break
        if i + 1 == j:
            ANS += 1
            break
        C = C[i+1:j]
        ANS += 1
    print(ANS)
if __name__ == '__main__':
    main()

Measured memory_bytes: 9380
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main()
{
    string N;
    ll n=0;
    cin >> N;
    ll l = N.length();
    for(int i=0;i<l;i++){
        n+=(ll)(N[i]-'0');
    }
    if(n%9==0){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    return 0;  
}



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

int main(){
    int a, b, c, x, ans = 0;
    cin >> a >> b >> c >> x;

    for (int i = 0; i <= a; i++) {
        for (int j = 0; j <= b; j++) {
            for (int k = 0; k <= c; k++) {
                if (500 * i + 100 * j + 50 * k == x) ans++;
            }
        }
    }
    cout << ans << endl;

    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;
inline void read(int &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;
}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 2333,mo=1e9+7;
int n,m,a[N],b[N],res;bool vis1[N*N],vis2[N*N];
void GG(){puts("0");exit(0);}
int main() {
	read(n);read(m);
	rep(i,1,n)read(a[i]);sort(a+1,a+n+1);
	rep(i,1,n)vis1[a[i]]=1;
	rep(i,1,m)read(b[i]);sort(b+1,b+m+1);
	rep(i,1,m)vis2[b[i]]=1;
	rep(i,1,n-1)if(a[i]==a[i+1])GG();
	rep(i,1,m-1)if(b[i]==b[i+1])GG();
	int cnt1=0,cnt2=0;res=1;
	per(i,m*n,1){
		cnt1+=vis1[i];cnt2+=vis2[i];
		if(vis1[i]&&vis2[i])continue;
		else if(vis1[i]){
			res=1LL*res*cnt2%mo;
		}
		else if(vis2[i]){
			res=1LL*res*cnt1%mo;
		}
		else {res=1LL*res*(cnt1*cnt2-(n*m-i))%mo;if(cnt1*cnt2-(n*m-i)<=0)GG();}
	}
	cout<<res;
	return 0;
}

Measured memory_bytes: 2304
n=int(input())
a=list(map(int,input().split()))
nums=sum(a)-a[0]
numa=a[0]
def ab(num1,num2):
    return abs(num1-num2)
ans=ab(nums,numa)
for i in range(n-2):
    nums-=a[i+1]
    numa+=a[i+1]
    ans=min(ans,ab(nums,numa))
print(ans)


Measured memory_bytes: 30644
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using ll=long long;
using namespace std;
const long MOD=1e9+7;
template<class T>
T lcm(T a,T b){
    return a/__gcd(a,b)*b;
}
template<class T>
void chmin(T &a,T b){
    if(a>b){
        a=b;
    }
}

int main(){
    string s;cin >> s;
    for(int i=0;i<s.size();i++){
        if((i+1)%2==1 && s[i]=='L'){
            cout << "No";
            return 0;
        }else if((i+1)%2==0 && s[i]=='R'){
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
    public static long mod(long x, long y){
    return x%y<0?x%y+(y<0?-y:y):x%y;
    }
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();		
        long b = 1000000007;
        long sum = 0;
        long mul = 0;
        for(int i=0;i<a;i++){long c = sc.nextLong();
                             sum+=c;
                             mul+=c*c;
                             sum=mod(sum,b);
                             mul=mod(mul,b);
                            }       
        long ans = mod(sum*sum-mul,b);
        if(ans%2==1){ans+=b;}
        ans/=2;
		System.out.println(ans);
	}
}

Measured memory_bytes: 57652
a, b, c, d = (int(i) for i in input().split())

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def lcm(a, b):
	return a * b // gcd (a, b)
  
def divisorNum(cd):
  global a, b
  res = a%cd
  length = b-a+1
  if res!=0:
    first = cd - res
    return (length - (first+1))//cd +1
  else:
    return (length - 1)//cd +1
  
e = lcm(c, d)
ans  = (b-a+1) - divisorNum(c) - divisorNum(d) + divisorNum(e)
print(ans)

Measured memory_bytes: 3064
N = int(input())
S = input() + " "

ans = 0
for i in range(1000) :
    code = str(i).zfill(3)
    j = 0
    for s in S :
        if j == 3 :
            ans += 1
            break
        if s == code[j] :
            j += 1

print(ans)


Measured memory_bytes: 41180
#include<bits/stdc++.h>
#include<vector>
#include<iostream>
#include<map>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<deque>
#define ll long long
using namespace std;
#define BUF_SIZE 1048576
char _buf[BUF_SIZE],*_is=_buf,*_it=_buf;
inline char rdc(){
	if (_is==_it) _it=(_is=_buf)+fread(_buf,1,BUF_SIZE,stdin);
	return *_is++;
}
inline int rdi(){
	int x=0,f=0;
	register char ch=rdc();
	while ((ch<'0' or ch>'9') and (ch^'-')) ch=rdc();
	if (ch=='-') f=1,ch=rdc();
	while (ch>='0' and ch<='9') x=(x<<3)+(x<<1)+(ch^'0'),ch=rdc();
	return f?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline void _write(int x){
	write(x);
	putchar(' ');
}
inline void print(int x){
	write(x);
	putchar('\n');
}
int n,k,x,sum;
int dp[105][100005];
const int md=1000000007;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	int i,j;
	dp[0][0]=1;
	for(i=1;i<=n;++i){
		cin>>x;
		sum=0;
		for(j=0;j<=k;++j){
			sum+=dp[i-1][j];
			if(j>x) sum-=dp[i-1][j-x-1];
			if(sum>=md) sum-=md;
			if(sum<0) sum+=md;
			dp[i][j]=sum;
		}
	}
	cout<<dp[n][k]<<endl;
	return 0;
}

Measured memory_bytes: 40832
#include<stdio.h>

int main(void)
{
    int n=0, i;
    char c[5];
    scanf("%s", &c);

    for(i=0; i<4; i++)
    {
        if(c[i]=='+')
            n++;
        else if(c[i]=='-')
            n--;
    }
    printf("%d\n", n);
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <utility>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define INF 1000000001
#define mod 1000000007
using namespace std;

int main(){
	//cin.tie(0);
	//ios::sync_with_stdio(false);
	int n;
	cin>>n;
	vector<int>a(n),b(n),c(n);
	rep(i,n)cin>>a[i];
	rep(i,n)cin>>b[i];
	rep(i,n)cin>>c[i];
	sort(a.begin(),a.end());
	reverse(a.begin(),a.end());
	sort(b.begin(),b.end());
	reverse(b.begin(),b.end());
	sort(c.begin(),c.end());
	reverse(c.begin(),c.end());

	ll ans=0;
	vector<ll> x(n);
	
	int j=0;
	rep(i,n){
		while(1){
			if(j==n){
				x[i]=j;
				break;
			}
			if(b[i]<c[j]){j++;}
			else{
				x[i]=j;
				//j++;
				break;
			}
		}
	}
	//rep(i,n){
		//cout<<x[i]<<endl;
	//}
	j=0;
	ll y=0;
	rep(i,n){
		while(1){
			if(j==n){
				//y+=x[j-1];
				ans+=y;
				break;
			}
			if(a[i]<b[j]){
				y+=x[j];
				j++;
			}
			else{
				ans+=y;
				//y+=x[j];
				break;
			}
		}
	}
	cout<<ans<<endl;
}
	




Measured memory_bytes: 2176
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Sort(a) sort(a.begin(), a.end())
#define Reve(a) reverse(a.begin(), a.end())
#define PI 3.14159265359
typedef long long ll;
const ll MOD = 1e9+7;

ll gcd(ll a, ll b){
  if(b==0) return a;
  return gcd(b, a%b);
}
/*ll myPow(ll x, ll n, ll m){
  if(n == 0)
    return 1;
  if(n % 2 == 0)
    return myPow(x * x % m, n / 2, m);
  else
    return x * myPow(x, n - 1, m) % m;
}*/

ll lcm(ll a, ll b){
  ll g = gcd(a, b);
  b /= g;
  a *= b;
  return a;
}

//素数判定 O(√n)
bool is_prime(int64_t n){
  for(int64_t i = 2; i*i<=n; i++){
    if(n%i==0) return false;
  }
  return n!=1;
}

//約数の列挙 O(√n)
vector<int64_t> dividor(int64_t n){
  vector<int64_t> res;
  for(int64_t i=1; i*i<=n; i++){
    if(n%i==0){
      res.push_back(i);
      if(i != n/i) res.push_back(i);
    }
  }
  return res;
}

//素因数分解 O(√n)
map<int64_t, int64_t> prime_factor(int64_t n){
  map<int64_t, int64_t> res;
  for(int64_t i=2; i*i<=n; i++){
    while(n%i==0){
      res[i]++;
      n /= i;
    }
  }
  if(n != 1) res[n] = 1;
  return res;
}
struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};



int main(){
  /*int n;
  cin >> n; 
  vector<int> A(n);
  rep(i, n) cin >> A[i];*/ 
  int n, m, a, b; cin >> n >> m;
  vector<int> H(n);
  vector<int> A(n, 1);
  rep(i, n) cin >> H[i];
  rep(i, m){
    cin >> a >> b;
    if(H[a-1]>H[b-1]) A[b-1] = 0;
    else if(H[a-1]<H[b-1]) A[a-1] = 0;
    else {A[b-1] = 0;A[a-1] = 0;}

  }
  int ans = 0;
  rep(i, n){
    if(A[i]==1) ans++;
  }
  cout << ans << endl;
}

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

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

int main(){
    int a,b,k,l,ans=0;
    cin >> a >> b >> k;
    l=gcd(a,b);
    for(int i=1;i<=l+1;i++){
        if(ans==k){
            cout << l/(i-1) <<endl;
            return 0;
        }
        if(l%i==0){
            ans++;
        }
    }
}

Measured memory_bytes: 256
#include<cstdio>

using namespace std;

int main(void){
	
	char str[5];
	int ans[3] = {1,0,0};
	
	while(scanf("%s", str) != EOF){
		int temp = ans[str[0]-'A'];
		ans[str[0]-'A'] = ans[str[2]-'A'];
		ans[str[2]-'A'] = temp;
	}
	
	for(int i = 0; i < 3; i++){
		if(ans[i] == 1)printf("%c\n",i+'A');
	}
	return 0;
}

Measured memory_bytes: 0
import itertools
import math
N = int(input())
x_y = {i : list(map(int, input().split())) for i in range(N)}
P = list(itertools.permutations(range(N)))
tmp = 0
for p in P:
    for n in range(N-1):
        #print(tmp)
        tmp += math.sqrt((x_y[p[n]][0] - x_y[p[n+1]][0])**2 + (x_y[p[n]][1] - x_y[p[n+1]][1])**2)

print(tmp/len(P))



Measured memory_bytes: 45168
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define mp make_pair
#define pp pair<ll,ll>
#define pq_min priority_queue<ll,vector<ll>,greater<ll>>
#define pq_max priority_queue<ll>
#define forx(i,a,b) for(ll i=0;i<a;i++)
#define ld long double
const ll mod=1e9 + 7;
const ll N=15; 
ll power(ll a,ll b)
{
	a=a%mod;
	ll ans=1;
	while(b>0)
	{
		if(b%2==1)
		{
			ans=(ans*a)%mod;
		}
		b=b/2;
		a=(a*a)%mod;
	}
	return ans;
}


ll sumXOR(ll arr[], ll n) 
{ 
    ll sum = 0; 
    for(ll i=0;i<60;i++)  
    { 
        //  Count of zeros and ones 
        ll zc = 0, oc = 0;  
          
        // Individual sum at each bit position 
        ll idsum = 0;  
        for(ll j=0;j<n;j++) 
        { 
            if(arr[j]%2==0) 
                zc++; 
            else
                oc++; 
            arr[j]/=2; 
        } 
          
        // calculating individual bit sum  
        idsum = ((oc*zc)%mod * power(2,i))%mod;  
  
        // final sum     
        sum = (sum + idsum)%mod;  
    } 
    return sum; 
}

int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	srand(time(NULL));
    ll n;
    cin>>n;
    ll a[n];
    for(ll i=0;i<n;i++)
    {
    	cin>>a[i];
	}
	cout<<sumXOR(a,n)<<endl;
}



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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(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 U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
  for(auto &e:u) fill_v<T>(e,v...);
}

int64 dy[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int64 dx[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

int main(void) {
  int64 h, w;
  while (cin >> h >> w && h +w) {
    vector<string> s(h);
    REP(i, h) cin >> s[i];
    map<string, int> mp;
    REP(sy, h) {
      REP(sx, w) {
        mp[string(1, s[sy][sx])]++;
        REP(d, 8) {
          int64 yy = sy, xx = sx;
          vector<vector<int>> used(h, vector<int>(w, 0));
          string t(1, s[sy][sx]);
          while (!used[yy][xx]) {
            used[yy][xx] = 1;
            yy = (yy + dy[d] + h) % h; xx = (xx + dx[d] + w) % w;
            if (!used[yy][xx]) {
              t += s[yy][xx];
              mp[t]++;
            }
          }
        }
      }
    }
    string res = "";
    for (auto& x : mp) {
      if (x.sc > 1) {
        if (res.size() < x.fs.size()) {
          res = x.fs;
        } else if (res.size() == x.fs.size()) {
          if (res >= x.fs) {
            res = x.fs;
          }
        }
      }
    }
    if (res.size() == 0) cout << 0 << endl;
    else cout << res << endl;
  }
}



Measured memory_bytes: 37876
arr=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
n=int(input())
print(arr[n-1])

Measured memory_bytes: 8928
import java.io.*;
import java.util.*;

public class Main {

    private static FastReader in = new FastReader(System.in);
    private static PrintWriter out = new PrintWriter(System.out);

    private static final long MOD = (long) 1e9 + 7;

    public static void main(String[] args) {
        solve();
        out.flush();
    }

    private static void solve() {
        int h = in.nextInt();
        int a = in.nextInt();
        out.println(
                h / a + (h % a == 0 ? 0 : 1)
        );
    }

    // https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        FastReader(InputStream inputStream) {
            br = new BufferedReader(new
                    InputStreamReader(inputStream));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException  e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        // https://qiita.com/masakinpo/items/5f77f2a879578a85a0bb
        public int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        public long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
    }
}


Measured memory_bytes: 21204
import java.io.*;
import java.lang.*;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.util.StringTokenizer;
import java.math.BigInteger;

public class Main {
    static InputReader in = new InputReader(System.in);
    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        String s = in.next();
        String ans = "";
        for(int i = 0; i<s.length(); i++){
            ans += 'x';
        }
        out.println(ans);
        out.close();
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public String nextLine() {
            try {
                return reader.readLine();
            } catch (Exception e) {
                e.printStackTrace();
            }
            return null;
        }

        public boolean hasNext() {
            String next = null;
            try {
                next = reader.readLine();
            } catch (Exception e) {
            }
            if (next == null) {
                return false;
            }
            tokenizer = new StringTokenizer(next);
            return true;
        }

        public BigInteger nextBigInteger() {
            return new BigInteger(next());
        }
    }
}



Measured memory_bytes: 36808
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<math.h>
#include<map>
typedef long long int ll;
using namespace std;
#define maxn 0x3f3f3f3f


int main()
{
    ll k,n,a[200050];
    scanf("%lld%lld",&k,&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    sort(a+1,a+n+1);
    ll minn=a[n]-a[1];
    for(int i=2;i<=n;i++)
    {
        minn=min(minn,k-a[i]+a[i-1]);
    }
    printf("%lld\n",minn);
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i,n) for (ll i=0; i<(n); i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
 
int main(){
    int A,B; cin >> A >> B;
    if (A==B){
        cout << "Draw" << endl;
        return 0;
    }
    else if (A==1 && B!=1){
        cout << "Alice" << endl;
        return 0;
    }
    else if (B==1 && A!=1){
        cout << "Bob" << endl;
        return 0;
    }
    
    if(A>B) cout << "Alice" << endl;
    else cout << "Bob" << endl;
    return 0;
}

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

int main(void){
    ll ans = 0;
    ll N;
    cin >> N;
    vector<ll> f(N + 1, 0);
    for(ll i = 1; i <= N; i++){
        for(ll j = 1; i * j <= N; j++) ans += i * j;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 81388
#include<iostream>
using namespace std;
int main()
{
	long long x,y;
	cin>>x>>y;
	long long ans = x*y;
	ans = ans - x;
	if(ans%y)
	{
		cout<<ans<<endl;
	}
	else
	{
		ans=-1;
		cout<<ans<<endl;
	}
}

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

int saiki(int x){
    if(x>=2){
        return saiki(x/2)*2+1;
    }
    else{
        return 1;
    }
}

signed main(){
    int H;
    cin>>H;
    cout <<saiki(H)<<endl;
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	c := make([]int, n+1)
	for x := 1; x < 100; x++ {
		for y := 1; y < 100; y++ {
			for z := 1; z < 100; z++ {
				i := x*x + y*y + z*z + x*y + y*z + z*x
				if i <= n {
					c[i]++
				}
			}
		}
	}
	for i := 1; i <= n; i++ {
		fmt.Println(c[i])
	}
}


Measured memory_bytes: 1984
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double lf;
typedef pair<ll,ll> ii;
typedef pair<ii,ll> iii;
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define RST(i,n) memset(i,n,sizeof i)
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(),a.end()
#define X first
#define Y second
#define mkp make_pair
#define pb push_back
#define eb emplace_back
#define pob pop_back
#ifdef cold66
#define debug(...) do{\
    fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<", ";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#endif // cold66
//}
template<class T> inline bool chkmax(T &a, const T &b) { return b > a ? a = b, true : false; }
template<class T> inline bool chkmin(T &a, const T &b) { return b < a ? a = b, true : false; }
template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;

const ll MAXn=1e5+5,MAXlg=__lg(MAXn)+2;
const ll MOD=1000000007;
const ll INF=0x3f3f3f3f;

vector<ii> e[MAXn];
ll c[MAXn];
void dfs(ll x,ll p,bool color){
    c[x] = color;
    for (auto i:e[x]) {
        if (i.X == p) continue;
        if (i.Y&1) dfs(i.X,x,!color);
        else dfs(i.X,x,color);
    }
}
int main(){
    IOS();
    ll n;
    cin >> n;
    REP (i,n-1) {
        ll u,v,w;
        cin >> u >> v >> w;
        u--,v--;
        e[u].eb(v,w);
        e[v].eb(u,w);
    }
    dfs(0,0,0);
    REP (i,n) cout << c[i] << endl;
}


Measured memory_bytes: 11008
#include <bits/stdc++.h>
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define reprrev(i,a,b) for(int i=b-1;i>=a;i--) // [a, b)
#define reprev(i,n) reprrev(i,0,n)
typedef long long ll;
typedef unsigned long long ull;
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; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/

const ll mod = 1e9+7;

void chmod(ll &M){
    if(M >= mod) M %= mod;
    else if(M < 0){
        M += (abs(M)/mod + 1)*mod;
        M %= mod;
    }
}

ll modpow(ll x, ll n){
    if(n==0) return 1;
    ll res=modpow(x, n/2);

    if(n%2==0) return res*res%mod;
    else return res*res%mod*x%mod;
}

int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };


// 線分 ab の偏角 返り値は[-π, π]
double argument(const pair<double, double> &a, const pair<double, double> &b){
    double ax=a.first, ay=a.second, bx=b.first, by=b.second;
    return atan2(by-ay, bx-ax);
}

/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */

void trace (vector<int> const & a) {
    int n = a.size();
    for(int i=0; i<n; ++i) {
        if(i) cout << " ";
        cout << a[i];
    }
    cout << endl;
}

void insertionSort(vector<int> &a, int g, int &cnt) {
    int n = a.size();
    for(int i=g; i<n; ++i) {
        int j = i-g;
        int v = a[i];
        while(j>=0 && a[j] > v) {
            ++cnt;
            a[j+g] = a[j];
            j -= g;
        }
        a[j+g] = v;
    }
}

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

    int n; cin >> n;
    vector<int> a(n);
    for(int i=0; i<n; ++i) cin >> a[i];
    int cnt = 0;
    
    vector<int> G;
    G.push_back(1);
    for(int i=4; i<n; i=3*i+1) G.push_back(i);
    reverse(G.begin(), G.end());
    for(auto g: G) insertionSort(a, g, cnt);
    
    cout << G.size() << endl;
    trace(G);
    cout << cnt << endl;

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


    return 0;
}



Measured memory_bytes: 6780
#include"bits/stdc++.h"
// #include "prettyprint.hpp"

using namespace std;

typedef long long ll;

#define rep(i, n) for(ll i=0; i<n; i++)
#define repr(i, n) for(ll i=n; i>=0; i--)
#define reps(i, s, e) for(ll i=s; i<e; i++)
#define all(x) x.begin(),x.end()


int main(){
	int H,N;

	cin >> H >> N;

	ll sum = 0;
	vector<int> A(N);

	rep(i,N){
		cin >> A[i];
		sum += A[i];
	}

	if(H<=sum) cout << "Yes" << endl;

	else cout << "No" << endl;

	return 0;
	
}


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

int main () {
  int a[50],b[50],road[50];
  int N,M;
  
  cin >> N >> M;
  for(int i = 0;i < M;i++){
    cin >> a[i] >> b[i];
  }
  for(int i = 0;i < N;i++){
  	road[i] = 0;
  }
  
  for(int i = 0;i < M;i++){
  	road[a[i]-1]++;
    road[b[i]-1]++;
  }
  for(int i = 0;i < N;i++)
    cout << road[i]<< endl;
}

Measured memory_bytes: 256
from itertools import accumulate

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a_acc = [0] + list(accumulate(a))
b_acc = [0] + list((accumulate(b)))

ans = 0
bn = m

for an in range(n + 1):
    rem = k - a_acc[an]
    if rem < 0:
        break

    # rem >= 0 かつ、b_acc[0] = 0なので、bnはどんなに減っても0で必ず止まります。マイナスになってバグることはありません
    while b_acc[bn] > rem:
        bn -= 1
    ans = max(ans, an + bn)

print(ans)

Measured memory_bytes: 135372
h,w=map(int,input().split())
s=[]
for _ in range(h):
    s.append(input())

dp=[]
ch=[]
for _ in range(h):
    tempDP=[]
    tempCh=[]
    for _ in range(w):
        tempCh.append(0)
        tempDP.append(0)
    dp.append(tempDP)
    ch.append(tempCh)

#startposi
if s[0][0]=="#":
    dp[0][0]=1
    ch[0][0]=1

for x in range(1,w):
    if s[0][x]=="#":
        ch[0][x] = 1
        if ch[0][x-1]==1:
            dp[0][x] = dp[0][x-1]
        else:
            dp[0][x] = dp[0][x-1]+1
    else:
        dp[0][x] = dp[0][x - 1]

for y in range(1,h):
    if s[y][0]=="#":
        ch[y][0] = 1
        if ch[y-1][0]==1:
            dp[y][0] = dp[y-1][0]
        else:
            dp[y][0] = dp[y-1][0]+1
    else:
        dp[y][0] = dp[y-1][0]


for y in range(1,h):
    for x in range(1,w):
        if s[y][x]==".":
            dp[y][x]=min(dp[y][x-1],dp[y-1][x])
        else:
            ch[y][x]=1
            if ch[y-1][x]==1:
                dp[y][x]=dp[y-1][x]
            else:
                dp[y][x]=dp[y-1][x]+1

            if ch[y][x-1]==1:
                dp[y][x]=min(dp[y][x],dp[y][x-1])
            else:
                dp[y][x]=min(dp[y][x],dp[y][x-1]+1)


print(dp[h-1][w-1])



Measured memory_bytes: 41968
// https://atcoder.jp/contests/abc072/tasks/abc072_c
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    map<int, int> mp;
    REP(i, n) {
        int t;
        cin >> t;
        mp[t]++;
    }
    int maxv = 0;
    pii p[2];
    for (auto &x : mp) {
        int sum = x.second;
        REP(i, 2) {
            if (p[i].first >= x.first - 2) {
                sum += p[i].second;
            }
        }
        maxv = max(maxv, sum);
        p[1] = p[0];
        p[0] = x;
    }
    cout << maxv << endl;
    return 0;
}


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

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

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

int main()
{
    ll A, B, C;
    cin >> A >> B >> C;
    ll x = std::min(C, B);
    C -= x;
    B -= x;
    ll y = std::min(C, A);
    C -= y;
    A -= y;
    cout << 2 * x + y + std::min(1LL, C) + std::max(0LL, B) << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int[] w = new int[n];

		for (int i = 0; i < w.length; i++) {
			w[i] = sc.nextInt();
		}

		int[] sub = new int[n - 1];
		int idx = 0;
		for (int t = 1; t < w.length; t++) {
			int s1 = 0;
			for (int i = 0; i < t; i++) {
				s1 += w[i];
			}
			int s2 = 0;
			for (int i = t; i < w.length; i++) {
				s2 += w[i];
			}

			sub[idx++] = Math.abs(s1 - s2);
		}

		Arrays.sort(sub);

		System.out.println(sub[0]);
		sc.close();
	}
}


Measured memory_bytes: 23124
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		long x = stdIn.nextLong();
		long step = 0;
		long a = 100;
		while(a < x) {
			a+= a/100;
			step++;
		}
		System.out.println(step);
		
		
	}

}


Measured memory_bytes: 35760
import java.io.File;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

/*
 * メモ
 * Scanner:nextは空白か改行までの単語
 * String[][] c = new String[h][w];
 * TemplateMain,"template_input.txt"
 * Deque deque = new ArrayDeque<String>();
 */

public class Main {
	
	public static void printlnYN(boolean b){
		if(b) System.out.println("Yes");
		else System.out.println("No");
	}

	public static void main(String[] args) throws IOException {
		
		//File file = new File("input.txt");
		//Scanner sc = new Scanner(file);
		
		Scanner sc = new Scanner(System.in);
		
		while(true) {
	    	int w = sc.nextInt();
	    	int h = sc.nextInt();
	    	if(w == 0 && h == 0) break;
	    	
	    	int[][] map = new int[h][w];
	    	for(int i = 0; i < h; i++) {
	    		for(int j = 0; j < w; j++) {
	    			String s = sc.next();
	    			if(s.equals("0")) map[i][j] = 0;
	    			else map[i][j] = 1;
	    		}
	    	}
	    	
	    	int count = 2;
	    	for(int i = 0; i < h; i++) {
	    		for(int j = 0; j < w; j++) {
	    			if(map[i][j] == 1) {
	    				map = find(map, h, w, count, i, j);
	    				count++;
	    			}
	    		}
	    	}
	    	
	    	
	    	System.out.println((count-2));
		}
		sc.close();
    }
	
	@SuppressWarnings({ "unchecked", "rawtypes" })
	public static int[][] find(int[][] map, int h, int w, int count, int s_y, int s_x) {
		Deque deque = new ArrayDeque<int[]>();
		int[] s = {s_y, s_x};
		map[s_y][s_x] = count;
		deque.addFirst(s);
		
		while(true) {
			int[] p = (int[])deque.pollFirst();
			
			if(p == null) break;
			
			int[] dy = {0, -1, -1, -1, 0, 1, 1, 1};
			int[] dx = {1, 1, 0, -1, -1, -1, 0, 1};
			int y = p[0];
			int x = p[1];
			
			for(int i = 0; i < 8; i++) {
				int next_y = y + dy[i];
				int next_x = x + dx[i];
				if(next_y >= 0 && next_y < h && next_x >= 0 && next_x < w) {
					if(map[next_y][next_x] == 1) {
						map[next_y][next_x] = count;
						int[] next_p = {next_y, next_x};
						deque.addFirst(next_p);
					}
				}
			}
		}
		
		return map;
	}
}


Measured memory_bytes: 41940