akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for (int i = (a); i < (b); i++)

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // cout << fixed << setprecision(10);
    int h, w, n;
    cin >> h >> w >> n;
    int sc, sr;
    cin >> sr >> sc;
    string s, t;
    cin >> s >> t;
    int l = 0, r = w + 1, u = 0, d = h + 1;
    for (int i = n - 1; i >= 0; i--) {
        if (t[i] == 'U') {
            if (d != h + 1)
                d++;
        } else if (t[i] == 'D') {
            if (u != 0)
                u--;
        } else if (t[i] == 'L') {
            if (r != w + 1)
                r++;
        } else {
            if (l != 0)
                l--;
        }
        if (s[i] == 'U') {
            u++;
        } else if (s[i] == 'D') {
            d--;
        } else if (s[i] == 'L') {
            l++;
        } else {
            r--;
        }
        if (r - l <= 1 || d - u <= 1) {
            cout << "NO" << endl;
            return 0;
        }
    }
    if (l < sc && sc < r && u < sr && sr < d)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return 0;
}

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

int a[114514];
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)cin >> a[i];
	int now = 0;
	for (int i = 0; i < 200000; i++) {
		now = a[now]-1;
		if (now == 1) {
			cout << i + 1 << endl;
			return 0;
		}
	}
	cout << -1 << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
bool is_prime(int n){
  for (int i = 2; i * i <= n; i++){
    if (n % i == 0){
      return false;
    }
  }
  return true;
}
int main(){
  while (1){
    int n;
    cin >> n;
    if (n == 0){
      break;
    }
    if (is_prime(n)){
      cout << 0 << endl;
    } else {
      int L = n;
      while (!is_prime(L)){
        L--;
      }
      int R = n;
      while (!is_prime(R)){
        R++;
      }
      cout << R - L << endl;
    }
  }
}


Measured memory_bytes: 3092
#include <bits/stdc++.h>
using namespace std;
#define FIN ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long ll;
typedef unordered_set<ll> usll;
typedef map<int, usll> misll;
typedef vector<ll> vll;
typedef vector<vll> vvll;

int main() {FIN
	
	ll h, w, n, i, j, k, x, y, t, sm;
	cin >> h >> w >> n;
	
	vvll pt(n, vll(2));
	vll pts(10);
	usll sq;
	for (i = 0; i < n; i++) {
		cin >> pt[i][0] >> pt[i][1];
		pt[i][0]--, pt[i][1]--;
		sq.insert(pt[i][0] * w + pt[i][1]);
	}
	
	misll txt;
	for (i = 0; i < n; i++) {
		for (j = pt[i][0] - 2; j <= pt[i][0]; j++) {
			for (k = pt[i][1] - 2; k <= pt[i][1]; k++) {
				if ((j >= 0 and j + 2 < h) and (k >= 0 and k + 2 < w)) {
					t = 0;
					for (x = j; x < j + 3; x++) {
						for (y = k; y < k + 3; y++) {
							if (sq.find(x * w + y) != sq.end())
								t++;
						}
					}
					txt[t].insert(j * w + k);
				}
			}
		}
	}
	
	sm = 0;
	for (auto it = txt.begin(); it != txt.end(); it++) {
		pts[it->first] = it->second.size();
		sm += it->second.size();
	}
	pts[0] = ((w - 2) * (h - 2) - sm);
	
	for (i = 0; i < (int)pts.size(); i++)
		cout << pts[i] << "\n";
	
	return 0;
}


Measured memory_bytes: 49096
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <array>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <bitset>
#include <tuple>
#include <cmath>
#include <complex>
#include <algorithm>
#include <utility>
#include <regex>
#include <cstdint>
#include <numeric>
#include <functional>
#include <cassert>

using namespace std;
using ll = int64_t;
using ull = uint64_t;

constexpr ll INF = 1'000'000'000'000'000'000;
namespace utils{
    template<class T, class Compare> using p_queue = priority_queue<T, vector<T>, Compare>;
    template<class T> using min_queue = p_queue<T, greater<T>>;
    template<class T> using max_queue = p_queue<T, less<T>>;

    template<class T> bool min_update(T& X, const T& A){ if(X > A) {X = A; return true;} return false; }
    template<class T> bool max_update(T& X, const T& A){ if(X < A) {X = A; return true;} return false; }
    using V_Set = unordered_set<int>;
    using E_Set = unordered_map<int, V_Set>;

#define ALL(x) begin(x), end(x)
#define rALL(x) rbegin(x), rend(x)
}
using namespace utils;


void sub_main(istream &is) {
    ll A, B;

    is >> A >> B;
    if(!is) return;
    ll mi, mx;
    ll K = (A + B) / 2;
    if((A + B) % 2 ){
        cout << "IMPOSSIBLE\n";
    }
    else{
        cout << K << endl;
    }


}

int main(int argc, char *argv[]) {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << setprecision(16) << scientific;
#ifdef DEBUG
    string test_cases = "test_A.txt";
    cerr << "DEBUG MODE" <<  endl;
    cerr << test_cases << " -->" << endl;
    auto fs = fstream(test_cases, fstream::in);
    int lp = 0;
    while(fs) {
        lp++;
        cout << lp <<  "#------\n";
        sub_main(fs);
    }
    cout << "------#" << endl;
    if(lp <= 1) sub_main(cin);
#else
    sub_main(cin);
#endif
    return 0;
}


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

using namespace std;

int main() {
    int a[5];
    
    for(int i=0; i<5; i++){
        cin>>a[i];
    }
    sort(a,a+5);

    cout<<a[4]<<" "<<a[3]<<" "<<a[2]<<" "<<a[1]<<" "<<a[0]<<endl;;
    
    return 0;
}

Measured memory_bytes: 1180
n,k=map(int,input().split())
ans=0
for i in range(k,n+2):
    ans+=i*(n-i+1)+1
mod=10**9+7
ans=ans%mod
print(ans)
#2個の和の総数は、2*10**100+(1~2N-1)の2N-1通り。
#↑最小値は2*10**100+1(10**100+(10*100+1))、最大値は2*10**100+(2N-1)
#最大値と最小値の間はすべて存在する。

