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

typedef long long int int64;
int q;
int64 a,b,c,d;
int main()
{
	scanf("%d",&q);
	while(q--) {
		scanf("%lld%lld%lld%lld",&a,&b,&c,&d);--c;
		int64 l = (a+b) / std::min(a+1,b+1); // l > 1
		if(l == 1) {
			// a==b || a==b+1 || a==b-1
			if(a == b-1) { ++c; ++d; }
			for(int i = c;i < d;++i) putchar(i%2==0?'A':'B');
			printf("\n");
			continue;
		}
		int64 rem = (int64)l*(a+1)-b;
		int64 cnt1 = std::min((rem-1)/(l*l-1),std::min(a/l,b)); // A*l+B
		if(cnt1 < 0) cnt1 = 0;
		int64 cnt1l = cnt1*(l+1);
		rem -= cnt1 * (l*l-1);
		while(c < d && c < cnt1l) {
			putchar(c%(l+1)==l?'B':'A');
			++c;
		}
		a -= cnt1*l;b -= cnt1;
		if(c < cnt1l) { printf("\n"); continue; } c -= cnt1l; d -= cnt1l;

		int64 cnt2 = rem / l; // A
		while(c < d && c < cnt2) {
			putchar('A');
			++c;
		}
		a -= cnt2;
		if(c < cnt2) { printf("\n"); continue; } c -= cnt2; d -= cnt2;
		rem -= cnt2 * l;

		if(rem > 0) {
			int cnt3 = l - rem; // B
			while(c < d && c < cnt3) {
				putchar('B');
				++c;
			}
			b -= cnt3;
			if(c < cnt3) { printf("\n"); continue; } c -= cnt3; d -= cnt3;
			while(c < d && c < 1) {
				putchar('A');
				++c;
			}
			--a;
			if(c < 1) { printf("\n"); continue; } --c; --d;
		}

		int cnt4 = b / l; // B*l+A
		int cnt4l = cnt4 * (l+1);
		while(c < d && c < cnt4l) {
			putchar(c%(l+1)==l?'A':'B');
			++c;
		}
		printf("\n");
	}
}


Measured memory_bytes: 384
# A - Integer Product 
n = int(input())
a = [input() for _ in range(n)]

# bi=ai*(10**9)とすると、(aiは小数第9位までの小数だからbiは整数)
# ai*ajが整数<=>bi*bj/(10**18)が整数<=>bi*bjが素因数に2を18個、5を18個持つ。
# p2[i]:biを素因数分解したときの2の数。
# p5[i]:biを素因数分解したときの5の数。
# c25[i][j]:bi...bnのうち、素因数に2をi個以上、5をj個以上持つbiの数。
# biに対して、ペアになれるのはc25[18-p2[i]][18-p5[i]]個。
# ただし、自分自身は含めないのでbiが素因数として2を9個以上、5を9個以上もつときは―1する。
# また、(bi,bj)と(bj,bi)を重複して数えてしまうので、最後に//2する。

p2 = [0 for _ in range(n)]
p5 = [0 for _ in range(n)]

for i in range(n):
  # Decimalを使ったらTLEしてしまったので、文字列操作でbiを計算する。
  if '.' in a[i]:
    bi = int(a[i].replace('.','')+'0'*(9-(len(a[i])-a[i].index('.')-1)))
  else:
    bi = int(a[i])*(10**9)
  c = 0
  while(bi%2 == 0 and c < 18):
    c += 1
    bi //= 2
  p2[i] = c
  c = 0
  while(bi%5 == 0 and c < 18):
    c += 1
    bi //= 5
  p5[i] = c

c25 = [[0 for _ in range(20)] for _ in range(20)]
for i in range(n):
  c25[p2[i]][p5[i]] += 1
for i in range(18,-1,-1):
  for j in range(18,-1,-1):
    c25[i][j] += c25[i+1][j]+c25[i][j+1]-c25[i+1][j+1]

ans = 0
for i in range(n):
  ans += c25[18-p2[i]][18-p5[i]]
  if p2[i] >= 9 and p5[i] >= 9:
    ans -= 1
