akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
/*
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_map>
#include <map>
*/
#define INF 100000000
#define rep(i, a) for (int i = 0; i < (a); i++)
using namespace std;

int main() {
    string s, t;
    cin >> s >> t;

    //dp[n+1][m+1] := sのn文字目までとtのm文字目までとのレーベンシュタイン距離
    int dp[1010][1010];

    int i, j;
    for(i = 0; i <= s.size(); i++){
        dp[i][0] = i;
    }
    for(i = 0; i <= t.size(); i++){
        dp[0][i] = i;
    }

    int x;
    for(i = 1; i <= s.size(); i++){
        for(j = 1; j <= t.size(); j++){
            if(s[i-1] == t[j-1]){
                x = 0;
            }else{
                x = 1;
            }

            dp[i][j] = min(dp[i-1][j] + 1, min(dp[i][j-1] + 1, dp[i-1][j-1] + x));
        }
    }

    cout << dp[s.size()][t.size()] << endl;
}




Measured memory_bytes: 7120
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define all(a) a.begin(),a.end()
#define SORT(a) sort(all(a))
#define int long long
#define FOR(i, m, n) for(int i = m;i < n;i++)
typedef vector<int> VI;
typedef vector<VI> VVI;
const int MOD=1000000007;
const long long INF = 1LL << 60;
//----------------------------------------------
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,m;
    cin >> n >> m;
    int kowa[m];
    rep(i,m) cin >> kowa[i];
    int dp[n + 1];
    dp[0] = 1;
    int x = 0;
    if(kowa[x] == 1){
        dp[1] = 0;
        x++;
    }else{
        dp[1] = 1;
    }
    for(int i = 2; i <= n; i++){
        dp[i] = (dp[i-1] + dp[i-2]) % MOD;
        if(kowa[x] == i){
            dp[i] = 0;
            x++;
        }
    }
    cout << dp[n] << endl;
    return 0;
}

Measured memory_bytes: 1792
import itertools

N, M = map(int, input().split())
graph = [[0] * N for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    graph[a-1][b-1] = 1
    graph[b-1][a-1] = 1

p = list(itertools.permutations(range(N)))

Sum = 0

for i in range(len(p)):
    if p[i][0] != 0:
        break
    for j in range(N - 1):
        if graph[p[i][j]][p[i][j + 1]] != 1:
            break
        elif j == N - 2:
            Sum += 1

print(Sum)

Measured memory_bytes: 46704
#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    int n;
    cin>>n;
    vector<long> arr(n);
  	int count = 0;
  	for(int i=0;i<n;i++)
    {
      	cin>>arr[i];
    }
    for(int i=0;i<n;i++)
    {
      for(int j=i+1;j<n;j++)
      {
        for(int k=j+1;k<n;k++)
        {
            if(arr[i]==arr[j] || arr[j]==arr[k] || arr[i]==arr[k])
                continue;
             if((arr[i] + arr[j] > arr[k]) && (arr[i]+arr[k]>arr[j]) && (arr[j]+arr[k]>arr[i]))
            count++;
        }
      }
    }
  	cout<<count;
    return 0;
}

Measured memory_bytes: 3628
N = int(input())
a = list(map(int, input().split()))

c1 = 0
c2 = 0
c4 = 0

for ai in a:
  if ai%2 == 0:
    if ai%4 == 0:
      c4 += 1
    else:
      c2 += 1
  else:
    c1 += 1

if c2 == 0:
  if c4 >= c1-1:
    print('Yes')
  else:
    print('No')
else:
  if c4 >= c1:
    print('Yes')
  else:
    print('No')


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