#このように考えていくと、
#3個の和の総数は、3*10**100+(3~3N-3)の3N-5通り。
#......
#k個の和の総数は、k*10**100+(k*(k-1)/2~k*(2N-k+1)/2)のk(N-k+1)+1通り
#要は和として取りえる値の最小値と最大値の差をk(N-k+1)+1として、
#それを入力で与えられたk以上N以下について和を求めてやればいい。

Measured memory_bytes: 9176
from queue import Queue

k=int(input())

q = Queue()
count = 0

for i in range(1,10):
    q.put(i)

for _ in range(k):
    count = q.get()

    if count%10 != 0:
        q.put(10*count + (count%10) - 1)
    
    q.put(10*count + (count%10))

    if count%10 != 9:
        q.put(10*count + (count%10) + 1)

print(count)


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

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

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

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

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

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


int main(void) {
    char c;
    cin >> c;
    if (string("aiueo").find(c) != string::npos) {
        cout << "vowel" << endl;
    } else {
        cout << "consonant" << endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define endl '\n'
#define FASTINOUT ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const ll mod = 1000000007;
const double PI = 3.141592653589793238463;
const int N=1e6+9;
int main()
{
    FASTINOUT;
    string s;
    cin>>s;
    if (s[0]==s[2])
        cout<<"Yes\n";
    else
        cout<<"No\n";
    return 0;
}


Measured memory_bytes: 256
import copy
 
H, W, K = map(int, input().split())
tiles = [list(input()) for _ in range(H)]
answer  = 0

for h in range(2**H):
  for w in range(2**W):
    b_cnt = 0
    for i in range(H):
      for j in range(W):
        if not (h>>i&1 or w>>j&1) and tiles[i][j] == '#':
          b_cnt += 1
    if b_cnt == K:
      answer += 1
print(answer)

Measured memory_bytes: 74732
import java.util.Scanner;

//Power Calculus
public class Main{

	int n;
	int[] k;
	boolean[] u;

	boolean reach(long b, long x, int rest){
		long r = b+x;
		while(rest--!=0)r+=r;
		return n<=r;
	}

	boolean dfs(int d, int x, int max, int len){
		if(d==0){
			return u[n];
		}
		if(d==1){
			return u[Math.abs(x-n)];
		}
		for(int i=len-1;i>=0;i--){
			int s = k[i]+x;
			if(!(2*n<s||u[s]||!reach(s, Math.max(max, s), d-1))){
				//				if(d!=1||u[Math.abs(s-n)]){
				u[s] = true;
				k[len] = s;
				if(dfs(d-1, s, Math.max(max, s), len+1))return true;
				u[s] = false;
				//				}
			}
			s = x-k[i];
			if(!(s<0||!reach(s, max, d-1)||u[s])){
				//				if(d!=1||u[Math.abs(s-n)]){
				u[s] = true;
				k[len] = s;
				if(dfs(d-1, s, max, len+1))return true;
				u[s] = false;
				//				}
			}
			s = k[i] - x;
			if(!(s<0||!reach(s, max, d-1)||u[s])){
				//				if(d!=1||u[Math.abs(s-n)]){
				u[s] = true;
				k[len] = s;
				if(dfs(d-1, s, max, len+1))return true;
				u[s] = false;
				//				}
			}
		}
		return false;
	}

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			n = sc.nextInt();
			if(n==0)break;
			int x = 1, res = 0;
			while(x<n){
				x*=2; res++;
			}
			for(;;){
				u = new boolean[2500];
				k = new int[res+1];
				u[1] = true;
				k[0] = 1;
				if(dfs(res, 1, 1, 1)){
					System.out.println(res); break;
				}
				res++;
			}
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 12000
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <cctype>
using namespace std;
typedef long long LL;
const int N = 1005;

int n , w , h;
pair<int , int> a[N] , b[N];

int id(int x , int y) {
    if (y == 0)
        return x;
    if (x == w)
        return w + y;
    if (y == h)
        return w + h + w - x;
    if (x == 0)
        return w + h + w + h - y;
    return -1;
}

int check(int x , int y , int dx , int dy) {
    int xx , yy , X , Y;
    if (dx == 1)
        xx = w - x;
    else
        xx = x;
    if (dy == 1)
        yy = h - y;
    else
        yy = y;
    int T = min(xx , yy);
    X = x + dx * T;
    Y = y + dy * T;
    return id(X , Y);
}
 
void work() {    
    scanf("%d%d%d" , &n , &w , &h);
    int L = 2 * (w + h);
    vector<int> Q;
    for (int i = 0 ; i < n ; ++ i) {
        int x , y , l , r;
        char dir[5];
        scanf("%d%d%s" , &x , &y , dir);
        
        if (*dir == 'E') {
            l = check(x , y , 1 , -1);
            r = check(x , y , 1 , 1);
        }
        if (*dir == 'N') {
            l = check(x , y , 1 , 1);
            r = check(x , y , -1 , 1);
        }
        if (*dir == 'W') {
            l = check(x , y , -1 , 1);        
            r = check(x , y , -1 , -1);            
        }
        if (*dir == 'S') {
            l = check(x , y , -1 , -1);        
            r = check(x , y , 1 , -1);            
        }        
        //if (l > r)
        //    r += L;
        //cout << l << ' ' << r << endl;
        a[i] = make_pair(l , r);
        Q.push_back(l);
        Q.push_back(r);
    }
    sort(Q.begin(), Q.end());
    Q.erase(unique(Q.begin(), Q.end()), Q.end());
    // sort(a , a + n);
    int m = 0;
    int ans;
    if (n == 0) ans = 0;
    else ans = 1 << 30;
    for (int c = 0; c < Q.size(); ++c) {
        int t = Q[c];
        vector<pair<int, int> > ver;
        for (int i = 0; i < n; ++i) {
            int l = a[i].first,  r = a[i].second;
            if ((l <= t && r >= t && l <= r) || (l >= t && r >= t && l > r) ||
                (l <= t && r <= t && l > r))
                continue;
            //if (t == 22) printf("%d %d\n", l, r);
            l = l - t;
            r = r - t;
            if (l < 0) l += L;
            if (r < 0) r += L;
            ver.push_back(make_pair(l, -r)); 
        }
        sort(ver.begin(), ver.end());
        int p = 0;
        for (int i = 0; i < ver.size(); ++i) {
            ver[i].second = -ver[i].second;
            while (p > 0 && ver[i].second <= ver[p - 1].second)
                --p;
            ver[p++] = ver[i];
        }
        int r = -1;
        int res = 1;
        for (int i = 0; i < p; ++i) {
            if (ver[i].first > r) {
                ++res;
                r = ver[i].second;
            }
            else continue;
        }
        ans = min(ans, res);
    }
    cout << ans << endl;
}

int main() {
    work();
    return 0;
}

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

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

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

int main()
{
  string S;
  cin >> S;

  rep(i, 3)
  {
    if (S[i] == S[i + 1])
    {
      cout << "Bad" << endl;
      return 0;
    }
  }

  cout << "Good" << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		if(x%2==0){
			if(x%3!=0&&x%5!=0){
				cout<<"DENIED"<<endl;
				return 0;
			}
		}
	}
	cout<<"APPROVED"<<endl;
}

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

int main(){
    int n;
    cin >> n;
    if (n == 0) cout << 1 << endl;
    else if (n == 1) cout << 0 << endl;
}

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

const string YES = "Yes";
const string NO = "No";

int main() {
  int64 N, A, B, C;
  std::vector<std::string> s;
  cin >> N >> A >> B >> C;
  vector<int64> buf{A, B, C};
  s = vector<string>(N);
  for (int i = 0; i < N; i++) {
    std::cin >> s[i];
  }
  vector<char> ans;
  auto dfs = [&](auto rec, int idx) -> bool {
    // while (idx < N - 1 && s[idx] == s[idx + 1]) {
    //   ans.push_back(s[idx][0]);
    //   ans.push_back(s[idx][1]);
    //   idx += 2;
    // }
    if (idx == N) {
      cout << YES << "\n";
      REP(i, N) { cout << ans[i] << "\n"; }
      return true;
    }
    int x = s[idx][0] - 'A';
    int y = s[idx][1] - 'A';
    REP(_, 2) {
      if (buf[x] > 0) {
        buf[x]--;
        buf[y]++;
        ans.push_back(y + 'A');
        if (rec(rec, idx + 1)) {
          return true;
        };
        ans.pop_back();
        buf[x]++;
        buf[y]--;
      }
      swap(x, y);
    }
    return false;
  };
  if (!dfs(dfs, 0)) {
    cout << NO << endl;
  }
}


Measured memory_bytes: 19164
#include <bits/stdc++.h>
#define N 50000

using namespace std;

typedef long long int ll;

ll i,j,k,x,z,p,q,M,co,b,c;
double a,y;
string str;
vector<ll>veca;
ll suma[N+5];

void sum()
{
    z = 0;
    for (i=1;i<=N;i++)
    {
        z += (i*i*i);
        suma[i]=z;
    }
}

int main()
{
    cin >> str;
    if (str=="Sunny")
        cout << "Cloudy" << endl;
    if (str=="Cloudy")
        cout << "Rainy" << endl;
    if (str=="Rainy")
        cout << "Sunny" << endl;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static Atcoder;
using System.Threading.Tasks;
using System.ComponentModel;

public class Hello
{

    public static void Main()
    {
        int N = intRead();
        int ans = 0;
        int count = 0;
        for (int i = 1; i <= N; i += 2)
        {
            count = 0;
            for (int j = 1; j <= i; j++)
            {
                if (i % j == 0)
                {
                    count++;
                }
            }
            if (count == 8) ans++;
        }
        Console.WriteLine(ans);
    }

}


public class Atcoder
{
    static void Swap<T>(ref T a, ref T b)
    {
        var t = a;
        a = b;
        b = t;
    }
    public static long LCM(long a, long b)
    {
        long c = a * b;
        if (a < b) Swap(ref a, ref b);
        long d = a % b;
        while (d != 0)
        {
            a = b;
            b = d;
            d = a % b;
        }
        return c / b;
    }
    public static string strReverce(string s)
    {
        return new string(s.Reverse().ToArray());
    }
    public static int intRead()
    {
        return int.Parse(Console.ReadLine());
    }
    public static bool IsPrime(int n)
    {
        if (n < 2) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;

        //double sqrtNum = Math.Sqrt(n);
        for (int i = 3; i < n; i += 2)
        {
            if (n % i == 0) return false;
        }
        return true;
    }
    public static string[] SpRead(char c)
    {
        return Console.ReadLine().Split(c);
    }
    public static int[] SpIntRead(char c)
    {
        return Console.ReadLine().Split(' ').Select(a => int.Parse(a)).ToArray();
    }
    public static string ToConvertBit(int N, int e)
    {
        string ret = "";
        int r = 0;
        while (N != 0)
        {
            r = N % e;
            ret += r.ToString();
            N -= r;
            N /= e;
        }
        ret = strReverce(ret);
        return ret;
    }

}


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

//#define int long long
#define DBG 1
#define dump(o) if(DBG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define each(it,c) for(auto it=(c).begin();it!=(c).end();it++)
#define all(c) c.begin(),c.end()
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);

signed main() {
	string s; int cnt(0);
	while (getline(cin, s)) {
		rep(i, 0, s.size() - 4) {
			if (s.substr(i, 5) == "apple") {
				s[i] = 'p';
				s[i + 1] = 'e';
				s[i + 2] = 'a';
				s[i + 3] = 'c';
				s[i + 4] = 'h';
			}
			else if (s.substr(i, 5) == "peach") {
				s[i] = 'a';
				s[i + 1] = 'p';
				s[i + 2] = 'p';
				s[i + 3] = 'l';
				s[i + 4] = 'e';
			}
		}
		cout << s << endl;
	}
	return 0;
}

Measured memory_bytes: 3092
#include<iostream>
#include<queue>
#include<iomanip>
using namespace std;

int main(){
    int n;
    cin >> n;
    priority_queue<double> pq;
    for(int i = 0; i < n; i++){
        double x;   cin >> x;
        pq.push(-x);
    }
    while(pq.size() > 1){
        double a = -pq.top();   pq.pop();
        double b = -pq.top();   pq.pop();
        pq.push(-(a+b)/2);
    }
    cout << fixed << setprecision(12) << -pq.top() << endl;
    return 0;
}

Measured memory_bytes: 256
use std::collections::*;
use std::io::*;
use std::cmp;
#[allow(dead_code)]
struct Io<'a> {
    r: BufReader<StdinLock<'a>>,
    w: BufWriter<StdoutLock<'a>>,
    buf: VecDeque<String>,
    buf_str: String,
}
#[allow(dead_code)]
impl<'a> Io<'a> {
    fn r<T: std::str::FromStr>(&mut self) -> T {
        if self.buf.len() == 0 {
            self.r.read_line(&mut self.buf_str).unwrap();
            for w in self.buf_str.split_whitespace() {
                self.buf.push_back(w.to_owned());
            }
            self.buf_str.clear();
        }
        self.buf
            .pop_front()
            .unwrap()
            .parse()
            .unwrap_or_else(|_| panic!())
    }
    fn w<T: std::fmt::Display>(&mut self, v: T) {
        write!(self.w, "{}", v).unwrap();
    }
    fn wl<T: std::fmt::Display>(&mut self, v: T) {
        writeln!(self.w, "{}", v).unwrap();
    }
    fn iter<'b, T: std::str::FromStr>(&'b mut self) -> IoIter<'a, 'b, T> {
        IoIter {
            io: self,
            p: std::marker::PhantomData,
        }
    }
}
#[allow(dead_code)]
struct IoIter<'a: 'b, 'b, T: std::str::FromStr> {
    io: &'b mut Io<'a>,
    p: std::marker::PhantomData<T>,
}
#[allow(dead_code)]
impl<'a, 'b, T: std::str::FromStr> Iterator for IoIter<'a, 'b, T> {
    type Item = T;
    fn next(&mut self) -> Option<T> {
        Some(self.io.r())
    }
}
fn main() {
    let stdin = stdin();
    let stdout = stdout();
    let r = BufReader::new(stdin.lock());
    let w = BufWriter::new(stdout.lock());
    let io = Io {
        r,
        w,
        buf: VecDeque::new(),
        buf_str: String::new(),
    };
    unsafe {
        problem(io);
    }
}