print(ans//2)


Measured memory_bytes: 121756
import java.util.Scanner;

public class Main {

   public static void main(final String[] args) {

      Scanner sc = new Scanner(System.in);
      int x = sc.nextInt();
      if(x==1) {
         System.out.println(0);
      } else if(x==0) {
         System.out.println(1);
      }
   }  
}

Measured memory_bytes: 35680
# include <bits/stdc++.h>
# define sz(x) (int)((x).size())
# define F first
# define S second
# define pb push_back
# define ub upper_bound
# define lb lower_bound
# define all(x) x.begin(), x.end()
# define pqueue priority_queue
# define mset multiset
# define umap unordered_map
# define Speed() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
# define rep(i,n) for(int i=0;i<n;++i)
# define forn(i,n) for(int i=1;i<=n;++i)
# define lr(i,l,r) for(int i=l;(l>r?i>=r:i<=r);(l>r?--i:++i))

using namespace std;

template<class T> void umin(T &a,T b){a=min(a,b);}
template<class T> void umax(T &a,T b){a=max(a,b);}

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

const int dx[]={1,0,-1,0,-1,-1,1,1},dy[]={0,1,0,-1,-1,1,-1,1}; 
const int mod = 1e9+7;
const ll N = 1e5+4;

ll n,ans;

void solve(){
	string s,t;
	cin>>s>>t;
	string ans(sz(s),'z');
	bool has=0;
	for(int i=0;i<sz(s)-sz(t)+1;++i){
		bool ok=1;
		for(int j=0;j<sz(t);++j){
			if(s[i+j]!='?' && s[i+j]!=t[j]){
				ok=0;
				break;
			}
		}
		if(!ok)continue;
		if(ok)has=1;
		string zz=s;
		for(int j=0;j<sz(t);++j){
			if(zz[i+j]=='?' && zz[i+j]!=t[j]){
				zz[i+j]=t[j];
			}	
		}
		rep(i,sz(zz))if(zz[i]=='?')zz[i]='a';
		umin(ans,zz);
	}
	if(!has)cout<<"UNRESTORABLE";
	else cout<<ans;
}

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

Measured memory_bytes: 3624
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;

#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define DEB 0
#define all(x) x.begin(), x.end()

int dp[5][32770];

int main(){
  for(int i=1; ; i++){
    if( i*i>(1<<15) )break;
    dp[1][i*i] = 1;
    for(int j=i*i+1; j<=(1<<15); j++){
      for(int k=1; k<4; k++){
	dp[k+1][j] += dp[k][j-i*i];
      }
    }
  }
#if DEB
  rep(i,30){
    rep(k,5){
      printf("i:%d  k:%d  ::%d\n",i,k,dp[k][i]);
    }
  }
#endif
  int n;
  while(scanf("%d",&n),n){
    printf("%d\n",dp[1][n]+dp[2][n]+dp[3][n]+dp[4][n]);
  }
  return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<vector>
#include<queue>
#define rep(i,n) for (int i = 0; i < n; i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int n;
void dfs(string s, char mx) {
  if (s.size() == n) {
    cout << s << endl;
    return;
  }
  for (char c = 'a'; c <= mx+1; c++) {
    string t = s;
    t += c;
    dfs(t, max(mx, c));
  }
}

int main() {
  cin >> n;
  dfs("", 'a'-1);
  return 0;
}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define rep(i,n) for(int (i) = 0, i_len = n; (i) < (i_len); ++(i))
#define repp(i,n) for(int (i) = 1, i_len = n; (i) <= (i_len); ++(i))
#define per(i,n) for(int (i) = n-1; (i) >= 0; --(i))
#define perr(i,n) for(int (i) = n; (i) > 0; --(i))
#define sz(x) ((int)(x).size())
#define popcnt __builtin_popcount
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).begin(),(v).end(),greater<>()
#define Pi 3.1415926535
#define MOD = 1e9+7;
using namespace std;
using ll = long long;
using pint = pair<int,int>;
using itn = int;
using vint = vector<int>;
template<class T,class S> inline bool chmax(T& a, S b){if(a<b){a = b; return true;} return false;}
template<class T,class S> inline bool chmin(T& a, S b){if(a>b){a = b; return true;} return false;}
template<class T> T gcd(T a, T b){return b?gcd(b,a%b):a;}
template<class T> T lcm(T a, T b){return a*b/gcd(a,b);}

int solve(){
    int x,y,z; cin >> x >> y >> z;
    cout << z << " " << x << " " << y << endl;

    return 0;
}

int main(){
    cin.tie(0);
    cout << fixed << setprecision(10);
    ios::sync_with_stdio(false);
    solve();
    return 0;
}
 

Measured memory_bytes: 256
S = list(input())
T = list(input())

dp = [[0 for i in range(len(S)+1)] for j in range(len(T)+1)]

for i in range(1,len(T)+1):
    for j in range(1,len(S)+1):
        if T[i-1]==S[j-1]:
            dp[i][j]=max(dp[i-1][j-1]+1,dp[i][j-1],dp[i-1][j])
        else:
            dp[i][j]=max(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])
    # print(dp)


i = len(S)
j = len(T)
ans = []
while (i>0  and j>0):
    if dp[j][i] == dp[j-1][i]:
        j -= 1
    elif dp[j][i] == dp[j][i-1]:
        i -= 1
    else:
        ans.append(T[j-1]) 
        i -= 1
        j -= 1


print("".join(reversed(ans)))

Measured memory_bytes: 120028
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;++i)
#include<string>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int, int>P;
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; }
//max=({});
//条件式が真ならwhileの中身を回し続ける
//printf("%d\n", ans);

//pairの入力
//vector<pair<ll, ll>>work(n);
//rep(i, n) {
//	ll a, b;
//	cin >> a >> b;
//	work[i] = make_pair(a, b);
//for(auto p:mp)(mapの探索)
//printf("%.10f\n",なんちゃら)

int g[15][15];
const int INF = 1001001001;
const int dx[4] = { -1,0,1,0 };
const int dy[4] = { 0,-1,0,1 };

//最大公約数
ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y) : x;
}

ll lcm(ll x, ll y) {
	if (x == 0 || y == 0)return 0;
	return (x / gcd(x, y) * y);
}

//素因数分解
map<ll, ll>ins;
void facterize(ll n) {
	ll a = 2;
	while (n >= a * a) {
		if (n % a == 0) {
			ins[a]++;
			ins[a] = ins[a] % 1000000007;
			n /= a;
		}
		else {
			a++;
		}
	}
	ins[n]++;
}

vector<ll>relation[20], money(20, 1);
char s[110][110];
int dp[110][110];

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	if (a + b < c) {
		cout << a + 2 * b + 1 << endl;
	}
	else {
		cout << b + c << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
bool same(const string& s){
	bool res=true;
	for(int i=1;i<s.size();i++)
		if(s[i]!=s[i-1])
			res=false;
	return res;
}
bool all(const string& s){
	bool res=true;
	for(int i=1;i<s.size();i++)
		if(s[i]==s[i-1])
			res=false;
	return res;
}
long long int dp[200000][3][3][2];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin>>s;
	int n=s.size();
	if(same(s))
		cout<<1<<endl;
	else if(n==2)
		cout<<2<<endl;
	else if(n==3){
		if(s[0]!=s[1]&&s[1]!=s[2]&&s[2]!=s[0])
			cout<<3<<endl;
		else if(s[0]==s[2])
			cout<<7<<endl;
		else
			cout<<6<<endl;
	}
	else{
		long long int ans=all(s);
		int sum=0;
		for(int i=0;i<n;i++)
			sum=(sum+s[i]-'a')%3;
		for(int i=0;i<3;i++)
			dp[0][i][i][0]=1;
		for(int i=0;i<n-1;i++)
			for(int j=0;j<3;j++)
				for(int k=0;k<3;k++)
					for(int l=0;l<2;l++)
						for(int m=0;m<3;m++)
							dp[i+1][(j+m)%3][m][l|(m==k)]=(dp[i][j][k][l]+dp[i+1][(j+m)%3][m][l|(m==k)])%mod;
		for(int i=0;i<3;i++)
			ans+=dp[n-1][sum][i][1];
		cout<<ans%mod<<endl;
	}
}


Measured memory_bytes: 28692
import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int[] h = new int[n];
		int count = 0;
		for (int i = 0; i < n; i++) {
			h[i] = sc.nextInt();
		}
		for (int i = 0; i < n; i++) {
			if (h[i] >= k) {
				count++;
			}
		}
		System.out.println(count);
	}
}