int main(){
  int X,Y;
  cin >> X >> Y;
  rep(i,X){
    if(Y == (i + 1) * 2 + (X - i - 1) * 4){
      cout << "Yes" << endl;
      return 0;
    }
  }
  if(Y == X * 2){
    cout << "Yes" << endl;
    return 0;
  }
  if(Y == X * 4){
    cout << "Yes" << endl;
    return 0;
  }
  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3592
/*~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=
    WRITER:kakitamasziru/OxOmisosiru
~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=*/
#ifdef LOCAL_JUDGE
#define _GLIBCXX_DEBUG //FOR THE DEBUG! COMMENT OUT THIS WHEN SUBMITTING!
#endif
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <iomanip>
#include <limits>//setprecision
//#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <math.h>//pow,,,
#include <cmath>//abs,,,
//#include <unordered_map> // unordered_map
//#include <unordered_set> // unordered_set
#include <bitset> // bitset
//#include <cctype> // isupper, islower, isdigit, toupper, tolower
//It is so troublesome that I include bits/stdc++.h !
using namespace std;

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const long long INF = 1001001001001001;
const long long MOD = 1000000007;
typedef pair<long long,long long> P;
//NのM乗を求める(繰り返し二乗法)
long long mod_pow(long long N, long long M) {
    if (M == 0) return 1;
    long long res = mod_pow((N * N) % MOD, M / 2);
    //最下位ビット(*N)が1の時は単独でNをかける
    if (M & 1) res = (res * N) % MOD;

    return res %= MOD;
}
long long nCr(long long n, long long r) {
    long long A = 1, B = 1;
    //Aが分子Bが1/r!
    for (long long i = n - r + 1; i <= n; i++) {
        A = A * i % MOD;
    }
    for (long long i = 1; i <= r; i++) {
        B = B * i % MOD;
    }
    B = mod_pow(B, MOD - 2);
    B %= MOD;
    //Bは割るのではなく掛ける
    return (A * B) % MOD;
}

long long gcd(long long a, long long b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}
 
long long lcm(long long a, long long b) {
    return a * b / gcd(a, b);
}

long long A,B;

bool ok(long long key,long long index){
    string S = to_string(index);
    long long nagasa = S.size();
    if(index*A+nagasa*B > key) return true;
    else if(index*A+nagasa*B <= key) return false;
}

long long binary_search(long long key,long long size){
    //left,right,midはいずれもindex
    long long left = -1,right = size;
    while(right - left > 1){
        long long mid = left + (right-left)/2;
        long long hantei = ok(key,mid);
        if(hantei) right = mid;
        else left = mid;
    }
    if(left == -1)return 0;
    return left;
}

int main() {
    int A,B;cin >> A >> B;
    int K;cin >> K;
    set<int> S;
    
    for(int i = 0;i<K;i++){
        if(A+i <= B){
            S.insert(A+i);
        }
    }
    for(int i = 0;i<K;i++){
        if(B-i >= A){
            S.insert(B-i);
        }
    }

    for(auto a : S){
        cout << a << endl;
    }

    // PLEASE GIVE ME THE "ACCEPTED" !
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

template<typename T> T chmax(T& a, const T& b){return a = (a > b ? a : b);}
template<typename T> T chmin(T& a, const T& b){return a = (a < b ? a : b);}

#define DEBUG_MODE
#ifdef DEBUG_MODE
#define dump(x) cout << #x << " : " << x << " "
#define dumpL(x) cout << #x << " : " << x << '\n'
#define LINE cout << "line : " << __LINE__ << " "
#define LINEL cout << "line : " << __LINE__ << '\n'
#define dumpV(v) cout << #v << " : ["; for(auto& t : v) cout << t << ", "; cout<<"]" << " "
#define dumpVL(v) cout << #v << " : ["; for(auto& t : v) cout << t << ", "; cout<<"]" << endl
#define STOP assert(false)
#else
#define dump(x) 
#define dumpL(x) 
#define LINE 
#define LINEL 
#define dumpV(v) 
#define dumpVL(v) 
#define STOP assert(false)
#endif
#define mp make_pair
 
namespace std {
template<class S, class T>
ostream &operator <<(ostream& out, const pair<S, T>& a) {
    out << '(' << a.fi << ", " << a.se << ')';
    return out;
}
}

int main(){
    int n;
    cin >> n;
    vi a(n);
    rep(i, n) cin >> a[i];
    vi cnt(n+10);
    ll ans = 1LL;
    cnt[0] = 3;
    rep(i, n) {
        {
            int pre = a[i]-1;
            int cur = a[i];
            int nxt = a[i] +1;
            (ans *= cnt[cur]) %= MOD;
            cnt[cur]--;
            cnt[nxt]++;
        }
        
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
S = input()
l, r = 0, len(S)

memo = [0] * len(S)

for i in range(len(S) - 1):
  if S[i] == "R" and S[i + 1] == "L":
    n = (i - l) // 2
    memo[i] = n + 1
    memo[i + 1] = (i - l - n) + 1
    l = i + 2
  if S[i] == "L" and S[i + 1] == "R":
    n = (i + 1 - l) // 2
    memo[l - 1] += n
    memo[l - 2] += i + 1 - l - n
    l = i + 1
if l < r:
  n = (r - l) // 2
  memo[l - 1] += n
  memo[l - 2] += r - l - n

print(" ".join([str(x) for x in memo]))

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

int main(){
  ll h,n,cnt=0;
  cin >> h >> n;
  vector<ll> a(n);
  for(ll i=0;i<n;i++){
    cin >> a.at(i);
    cnt += a.at(i);
  }
  if(cnt >= h) cout <<  "Yes" << endl;
  else cout << "No" << endl;
  
  
  return 0;
}


Measured memory_bytes: 1024
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
    s=readline()
    t=readline()
    ans=0
    for i in 1:length(s)
        if s[i]!=t[i]
            ans+=1
        end
    end
    println(ans)
end
main()

Measured memory_bytes: 158656
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct shop_data{

  long long value;
  long long num;
  bool operator < (const shop_data&other){
  
    if(value<other.value){
    
      return 1;
    }
    else return 0;
  }
};
int main(){
  
  long long N;
  cin>>N;
  long long M;
  cin>>M;
  vector<shop_data>shop(N);
  for(int i=0;i<=N-1;i++){
  
    cin>>shop[i].value>>shop[i].num;
  }
  sort(shop.begin(),shop.end());
  long long cost=0;
  for(int i=0;i<=N-1;i++){
  
    if(shop[i].num>=M){
    
      cost+=M*shop[i].value;
      break;
    }
    else{
    
      cost+=shop[i].value*shop[i].num;
      M-=shop[i].num;
    }
  }
  cout<<cost;
  return 0;
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define each(it,v) for(auto it : v)
#define mod 1000000007
#define all(v) (v).begin(),(v).end()
#define vi vector<int>
#define vl vector<long>
#define P pair<int,int>
using namespace std;

main()
{
        string s,t={}; cin>>s;
        int n; cin>>n;
        for(int i=0;i<s.size();i+=n)
        {
                t.push_back(s[i]);
        }
        cout<<t<<endl;
}



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

int main() {

	int W, H, x, y, r;
	scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);

	if (r <= x && r <= y) {
		if (x <= W - r && y <= H - r)cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	else cout << "No" << endl;

	return 0;
}


Measured memory_bytes: 3188
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <ctime>
#include <fstream>
#include <complex>
using namespace std;

#define FOR(i,a,b) for(int i = (a); i <(b); i++)
#define RFOR(i,b,a) for(int i = (b) - 1; i >= (a); i--)
#define ITER(it,a) for(typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a, value) memset(a,value, sizeof(a))

#define ALL(a) a.begin(),a.end()
#define SZ(a) (int)a.size()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<LL> VI;
typedef pair<int, LL> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;
const int MOD = 1000 * 1000 * 1000 + 7;

const int MAX = 100 * 2 + 7;

int A[MAX];



int main()
{
    //cout << f(2, 1) << endl;
    //freopen("input.txt", "r", stdin);
    //ios::sync_with_stdio(false);cin.tie(NULL);
  
    int  n, m;
    scanf("%d%d", &n, &m);
    FOR(i, 0, m)
        scanf("%d", A + i);
    sort(A, A + m);
    reverse(A, A + m);
    
    if( m == 1)
    {
        cout << A[0] << endl;
        if (n == 1)
        {
            cout << 1 << endl << 1 << endl;
        }
        else
        {
            cout << 2 << endl << n-1 << " " << 1 << endl;
        }
        return 0;
    }
    VI X[2];
    FOR(i, 0, m)
        X[A[i] & 1].PB(A[i]);
    
    if (SZ(X[1]) > 2)
    {
        cout << "Impossible" << endl;
        return 0;
    }
    
    VI RES;
    if (SZ(X[1]))
        RES.PB(X[1][0]);
    
    FOR(i, 0, SZ(X[0]))
        RES.PB(X[0][i]);
    
    if (SZ(X[1]) > 1)
        RES.PB(X[1][1]);
    
    FOR(i, 0, SZ(RES))
    {
        cout << RES[i] << " ";
    }
    cout << endl;
    
    RES[0]--;
    RES[SZ(RES)-1]++;
    int idx = 0;
    if (RES[idx] == 0)idx++;
    cout << SZ(RES)-idx << endl;
    FOR(i, idx, SZ(RES))
    cout << RES[i] << " ";
    cout << endl;
    
    
    
    return 0;
}


Measured memory_bytes: 256
// E - Divisible Substring
#include <bits/stdc++.h>
using namespace std;
#define c2d(c) ((c)-'0') // char to digit
#define modadd(x,y,m) x=(x+(y))%(m)
#define modmul(x,y,m) x=(x*(y))%(m)

int main(){
	int N,P; string S; cin>>N>>P>>S;
	long long total = 0;
	if(10%P == 0){ // P={2,5}
		for(int i=0; i<N; ++i) if(c2d(S[i]) % P == 0) total += i+1;
	}
	else{
		vector<int> cnt(P, 0);
		int r = 0, ten = 1;
		for(int i=N-1; i>=0; --i){
			cnt[r]++;
			modadd(r, c2d(S[i])*ten, P);
			total += cnt[r];
			modmul(ten, 10, P);
		}
	}
	cout << total << endl;
}

Measured memory_bytes: 640
//RN
#include<iostream>
using namespace std;

int main()
{
	int x, a[100];
	cin >> x;
	
	for(int i = 0; i < x; i++)
		cin >> a[i];
	
	for(int i = x-1; i > 0; i--)
		cout << a[i] << " ";
		
	cout << a[0] << endl;
	return 0;
}


Measured memory_bytes: 3068
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
 
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
 
using namespace std;
 
 
int inputValue(){
    int a;
    cin >> a;
    return a;
};
 
void inputArray(int * p, int a){
    rep(i, a){
        cin >> p[i];
    }
};
 
void inputVector(vector<int> * p, int a){
    rep(i, a){
        int input;
        cin >> input;
        p -> push_back(input);
    }
}
 
template <typename T>
void output(T a, int precision) {
    if(precision > 0){
        cout << setprecision(precision)  << a << "\n";
    }
    else{
        cout << a << "\n";
    }
}
 
int main(int argc, const char * argv[]) {
    int a[3];
    scanf("%d %d %d",&a[0],&a[1],&a[2]);
	int max=0;
    int i;
  	rep(i,3){
    	if(max < a[i]){
        	max = a[i];
        }	
    }
  
  	printf("%d\n",a[0]+a[1]+a[2] - max);
    
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

int main()
{
	char S[200003] = {};
	scanf("%s", &S);
	
	int i, count = 0;
	for (i = 1; S[i] != 0; i++) {
		if (S[i] == S[i-1]) {
			count++;
			if (S[i+2] != 0) i += 2;
			else if (S[i+1] != 0) i++;
		}
	}
	
	printf("%d\n", i - count);
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 384
from collections import deque
N = int(input())
G = {}
for _ in range(N-1):
    u,v,w = map(int,input().split())
    if u not in G:
        G[u] = []
    G[u].append((v,w%2))
    if v not in G:
        G[v] = []
    G[v].append((u,w%2))
que = deque([(1,0)])
hist = [0 for _ in range(N+1)]
hist[1] = 1
col = [0 for _ in range(N+1)]
while que:
    u,c = que.popleft()
    for x in G[u]:
        v,w = x[0],x[1]
        if hist[v]==0:
            if w==0:
                col[v] = c
                que.append((v,c))
            else:
                col[v] = 1-c
                que.append((v,1-c))
            hist[v] = 1
for i in range(1,N+1):
    print(col[i])

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

int main()
{
    ll n;
    cin>>n;
    ll a[n], ans=0;
    unordered_map<ll ,ll> m;
    for(int i=0;i<n;++i)
    {
        cin>>a[i];
        m[a[i]]++;
    }
    for(auto it:m)
    {
        ans+=((it.second * (it.second-1))/2);
    }
    for(int i=0;i<n;++i)
    {
        cout<<ans+1-m[a[i]]<<endl;
    }
    return 0;
}

Measured memory_bytes: 9160
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin>>n;
    if (n<1000) cout<<"ABC\n";
    else cout<<"ABD\n";
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>


using namespace std;
typedef long long ll;

char S[310][310];

int main(){
 int N; scanf("%d", &N);
  int cnt = 0;
  
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){  
      scanf(" %c", &S[i][j]);
    }
  }

  
  bool flag;
  for(int A = 0; A < N; A++){ 
    flag = true;
    char T[310][310];
    
    for(int i = 0; i < N; i++){
      for(int j = 0; j < N; j++){ 
        T[(i+A)%N][j] = S[i][j];}
    }
    
    
    for(int i = 0; i < N; i++){
      for(int j = 0; j < N; j++){
        if( T[i][j] != T[j][i]){ flag = false; break;
                               }
      }
    }
    
    if( flag){ cnt++;}
  }
  
  printf("%d\n", N*cnt); return 0;
}
    
  
  

Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int main(){
	
	string str;
	
	cin >> str;
	
	for(int i = 0; i < str.size(); i++){
		str[i] -= 3;
		if(str[i] < 'A'){
			str[i] += 26;
		}
	}
	
	cout << str << endl;
	
	return 0;
}

Measured memory_bytes: 1180
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define MOD (1000000007)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()

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

int gcd(int a, int b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

const ll INF = 1LL << 60;

int main(){
  int n; cin >> n;
  vector<ll> a(n), b(n); rep(i, n) cin >> a[i] >> b[i];

  vector<pair<ll, int>> c(n);
  rep(i, n){
    c[i] = mp(b[i]+a[i], i);
  }

  sort(all(c));
  reverse(all(c));

  ll ans = 0;
  rep(i, n){
    int index = c[i].second;
    if(i%2 == 0) ans += a[index];
    else ans -= b[index];
  }
  std::cout << ans << '\n';
}


Measured memory_bytes: 3328
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list()
i = 0
while i + 1 < len(b):
    c.append(b[i + 1] - b[i])
    i += 1
c.append(a[0] - b[len(b) - 1] + b[0])
print(sum(c) - max(c))


Measured memory_bytes: 86140
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int maxn=400+5;
const int mod=1e9+7;
ll dp[maxn][maxn];
ll kpws[maxn][maxn];
ll a[maxn];
ll b[maxn];
int main() {
	for(int i=1;i<=400;i++) {
		kpws[i][0]=1;
		for(int j=1;j<=400;j++) kpws[i][j]=kpws[i][j-1]*i%mod;
	}
	for(int j=0;j<=400;j++)
		for(int i=1;i<=400;i++) 
			(kpws[i][j]+=kpws[i-1][j])%=mod;

    int n,c;cin>>n>>c;


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

    for(int i=0;i<=400;i++){
    	dp[1][i]=(kpws[b[1]][i]-kpws[a[1]-1][i])%mod;
    	(dp[1][i]+=mod)%=mod;
    }

    // for(int i=0;i<=c;i++) cout<<dp[1][i]<<' ';cout<<endl;

    for(int i=2;i<=n;i++) {
    	for(int j=0;j<=400;j++) {
    		for(int k=0;j+k<=400;k++) {
    			(dp[i][j+k]+=(kpws[b[i]][k]-kpws[a[i]-1][k])*dp[i-1][j]%mod)%=mod;
    			(dp[i][j+k]+=mod)%=mod;
    		}
    	}
    }
    cout<<dp[n][c]<<endl;
    return 0;
}

Measured memory_bytes: 6152
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){

  int N;

  cin >> N;

  vector<int> A(2 * 100001,0);
  vector<int> has(1000001,0);
  
  for(int i = 0; i < N; i++){
    cin >> A[i];
  }

  sort(A.begin(), A.begin() + N);

  /*for(int i = 0; i < N; i++){
    cout << A[i] << endl;
    }*/

  int ans = 0;
  for(int i = 0; i < N;i++){
    if( i < N-1 && A[i] != A[i+1] ){
      if( has[A[i]] == 0) ans++;
    }
    else if( i == N-1 ){
      if( has[A[i]] == 0) ans++;
    }
    
    for(int t = A[i]; t <= A[N-1]; t += A[i]){
      has[t] = 1;
    }
  }

  cout << ans << endl;
  
  
  return 0;
  

  
}


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

int main(){
    int n,l;
    cin >> n >> l;
  	int sum = 0;
    int s = 200;
    int r;
    vector<int> v(n);
    rep(i,n){
        v[i] = l;
        l++;
        sum += v[i];
        s = min(s, abs(v[i]));
        if(s == abs(v[i])) r = v[i];
    }
    cout << sum - r << endl;
}

Measured memory_bytes: 256
N=int(input())
a=list(map(int, input().split()))

a.sort()
a.reverse()

count=1
ans=[]

for i in range(N-1):
    if a[i]==a[i+1]:
        count+=1
    else:
        if count//2>0:
            tmp=[a[i], count//2]
            ans.append(tmp)
        count=1
else:
    if count//2>0:
        tmp=[a[i], count//2]
        ans.append(tmp)
        
ans.sort()
ans.reverse()

if len(ans)>0:
    if ans[0][1]>1:
        print(ans[0][0]*ans[0][0])
    else:
        print(ans[0][0]*ans[1][0])
else:
    print(0)

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

// template {{{  0 
// using {{{ 1
using ll = long long int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// definition {{{ 1
// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// }}} 0


ll dp[402][402] = {};
// dp[l][r] [l,r]の最小値
vl a;
vl s;

ll ans( int l, int r ){
    // printf ("![%d,%d]\n", l, r);
    if( dp[l][r] ) return dp[l][r];
    if( r-l == 0 ) return dp[l][l] = a[l];
    ll minv = 1e15;
    Repe(i,r,l){
        minv = min( minv, ans(l,i)+ans(i+1,r) );
    }
    return dp[l][r] = minv + (s[r+1]-s[l]);
}

int main() {

    int N;
    Scd(N);

    a.resize(N);
    s.assign(N+1,0);

    Rep(i,N){
        Scll(a[i]);
        s[i+1] += a[i] + s[i];
    }

    printf ("%lld\n", ans(0,N-1) - s[N] );

    return 0;
}



Measured memory_bytes: 1536
#include <bits/stdc++.h>  // clang-format off
using Int = long long;
#define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++)
#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io;
#ifndef dump
#define dump(...)
#endif  // clang-format on

/**
 *    author:  knshnb
 *    created: Sun Apr 26 21:18:52 JST 2020
 **/

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

using namespace std;
class UndirectedGraph {
    struct Edge {
        Int to, cost;
    };

public:
    vector<vector<Edge>> G;
    Int V;
    UndirectedGraph(Int V) : G(V), V(V) {}
    void add_edge(Int u, Int v, Int cost) {
        G[u].push_back({v, cost});
    }
    vector<Int> dijkstra(Int s) {
        vector<Int> d(V, 1e18);
        d[s] = 0;
        priority_queue<pair<Int, Int>, vector<pair<Int, Int>>, greater<pair<Int, Int>>> que;  // {dist, v}
        que.push({0, s});
        while (!que.empty()) {
            pair<Int, Int> p = que.top();
            dump(p);
            que.pop();
            Int v = p.second;
            if (d[v] < p.first) continue;  // 定数倍枝刈り
            for (Edge e : G[v]) {
                Int tmp = d[v] + e.cost;
                if (d[e.to] <= tmp) continue;
                d[e.to] = tmp;
                que.push({tmp, e.to});
            }
        }
        return d;
    }
};

signed main() {
    Int n, m, S;
    std::cin >> n >> m >> S;
    const Int K = 5001;
    auto enc = [&](Int v, Int j) {
        assert(j < K);
        return K * v + j;
    };
    UndirectedGraph g(n * K);
    REP(_, m) {
        Int u, v, a, b;
        std::cin >> u >> v >> a >> b;
        u--, v--;
        REP(j, a, K) {
            g.add_edge(enc(u, j), enc(v, j - a), b);
            g.add_edge(enc(v, j), enc(u, j - a), b);
        }
    }
    REP(i, n) {
        Int c, d;
        std::cin >> c >> d;
        REP(j, K) {
            if (j + c >= K) break;
            g.add_edge(enc(i, j), enc(i, j + c), d);
        }
    }
    auto d = g.dijkstra(enc(0, std::min(S, K - 1)));
    dump(d);
    REP(i, 1, n) {
        Int mi = 1e18;
        REP(j, K) chmin(mi, d[enc(i, j)]);
        std::cout << mi << "\n";
    }
}


Measured memory_bytes: 44304
#include <bits/stdc++.h>
// 111
int main() {
  char x[3];
  std::cin >> x[0] >> x[1] >> x[2];
  x[0] -= '0';
  x[1] -= '0';
  x[2] -= '0';
  int sum = x[0]*100 + x[1]*10 + x[2];
  if (x[0]*111 < sum){
    std::cout << (x[0]+1)*111;
  }
  else {std::cout << x[0]*111;}
}

Measured memory_bytes: 256
N = gets.to_i
l = [1]

tmp_six = 6
while 100000 > tmp_six
    l << tmp_six
  tmp_six *= 6
end

tmp_nine = 9
while 100000 > tmp_nine
  l << tmp_nine
  tmp_nine *= 9
end

dp = [N] * (N + 1)
dp[0] = 0

(N + 1).times do |i|
  l.each do |val|
    if i >= val
      dp[i] = [dp[i], dp[i-val] + 1].min
    end
  end
end

p dp[N]

Measured memory_bytes: 2556
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#define INF (int)1e9
#define pb push_back
using namespace std;

long long int ncm(long long int n,long long int m){
  if(m>0) return (ncm(n,m-1)*(n-m+1))/m;
  else return 1;
}

int main(void){
  long long int n;
  vector<long double> v;
  long long int a,b,i;
  long double x,ave,lastv;
  long long int numlv,allv,res;
  long long int nave;
  cin>>n>>a>>b;
  for(i=0;i<n;i++){
    cin>>x;
    v.pb(x);
  }
  sort(v.begin(),v.end(),greater<long double>());
  res=0;
  nave=0;
  ave=0;
  lastv=-1;
  numlv=0;

  for(i=0;i<a;i++){
    if(lastv==v[i]) numlv++;
    else numlv=1;
    nave++;
    ave+=v[i];
    lastv=v[i];
  }
  
  allv=0;
  i=a-1;
  while(i>=0&&v[i]==lastv){
    allv++;
    i--;
  }
  i=a;
  while(i<n&&v[i]==lastv){
    allv++;
    i++;
  }

  res+=ncm(allv,numlv);
  for(i=nave;i<b;i++){
    if((ave/nave)>((ave+v[i])/(nave+1))) break;
    else{
      numlv++;
      ave+=v[i];
      nave++;
      res+=ncm(allv,numlv);
    }
  }
  printf("%.6Lf\n",ave/nave);
  printf("%lld\n",res);
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>

using namespace std;
// template for creating 2d vector
template<typename T>
vector<vector<T>> make_2d_vector(size_t rows, size_t cols, T init)
{ return vector< vector<T> >(rows, vector<T>(cols, init)); }



#define debug(x) cout << #x << "==" << x << endl;

const int inf = 100000000;

typedef long long ll;

int main() {
  ios::sync_with_stdio(false);

  // vector<int> hoge(1e7);        // 39296 KB
  // vector<bool> hoge(1e7);        // 1536 KB KB
  vector<int> hoge(5*1e7);        // 39296 KB

  char a, b;
  cin >> a >> b;
  if(a==b) {
    cout << "H" << endl;
  } else {
    cout << "D" << endl;
  }


  return 0;
}



Measured memory_bytes: 195584
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <string>
#include <utility>
#include <queue>
#include <unordered_set>
#include <set>
#include <unordered_map>
#include <cmath>
#include <iomanip>
#include <cassert>
using namespace std;
#define sL(i) i << 1
#define sR(i) i << 1 | 1
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<pair<int,int>, int> ppi;
const int MOD = 1e9 + 7;
const int INF = 2e9 + 5;

set<int> seen;
vector<int> check;
int n, a[100010], b[100010];

ll cnt(int x){
    unordered_map<int, int> d;
    for (int i = 0; i < n; i++) {
        b[i] = a[i] >= x ? 1 : -1;
        if (i > 0) b[i] += b[i - 1];
    }
    ll res = 0;
    int cur = 1;
    d[0] = 1;
    for (int i = 0; i < n; i++) {
        int prev = i > 0 ? b[i - 1] : 0;
        if (b[i] > prev) cur += d[b[i]];
        else cur -= d[prev];
        res += cur;
        ++d[b[i]];
        ++cur;
    }
    return res;
}

int main(){
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (!seen.count(a[i])) {
            seen.insert(a[i]);
            check.pb(a[i]);
        }
    }
    sort(check.begin(), check.end());
    int lo = 0;
    int hi = check.size() - 1;
    int x = check.size() - 1;
    ll M = (ll) n * (n + 1) / 4;
    while (lo <= hi) {
        int m = (lo + hi) / 2;
        if (cnt(check[m]) < M) {
            x = m - 1;
            hi = m - 1;
        } else {
            lo = m + 1;
        }
    }
    cout << check[x];
}

Measured memory_bytes: 9524
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <numeric>
#include <complex>
#include <iomanip>
#include <cassert>
#include <random>


int main() {
    int n, l; std::cin >> n >> l;
    std::vector<std::string> s(n);
    for (int i = 0; i < n; i++) std::cin >> s[i];
    std::sort(s.begin(), s.end());
    for (int i = 0; i < n; i++) std::cout << s[i];
    std::cout << std::endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define db(x) cout << #x << " = " << (x) << "\n";
using ll = long long;
using ld = long double;

static const auto do_fast_io = [] {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return nullptr;
}();

int main() {
    int n;
    cin >> n;
    vector<double> p(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
    }
    vector<long double> dp(n + 1);
    dp[0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = n; j >= 0; --j) {
            dp[j] = dp[j] * (1 - p[i]);
            if (j - 1 >= 0) {
                dp[j] += dp[j - 1] * p[i];
            }
        }
    }
    long double ans = 0;
    for (int i = n / 2 + 1; i <= n; ++i) {
        ans += dp[i];
    }
    cout << fixed << setprecision(10) << ans;
    return 0;
}

Measured memory_bytes: 384
#include <stdio.h>

int main(){
    int n, k;
    int h[10000000];
    int ans = 0;
    int i;

    scanf("%d %d", &n, &k);
    for(i = 0; i < n; i++){
        scanf("%d", &h[i]);
    }

    for(i = 0; i < n; i++){
        if(h[i] >= k){
            ans++;
        }
    }

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

    return 0;
}

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

namespace ConsoleApp88 {
    class Program {
        static void Main(string[] args) {
            long N = long.Parse(Console.ReadLine());
            long A = long.Parse(Console.ReadLine());
            long B = long.Parse(Console.ReadLine());
            long C = long.Parse(Console.ReadLine());
            long D = long.Parse(Console.ReadLine());
            long E = long.Parse(Console.ReadLine());

            var gate = new long[5] { A, B, C, D, E };

            long min = gate.Min();
            long minIndex = Array.IndexOf(gate, min);

            long ans = 0;

            //最小のゲートに到達してからゴールするまでの時間
            //minGateよりあとの時間
            ans += 5 - minIndex - 1;
            //minGateを通過するのにかかる時間
            ans += (long)Math.Ceiling((double)N / min);
            //minGateに到達するまでの時間
            ans += minIndex;

            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 13396
#[allow(unused_imports)]
use itertools::Itertools;
#[allow(unused_imports)]
use num::*;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use std::collections::*;

fn solve() {
    input! {
        n: usize,
        av: [usize; n]
    };

    let is_ok = av.into_iter().all(|a| {
        if a % 2 == 1 {
            return true;
        }
        a % 3 == 0 || a % 5 == 0
    });
    let res = if is_ok { "APPROVED" } else { "DENIED" };
    println!("{}", res);
}

fn main() {
    std::thread::Builder::new()
        .name("big stack size".into())
        .stack_size(256 * 1024 * 1024)
        .spawn(|| {
            solve();
        })
        .unwrap()
        .join()
        .unwrap();
}


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

int main(){
    int A, B, C;
    cin >> A >> B >> C;

    if (A == B && A != C){
        cout << "Yes" << endl;
    }else if(A == C && A != B){
        cout << "Yes" << endl;
    }else if(B == C && A != B){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define N 200010
multiset<int> p,q;
multiset<int>::iterator it1,it2;
int main()
{
    int i,j,k,t,x,y,d;
    LL ans,s,s1,s2;
    scanf("%d",&t);
    s=0;
    s1=0;
    s2=0;
    d=0;
    while(t--)
    {
        scanf("%d",&k);
        if(k==1)
        {
            scanf("%d%d",&x,&y);
            d++;
            if(d%2)
            {
                if(d==1)
                {
                    q.insert(x);
                    s2=s2+x;
                }
                else
                {
                    it1=p.end();
                    it1--;
                    j=*it1;
                    if(x<j)
                    {
                        q.insert(j);
                        s2=s2+j;
                        p.erase(it1);
                        s1=s1-j;
                        p.insert(x);
                        s1=s1+x;
                    }
                    else
                    {
                        q.insert(x);
                        s2=s2+x;
                    }
                }
            }
            else
            {
                it2=q.begin();
                j=*it2;
                if(x>j)
                {
                    p.insert(j);
                    s1=s1+j;
                    q.erase(it2);
                    s2=s2-j;
                    q.insert(x);
                    s2=s2+x;
                }
                else
                {
                    p.insert(x);
                    s1=s1+x;
                }
            }
            s=s+y;
        }
        else
        if(k==2)
        {
            ans=s2-s1+s;
            if(d%2)
            {
                it2=q.begin();
                j=*it2;
                ans=ans-j;
                printf("%d %lld\n",j,ans);
            }
            else
            {
                it1=p.end();
                it1--;
                j=*it1;
                printf("%d %lld\n",j,ans);
            }
        }
    }
    return 0;
}

Measured memory_bytes: 9600
#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>

using namespace std;
int main(){
  string S,T;
  int ans = 0;
  cin >> S >> T;
  for (int i=0;i<S.length();i++){
    if (S[i]!=T[i]){
      ans++;
    }
  }
  cout << ans << endl; 

}


Measured memory_bytes: 3896
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#pragma GCC optimize("Ofast")
//*********************************************DO IT NOW****************************************************************
#include<bits/stdc++.h> 
#include<random>
#define int long long   
#define pp pair<int,int> 
#define ss second 
#define ff first 
#define pb push_back
#define mod 1000000007
#define pi 3.14159265359
#define mk(arr,n,type)  type *arr=new type[n];
#define sl s1.length();
#define yes cout<< "YES"<<endl
#define no  cout<< "NO"<<endl
#define all(v) (v).begin(),(v).end()
#define s(v)   sort(v,v+n)
#define  mt mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define read(a,n) for(int i=0;i<n;i++)cin>>a[i]
#define print(a,n) for(int i=0;i<n;i++)cout<<a[i]<<" "
using namespace std;
//**********************************************DO IT NOW***************************************************************
void fastio()
{  
  #ifndef ONLINE_JUDGE
  freopen("INPUT.txt","r",stdin);
  freopen("OUTPUT.txt","w",stdout); 
  #endif
  ios_base :: sync_with_stdio(false); 
  cin.tie(NULL) ; 
  cout.tie(NULL);
}
int dp[101][1001],ans1=1e9,dp1[1000001];
int num[10];
int a[1000000];
int prime(int n)
{
 for(int i=2;i*i<=n;i++)
      {
          if(n%i==0)
          return 0;
      }
      return 1;
}
signed main()
{   
    fastio();
    int t=1;
   // cin>>t;
    while(t--)
    {  
        int n;
        cin>>n;
        int a[n];
        read(a,n);
        int c=0;
        for(int i=0;i<n;i++)
        {
            if(a[i]%2==0)
            {
                if(a[i]%3==0 ||a[i]%5==0)
                {
                    c++;
                }
                else
                {
                    cout<<"DENIED";
                    return 0;
                }
            }
        }
        cout<<"APPROVED";
    }
    
}
// 🍪 🍪 🍪


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

int main(){
    long long N, A, B;
    cin >> N >> A >> B;

    long long ans = 0;

    if((A - B) % 2 == 0 ){
        ans = abs(A - B) / 2;
    }else{

        long long tmp1 = abs((2*N - A + 1) - B)/2;
        long long tmp2 = abs(-A + 1 - B)/2;

        ans = min({tmp1, tmp2});
    }

    cout << ans << endl;
    return 0;

}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define FOR(i, m, n) for (ll i = m; i < (n); i++)
#define RFOR(i, m, n) for (ll i = (m - 1); i >= 0; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define print(ele) cout << (ele) << "\n"
#define print10(ele) cout << fixed << setprecision(10) << (ele) << "\n"

using namespace std;
typedef long long ll;
typedef vector<int> ivec;
typedef vector<string> svec;
typedef vector<ll> lvec;

const int mod = 1e9 + 7;
const ll INF = 1000000000000000000LL;

int main() {
  ivec n(3);
  REP(i, 3) cin >> n[i];
  sort(RALL(n));
  int a = n[0] * 10 + n[1];
  int b = n[2];
  int ans = a + b;
  print(ans);
  return 0;
}

Measured memory_bytes: 256
#define _LIBCPP_DEBUG 0
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const long long INF = 1LL << 60;
ll MOD = 1e9+7;

int main() {

    ll N; cin>>N;
    ll sum=1;
    double sum2=1;
    for (int i = 0; i < N; ++i) {
        ll A; cin>>A;
        sum *= A;
        sum2 *= A;
    }
    if((sum > 1000000000000000000ll)||(sum2 > 1000000000000000000ll)){
        cout<<-1<<endl;
    }else cout<<sum<<endl;
}

Measured memory_bytes: 3620
#pragma GCC optimize("Ofast")
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip> // setprecision
#include <complex> // complex
#include <math.h> 
#include <functional>
using namespace std;
using ll = long long;
using P = pair<int,int>;
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr ll mod2 = 1000000007;
constexpr ll mod = 998244353;
const int dx[8] = {1, 0, -1, 0,1,1,-1,-1};
const int dy[8] = {0, 1, 0, -1,1,-1,1,-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; }
// --------------------------------------------------------------------------
// i-1番目までで、j回操作をして、k個1を使ってる
ll dp[310][310][310];

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  string S;
  cin >> S;
  int K;
  cin >> K;
  vector<int> one;
  int N0=0,N1=0;
  int len = 0;
  for(int i=0; i<S.size(); i++){
    if(S[i] == '1'){
      len++;
      N1++;
    }else{
      one.emplace_back(len);
      len = 0;
      N0++;
    }
  }
  one.emplace_back(len);
  vector<int> oneS;
  oneS = one;
  for(int i=1; i<one.size(); i++){
    oneS[i] += oneS[i-1];
  }
  chmin(K,N1);
  dp[0][0][0] = 1;
  for(int i=0; i<=N0; i++){
    // 区間iの1の数はone[i]未満
    for(int j=0; j<=K; j++){
      // sは(k-one[i],k]の区間の累積和
      ll s = 0;
      for(int k=0; k<=N1; k++){
        s += dp[i][j][k];
        if(k >= one[i]){
          s -= dp[i][j][k-one[i]];
          s += mod;
          s %= mod;
        }
        // kがoneS[i]以上じゃなければ遷移できない
        if(k >= oneS[i]){
          dp[i+1][j][k] += s;
          dp[i+1][j][k] %= mod;
        }
      }
    }

    // 区間iの1の数はone[i]以上
    for(int j=0; j<=K; j++){
      for(int k=0; k<=N1; k++){
        // 先に遷移させておく
        dp[i][j+1][k+1] += dp[i][j][k];
        dp[i][j+1][k+1] %= mod;
        // one[i]は絶対使うのでk+one[i]がoneS[i]以上か判定する
        if(k+one[i] >= oneS[i]){
          dp[i+1][j][k+one[i]] += dp[i][j][k];
          dp[i+1][j][k+one[i]] %= mod;
        }
      }
    }
  }
  ll ans = 0;
  for(int i=0; i<=K; i++){
    ans += dp[N0+1][i][N1];
    ans %= mod;
  }
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 59476
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char H[1046527][14];
int getchar(char ch)
{
	if(ch=='A') return 1;
	if(ch=='C') return 2;
	if(ch=='G') return 3;
	if(ch=='T') return 4;
	else return 0;
}
long long getkey(char str[])
{
	long long num=0,p=1,i;
	for(i=0;i<strlen(str);i++)
	{
		num+=p*(getchar(str[i]));
		p*=5;
	}
	return num;
}
int h1(int key){return key%1046527;}
int h2(int key){return 1+(key%(1046527-1));}
int find(char str[])
{
	long long key,i,h;
	key=getkey(str);
	for(i=0;;i++)
	{
		h=(h1(key)+i*h2(key))%1046527;
		if(strcmp(H[h],str)==0) return 1;
		else if(strlen(H[h])==0) return 0;
	}
	return 0;
}
int insert(char str[])
{
	long long key,i,h;
	key=getkey(str);
	for(i=0;;i++)
	{
		h=(h1(key)+i*h2(key))%1046527;
		if(strcmp(H[h],str)==0) return 1;
		else if(strlen(H[h])==0)
		{
			strcpy(H[h],str);
			return 0;
		}
	}
	return 0;
}
int main()
{
	int i,n,h;
	char str[14],com[9];
	for(i=0;i<1046527;i++)
	{
		H[i][0]='\0';
	}
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%s %s",com,str);
		if(com[0]=='i')
		{
			insert(str);
		}else
		{
			if(find(str))
			printf("yes\n");
			else{
				printf("no\n");
			}
		}
	}
	return 0;
}

Measured memory_bytes: 17448
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
  int a = 0, b = 0;
  cin >> a >> b;
  if(2 * b >= a) {
    cout << 0 << endl;
  } else {
    cout << (a - 2 * b) << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll big=1e18;
const double PI=2*asin(1);

ll DP[3005][3005];

int main() {
  ll mod = 998244353;
  int A, B, C, D;
  cin>>A>>B>>C>>D;
  DP[A][B] = 1;
  for(ll i=A+1;i<=C;++i) {
    DP[i][B] = DP[i-1][B]*B%mod;
  }
  for(ll j=B+1;j<=D;++j) {
    DP[A][j] = DP[A][j-1]*A%mod;
  }
  for(ll i=A+1;i<=C;++i) {
    for(ll j=B+1;j<=D;++j) {
      DP[i][j] = (DP[i-1][j]*j%mod + DP[i][j-1]*i%mod - DP[i-1][j-1]*(i-1)%mod*(j-1)%mod)%mod;
      DP[i][j] = (DP[i][j]+mod)%mod;
    }
  }
  cout<<DP[C][D]<<endl;
}



Measured memory_bytes: 73992
n = int(input())
h = list(map(int , input().split()))

dp = [0] * n

for i in range(n):
    if i == 0:
        dp[i] = 0
        continue
    if i == 1:
        dp[i] = abs(h[i] - h[i - 1])
        continue
    if i == 2:
        dp[i] = abs(h[i] - h[i - 2])
        continue
    dp1 = abs(h[i] - h[i - 1]) + dp[i - 1]
    dp2 = abs(h[i] - h[i - 2]) + dp[i - 2]
    dp[i] = min(dp1, dp2)
print(dp[n-1])

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

int n, v[1000];
string s;
map<string, int> f;

struct cmp
{
	bool operator ()(string x, string y)
	{
		return x > y;
	}
};
priority_queue<string, vector<string>, cmp> a;

void dfs(int x, int y, int z)
{
	if (x == 0)
	{
		if (f[s] == 1) return;
		f[s] = 1;
		a.push(s);
		return;
	}
	int h = y; 
	for (int i = 0; i <= y; i++)
	{
		char c = s[z];
		v[s[z]]--;
		if (!v[s[z]]) h--;
		s[z] = 'a' + i;
		v[s[z]]++;
		if (v[s[z]] == 1) h++;
		dfs(x - 1, h, z + 1);
		v[s[z]]--;
		if (!v[s[z]]) h--;
		s[z] = c;
		v[s[z]]++;
		if (v[s[z]] == 1) h++;
	}
}

int main()
{
	cin >> n;
	s = "";
	for (int i = 1; i <= n; i++) s += 'a', v['a']++;
	f[s] = 1;
	a.push(s);
	for (int i = 1; i < n; i++)
	{
		s = "";
		for (int i = 1; i <= n; i++) s += 'a';
		s[n - i] = 'b';
		memset(v, 0, sizeof(v));
		v['a'] = n - 1;
		v['b'] = 1;
		dfs(i - 1, 2, n - i + 1);
	}
	while (!a.empty())
	{
		cout << a.top() << endl;
		a.pop();
	}
	return 0;
}

Measured memory_bytes: 20468
#include <cstdio>
using namespace std;

typedef long long LL;

inline bool check(LL i, LL j, LL k)
{
	if(i == j || j == k || i == k) return false;
	return i + j > k && i + k > j && j + k > i;
}

int main(int argc, char** argv)
{
	int n;
	scanf("%d", &n);
	int a[105];
	for(int i=0; i<n; i++)
		scanf("%d", a + i);
	int ans = 0;
	for(register int i=0; i<n; i++)
		for(register int j=i+1; j<n; j++)
			for(register int k=j+1; k<n; k++)
				if(check(a[i], a[j], a[k]))
					ans ++;
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 1736
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
    ll a,b,c,k;
    cin>>a>>b>>c>>k;
    
    ll temp = k;

    k = k - min(a,k);
    if(k==0) cout<<min(temp,a)<<endl;
    else{
        temp = k;
        k = k - min(k,b);
        if(k==0) cout<<(a+min(temp,b)*0)<<endl;
        else{
            temp = k;
            k = k - min(k,c);
            if(k==0) cout<<(a + min(temp,b)*0 + min(temp,c)*(-1))<<endl;
        }
    }
    
    return 0;
    
}



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

ll gcd(ll n, ll m){
    if(n % m == 0) return m;
    return gcd(m, n % m);
}

int main()
{
    ll a, b;
    cin >> a >> b;
    ll g = gcd(a, b);
    cout << a * b / g << endl;
}

Measured memory_bytes: 256