unsafe fn problem(mut io: Io) {
    let n: usize = io.r();
    let mut a: Vec<isize> = io.iter().take(n).collect();

    let mut swap_count = 0;
    let mut swapped = true;
    while swapped {
        swapped = false;
        for i in (1..a.len()).rev() {
            if a[i] < a[i - 1] {
                a.swap(i, i - 1);
                swap_count += 1;
                swapped = true;
            }
        }
    }
    print(&mut io, &a);
    io.wl(swap_count);
}
fn print(io: &mut Io, a: &Vec<isize> ) {
    io.w(a[0]);
    for i in a.iter().skip(1) {
        io.w(" "); 
        io.w(i.to_string());
    }
    io.w("\n");
}


Measured memory_bytes: 5032
// #include <iostream>
// #include <utility>
// #include <numeric>
// #include <stdint.h>
// #include <set>
// #include <vector>

// using namespace std;

// int main()
// {
//   int64_t N, K;
//   cin >> N >> K;
//   vector<int64_t> V;

//   for (int64_t n=0; n<N; ++n) {
//     int64_t v;
//     cin >> v;
//     V.push_back(v);
//   }

//   int64_t max_v = 0;

//   for (int64_t get = 0; get<=K && get<=N; ++get) {
//     for (int64_t get_left = 0; get_left <= get; ++get_left) {
//       int64_t get_right = get - get_left;
//       set<int64_t> got_v;