Measured memory_bytes: 60880
import java.util.Arrays;

public class Main {
	public static void main(String[] args) {
		java.util.Scanner s = new java.util.Scanner(System.in);
		int n = s.nextInt();
		int d[] = new int[n];
		for (int i = 0; i < n; i++) {
			d[i] = s.nextInt();
		}
		Arrays.sort(d);
		System.out.println(d[n / 2] - d[n / 2 - 1]);
	}
}


Measured memory_bytes: 50200
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#define MP make_pair
#define PB push_back
#define ALL(a)  (a).begin(),(a).end()
#define REP(i,n)  for(int i=0;i<(n);++i)
using namespace std;
typedef pair<int,int> P;
int main(){
	int times;
	cin>>times;
	REP(i,times){
		int n,k;
		cin>>n>>k;
		int x[100100];
		REP(j,n)cin>>x[j];
		vector<int>v;
		REP(j,n-1){
			v.PB(x[j+1]-x[j]);
		}
		sort(ALL(v));
        reverse(ALL(v));
        int btw=x[n-1]-x[0];
        REP(j,min(n-1,k-1)){
            btw-=v[j];
        }
        cout<<max(0,btw)<<endl;
    }
}




Measured memory_bytes: 4200
#include<vector>
#include<iostream>
#include<algorithm>
#include<functional>
#include<string>
#include<limits.h>
#include<cmath>
using namespace std;



int main(){

  int n; cin >> n;
  vector<int> s(n);
  for (int i=0; i<n; i++){cin >> s[i];}
  int q; cin >> q;
  vector<int> t(n);
  for (int i=0; i<q; i++){cin >> t[i];}

  int c=0;

  for (int i=0; i<q; i++){
    for (int j=0; j<n; j++){
      if (t[i]==s[j]){c++;break;}
    }
  }

  cout << c << endl;

  return 0;
}



Measured memory_bytes: 3148
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<stack>
using namespace std;

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