//       got_v.insert(V.begin(), V.begin()+get_left);
//       got_v.insert(V.end()-get_right, V.end());

//       for (int64_t refund = 1; refund<=K-get && got_v.size() > 0; ++refund) {
// 	int64_t min = *got_v.begin();
// 	if (min >= 0)
// 	  break;
// 	got_v.erase(got_v.begin());
//       }

//       max_v = max(max_v, accumulate(got_v.begin(), got_v.end(), 0));
//     }
//   }

//   cout << max_v << endl;

//   return 0;
// }


#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <numeric>

using namespace std;

typedef long long ll;

long long GCD(long long a, long long b){if(b==0)return a;return GCD(b,a%b);}

int main() {
    int N, K; cin >> N >> K;
    vector<ll> v(N); for (int i = 0; i < N; ++i) cin >> v[i];

    ll res = 0;

    for (int i = 0; i <= K; ++i) {
        for (int j = 0; i + j <= K; ++j) {
            if (i + j > N) continue;

            vector<ll> h;
            for (int k = 0; k < i; ++k) h.push_back(v[k]);
            for (int k = 0; k < j; ++k) h.push_back(v[N-k-1]);

            sort(h.begin(), h.end());

            int n = i + j;
            for (int k = 0; k < K - n && k < n; ++k) h[k] = max(0LL, h[k]);

            res = max(res, accumulate(h.begin(), h.end(), 0LL));
        }
    }

    cout << res << endl;
}


Measured memory_bytes: 256
r, g, b, n = map(int, input().split())