string S, T, ans;
signed main() {
	cin >> S >> T;
	ans = S;
	int lenS = S.length();
	int lenT = T.length();
	bool matched = false;
	for (int i = lenS-1; i >= lenT-1; i--) {
		for (int k = 0;k < lenT; k++) {
			//cout << T[lenT - 1 - k] << " " << S[i - k] << endl;
			if (T[lenT - 1 - k] != S[i - k] && S[i - k] != '?') break;
			if (k == lenT - 1) matched = true;
		}
		if (matched) {
			for (int k = 0;k < lenT; k++) {
				ans[i - k] = T[lenT - 1 - k];
			}
			break;
		}
	}
	if (!matched) ans = "UNRESTORABLE";
	else {
		for (int i = 0;i < lenS;i++) {
			if (ans[i] == '?') ans[i] = 'a';
		}
	}

	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define forr(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = 1; i <= (n); i++)
#define ALL(a) (a.begin()),(a.end())
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll, ll> LP;
const ll LINF = 1LL<<60;
const int INF = 1001001001;
const int MOD = 1000000007;

/* --------------------------------------------------- */

int main() {
    string s;
    cin >> s;
    vector<int> A(4);
    rep(i, 4) A[i] = s[i] - '0';
    rep(s, (1 << 3)) {
        int tot = 7 - A[0];
        vector<string> B(3);
        rep(i, 3) {
            if((s >> i) & 1) {
                tot -= A[i + 1];
                B[i] = '+';
            } else {
                tot += A[i + 1];
                B[i] = '-';
            }
        }
        if(tot == 0) {
            rep(j, 3) cout << A[j] << B[j];
            cout << A[3] << "=7" << endl;
            return 0;
        }
    } 
    return 0;
}

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

int main() {
  int rank[4];
  int n[4];
  int out[4];
  int price;

  for(int i = 0; i < 4; i++) {
    cin >> rank[i] >> n[i];
    if(rank[i] == 1) price = 6000;
    else if(rank[i] == 2) price = 4000;
    else if(rank[i] == 3) price = 3000;
    else price = 2000;
    out[i] = price * n[i];
  }

  for(int i = 0; i < 4; i++) cout << out[i] << endl;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
#define pb push_back
#define fr first
#define sc second
#define all(x) x.begin(), x.end()
#define skip continue
#define NAME "code"
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
void faster(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
 
const int MAXN = 2e5 + 1;
const ll INF = 1e18;
const ld pi = acos(-1);

ll n, a[MAXN], b[MAXN], ans;

int main() {

    faster();

    cin >> n;

    for(int i = 1; i <= n; ++i){
        cin >> a[n - i + 1];
        cin >> b[n - i + 1];
    }

    for(int i = 1; i <= n; ++i){
        a[i] += ans;
        ans += (((b[i] - a[i]) % b[i] + b[i]) % b[i]);
    }

    cout << ans;

    return 0;
}

Measured memory_bytes: 1792
#include<vector>
#include<iostream>
#include<list>
#include<algorithm>
#include<chrono>
#include<map>
#include<set>
#include<string>
#include<unordered_map>

using namespace std;


int main()
{
    int n;
    long long ans = 0;
    cin >> n;
    for(long long j = 1; j <= n; j++){
        long long h = n/j;
        ans += j*(1+h)*h/2;
    }
    cout << ans;
}

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

using namespace std;

int main(){
    int N;
    cin >> N;
    int cake = 4,doughnut = 7;
    int result = 0;
    for(int i = 0; i < (N / doughnut) + 1;i++){
        if((N - i * doughnut) % cake == 0){
            result = 1;
            break;
        } 
    }
    if(result == 1){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

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

int main()
{ 
  int N,M,s,c;
  bool x = true;
  cin >> N >> M;
  int value[N] = {-1};
  for(int i = 0; i < N;i++){
    value[i] = -1;
  }
  int v = 0;
  for(int i = 0; i < M;i++){
    cin >> s >> c;
    if(value[s-1] != -1 && value[s-1] != c){
      x = false;
    }
    else value[s-1] = c;
  }

  if(value[0] == 0 && N != 1) x = false;
  else{
    for(int i = 0; i < N;i++){
      if(i == 0 && value[0] == -1 && N != 1) value[0] = 1;
      else if(value[i] == -1) value[i] = 0;
    }
  }
  for(int i = 0; i < N;i++){
    v = 10 * v + value[i];
  }
  if(!x) cout << -1 << endl;
  else cout << v << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>

using namespace std;


long long mul_inv(long long a, long long b)
{
	long long b0 = b, t, q;
	long long x0 = 0, x1 = 1;
	if (b == 1) return 1;
	while (a > 1) {
		q = a / b;
		t = b, b = a % b, a = t;
		t = x0, x0 = x1 - q * x0, x1 = t;
	}
	if (x1 < 0) x1 += b0;
	return x1;
}

long long division(long long a, long long b, long long p) {		// (a / b) mod p = ((a mod p) * (b^(-1) mod p)) mod p
	long long ans, inv;
	inv = mul_inv(b, p);
	ans = ((a % p) * inv) % p;
	return ans;
}

long long gcd(long long a, long long b)
{
	while (b != 0) {
		long long t = b;
		b = a % b;
		a = t;
	}
	return a;
}


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

	long long n, m, a, b, c, MOD = 1000000007, r, ans, nn, i, j, k, p, q, pp, qq, x, newp, newq, a2, b2, ab, g;
	cin >> n >> a >> b >> c;

	nn = n * 2;
	vector<long long> fact(nn), aa(nn), bb(nn), f100(nn);
	fact[0] = 1; aa[0] = 1; bb[0] = 1; f100[0] = 1;
	a2 = division(a, a + b, MOD);
	a2 = (a2 * 100) % MOD;
	b2 = division(b, a + b, MOD);
	b2 = (b2 * 100) % MOD;

	for (i = 1; i < nn; i++) {
		fact[i] = (fact[i - 1] * i) % MOD;
		aa[i] = (aa[i - 1] * a2) % MOD;
		bb[i] = (bb[i - 1] * b2) % MOD;
		f100[i] = (f100[i - 1] * 100) % MOD;
	}

	p = 0; q = 1;
	for (m = n; m < nn; m++) {
		pp = (fact[m - 1] * m) % MOD;
		x = (aa[n] * bb[m - n] + aa[m - n] * bb[n]) % MOD;
		pp = (pp * x) % MOD;

		qq = (fact[n - 1] * fact[m - 1 - (n - 1)]) % MOD;
		x = (f100[m - 1] * (100 - c)) % MOD;
		qq = (qq * x) % MOD;

		newp = (p * qq + pp * q) % MOD;
		newq = (q * qq) % MOD;

		p = newp;
		q = newq;
	}

	g = gcd(p, q);
	p /= g;
	q /= g;

	ans = division(p, q, MOD);

	cout << ans << "\n";

	return 0;
}




Measured memory_bytes: 6528
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <array>
#include <bitset>
#include <assert.h>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

const int N = 510;
double dp[N][N];

int main() {
    int n, m;
    cin >> n >> m;
    VI a(n);
    REP(i,n) a[i] = in();

    vector<double> sum(n+1);
    REP(i,n) sum[i+1] = sum[i] + a[i];

    REP(i,N) REP(j,N) dp[i][j] = -1e9;

    dp[0][0] = 0;
    REP(k,m) REP(i,n+1){
        REP(j,i){
            dp[k+1][i] = fmax(dp[k+1][i], dp[k][j] + (sum[i] - sum[j]) / (i - j));
        }
    }

    printf("%.16f\n", dp[m][n]);

    return 0;
}


Measured memory_bytes: 5312
#include <iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>

using namespace std;

int main()
{
	int X,K;
	cin >> K >> X;
	cout << X - K + 1;
	for (int i = X - K + 2; i <= X + K - 1; i++)
	{
		cout << " " << i ;
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 256
"""
A - Pair
1 以上 K 以下の正の整数から、偶数と奇数ひとつずつの組を選ぶ方法の個数を求めてください。なお、選ぶ順番は考慮しません。

K=６のとき、
選ぶ組の距離は、１，３，５となる
これを列挙すればよいはず
"""

K = int(input())

cnt = 0
for start in range(1, K):
    for dist in range(1, K, 2):
        if (start + dist) <= K:
            cnt += 1
        else:
            break

print(cnt)

Measured memory_bytes: 2940
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <cassert>
#include <numeric>
#include <functional>
#include <cassert>
//#include <numeric>
#pragma warning(disable:4996) 
 
typedef long long ll;
typedef unsigned long long ull;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF  9223300000000000000
#define LINF2 1223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;

using namespace std;

int n, m, Q;
vector<int> a, b, c, d;
ll ans;

void dfs(vector<int> v)
{
    int siz = (int)v.size();
    if (siz== n) {
        ll sum = 0;
        int i;
        for (i = 0; i < Q; i++) {
            if (a[i] < siz && b[i] < siz && v[b[i]] - v[a[i]] == c[i]) {
                sum += d[i];
            }
        }
        ans = MAX(ans, sum);
        return;
    }
    
    int lim0 = (v.empty() ? 1 : v.back());
    int i;
    for (i = lim0; i <= m; i++) {
        v.push_back(i);
        dfs(v);
        v.pop_back();
    }

    return;
}

void solve()
{
    scanf("%d%d%d", &n, &m, &Q);
    a.resize(Q);
    b.resize(Q);
    c.resize(Q);
    d.resize(Q);
    int i;
    for (i = 0; i < Q; i++) {
        scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]); a[i]--; b[i]--;
    }

    ans = -LINF;
    vector<int> v;
    dfs(v);

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

    return;
}

int main(int argc, char* argv[])
{
#if 1
    solve();
#else
    int T;
    scanf("%d", &T);
    int t;
    for(t=0; t<T; t++) {
        //printf("Case #%d: ", t+1);
        solve();
    }
#endif
    return 0;
}



Measured memory_bytes: 3232
n = int(input())
r = [[0 for _ in range(19)] for _ in range(19)]
ans = 0
for _ in range(n):
  x = int(float(input()) * 10**9+0.1)
  y2 = -9
  y5 = -9
  while x % 2 == 0:
    x //= 2
    y2 += 1
  while x % 5 == 0:
    x //= 5
    y5 += 1
  y2 = min(18,y2+9)
  y5 = min(18,y5+9)
  r[y2][y5] += 1
  #print(y2,y5)
  if y2 >= 9 and y5 >= 9:
    #print('%')
    ans -= 1
for i2 in range(19):
  for i5 in range(19):
    for j2 in range(19):
      for j5 in range(19):
        if i2 + j2 >= 18 and i5 + j5 >= 18:
          ans += r[i2][i5] * r[j2][j5]
          #if r[i2][i5] * r[j2][j5]:
            #print(i2,i5,j2,j5,r[i2][i5] * r[j2][j5])
#for x in r:
  #print(x,sum(x))
print(ans//2)

Measured memory_bytes: 72360
import java.math.BigInteger;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        List<BigInteger> A = new LinkedList<>();
        for (int i = 0; i < N; i++) A.add(BigInteger.valueOf(sc.nextInt()));
        sc.close();

        BigInteger lcm = A.stream().parallel()
                .reduce(BigInteger.ONE, (a, b) -> a.divide(a.gcd(b)).multiply(b));

        BigInteger ans = A.stream().parallel()
                .map(lcm::divide)
                .reduce(BigInteger::add)
                .get();

        BigInteger mod = BigInteger.valueOf(1000000007);
        System.out.println(ans.mod(mod));
    }
}


Measured memory_bytes: 195552
// A.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

#include <iostream>
#include<vector>
#include<string>
using namespace std;

int main()
{
    long long n, m, k,x;
    vector<long long>a, b;

    cin >> n >> m >> k;

    for (int i = 0; i < n; i++) {
        cin >> x;
        a.emplace_back(x);
    }
    for (int i = 0; i < m; i++) {
        cin >> x;
        b.emplace_back(x);
    }
 //   a[n] = 10000000000;
   // b[m] = 10000000000;
   /* long long sum = 0;
    int akey = 0;
    int bkey = 0;
    int ans = 0;*/

    vector<long long >asum(n+1), bsum(m+1);
    vector<double >cospa(n + 1), cospab(m + 1);
    asum[0] = 0;
    bsum[0] = 0;
    cospa[0] = 10000000000;
    cospab[0] = 10000000000;
    double mincospa = 1000000;
    long long ans = 0;
    bool ac = true;
    int amax, bmax;

    for (int i = 1; i <= n; i++) {
        asum[i] = asum[i - 1] + a[i - 1];
    }
    for (int i = 1; i <= m; i++) {
        bsum[i] = bsum[i - 1] + b[i - 1];
    }

    int mmax = m;
  
    for (int i = 0; i <= n; i++) {
        if (asum[i] > k)break;
        for (int j = mmax; j >= 0; j--) {
            if (asum[i] + bsum[j] <= k) {
                mmax = j;
                if (i + j > ans)ans = i + j;
                break;
            }

        }
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 12680
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    ll x,k,d;
    cin>>x>>k>>d;
    x = abs(x);
    ll steps = x/d;
    if(k<steps)
    {
        cout<<min(abs(x-k*d),abs(x+k*d));
        return 0;
    }
    ll left = k - steps;
    ll ans = x-d*steps;
    if(left%2)
    {
        cout<<min(abs(ans-d),abs(ans+d));
    }
    else
    {
        cout<<ans;
    }
}


Measured memory_bytes: 3628
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define D()
#define INF 1000000000000
#define MOD 10000007
#define MAXR 100000
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define INITA(a,i,j,v) for(ll k=i;k<=j;k++){a[k]=v;}

int main() {
    int n;
    cin >> n;
    ll a[100001]; INITA(a, 0, 100000, 0);
    ll b[100001]; INITA(b, 0, 100000, 0);
    REP(i, n+1) {
        cin >> a[i];
    }
    REP(i, n) {
        cin >> b[i];
    }

    ll res = 0;
    ll prev_rem = 0;
    REP(i, n+1) {
        ll by_prev = min(a[i], prev_rem);
        ll by_current;
        if (i == n) {
            by_current = 0;
        } else {
            by_current = min(a[i] - by_prev, b[i]);
        }
        res += by_prev + by_current;
        if (i != n) {
            prev_rem = b[i] - by_current;
        }
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
 
using namespace std;
 
#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
 
 
vector<lli> d[100100];
vector<lli> f[100100];
 
signed main(){
 
	lli n,m;
	cin>>n>>m;

	lli in[100100];
	for(lli i=0;i<100100;i++)in[i]=0;
 
	REP(i,0,n-1+m){
		lli a,b;
		cin>>a>>b;
		a--;b--;
		d[a].push_back(b);
		in[b]++;
	}

	if(DEBUG){
		REP(i,0,n){
			cout<<"i="<<i<<" in[i]="<<in[i]<<endl;
		}
	}
 
	/*適当な点から逆側に幅優先探索で最後にたどり着く箇所が根になる*/
	/*さらに根から幅優先探索を行っていき、親を更新していくことで答えとなる*/
 
	queue<lli> q;
 
	lli last=-1;
	REP(i,0,n){
		if(in[i]==0){
			last = i;
			break;
		}
	}
	lli ans[100100]={-1};
	ans[last]=0;
	q.push(last);
 
	while(q.size()){
		lli top=q.front();
		q.pop();
		if(DEBUG)cout<<"top="<<top<<endl;
 
		for(lli i=0;i<d[top].size();i++){
			lli now = d[top].at(i);
			if(DEBUG)cout<<"now="<<now<<endl;
			in[now]--;
			if(in[now]==0){
				q.push(now);
				if(DEBUG)cout<<"pushNow="<<now<<endl;
				ans[now]=top+1;
			}
		}
	}
 
	REP(i,0,n){
		cout<<ans[i]<<endl;
	}
 
	return 0;
}

Measured memory_bytes: 10240
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    while(m--)
    {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    queue<pair<int, int>> q;
    vector<bool> vis(n + 1, false);
    q.push({1, -1});
    vector<int> par(n + 1, -1);
    int cnt = 0;
    vis[1] = true;
    while(!q.empty())
    {
        pair<int, int> tt = q.front();
        int u = tt.first;
        int v = tt.second;
        q.pop();
        par[u] = v;
        cnt++;
        for(auto it:adj[u])
        {
            if(!vis[it])
            {
                vis[it] = true;
                q.push({it, u});
            }
        }
    }
    if(cnt==n)
    {
        cout << "Yes\n";
        for (int i = 2; i <= n;++i)
            cout << par[i] << '\n';
    }
    else
        cout << "No";
    return 0;
}

Measured memory_bytes: 10496
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include <numeric>
#include<map>
#include<unordered_map>
#include <queue>
 
using namespace std;
using ll=long long;
#define rep(i,n)  for(ll i=0;i<n;++i)
#define all_map(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define ALL(a) (a).begin(),(a).end()

int main(){
    ll n;
    cin >> n;
    vector<ll> a(n), b(n);
    rep(i, n)cin >> a[i] >> b[i];
    reverse(ALL(a));
    reverse(ALL(b));
    ll ans = 0;
    rep(i, n){
        if((a[i]+ans)%b[i]==0)continue;
        ans+=b[i]-(a[i]+ans)%b[i];
    }
    cout << ans << endl;

}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define int long long
#define double long double
#define rep(i, a, n) for(int i = (int)(a);(i) < (int)(n);++(i))
#define repe(i, a, n) for(int i = (int)(a);(i) <= (int)(n);++(i))
#define repif(i, a, x) for(int i = (int)(a);(x);++(i))
#define repr(i, a, n) for(int i = ((int)(a)-1);(i) >= (int)(n);--(i))
#define reper(i, a, n) for(int i = (int)(a);(i) >= (int)(n);--(i))
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x), end(x)
#define CEIL(x) ((int)ceil(((double)x)))
#define POW(x, y) ((int)pow(x, y))
#define UNIQUE(x) (x).erase(unique(ALL((x))), end(x))
using namespace std;
using VI = vector<int>;
using VVI = vector<vector<int>>;
using PII = pair<int, int>;
using TIII = tuple<int, int, int>;
using VPII = vector<pair<int, int>>;
using VTIII = vector<tuple<int, int, int>>;
using Complex = complex<double>;
template<typename T> inline bool chmax(T& a, const T& b, bool t = false){ if(a<b or (t and a==b)){ a=b; return true; } return false; }
template<typename T> inline bool chmin(T& a, const T& b, bool t = false){ if(a>b or (t and a==b)){ a=b; return true; } return false; }
template<typename T> inline bool isin(const T& x, const T& l, const T& r){ return l <= x and x < r; }
inline ostream& fcout(int n = 10){ return cout << fixed << setprecision(n); }
inline ostream& rcout(int n = 2){ return cout << right << setw(n); }
constexpr int64_t INF = numeric_limits<int64_t>::max();
constexpr int32_t INF32 = numeric_limits<int32_t>::max();
constexpr int64_t MOD = 1000000007LL;
constexpr double PI = 3.14159265358979323846264338327950288;
constexpr double EPS = 1e-10;


struct UF {
    int num;
    vector<int> r, p, s;
    UF() = default;
    UF(int sz) : num(sz), r(sz, 1), p(sz, 0), s(sz, 1){ iota(begin(p), end(p), 0LL); }
    int find(int x){
        return (x == p[x] ? x : p[x] = find(p[x]));
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
    void unite(int x, int y){
        x = find(x), y = find(y);
        if(x == y) return;
        if(r[x] < r[y]) swap(x, y);
        r[x] += r[y];
        p[y] = x;
        s[x] += s[y];
        --num;
    }
    int count() const {
        return num;
    }
    int size(int x){
        return s[find(x)];
    }
};


int N, M;
PII AB[100010];
UF uf;
int ans[100010];


int32_t main(){
    cin >> N >> M;
    uf = UF(N);
    repr(i, M, 0) cin >> AB[i].first >> AB[i].second;

    ans[0] = N*(N-1)/2;
    rep(i, 0, M){
        auto [a, b] = AB[i];
        a--;
        b--;
        if(uf.same(a, b)) ans[i+1] = ans[i];
        else {
            ans[i+1] = ans[i]-uf.size(a)*uf.size(b);
            uf.unite(a, b);
        }
    }

    repr(i, M, 0) cout << ans[i] << endl;

    return 0;
}

Measured memory_bytes: 8008
#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
#define int long long
#define REP(i,n) for(int i = 0; i < (n); ++i)
#define FOR(i,a,b)  for(int i = (a); i <= (b); ++i)

using namespace std;
constexpr int MOD = 10e9+7;
constexpr int INF = 1LL << 60;
template <class T> inline bool chmin(T& a, T b){if(a > b){ a = b; return 1;} return 0;}  
template <class T> inline bool chmax(T& a, T b){if(a < b){ a = b; return 1;} return 0;}  

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

    int N ;    
    cin >> N;
    vector<int> primeNum(N+1,0);
    FOR(i,2,N){
        int isPrime = 1;
        FOR(j,2,i-1){
            if(i % j == 0) isPrime = 0;
        }

        if(isPrime) {
            int p = i;
            int tmp = N/p;
            while(tmp > 0){
                
                tmp = N/p;
                primeNum[i] += tmp;
                p *= i;
            }
        } else {
            primeNum[i] = -1; //素数でない
        }
    }
#define pNum(i)  count_if(primeNum.begin(),primeNum.end(),[](const auto& x){return x >= (i) ;})
    int ans = pNum(74) + pNum(24)*(pNum(2)-1/*同じものは使えない*/) + (pNum(4)-1) * pNum(14) + (pNum(2)-2)*pNum(4) * (pNum(4)-1)/2;//4,4の時、二つ選ぶ、つまりnC2をしなくちゃいけない
    cout << ans << endl;
    
}

Measured memory_bytes: 256
#include <iostream>

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

using namespace std;

int main()
{
  int n;
  string s, t;
  cin >> n >> s >> t;
  rep(i, n)
    cout << s[i] << t[i];
  cout << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void) {
	int n;
	int i,m,e,j;
	while(1){
		scanf("%d",&n);
		if(n==0){
			break;
		}
		for(i=0;i<n;i++){
			scanf("%d%d%d",&m,&e,&j);
			if(m==100||e==100||j==100){
				printf("A\n");
			}else if(m+e>=180){
				printf("A\n");
			}else if(m+e+j>=240){
				printf("A\n");
			}else if(m+e+j>=210){
				printf("B\n");
			}else if(m+e+j>=150&&(m>=80||e>=80)){
				printf("B\n");
			}else{
				printf("C\n");
			}
		}
	}
	return 0;
}

Measured memory_bytes: 2532
/* ****GT_18**** */

#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define	endl		'\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)	for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
using namespace std;

#define N  100005

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int TESTS=1;
//	cin>>TESTS;
	while(TESTS--)
	{
		int n;
		cin>>n;
		if(n==25)
			cout<<"Christmas ";
		else if(n==24)
			cout<<"Christmas Eve";
		else if(n==23)
			cout<<"Christmas Eve Eve";
		else
			cout<<"Christmas Eve Eve Eve";
		

	}
	return 0;
}

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

#include <vector>
#define rep(i, n) for (int(i) = 0; (i) < (n); (i)++)
using namespace std;

int main() {
  int S, W;
  cin >> S >> W;
  if (W >= S) {
    cout << "unsafe" << endl;
  } else {
    cout << "safe" << endl;
  }
}

Measured memory_bytes: 3636
import itertools


n_even, n_odd = map(int, input().split())

# nC2 なので、combinations使わなくてもいいと思う
count1 = n_even * (n_even - 1) // 2
count2 = n_odd * (n_odd - 1) // 2

print(count1 + count2)

# itertools.combinations を使ってもOK
count1 = len(list(itertools.combinations(range(n_even), r=2)))
count2 = len(list(itertools.combinations(range(n_odd), r=2)))



Measured memory_bytes: 3444
#include <iostream>
#include <algorithm>
using namespace std;
static const int MAX = 200000;

int main() {
  int R[MAX], n;
  cin >> n;
  for(int i = 0; i < n; i++) cin >> R[i];

  int maxv = -2000000000; // 十分小さい値を初期日設定
  int minv = R[0];

  for(int i = 1; i < n; i++) {
    maxv = max(maxv, R[i] - minv);
    minv = min(minv, R[i]);
  }

  cout << maxv << endl;

  return 0;
}


Measured memory_bytes: 3860
#include <bits/stdc++.h>
using namespace std;
int main(){
    int a;
    cin >> a;
    
    for (int i=1; i<10; i++) {
        for (int j=1; j<10; j++) {
            if (a == i*j) {
              cout << "Yes" << endl;
              return 0;
            }
        }
    }
    cout << "No" << endl;

}


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

int main() {

    int A, B, X;

    cin >> A >> B >> X;

    if (A == X) {
        cout << "YES" << endl;
    }

    else if (A < X && (A + B) >= X) {
        cout << "YES" << endl;
    }

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

Measured memory_bytes: 256
n = int(input())
x2, x4, x = 0, 0, 0

for num in input().split(' '):
    tmp = int(num)
    x2 += tmp % 2 == 0 and tmp % 4 != 0
    x4 += tmp % 4 == 0
    x += tmp % 2 != 0

print("Yes" if x + (x2 != 0) <= x4 + 1 else "No")

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

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

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

int main(){

	int N;
	string S;
	cin >> N >> S;
	vector<int> V;
	V.pb(0);
	int blackSum = 0;
	for(int i = 0; i < N; i ++){
		if(S[i] == '#'){
			V.pb(V[i] + 1);
			blackSum ++;
		}
		else V.pb(V[i]);
	}
	int ans = 1000000;
	for(int i = 0; i <= N; i ++){
		//cout << "V: " << V[i] << endl;
		ans = min(ans, V[i] + N - i - (blackSum - V[i]));
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1532
//   _/                _/                 _/_/_/   _/
//_/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
// _/     _/    _/   _/     _/    _/  _/_/_/     _/
//_/     _/    _/   _/     _/    _/  _/    _/   _/
// _/_/   _/_/       _/_/   _/_/      _/_/     _/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const double pi=3.14159265358979323846;
const int inf=2e9;
const ll INF=9e18;
typedef pair<int,int> P;
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  int n,m,c[25]={},dp[50005]={};
  cin >> n >> m;
  for(int i=0; i<=n; i++) {
    dp[i]=inf;
  }
  dp[0]=0;
  for(int i=0; i<m; i++) {
    cin >> c[i];
  }
  for(int i=1; i<=n; i++) {
    for(int j=0; j<m; j++) {
      if(i-c[j]>=0) {
        dp[i]=min(dp[i],dp[i-c[j]]+1);
      }
    }
  }
  cout << dp[n] << endl;
}


Measured memory_bytes: 3320
N, *S = map(int, open(0).read().split())

B = [s for s in S if s % 10]

if len(B) == 0:
    print(0)
elif len(B) % 2 == 0:
    print(sum(S) - min(B))
else:
    if sum(S) % 10:
        print(sum(S))
    else:
        print(sum(S) - min(S))

Measured memory_bytes: 61732
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
#include <cstring>
using namespace std;

using ll = long long;
using P = pair<int, int>;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

template<class T>
inline bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

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

    string s;
    cin >> s;
    int n = s.length();
    reverse(s.begin(), s.end());
    s += '0';
    vector<vector<int>> dp(2, vector<int>(2, INF));
    dp[0][0] = 0;
    for(int i = 0; i <= n; ++i){
        int num = s[i] - '0';
        dp[1][0] = min(dp[0][0], dp[0][1] + 1) + num;
        dp[1][1] = min(dp[0][0] + 10, dp[0][1] + 9) - num;
        swap(dp[0], dp[1]);
    }
    cout << dp[0][0] << endl;
}

Measured memory_bytes: 4288
N,Q = map(int,input().split())
S = input()
td = [input().split() for _ in range(Q)]
def solve(i):
    cur = i
    for t,d in td:
        if S[cur] == t:
            cur += 1 if d=='R' else -1
        if cur < 0 or cur >= N:
            return False
    return True
 
def binary_search(ok,ng):
    while abs(ok-ng) >1:
        mid = (ok+ng)//2
        if solve(mid):
            ok = mid
        else:
            ng = mid
    return ok

print(max(0,binary_search(-1,N)-binary_search(N,-1)+1))

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

struct Node{
  int num;
  Node *right,*left,*parent;
};

Node *NIL,*root;

Node *treeMinimum(Node *T){
  while(T->left!=NIL)T=T->left;
  return T;
}

Node *find(Node *T,int k){
  while(T!=NIL&&k!=T->num){
    if(k<T->num)T=T->left;
    else T=T->right;
  }
  return T;
}

Node *treeSuccessor(Node *x){
  if(x->right!=NIL)return treeMinimum(x->right);
  Node *y=x->parent;
  while(y!=NIL&&x==y->right){
    x=y;
    y=y->parent;
  }
  return y;
}

void deletNode(Node *z){
  Node *y;
  Node *x;

  if(z->left==NIL||z->right==NIL) y=z;
  else y=treeSuccessor(z);

  if(y->left!=NIL) x=y->left;
  else x=y->right;

  if(x!=NIL) x->parent=y->parent;

  if(y->parent==NIL) root=x;
  else{
    if(y==y->parent->left){
      y->parent->left=x;
    }else y->parent->right=x;
  }

  if(y!=z) z->num=y->num;

  free(y);

}

void insert(int k){
  Node *y=NIL;
  Node *x=root;
  Node *T;
  
  T=(Node *)malloc(sizeof(Node));
  T->num=k;
  T->left=NIL;
  T->right=NIL;
  
  while(x!=NIL){
    y=x;
    if(T->num<x->num) x=x->left;
    else x=x->right;
    
  }
  
  T->parent=y;
    
  if(y==NIL) root=T;
  else{
    if(T->num<y->num) y->left=T;
    else y->right=T;
  }
}

void inorder(Node *T){
  if(T==NIL) return;
  inorder(T->left);
  cout<<" "<<T->num;
  inorder(T->right);
}

void preorder(Node *T){
  if(T==NIL) return;
  cout<<" "<<T->num;
  preorder(T->left);
  preorder(T->right);
}

int main(){
  int m,k;
  string S;

  cin>>m;
  for(int i=0;i<m;i++){
    cin>>S;
    if(S=="insert"){
      cin>>k;
      insert(k);
    }else if(S=="print"){
      inorder(root);
      cout<<endl;
      preorder(root);
      cout<<endl;
    }else if(S=="find"){
      cin>>k;
      Node *t=find(root,k);
      if(t!=NIL) cout<<"yes"<<endl;
      else cout<<"no"<<endl;
    }else if(S=="delete"){
      cin>>k;
      deletNode(find(root,k));
    }
  }
  return 0;
}

Measured memory_bytes: 19960
N = int(input())
L = list(map(int, input().split()))
l = sorted(L)

t = 0

for a in range(N):
    for b in range(a + 1, N):
        for c in range(b + 1, N):

            if l[a] < l[b] < l[c] and l[a] + l[b] > l[c]:
                t += 1

print(t)


Measured memory_bytes: 9084
#include<bits/stdc++.h>
#define ll long long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
static const ll MAX = 1000000000000000;
static const int NIL = -1;
using namespace std;
const long double EPS = 0.0000000001;
const long double PI = (acos(-1));
const ll MOD = 1e9 + 7;

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


int main() {

    ll n; cin >> n;
    ll sum = 0;
    ll ans = 0;
    vector<ll> a(n);

    rep(i,n) {
        cin >> a[i];
        sum += a[i];
    }

    rep(i,n-1){
        sum -= a[i];

        ans = (ans%MOD + ((a[i]%MOD)*(sum%MOD))%MOD)%MOD;
    }

    cout << ans;
}


Measured memory_bytes: 4776
#include <stdio.h>
     
    int main(void)
    {
     int X, A, B;
     
     scanf("%d", &X);
     scanf("%d", &A);
     scanf("%d", &B);
     
     int c = (B - A);
     if (c <= 0) puts("delicious");
     if (c > 0 && c <= X) puts("safe");
     if (c > 0 && c > X)  puts("dangerous"); 
     
     return 0;
     
    }

Measured memory_bytes: 128
import java.util.Scanner;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int p = sc.nextInt();
      
        int oddCount = 0;
        int evenCount = 0;
        for (int i = 0; i < n; i++) {
            if (sc.nextInt() % 2 == 0)
                evenCount++;
            else
                oddCount++;
        }

        long combSum = 0;
        for (long l = p % 2; l <= oddCount; l += 2)
            combSum += combination(oddCount, l);

        System.out.println(combSum * (long) Math.pow(2, evenCount));
    }

    static long combination(long n, long r) {
        if (n - r < r)
            return combination(n, n - r);

        long ans = 1;
        for (long k = n; k > n - r; k--)
            ans *= k;
        for (long k = r; k >= 2; k--)
            ans /= k;
        return ans;
    }
}


Measured memory_bytes: 21844
/* ****TCIITB**** */

#include<bits/stdc++.h>
#define io          ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 
#define ll          long long
#define pb          push_back
#define    endl        '\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)    for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define time        cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
using namespace std;

#define N  100005

int main()
{
    
    io
    
    ll n;
    cin>>n;
    ll s=0;
    rep(i,1,n+1)
    {
        rep(j,1,n+1)
        {
            rep(k,1,n+1)
            {
                ll z=i;
                z=__gcd(z,j);
                z=__gcd(z,k);
                s+=z;
            }
        }
    }
    cout<<s;
}

Measured memory_bytes: 3648
#include <iostream>
#include <limits>
#include <vector>
#include <stack>
#include <algorithm>
#include <array>
#include <queue>
#include <cmath>
#include <iomanip>
#include <set>
#include <map>
#include <cassert>

typedef uint_fast64_t u64;
typedef int_fast64_t i64;
typedef uint_least32_t u32;
typedef int_fast32_t i32;
typedef uint_least16_t u16;
typedef int_fast16_t i16;
typedef uint_least8_t u8;
typedef int_fast8_t i8;

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  u64 n,r,g,b, cnt=0;
  std::cin >> r>>g>>b>>n;
  u64 mx = std::max(r,std::max(g,b)), mn=std::min(r,std::min(g,b)), md=r+g+b-mx-mn;
  for (u64 i=0; i<n/mx+1;++i) {
    if (i*mx>n) break;
    u64 tmp = n - i*mx;
    for (u64 j=0; j<tmp/md+1;++j) {
      if (j*md>tmp) break;
      u64 tmp2 = tmp - j*md;
      if (tmp2%mn == 0) ++cnt;
    }
  }

  std::cout << cnt<<std::endl;
  return 0;
}

Measured memory_bytes: 256