ans = 0
for i in range(n // r + 1):
    for j in range(n // g + 1):
        m = r * i + g * j
        if m <= n and (n - m) % b == 0:
            ans += 1
        elif m > n:
            break

print(ans)


Measured memory_bytes: 9064
import java.util.Scanner;

public class Main {

	private static long MOD = 1000000007;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.close();


		long ans = 1L;
		for(int i=1;i<=n;i++) {
			ans = ans * 10L%MOD;
		}

		long bb = 1L;
		for(int i=1;i<=n;i++) {
			bb = bb * 9L%MOD;
		}

		long cc = 1L;
		for(int i=1;i<=n;i++) {
			cc = cc * 8L%MOD;
		}

		ans = (ans - bb)%MOD;
		ans = (ans -bb)%MOD;
		ans = (ans +cc)%MOD;
		if(ans<0) {
			ans=ans+MOD;
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 35620
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define f(i, n)         for(int i=0; i<n; i++)
#define fo(i, k, n)     for(int i=k; i<n; i++)
#define forr(i, a, b)   for(int i=a; i<=b; i++)
#define rf(i,n)         for(int i=n;i>=0;i--)
typedef unsigned long long ull;
typedef pair<int,int> pr;
#define MAX 100005
#define INF 1000000009
#define   sq(n)         (n*n)
#define p(n) cout<<n<<endl
#define pb push_back
#define py cout<<"YES"<<endl;
#define pn cout<<"NO"<<endl;
ll mod =1e9+7;
#define __FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
ll lcm ( ll a, ll b )
{
    return ( a / __gcd ( a, b ) ) * b;
}


ll modpow(ll a,ll n, ll mod)
{
    ll res = 1;
    while(n>0)
    {
        if (n%2==1)
        {
            res = res * a % mod;
        }
        a = a * a % mod;
        n/=2;
    }
    return res;
}

int bin_ser(int *a,int n,int x)
{
    int l=0;
    int h=n-1;
    while(l<=h)
    {
        int mid=l+((h-l)/2);
        if(a[mid]==x)
        {
            return mid;
        }
        else if(a[mid]<x)
        {
            l=mid+1;
        }
        else
        {
            h=mid-1;
        }
    }
}

int main()
{
    __FastIO;

    int n;
    cin>>n;
    int cnt=0,a[n+1],b[n+1];
    f(i,n)
    {
            cin>>a[i]>>b[i];
    }
    f(i,n-2)
    {
        if(a[i]==b[i] && a[i+1]==b[i+1] && a[i+2]==b[i+2])
        {
            cnt=1;
        }
    }

    if(cnt==1)
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }
    return 0;
}



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

int UwaitN[100] = {0};
int Uwait[100][100];
int DlockN[100] = {0};
int Dlock[100][100];

int UvisitedN;
int Uvisited[100];

bool tansaku(int u){	//??????????????????????????§1????????????
	int i,j;

	//????????\????????¨????????£???????????????????????????
	for(i=0;i<UvisitedN;i++){
		if(u==Uvisited[i]) return true;
	}

	//??\????????¨??????????????°?????¢???
	Uvisited[UvisitedN]=u;
	UvisitedN++;
	for(i=0;i<UwaitN[u];i++){
		for(j=0;j<DlockN[Uwait[u][i]];j++){
			//??¢?´¢?????§???????????????????????????????????????????????\?????????
			if(tansaku(Dlock[Uwait[u][i]][j])) return true;
			UvisitedN--;
		}
	}
	return false;
}

int solve(){
	for(int u=0;u<100;u++){
		UvisitedN=0;
		if(tansaku(u)) return 1;
	}
	return 0;
}

int main(){
	int n,u,d;
	string s;

	cin>>n;
	while(n--){
		cin>>u>>s>>d;
		u--;d--;
		if(s=="lock"){
			Dlock[d][DlockN[d]] = u;
			DlockN[d]++;
		}else if(s=="wait"){
			Uwait[u][UwaitN[u]] = d;
			UwaitN[u]++;
		}
	}

	cout<<solve()<<endl;

	return 0;
}

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

int main()
{
  int n, k; cin >> n >> k;
  vector<int> a(n);
  rep(i, k) {
    int d; cin >> d;
    rep(j, d) {
      int t; cin >> t; t--;
      a[t]++;
    }
  }
  int ans = 0;
  rep(i, n) {
    if (a[i]==0) ans++;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define qwq(x) cerr<<" #"<<#x<<" = "<<x<<endl;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
 
template<class T> inline void read(T &x){
	int f=0;x=0;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())f|=(ch=='-');
	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	if(f)x=-x;
}

const int N=100005;
int x,y;

int main(){
	read(x),read(y);
	int ans=2e9+99;
	if(x<=y)ans=min(ans,y-x);
	if(-x<=y)ans=min(ans,y+x+1);
	if(x<=-y)ans=min(ans,-y-x+1);
	if(-x<=-y)ans=min(ans,-y+x+2);
	cout<<ans<<endl;
	return 0;
}


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

int n;
ll a,b;
int d[100001];

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout<<fixed;
#ifdef LOCAL_DEFINE
    freopen("in", "r", stdin);
    freopen("out","w",stdout);
#endif
  cin>>n>>a>>b;
  int pre=-1;
  for(int i=0;i<n;i++){
    int x;cin>>x;
    if(i==0){
      pre=x;
      continue;
    }
    d[i-1]=x-pre;
    pre=x;
  }
  n--;
  ll ans=0;
  for(int i=0;i<n;i++){
    ll wcost=d[i]*a;
    if(wcost<=b){
      ans+=wcost;
    }else{
      ans+=b;
    }
  }
  cout<<ans<<"\n";
#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}

Measured memory_bytes: 640
import java.lang.Math

class IntSegmentTree(n: Int, private val init: Int, private val func: (Int, Int) -> Int) {
    private var size = 1

    init {
        while (size < n) {
            size *= 2
        }
    }

    private val segTree = IntArray(size * 2 - 1) { init }

    // 指定要素を更新
    fun update(x: Int, value: Int) {
        var tmp = x + size - 1

        segTree[tmp] = value
        while (tmp > 0) {
            tmp = (tmp - 1) / 2
            segTree[tmp] = func(segTree[2 * tmp + 1], segTree[2 * tmp + 2])
        }
    }

    // [a, b)の関数適用結果を取得
    // bが開区間であることに注意
    fun get(a: Int, b: Int, k: Int = 0, l: Int = 0, r: Int = size): Int {
        if (r <= a || b <= l) {
            return init
        }
        if (a <= l && r <= b) {
            return segTree[k]
        }

        val vl = get(a, b, 2 * k + 1, l, (l + r) / 2)
        val vr = get(a, b, 2 * k + 2, (l + r) / 2, r)

        return func(vl, vr)
    }

    // 指定要素を取得
    fun getElem(x: Int): Int = segTree[x + size - 1]
}

fun main(args: Array<String>) {
    val mod = 998244353L
    val N = readInputLine().toInt()
    val collisionChain = IntSegmentTree(N, 0, Math::max)
    val robots = Array(N) { readInputLine().split(" ").let { Pair(it[0].toInt(), it[1].toInt()) } }
    robots.sortBy { it.first }

    // ロボットを動かした場合の最大衝突範囲を初期化
    repeat(N) {
        collisionChain.update(it, it)
    }

    // ロボットを動かした場合の最大衝突範囲を二分探索で求めてセグ木に詰める
    for (i in N - 2 downTo 0) {
        val maxCollision = lowerBound(robots, robots[i].first + robots[i].second)
        collisionChain.update(i, collisionChain.get(i, maxCollision))
    }

    // dp[0:動かさない, 1:動かした][Nロボット目でのパターン数(遠くから見る)]
    val dp = Array(2) { LongArray(N) }
    dp[0][N - 1] = 1L
    dp[1][N - 1] = 1L

    for (i in N - 2 downTo 0) {
        dp[0][i] = (dp[0][i + 1] + dp[1][i + 1]) % mod
        val maxCollision = collisionChain.getElem(i)
        if (maxCollision == N - 1) {
            dp[1][i] = 1L
        } else {
            dp[1][i] = (dp[0][maxCollision + 1] + dp[1][maxCollision + 1]) % mod
        }
    }

    println((dp[0][0] + dp[1][0]) % mod)
}

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

fun lowerBound(robots: Array<Pair<Int, Int>>, dist: Int): Int {
    var l = -1
    var r = robots.size

    while (r - l > 1) {
        val mid = (r + l) / 2
        if (robots[mid].first >= dist) {
            r = mid
        } else {
            l = mid
        }
    }

    return r
}


Measured memory_bytes: 139452
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<tuple>
#include<map>
#include<queue>
#include<math.h>
#include<iomanip>
#define rep(i, n) rep2(i,0,n)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define PI acos(-1);
typedef long long ll;
using namespace std;
#define MOD 1000000007
//scanf("%d", &a) '\n'

int main() {
	int n;
	cin >> n;
	int ans = n / 1.08;
	int ans1 = ans + 1;
	int ans2 = ans - 1;
	if (int(ans*1.08) == n) { cout << ans << endl; return 0; }
	if (int(ans1*1.08) == n) { cout << ans1 << endl; return 0; }
	if (int(ans2*1.08) == n) { cout << ans2 << endl; return 0; }

	cout << ":(" << endl;

}
	

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

int main() {
  string s; 
  char op;
  int a, b;
  cin >> a >> op >> b;
 
  

if(op == '+') {
  cout << a + b << endl;
}
else if (op == '-') {
  cout << a - b << endl;
}
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#pragma warning( disable:4996 )
#define SWAP(a,b) (a += b,b = a - b,a -= b)
int main() {

	int r, g, b, N, R, G, B;
	int count = 0;
	scanf("%d %d %d %d", &R, &G, &B, &N);
	if (R < G) {
		SWAP(R, G);
	}
	if (G < B) {
		SWAP(G, B);
		if (R < G) {
			SWAP(R, G);
		}
	}
	for (r = N / R; r >= 0; r--) {
		int rest = N - r * R;
		for (g = rest / G; g >= 0; g--) {
			int rest2 = rest - g * G;
			if (rest2%B == 0)count++;
		}
	}

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

Measured memory_bytes: 128
#include <iostream>

using namespace std;

int main() {

    int fib[50];
    fib[0] = fib[1] = 1;

    for (int i = 2; i <= 44; ++i) fib[i] = fib[i-1] + fib[i-2];

    int n;
    cin >> n;

    cout << fib[n] << endl;

    return 0;
}

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

int A[1000][1000];
int cnt[1000][1000];
int idx[1000];

vector<pair<int, int> > V1, V2;

void upd(int i, int j) {
    if (cnt[i][j] == 0) {
        cnt[i][j]++;
        cnt[j][i]++;
    }
    else
        V2.emplace_back(i, j);
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        idx[i] = 0;
        for (int j = 0; j < n - 1; j++) {
            cin >> A[i][j];
            A[i][j]--;
            cnt[i][A[i][j]] = 0;
        }
    }
    for (int i = 0; i < n; i++)
        upd(i, A[i][0]);

    int CNT = 0;
    int ans = 0;
    while (!V2.empty()) {
        ans++;
        swap(V1, V2);
        V2.clear();
        for (auto p : V1) {
            int i = p.first, j = p.second;
            if (idx[i] < n - 2)
                upd(i, A[i][++idx[i]]);
            if (idx[j] < n - 2)
                upd(j, A[j][++idx[j]]);
            CNT++;
        }
    }
    cout << ((CNT == n * (n - 1) / 2) ? ans : -1) << "\n";
}


Measured memory_bytes: 8064
package main

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

var mod int = 1e9 + 7

func permutation(n int, k int) int {
	v := 1
	if 0 < k && k <= n {
		for i := 0; i < k; i++ {
			v *= (n - i) % mod
			v %= mod
		}
	} else if k > n {
		v = 0
	}
	return v
}

func factorial(n int) int {
	return permutation(n, n-1)
}

func combination(n int, k int) int {
	return permutation(n, k) / factorial(k)
}

func homogeneous(n int, k int) int {
	return combination(n+k-1, k)
}

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

func scanInt64() int64 {
	sc.Scan()
	i, _ := strconv.ParseInt(sc.Text(), 10, 64)
	return i
}

func scanInts(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = scanInt()
	}
	return res
}

func scanInts64(n int) []int64 {
	res := make([]int64, n)
	for i := range res {
		res[i] = scanInt64()
	}
	return res
}

func scanText() string {
	sc.Buffer([]byte{}, math.MaxInt64)
	sc.Scan()
	return sc.Text()
}

var sc = bufio.NewScanner(os.Stdin)

func main() {
	sc.Split(bufio.ScanWords)

	n, k := scanInt(), scanInt()
	sum := 0
	for i := k; i < n+2; i++ {
		sum += i*(n-i+1) + 1
		sum %= int(1e9 + 7)
	}
	fmt.Println(sum)
}


Measured memory_bytes: 1756
import java.util.*;

public class Main {
  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int K = sc.nextInt();
    int[] x = new int[N];
    for (int i = 0; i < N; i++) {
      x[i] = sc.nextInt();
    }

    int ans = Integer.MAX_VALUE;

    // sacn minus range
    int i = K-1;
    if (x[0] < 0 && x[i] <= 0) {
      while (i < N && x[i] <= 0) {
        i++;
      }
      ans = Math.min(ans, Math.abs(x[i-K]));
    }
    
    // scan across zero range
    while (i < N && x[i-(K-1)] < 0) {
      int leftPos = Math.abs(x[i-(K-1)]);
      int rightPos = x[i];
      // turn left edge
      ans = Math.min(ans, 2*leftPos + rightPos);
      // turn right edge
      ans = Math.min(ans, leftPos + 2*rightPos);
      
      i++;
    }
    
    // scan plus range
    if (i < N && x[i-(K-1)] >= 0) {
      ans = Math.min(ans, x[i]);
    }
    
    System.out.println(ans);
  }
}

Measured memory_bytes: 50292
#include <iostream>

using namespace std;

int main() {
    int N;
    cin >> N;

    for (int i = N; i < 1000; i++) {
        int a, b, c;
        a = i / 100;
        b = (i / 10) % 10;
        c = i % 10;
        if ( a == b && b == c) {
            cout << i << endl;
            break;
        }
    }

    return 0;
}


Measured memory_bytes: 256
import fractions
from functools import reduce
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)#数列に対しての最小公倍数

n,m = map(int,input().split())
a = list(map(int,input().split()))
b = [x//2 for x in a]
c = 0
while True:
    if a[0]%2:
        for i in range(n):
            if a[i]%2 == 0:
                print(0)
                exit()
        break
    else:
        for i in range(n):
            if a[i]%2:
                print(0)
                exit()
            a[i]//=2
        c += 1

least = lcm(*b)
ans = ((m//least)+1)//2
print(ans)

Measured memory_bytes: 89580
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define dbg(x) cerr << #x << " = " << x << endl
#define _ << ' ' <<
using namespace std;
using ll = long long;
using vi = vector<int>;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    ll k;
    cin >> k;
    ll p = 0;
    vector<pair<int, int>> v;
    for (int i = 0; i < n; ++i)
    {
        int a, b;
        cin >> a >> b;
        v.emplace_back(a, b);
    }
    sort(all(v));
    for (int i = 0; i < n; ++i)
    {
        int a, b;
        tie(a, b) = v[i];
        p += b;
        if (p >= k)
            return cout << a, 0;
    }
}


Measured memory_bytes: 1400
#include<stdio.h>
#include<string.h>
#define NIL -1
int main(){
    char sa[105],sb[105],sc[105];
    scanf("%s %s %s",sa,sb,sc);
    int lena=strlen(sa),lenb=strlen(sb),lenc=strlen(sc);
    sa[lena]=NIL;
    sb[lenb]=NIL;
    sc[lenc]=NIL;
    
    int a=0,b=0,c=0;
    char p=sa[a];
    a++;
    while(1){
        if(p=='a' && sa[a]==NIL){
            printf("A");
            break;
        }else if(p=='b' && sb[b]==NIL){
            printf("B");
            break;
        }else if(p=='c' && sc[c]==NIL){
            printf("C");
            break;
        }else if(p=='a'){
            p=sa[a];
            a++;
        }else if(p=='b'){
            p=sb[b];
            b++;
        }else if(p=='c'){
            p=sc[c];
            c++;
        }else{
            printf("bug");
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
//ll gcd(ll a,ll b){if(a%b==0)return b;return gcd(b,a%b);}
//ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=ll(1e16)+ll(7);
const ll MOD=1000000007LL;
#define out(a) cout<<fixed<<setprecision((a))
//tie(a,b,c) = make_tuple(10,9,87);
#define pop_(a) __builtin_popcount((a))
ll keta(ll a){ll r=0;while(a){a/=10;r++;}return r;}
ll ketawa(ll a){ll r=0;while(a){r+=a%10;a/=10;}return r;}


int main(){

  int n,m;
  cin >> n >> m;

  vector< vector<ll> > dp(n+1,vector<ll>(m+1,0));
  vector<ll> s(n),t(m);

  /*
    2dimBITを使えば
    cnt[i][j] := sのi文字目とtのj文字目が最後になるときの個数
    とすると
    s[i]==t[j]:
      cnt[i][j] = sum(cnt[x][y]|x<i,y<j) + 1;
    s[i]!=t[j]:
      cnt[i][j] = 0;
    とするとO(NM(logNlogM))でできる
    ans = sum(cnt)


    dp[i][j] := sはi文字目までtはj文字目まで見た時の個数
    ans = dp[n][m]
    2dimBITの時はans=sum(cnt)だった。今回はdp[i][j]をdp[n][m]まで伝搬させてる？？
    dp[i][j] = (伝搬されてきたやつ) + (sのi文字目とtのj文字目が最後になるときの個数)
    (伝搬されてきたやつ) = dp[i-1][j] + dp[i][j-1] - dp[i][j]
    (sのi文字目とtのj文字目が最後になるときの個数) = dp[i][j]
    O(NM)

    s[i]!=t[j]の時:
      dp[i+1][j+1] = dp[i+1][j]+dp[i][j+1]-dp[i][j];
    s[i]==t[j]の時:
      dp[i+1][j+1] = dp[i+1][j]+dp[i][j+1];
  */

  for(auto &&x:s)cin>>x;
  for(auto &&x:t)cin>>x;
  for(int i=0;i<n+1;i++)dp[i][0] = 1;
  for(int j=0;j<m+1;j++)dp[0][j] = 1;
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      dp[i+1][j+1] += dp[i][j+1];
      dp[i+1][j+1] += dp[i+1][j];
      if(s[i]!=t[j]){
        dp[i+1][j+1] += MOD - dp[i][j];
      }
      dp[i+1][j+1] %= MOD;
    }
  }
  cout << dp[n][m] << endl;
}


Measured memory_bytes: 31616
N = int(input())

numlist = []
keta = len(str(N-1))
for k in range(3,keta+1):
    for i in range(3**k):
        cur = ''
        tmp = i
        tk = 0
        while tk<k:
            cur += str(tmp%3)
            tmp //= 3
            tk += 1

        numlist.append(cur)

ans = 0
coeff = [3,5,7]
for s in numlist:
    if len(s)<3 :continue
    flag = [False,False,False]
    val = 0
    base = 1
    for t in s:
        flag[int(t)] = True
        val += coeff[int(t)] * base
        base *= 10
    if (sum(flag)==3) and (val <= N):
        ans += 1
print(ans)
        


Measured memory_bytes: 5144
#include <iostream>
#include <string>
#include <math.h>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <set>
#include <queue>
#include <map>
using namespace std;

#define mod 1000000007
#define ten5 100005
#define ten52 200005
#define ten6 1000005
#define PI 3.1415926

typedef long long int ll;

//ll num[ten52];
//ll num[10][10];
//set<ll> sll;
map<string,ll> mp,mp1;
map<string,ll>::iterator iter;

int main(void)
{
    long long int sum=0,range=0,ceiling;
    double ans=0.0,d;
    long long int m,n,o,i,j,k=0,money;
    long long int a,a1=0,a2=0,a3=0,ar,as,at1;
    string s;
    char c;
    a=a1=a2=a3=0;
    //vector <int> v;
    //float f,g,h;
    //int c,d,big=0;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>s;
        mp[s]++;
    }
    for(auto au:mp) a=max(a,au.second);
    for(auto au:mp)
    {
        if(au.second==a) mp1[au.first]=au.first[0]-'a';
    }
    for(auto au:mp1)
    {
        cout<<au.first<<endl;
    }
    return 0;
}





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

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll,int> plli;
typedef pair<double, int> pdbi;
typedef pair<int,pii> pipii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()

const ll mod = 1000000000 + 7;
const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const ll INF = 1<<30;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;

string a;
vector<vector<int>> pos(26);

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> a;
    int n = a.size();
    rep(i, n) {
        pos[a[i] - 'a'].pb(i);
    }
    int ans = n * (n - 1) / 2;
    rep(i, n) {
        int idx = lower_bound(all(pos[a[i] - 'a']), i) - pos[a[i] - 'a'].begin();
        //if (idx == pos[a[i] - 'a'].size()) continue;
        ans -= pos[a[i] - 'a'].size() - 1 - idx;
    }
    cout << ans + 1<< endl;
}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
int main(){
  int w,h,x,y,r;
  cin>>w>>h>>x>>y>>r;
  if(0<=x-r&&0<=y-r&&w>=x+r&&h>=y+r) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}


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

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

    int d;
    cin >> d;
    if(d == 25){
        cout << "Christmas" << endl;
    }else if(d == 24){
        cout << "Christmas Eve" << endl;
    }else if(d == 23){
        cout << "Christmas Eve Eve" << endl;
    }else{
        cout << "Christmas Eve Eve Eve" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <functional>
#include <stack>
#include <queue>
#include <string>
#include <unordered_map>
#include <bitset>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;

const ll mod=1000000007ll;
const ll inf=1000000000000000ll;

const ll nmax=100000;
ll a[nmax];

unordered_map<string,ll> mp;

int main(){
    ll n,t;
    cin>>n>>t;
    for(ll i=0;i<n;i++) cin>>a[i];

    ll ct=0;
    ll mn=0;
    ll mina=a[0];
    for(ll i=0;i<n;i++){
        if((a[i]-mina)==mn){
            ct++;
        }

        if(a[i]-mina>mn){
            ct=1;
            mn=a[i]-mina;
        }

        if(a[i]<mina) mina=a[i];
    }
    cout<<ct<<endl;
    return 0;
}


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

int main()
{
	int n,A,B,f,ball;
	cin >> n;
	
	for(int i=0;i<n;i++){
		A=0;
		B=0;
		f=0;
		for(int j=0;j<10;j++){
			cin >> ball;
			if(ball<A && ball<B) f=1;
			else if(A<ball && ball<B) A=ball;
			else if(ball<A && B<ball) B=ball;
			else if(A<B) B=ball;
			else A=ball;
		}
		
		if(f==0) cout << "YES" << endl;
		else cout << "NO" << endl;
		
	}
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REPR(i,n) for (int i=(int)(n)-1;i>=0;--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
#define tpl(...) make_tuple(__VA_ARGS__)
const int INF = 0x3f3f3f3f;
const double EPS = 1e-8;
const double PI = acos(-1);
const int dy[] = {-1,0,1,0};
const int dx[] = {0,1,0,-1};
typedef long long ll;
typedef pair<int,int> pii;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename Ch,typename Tr,typename C,typename=decltype(begin(C()))>basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>&os,
const C& c){os<<'[';for(auto i=begin(c);i!=end(c);++i)os<<(i==begin(c)?"":" ")<<*i;return os<<']';}
template<class S,class T>ostream&operator<<(ostream &o,const pair<S,T>&t){return o<<'('<<t.first<<','<<t.second<<')';}
template<int N,class Tp>void output(ostream&,const Tp&){}
template<int N,class Tp,class,class ...Ts>void output(ostream &o,const Tp&t){if(N)o<<',';o<<get<N>(t);output<N+1,Tp,Ts...>(o,t);}
template<class ...Ts>ostream&operator<<(ostream&o,const tuple<Ts...>&t){o<<'(';output<0,tuple<Ts...>,Ts...>(o,t);return o<<')';}
template<class T>void output(T t,char z=10){if(t<0)t=-t,putchar(45);int c[20];
int k=0;while(t)c[k++]=t%10,t/=10;for(k||(c[k++]=0);k;)putchar(c[--k]^48);putchar(z);}
template<class T>void outputs(T t){output(t);}
template<class S,class ...T>void outputs(S a,T...t){output(a,32);outputs(t...);}
template<class T>void output(T *a,int n){REP(i,n)cout<<a[i]<<(i!=n-1?',':'\n');}
template<class T>void output(T *a,int n,int m){REP(i,n)output(a[i],m);}
template<class T>bool input(T &t){int n=1,c;for(t=0;!isdigit(c=getchar())&&~c&&c-45;);
if(!~c)return 0;for(c-45&&(n=0,t=c^48);isdigit(c=getchar());)t=10*t+c-48;t=n?-t:t;return 1;}
template<class S,class ...T>bool input(S&a,T&...t){input(a);return input(t...);}
template<class T>bool inputs(T *a, int n) { REP(i,n) if(!input(a[i])) return 0; return 1;}


int n;
char res[20];

void dfs(int index, int used) {
  if (index == n) {
    printf("%s\n", res);
    return;
  }
  REP(i,used+1) {
    res[index] = 'a'+i;
    dfs(index+1, max(used,i+1));
  }
}

int main() {
  while(cin>> n) {
    res[n] = 0;
    dfs(0, 0);
  }
}


Measured memory_bytes: 1536
from sys import stdin
readline=stdin.readline
h,n=map(int,readline().split())
AB=[list(map(int,readline().split())) for i in range(n)]

A_max=max(AB)[0]
DP=[0]+[float("inf")]*(h+A_max)
for i in range(h):
    if DP[i]==float("inf"):continue
    for a,b in AB:
        t=DP[i]+b
        if t<DP[i+a]:
            DP[i+a]=t
print(min(DP[h:]))

Measured memory_bytes: 42332