akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include<boost/variant.hpp>
using namespace std;
typedef long long ll;
typedef vector<boost::variant<bool, ll, int, string, double, char*, const char*>> any;
template<typename T> inline void pr(const vector<T> &xs){
	for(int i=0; i<xs.size()-1; i++) cout<<xs[i]<<" ";
	(xs.empty()?cout:(cout<<xs[xs.size()-1]))<<endl;
}
#ifdef DEBUG
#define debug(...) pr(any{__VA_ARGS__})
#define debugv(x) pr((x))
#else
#define debug(...)
#define debugv(x)
#endif

struct mint {
	typedef long long ll;
	ll x, m;
	mint(ll x=0, ll m=1e9+7): x(x%m), m(m) {}
	mint operator-() const { return mint(m-x, m); }
	mint operator+(const mint o) const { return mint(x+o.x, m); }
	mint operator-(const mint o) const { return mint(x-o.x+m, m); }
	mint operator*(const mint o) const { return mint(x*o.x, m); }
	mint& operator+=(const mint o) { x = (x+o.x)%m; return *this; }
	mint& operator-=(const mint o) { x = (x-o.x+m)%m; return *this; }
	mint& operator*=(const mint o) { x = x*o.x%m; return *this; }
	bool operator==(const mint o) const { return x==o.x; }
	bool operator!=(const mint o) const { return x!=o.x; }
	template<typename T> mint& operator=(const T o) { x = o%m; return *this; }
	template<typename T> mint operator+(const T o) const { return mint(x+o, m); }
	template<typename T> mint operator-(const T o) const { return mint(x-((ll)o)%m+m, m); }
	template<typename T> mint operator*(const T o) const { return mint(x*o, m); }
	template<typename T> mint& operator+=(const T o) { x = (x+(ll)o%m)%m; return *this; }
	template<typename T> mint& operator-=(const T o) { x = (x-((ll)o)%m+m)%m; return *this; }
	template<typename T> mint& operator*=(const T o) { x = x*((ll)o%m)%m; return *this; }
	template<typename T> bool operator==(const T o) const { return x==o%m; }
	template<typename T> bool operator!=(const T o) const { return x!=o%m; }

	mint pow(ll k) const {
		if(k==0) return mint(1, m);
		if(k%2) return pow(k-1)*x;
		mint z = pow(k/2);
		return z*z;
	}

	mint inv() const { return pow(m-2); }
};

int N;
void dfs(int u, int p, vector<int> &n_child, vector<vector<int>> &graph){
	int r = 1;
	for(int v: graph[u]){
		if(v==p) continue;
		dfs(v, u, n_child, graph);
		r += n_child[v];
	}
	n_child[u] = r;
}

mint dfs1(int u, int p, vector<int> &n_child, vector<vector<int>> &graph){
	mint r = mint(2).pow(N-1) - 1;
	int sum = 0;
	for(int v: graph[u]){
		if(v == p) continue;
		r -= (mint(2).pow(n_child[v]) - 1);
		sum += n_child[v];
	}
	if(N-sum-1 > 0){
		r -= (mint(2).pow(N-sum-1) - 1);
	}
	debug(u, r.x);
	for(int v: graph[u]){
		if(v == p) continue;
		r += dfs1(v, u, n_child, graph);
	}
	return r;
}

int main(){
	cin >> N;
	vector<vector<int>> graph(N);
	for(int i=0; i<N-1; i++){
		int a, b;
		cin >> a >> b;
		a--; b--;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	vector<int> n_child(N);
	dfs(0, -1, n_child, graph);

	debugv(n_child);

	cout << (dfs1(0, -1, n_child, graph) * mint(2).pow(N).inv()).x << endl;;

	return 0;
}


Measured memory_bytes: 29824
S = input()
T = input()
s = len(S)
t = len(T)

def hantei(a):
    for i in range(t):
        if S[a + i] != "?" and S[a + i] != T[i]:
            return(False)
    return(True)

def solve():
    p = s - t
    while p >= 0:
        if hantei(p):
            ans = ""
            for i in range(s):
                if i >= p and i < p + t:
                    ans += T[i - p]
                else:
                    if S[i] == "?":
                        ans += "a"
                    else:
                        ans += S[i]
            return(ans)
        else:
            p -= 1
    return("UNRESTORABLE")
print(solve())

Measured memory_bytes: 3064
#include <stdio.h>

int main (void)
{
 int n,m;
  int a[m];
int  count = 0,i,s;

scanf("%d %d",&n,&m);

for(i = 0; i<m;i++)
{
scanf("%d",&a[i]);
count += a[i];
}

s = n - count;

if(s>=0)
printf("%d",s);
else
printf("-1");

return 0;
}


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

int n;

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		if(n%i!=0) continue;
		int d1=i,d2=n/i;
		if(max(d1,d2)<10) return 0 * printf("Yes");
	}
	printf("No");
}

Measured memory_bytes: 3688
#include <stdio.h>
#include <algorithm>

using namespace std;

int main()
{
	int n, a, mini=1000, maxi=0;
	
	scanf("%d", &n);
	while(n--){
		scanf("%d", &a);
		mini = min(mini, a);
		maxi = max(maxi, a);
	}
	
	printf("%d", maxi - mini);
	
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false
#define MOD 1000000007
 
typedef long long ll;
typedef pair<int, int> ii;

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int main() {
	
	ll h, w;
	cin >> h >> w;
	vector<string> s(h);
	
	rep(i, h) cin >> s[i];
	
	vector<vector<bool>> used(h, vector<bool>(w, false));
	
	ll ans = 0;
	
	rep(i, h){
		rep(j, w){
			ll white, black;
			white = black = 0;
			
			queue<ii> qu;
			qu.push(make_pair(j, i));
			
			while(!qu.empty()){
				auto tmp = qu.front(); qu.pop();
				
				if(used[tmp.second][tmp.first]) continue;
				used[tmp.second][tmp.first] = true;
				
				if(s[tmp.second][tmp.first] == '.') white++;
				else black++;
				
				rep(k, 4){
					int nx = tmp.first + dx[k];
					int ny = tmp.second + dy[k];
					if(0 <= nx && nx < w && 0 <= ny && ny < h){
						if(s[tmp.second][tmp.first] != s[ny][nx] && !used[ny][nx]){
							qu.push(make_pair(nx, ny));
						}
					}
				}
			}
			
			ans += (white * black);
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 512
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int main(void)
{
	int n,p[100],i,j,cnt,x;
	cnt=0;
	cin>>n;
	for(i=0;i<n;i++){
		cin>>p[i];
	}
	for(i=1;i<=n;i++){
		cnt=0;
		for(j=0;j<n;j++){
			if(p[j]>=i){
				cnt=cnt+1;
			}
		}
		if(cnt>=i) x=i;
	}
	
	cout<<x<<endl;
	
	return 0;
}



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

int firstDigit(int num){
    while(num >= 10){
        num /= 10;
    }
    return num;
}

int lastDigit(int num){
    return num % 10;
}

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

    int n;
    cin >> n;

    map<pair<int, int>, long long> mp;
    vector<pair<int, int>> A(n + 1);

    for(int i = 1; i <= n; i++){
        int fd = firstDigit(i);
        int ld = lastDigit(i);
        A[i] = {fd, ld};
        mp[{fd, ld}]++;
    }

    long long ans = 0;
    for(int i = 1; i <= n; i++){
        ans += mp[{A[i].second, A[i].first}];
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1792
n = int(input())
a = list(map(int, input().split()))

flag = False
ans = 1000
for i in range(n - 1):
    if a[i] < a[i + 1]:
        flag = True
        break

if flag:
    x = 0
    for i in range(n):
        if x == 0:
            x = ans // a[i]
            ans = ans % a[i]
            #print(ans, x, a[i])

        if i == n - 1 or a[i] > a[i + 1]:
            ans += x * a[i]
            x = 0
print(ans)

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

int main(){
    int N,M;
    cin >> N >> M;
    map<int,bool> ma;
    int ac = 0;
    int wa = 0;
    vector<int> wcnt(N);
    for(int i = 0;i < M;i++){
        int p;
        string s;
        cin >> p >> s;
        if(s == "AC"){
            if(!ma.count(p) || ma[p] == false){
                ac++;
                wa += wcnt[p-1];
                ma[p] = true;
            }else if(ma[p] == true);
        }else if(s == "WA"){
            if(!ma.count(p)){
                wcnt[p-1]++;
                ma[p] = false;
            }else if(ma[p] == false){
              wcnt[p-1]++;
            }else if(ma[p] == true);
        }
    }
  
    cout << ac << " " << wa << endl;
}

Measured memory_bytes: 5376
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<string>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>
#define PI acos(-1)
#define pb push_back
#define all(x) x.begin(),x.end()
#define INF 0x3f3f3f3f
#define dd(x) cout<<#x<<" = "<<x<<","
#define de(x) cout<<#x<<" = "<<x<<"\n"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=3e3+5;
const int mod=998244353;
int a[N],dp[N][N];
int main()
{
	int n,s;
	scanf("%d%d",&n,&s);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=s;j++){
			dp[i][j]=dp[i-1][j]*2;
			if(dp[i][j]>=mod)
			dp[i][j]-=mod;
		}
		for(int j=a[i];j<=s;j++){
			dp[i][j]+=dp[i-1][j-a[i]];
			if(dp[i][j]>=mod)
			dp[i][j]-=mod;
		}
	}
	printf("%d",dp[n][s]);
}


Measured memory_bytes: 39048
#include <iostream>
#include <string>

int main()
{
	std::string S = "";
	std::string T = "";

	std::cin >> S >> T;

	int answer = 0;
	for (int i = 0; i < 3; ++i)
	{
		if (S.at(i) == T.at(i))
		{
			answer++;
		}
	}

	std::cout << answer << "\n";

	return 0;
}

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

class Node {
    public:
        vector<int> children;
        vector<int> edge_value;
        int value;
        int parent;
};

class Tree {
    public:
        int root;
        int node_num;
        vector<Node> node;
        
        Tree(vector<vector<int>> hen, int r) {
            root = r;
            node_num = hen.size();
            node = vector<Node>(hen.size());
            
            queue<int> v;
            v.push(root);
            node[root].parent = -1;
            int edge_num = 0;
            while(!v.empty()) {
                int tyoten = v.front();
                node[tyoten].value = tyoten;
                v.pop();
                for (int i = 0; i < hen[tyoten].size(); i++) {
                    int child = hen[tyoten][i];
                    if (child != node[tyoten].parent) {
                        node[tyoten].children.push_back(child);
                        node[tyoten].edge_value.push_back(edge_num);
                        edge_num++;
                        node[child].parent = tyoten;
                        v.push(child);
                    }
                }
            }
        }
};

long long mod_nPr(long long n, long long r, long long mod) {
    if (r <= 0)
        return 1;
    else if (n <= 0)
        return 0;
    else {
        long long result = 1;
        for (int i = n; i > n-r; i--)
            result = (result * i) % mod;
        return result;
    }
}

int main(void){
    ll MOD = 1000000007;
    ll n, k;
    cin >> n >> k;
    vector<vector<int>> hen(n);
    rep(i, n-1) {
        int a, b;
        cin >> a >> b;
        hen[a-1].push_back(b-1);
        hen[b-1].push_back(a-1);
    }
    
    Tree tree(hen, 0);
    queue<int> que;
    que.push(0);
    ll ans = k;
    while(!que.empty()) {
        int local_tree_node = que.front();
        que.pop();
        if (tree.node[local_tree_node].parent != -1)
            ans = ans * mod_nPr(k-2, tree.node[local_tree_node].children.size(), MOD) % MOD;
        else
            ans = ans * mod_nPr(k-1, tree.node[local_tree_node].children.size(), MOD) % MOD;
        
        for (int i = 0; i < tree.node[local_tree_node].children.size(); i++)
            que.push(tree.node[local_tree_node].children[i]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 22912
use std::io;
use std::collections::VecDeque;


fn main() {
    let n = read_one::<usize>();
    let mut edge = vec![Vec::new(); n];
    for _ in 1..n {
        let (a, b, c) = {
            let i = read::<usize>();
            (i[0] - 1, i[1] - 1, i[2])
        };
        edge[a].push((b, c));
        edge[b].push((a, c));
    }

    let (q, k) = {
        let i = read::<usize>();
        (i[0], i[1] - 1)
    };

    let mut dist = vec![0; n];
    let mut que = VecDeque::new();
    que.push_back(k);
    while let Some(v) = que.pop_front() {
        for &(u, w) in edge[v].iter() {
            if dist[u] != 0 { continue; }
            dist[u] = dist[v] + w;
            que.push_back(u);
        }
    }

    for _ in 0..q {
        let (x, y) = {
            let i = read::<usize>();
            (i[0] - 1, i[1] - 1)
        };
        println!("{}", dist[x] + dist[y]);
    }
}


#[allow(dead_code)]
fn read<T>() -> Vec<T>
where T:
std::str::FromStr,
T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.split_whitespace()
        .map(|s| s.trim().parse().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_one<T>() -> T
where T:
std::str::FromStr,
T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().unwrap()
}

Measured memory_bytes: 19708
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <random>
#include <chrono>
#include <queue>
#include <math.h>
#include <string>
#include <sstream>

using namespace std;

int main(){
    long h,n;
    cin >> h >>n;
    vector<pair<long,long>> magic;
    long maxdm=0;
    for (long i=0;i<n;i++){
        long a,b;
        cin >> a >> b;
        maxdm=max(maxdm,a);
        magic.push_back(make_pair(a,b));
    }
    long d[h+maxdm+10];
    for(long i=1;i<h+maxdm+2;i++){
        d[i]=1e+9;
    }
    d[0]=0;
     for(long i=1;i<h+maxdm;i++){
        //魔法選択パート
        for(long j=0;j<n;j++){
            if(i-magic[j].first<0) continue;
            else{
                d[i]=min(d[i],d[i-magic[j].first]+magic[j].second);
            }
        }
    }
    long ans=1e+9;
    for(long i=h;i<h+maxdm;i++){
        ans=min(ans,d[i]);
    }
    cout << ans << endl;
}



Measured memory_bytes: 384
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

int readint() {
    return readln.chomp.to!int;
}

int[] readints() {
    return readln.split.map!(to!int).array;
}

Vec2 intersectionPoint(Vec2 a, Vec2 b, Vec2 c, Vec2 d) {
    auto d1 = abs((d - c).cross(a - c));
    auto d2 = abs((d - c).cross(b - c));
    auto t = d1 / (d1 + d2);
    return a + (b - a) * t;
}

void main() {
    int q = readint();
    for (int i = 0; i < q; i++) {
        auto xs = readints();
        auto a = Vec2(xs[0], xs[1]);
        auto b = Vec2(xs[2], xs[3]);
        auto c = Vec2(xs[4], xs[5]);
        auto d = Vec2(xs[6], xs[7]);

        auto p = intersectionPoint(a, b, c, d);
        writefln("%.8f %.8f", p.x, p.y);
    }
}

struct Vec2 {
    immutable double x;
    immutable double y;

    this(double x, double y) {
        this.x = x;
        this.y = y;
    }

    Vec2 opAdd(Vec2 other) {
        return Vec2(this.x + other.x, this.y + other.y);
    }

    Vec2 opSub(Vec2 other) {
        return Vec2(this.x - other.x, this.y - other.y);
    }

    Vec2 opMul(double d) {
        return Vec2(this.x * d, this.y * d);
    }

    double dot(Vec2 other) {
        return this.x * other.x + this.y * other.y;
    }

    double cross(Vec2 other) {
        return this.x * other.y - other.x * this.y;
    }

    double mag() {
        return sqrt(magSq());
    }

    double magSq() {
        return this.x * this.x + this.y * this.y;
    }

    Vec2 normalize() {
        auto m = mag();
        if (m != 0 && m != 1)
            return Vec2(this.x / m, this.y / m);
        return this;
    }

    static double distance(Vec2 a, Vec2 b) {
        return (a - b).mag();
    }
}

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

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using WGraph = vector<vector<pair<int, ll>>>;

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

constexpr int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
constexpr int INF = 1e9;
// constexpr int MOD = 1e9 + 7;
constexpr long long LINF = 1e18;
constexpr double EPS = 1e-10;
constexpr double PI = M_PI;

constexpr int MOD = 998244353;

void solve() {
    int n, s;
    cin >> n >> s;
    vector<int> a(n);
    for (int i=0; i<n; ++i) {
        cin >> a.at(i);
    }

    vector<vector<ll>> dp(n+1, vector<ll>(s+1));
    dp.at(0).at(0) = 1;
    for (int i=1; i<n+1; ++i) {
        int cur = a.at(i-1);
        for (int j=0; j<s+1; ++j) {
            dp.at(i).at(j) = dp.at(i-1).at(j) * 2;
            if (j >= cur) dp.at(i).at(j) += dp.at(i-1).at(j-cur);
            dp.at(i).at(j) %= MOD;
        }
    }

    cout << dp.at(n).at(s) << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    solve();

    return 0;
}


Measured memory_bytes: 73672
#include <iostream>
#include <iomanip>
#include<vector>
#include <algorithm>
#include <queue>
#include<string>
#include <map>
#include <cmath>
#include <deque>
#include <list>
#include <stack>
#include <queue>
#include <utility>
#include <set>
#include <bitset>
typedef long long ll;
typedef long double ld;

#define REP(i,s,n)for(ll i=s;i<(n);++i)
#define rep(i,n) REP(i,0,n)
using namespace std;


int main() {
	ll N;
	cin >> N;
	vector<ll>A(N);
	rep(i,N) {
		A[i] = i;
	}
	for (int i = 0; i < (1 << N);++i) {
		vector<ll>B;
		for (int j = 0; j < N;++j) {
			if (i&(1<<j)) {
				B.push_back(A[j]);
			}
		}
		cout << i << ":";
		for (int j = 0; j < B.size();++j) {
			cout << " " << B[j];
		}
		cout << endl;
	}
	return 0;
}


Measured memory_bytes: 3164
#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <queue>
#include <map>
#include <algorithm>
#include <functional>
#include <string>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

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

using ll = long long int;
using pll = pair<ll, ll>;

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

    const int a = (s[0] - '0') * 10 + (s[1] - '0');
    const int b = (s[2] - '0') * 10 + (s[3] - '0');

    if (a == 0 && b == 0) { cout << "NA" << endl; }
    else if (a == 0 && b <= 12) { cout << "YYMM" << endl; }
    else if (b == 0 && a <= 12) { cout << "MMYY" << endl; }
    else if (b == 0 || a == 0) { cout << "NA" << endl; }
    else if (a <= 12 && b <= 12) { cout << "AMBIGUOUS" << endl; }
    else if (a <= 12 && b >  12) { cout << "MMYY" << endl; }
    else if (a >  12 && b <= 12) { cout << "YYMM" << endl; }
    else { cout << "NA" << endl; }

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
#include<cmath>
#include<queue>	
#include<functional>
#include<climits>
#include<tuple>
#include<utility>
#include<cassert>

using namespace std;

//define
#define ALL(a) a.begin(),a.end()
#define REP(i,n) for(int i=0;i<n;i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define debug(x) if(1)cout<<#x<<":"<<x<<endl;
#define DEBUG(x) if(1)cout<<#x<<":"<<x<<endl;
#define ll long long
#define pb push_back
#define PB push_back
#define lb lower_bound
#define LB lower_bound
#define ub upper_bound
#define UB upper_bound


//constant
const int MOD = 1000000007;
const int INF = INT_MAX / 2-1;
const double EPS = 1e-9;
const int dx4[4] = { 1,0,-1,0 };
const int dy4[4] = { 0,1,0,-1 };

//typedef
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;


int main() {
	int n,a;
	cin >> n>>a;
	vi x(n);
	REP(i, n)
		cin >> x[i];

	vector<vector<vector<ll>>> dp(n+1, vector<vector<ll>>(n+1, vector<ll>(n*a+1, 0)));
	for (int i = 0; i < n+1; i++)
		dp[0][i][0] = 1;
	for(int i=1;i<n+1;i++) {
		for(int j=1;j<n+1;j++) {
			REP(k, n*a + 1) {
				if (k - x[j - 1] >= 0)
					dp[i][j][k] = dp[i][j - 1][k] + dp[i-1][j-1][k - x[j - 1]];
				else
					dp[i][j][k] = dp[i][j - 1][k];

			}

		}

	}
	ll res = 0;
	REP(i, n)
		res += dp[i+1][n][a*(i+1)];
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 52224
n, k = map(int, input().split())
p = list(map(int, input().split()))

kdice = [(1+p[i])/2 for i in range(n)]
maxexp = sum(kdice[:k])
ans = maxexp

for i in range(k, n):
    maxexp += kdice[i] - kdice[i-k]
    ans = max(maxexp, ans)

print(ans)


Measured memory_bytes: 24816
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
    ll n,b,l,e,k,t=0;
    cin>>n;

    for(ll i = 1;i <= n;i++)
    {
        if(i%3!=0 && i%5!=0)
        {
            t += i;
        }
    }
    cout<<t<<endl;

}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
int main() {
  int max = 2000000;
  int min = -2000000;
  int K, X;
  int output;
  bool flag = true;
  
  cin >> K >> X;
  
  if(K >= 4000001){
  	for(int i=0; i< 4000001; i++){
    	cout << i - 2000000;
    }
  }else if(X-K < -2000000){
    output = -2000000;
  	while(flag){
    	cout << output << " ";
      	output++ ;
      	if(output == X+K){
          flag = false;
        }
    }
  }else if(X+K > 2000000){
    output = X-K;
    while(flag){
        cout << output << " ";
        output++;
        if(output == 2000000)flag = false;
        }
    }else{
    	output = X-K+1;
      	while(flag){
        	cout << output << " ";
          	output++;
          	if(output == K+X)flag = false;
        }
    }
  }

Measured memory_bytes: 256
#include <iostream>
#include <cstring>

using namespace std;

const int INF=100000;
int cost[101][101];
int tim[101][101];

int main(void){
	int n,m,a,b,c;
	while(1){
		for(a=0;a<=100;a++){
			for(b=0;b<=100;b++){
				cost[a][b]=INF;
				tim[a][b]=INF;
				if(a==b)cost[a][b]=0,tim[a][b]=0;
			}
		}
		cin >> n >> m;
		if(n==0 && m==0)break;
		for(a=0;a<n;a++){
			int f,t,co,ti;
			scanf("%d%d%d%d",&f,&t,&co,&ti);
			if(cost[f][t]>co)cost[f][t]=co,cost[t][f]=co;
			if(tim[f][t]>ti)tim[f][t]=ti,tim[t][f]=ti;
		}
		for(c=1;c<=m;c++){
			for(b=1;b<=m;b++){
				for(a=1;a<=m;a++){
					cost[a][b]=min(cost[a][b],cost[a][c]+cost[c][b]);
					tim[a][b]=min(tim[a][b],tim[a][c]+tim[c][b]);
				}
			}
		}
		cin >> n;
		for(a=0;a<n;a++){
			int d,f,t;
			scanf("%d%d%d",&f,&t,&d);
			if(d==0)printf("%d\n",cost[f][t]);
			if(d==1)printf("%d\n",tim[f][t]);
		}
	}
    return 0;
}

Measured memory_bytes: 996
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

D, T, S = rl()

if D <= S*T:
	print('Yes')
else:
	print('No')

Measured memory_bytes: 67952
package main

import (
	"fmt"
)

func main(){
	var n int
	var x, num, sum float64
	m := map[int]float64{}

	fmt.Scan(&n, &x)

	for i:=0; i<n; i++ {
		fmt.Scan(&num)
		m[i] = num
		sum++
		x -= num
	}

	min := m[0]
	for _,v := range m {
		if min > v {
			min = v
		}
	}

	for {
		if (x - min) >= 0 {
			sum++
			x -= min
		}else{
			break
		}
	}

	fmt.Print(sum)
}

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

using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int

int main(){
  int N,M;
  cin>>N>>M;
  int X[M];
  rep(i,M)
    cin>>X[i];
  sort(X,X+M);
  int L[M-1];
  for(int i=0;i<M-1;i++)
    L[i]=X[i+1]-X[i];
  sort(L,L+M-1);
  int count=0;
  //  rep(i,M-1)
  //cout<<L[i]<<endl;
  rep(i,M-N)
    count+=L[i];
  cout<<count<<endl;

  return 0;
}


Measured memory_bytes: 1024
<?php
list($a,$b,$c)=explode(" ",trim(fgets(STDIN)));
list($d,$e,$f)=explode(" ",trim(fgets(STDIN)));
list($g,$h,$i)=explode(" ",trim(fgets(STDIN)));
$n=trim(fgets(STDIN));
$j=0;
while($j<$n){
  $m=trim(fgets(STDIN));
  switch($m){
    case $a:
      $a=0;
      break;
    case $b:
      $b=0;
      break;
    case $c:
      $c=0;
      break;
    case $d:
      $d=0;
      break;
    case $e:
      $e=0;
      break;
    case $f:
      $f=0;
      break;
    case $g:
      $g=0;
      break;
    case $h:
      $h=0;
      break;
    case $i:
      $i=0;
      break;
  }
  ++$j;
}
$s=$a+$b+$c;
$t=$d+$e+$f;
$u=$g+$h+$i;
$v=$a+$d+$g;
$w=$b+$e+$h;
$x=$c+$f+$i;
$y=$a+$e+$i;
$z=$c+$e+$g;
if($s==0 or $t==0 or $u==0 or $v==0 or $w==0 or $x==0 or $y==0 or $z==0){
  echo "Yes";
}else{
  echo "No";
}

Measured memory_bytes: 4728
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <climits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#define int long long
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL)
using namespace std;
int mod = 1e9+7;

int32_t main(){

	int s,w;
	cin>>s>>w;
	if(w>=s)
		cout<<"unsafe\n";
	else
		cout<<"safe\n";
	return 0;
}

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

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

    int N, K;
    cin >> N >> K;

    vector<ll> h(N);
    rep(i,N) cin >> h[i];

    vector<ll> cost(N, LLONG_MAX);
    cost[0] = 0;
    for (int i = 0; i < N - 1; i++) {
        for (int j = i + 1; j - i <= K; j++) {
            cost[j] = min(cost[j], cost[i] + abs(h[j] - h[i]));
        }
    }

    cout << cost[N-1] << endl;

    return 0;
}


Measured memory_bytes: 1792
# coding: utf-8

# In[11]:


N,K,Q=map(int,input().split())


# In[13]:


ans = [0] * N
for i in range(Q):
    ans[int(input())-1]+=1


# In[14]:


for i in range(N):
    score = K-Q + ans[i]
    if score > 0:
        print("Yes")
    else:
        print("No")


Measured memory_bytes: 4680
MOD = 10 ** 9 + 7
MAX = 2 * 10 ** 5

def comb(n, k)
  npk = 1
  k.times do |i|
    npk = (npk * (n - i)) % MOD
  end
 
  k_x = 1
  k.downto(1) do |i|
    k_x = (k_x * i) % MOD
  end
  (npk * mod_inv(k_x, MOD)) % MOD
end

def mod_inv(a, m)
  b = m
  u = 1
  v = 0 
  while b != 0
    t = a / b
    a -= t * b;
    tmp = a
    a = b
    b = tmp
 
    u -= t * v
    tmp = u
    u = v
    v = tmp
  end
 
  u = u % m
  if u < 0
    u += m
  end
  return u
end

def modpow(a, n)
  res = 1
  while n > 0
    res = res * a % MOD if n & 1 == 1
    a = a * a % MOD
    n >>= 1
  end
  res
end

  
N, A, B = gets.split.map(&:to_i)


ans = (modpow(2, N) - 1) % MOD
[A, B].each do |kk|
  ans -= comb(N, kk)
end

p ans % MOD


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

int main(){
  int N;
  int x[110] = {}, y[110] = {}, h[110] = {};

  scanf("%d", &N);
  for(int i = 0; i < N; i++){
    scanf("%d %d %d", &x[i], &y[i], &h[i]);
  }

  for(int Cx = 0; Cx <= 100; Cx++){
    for(int Cy = 0; Cy <= 100; Cy++){
      int H;
      for(int i = 0; i < N; i++){
        if(h[i] != 0){
          H = h[i] + abs(x[i] - Cx) + abs(y[i] - Cy);
          break;
        }
      }
      int flag = 1;
      for(int i = 0; i < N; i++){
        if(h[i] != 0 && h[i] + abs(x[i] - Cx) + abs(y[i] - Cy) != H){
          flag = 0;
          break;
        }
        if(h[i] == 0 && H - abs(x[i] - Cx) - abs(y[i] - Cy) > 0){
          flag = 0;
          break;
        }
      }
      if(flag == 1){
        printf("%d %d %d\n", Cx, Cy, H);
      }

    }
  }
  return 0;
}


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

int main() {
    int n, m;
    cin >> n >> m;
    int a[60], b[60];
    for(int i = 0; i < m; ++i) cin >> a[i] >> b[i];
    
    int num[60] = {0};
    for(int i = 0; i < m; ++i) {
        num[a[i]]++;
        num[b[i]]++;
    }
    
    for(int i = 1; i <= n; ++i) cout << num[i] << endl;
}

Measured memory_bytes: 256
N, M = map(int, input().split(" "))
S = input()
T = input()

def gcd(n, m):
	if m < n:
		n, m = m, n
	while n:
		n, m = m%n, n
	return m

gcd_NM = gcd(N, M)
if S[::N//gcd_NM] == T[::M//gcd_NM]:
	print(N*M//gcd_NM)
else:
	print(-1)

# large, small = sorted(N, M)
# if large%small == 0:
# 	if S[0] == T[0]:
# 		print(N*M)
# 	else:
# 		print(-1)
# else:
# 	large//small




gcd_NM = gcd(N, M)
M//gcd_NM, N//gcd_NM





################################
#-------------------------------
################################

# # no submit

# def gcd(n, m):
# 	if m < n:
# 		n, m = m, n
# 	while n:
# 		n, m = m%n, n
# 	return m
# def lcm(n, m):
# 	return n*m // gcd(n, m)

# n, m = map(int, input().split(" "))
# s, t = [input() for _ in range(2)]

# gcd_nm = gcd(n, m)
# print(lcm(n, m) if s[::n//gcd_nm] == t[::m//gcd_nm] else -1)

################################

# 6
# 2 3
# a__e__
# a_c_p_
# 最初の文字は同じ

# 6 3
# abcdef
# a_b_c_

# def gcd(n, m):
# 	if m < n:
# 		n, m = m, n
# 	while n:
# 		n, m = m%n, n
# 	return m
# def lcm(n, m):
# 	return n*m // gcd(n, m)

# n, m = map(int, input().split(" "))
# s, t = [input() for _ in range(2)]

# lcm_nm = lcm(n, m)
# s_ = "".join([s_i+"_"*(lcm_nm//n - 1) for s_i in s])
# t_ = "".join([t_i+"_"*(lcm_nm//m - 1) for t_i in t])
# for i in range(lcm_nm):
# 	if not (s_[i] in ["_", t_[i]] or t_[i] == "_"):
# 		print(-1)
# 		exit()
# print(lcm_nm)


Measured memory_bytes: 3316
n,a,b = gets.split.map(&:to_i)
if a+b > n+1 || (n+a-1)/a > b
    puts -1
    exit
end

while n-a > b-1
    for i in n-a+1..n
        print i," "
    end
    n -= a
    b -= 1
end
for i in b..n
    print i," "
end
(b-1).downto(1) do |i|
    print i," "
end

Measured memory_bytes: 3708
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;


bool used[101010];
int main(){
    int n,k;
    cin>>n>>k;
    pair<ll,int> a[n];
    rep(i,n)cin>>a[i].second>>a[i].first;
    priority_queue<ll,vector<ll>,greater<ll>> que;
    ll cnt=0;
    sort(a,a+n);
    reverse(a,a+n);
    ll sum=0;
    rep(i,k){
        if(!used[a[i].second]){
            ++cnt;
            used[a[i].second]=true;
        }
        else {
            que.push(a[i].first);
        }
        sum+=a[i].first;
    }
    ll ans=sum+cnt*cnt;
    for(int i=k;i<n;++i){
        if(cnt>=k)break;
        if(used[a[i].second])continue;
        ++cnt;
        used[a[i].second]=true;
        ll res=que.top();que.pop();
        sum-=res;
        sum+=a[i].first;
        ans=max(ans,sum+cnt*cnt);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 2556
import Data.List

atgc :: Char -> Bool
atgc 'A' = True
atgc 'C' = True
atgc 'G' = True
atgc 'T' = True
atgc othrewise = False

part [] = []
part xs = [a | a <- xs] : part (tail xs)

f xs = last $ sort $ map (length . takeWhile atgc) (part xs)

main :: IO ()
main = do
    s <- getLine
    putStrLn $ show $ f s


Measured memory_bytes: 380
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<cstring>
#include<climits>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<deque>
#include<tuple>
#include<list>
#include<unordered_map>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define lb lower_bound
#define pb push_back
#define mp make_pair
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define INF (1 << 30) - 1
#define LLINF (1LL << 61) - 1
// #define int ll
using namespace std;
const int MOD = 1000000007;
const int MAX = 510000;



int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,d,ans=0;
    cin>>n>>d;
    ans+=(n/(2*d+1));
    if(n%(2*d+1)!=0) ans++;
    cout<<ans<<endl;
    return 0;
}

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


signed main()
{
    string s;
    cin>>s;
    int c=0;
    int ans=0;
    for(int i=0;i<s.length();i++){
        if(s[i]=='R'){
            c++;
        }
        else{
            ans=max(ans,c);
            c=0;
        }
    }
    ans=max(ans,c);
    cout<<ans<<endl;
}


Measured memory_bytes: 3592
n,p = map(int,input().split())
a = list(map(int,input().split()))

num = 0
count = 0

for i in range(n):
    if a[i] % 2 == 0:
        count += 1

if count == n:
    if p == 0:
        print(2**n)
    elif p == 1:
        print(0)
else:
    print(2**(n-1))
    







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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using P = pair<int, int>;

void Main() {
    string s; cin >> s;
    if(s.size() == 3) reverse(all(s));
    cout << s << endl;
    return;
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}

Measured memory_bytes: 3680
#include<bits/stdc++.h> 
#define ll long long 
#define pb push_back 
#define vec vector<int> 
#define fo(i,n) for (ll i = 0; i < n; i++)
#define so(v) sort(v.begin(), v.end())
#define fi first
#define se second 
using namespace std;  
int main()
{
int t;
cin>>t;
if(t>=30)
{
    cout<<"Yes";
}
else
cout<<"No";

}

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

int main(){
int a[100000],b[100000],c;
c=0;
char op[100000];
for(int i=1;i<100000;i++){
cin>>a[i]>>op[i]>>b[i];
c++;
if(op[i]=='?'){
goto aa;
}
}
aa:;
for(int i=1;i<c;i++){
if(op[i]=='+'){
cout<<a[i]+b[i]<<endl;
}
if(op[i]=='-'){
cout<<a[i]-b[i]<<endl;
}
if(op[i]=='*'){
cout<<a[i]*b[i]<<endl;
}
if(op[i]=='/'){
cout<<a[i]/b[i]<<endl;
}
}
return 0;
}

Measured memory_bytes: 1176
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
struct edge{
    ll p;//点
    ll w;//辺の重み*-1
};
vector<vector<edge> > graph(100000);
vector<ll> res(100000);
ll v,e,r;//vは頂点,eは辺,rは始点
void dijkstra(){
  for(int i = 0;i < v;i++)res[i] = pow(10,18);
    res[r] = 0;
    priority_queue<pair<ll,ll> > que;//重み、頂点
    que.push(make_pair(0,r));
    while(!que.empty()){
        edge now;
        now.p = que.top().second;
        now.w = que.top().first * -1;
        que.pop();
        if(res[now.p] < now.w)continue;
        for(int i = 0;i < graph[now.p].size();i++){
            if(res[graph[now.p][i].p] > now.w + graph[now.p][i].w){
                res[graph[now.p][i].p] = now.w + graph[now.p][i].w;
                que.push(make_pair(res[graph[now.p][i].p] * -1,graph[now.p][i].p));
            }
        }
    }
}
int main(){
  cin >> v;
  e = v - 1;
  for(int i = 0;i < e;i++){
    ll a,b,c;
    cin >> a >> b >> c;
    a--,b--;
    edge memoa = {b,c};
    edge memob = {a,c};
    graph[a].push_back(memoa);
    graph[b].push_back(memob);//無向グラフのときはこれを追加
  }
  ll q;
  cin >> q >> r;
  r--;
  dijkstra();
  for(int i = 0;i < q;i++){
    ll from,to;
    cin >> from >> to;
    from--,to--;
    cout << res[from] + res[to] << endl;
  }
}

Measured memory_bytes: 11120
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <utility>
#include <iomanip>

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

using namespace std;

typedef pair<int, int> P;

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

int lis(const vector<int>& a){
    int n = a.size();
    vector<int> dp(n+1, INF);
    dp[1] = a[0];
    for(int i = 1; i < n; i++){
        int l = 0;
        int r = n;
        while(r - l > 1){
            int m = (r + l) / 2;
            if(dp[m] < a[i]){
                l = m;
            }else{
                r = m;
            }
        }
        dp[l+1] = a[i];
    }
    int ans;
    for(int i = 1; i <= n; i++){
        if(dp[i] != INF){
            ans = i;
        }
    }
    return ans;
}

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

    cout << lis(a) << endl;

    return 0;
}



Measured memory_bytes: 4416
#include <bits/stdc++.h>
using namespace std;
const int MaxN = 100000;

int n, Q;
char s[MaxN + 5];
int sum[MaxN + 5];

int main()
{
	while(scanf("%d %d", &n, &Q) != EOF)
	{
		scanf("%s", s + 1);
		for(int i = 1; i < n; i++) {
			if(s[i] == 'A' && s[i + 1] == 'C')
				sum[i] = 1;
		}
		for(int i = 1; i <= n; i++) sum[i] += sum[i - 1];
		for(int cas = 1; cas <= Q; cas++) {
			int l, r; scanf("%d %d", &l, &r);
			int ans = sum[r] - sum[l - 1];
			if(s[r] == 'A' && s[r + 1] == 'C') ans--;
			printf("%d\n", ans);
		}
	}
	return 0;
}

Measured memory_bytes: 1280
alphabets = "abcdefghijklmnopqrstuvwxyz"
#print(len(alphabets))
#a = len(alphabets)
#print(a)
x = ''
while True:
    try:
        x += input().lower()
    except EOFError:
        break

for i in range(len(alphabets)):
    print("{0} : {1}".format(alphabets[i], int(x.count(alphabets[i]))))

Measured memory_bytes: 7392
#include<iostream>
#include<string>
#include<vector>
#include <algorithm>
using namespace std;
int main() {
    int N,X;
    cin >> N >> X;
    vector<int> m(N);
    for(int i=0;i<N;i++){
        cin >> m.at(i) ;
    }
    //まず、それぞれ一個は必ず作るので
    
    int dec=0;
    for(int i=0;i<N;i++){
        dec = dec + m.at(i);
    }
    int x = X - dec;
    int total_number = N;
    int min_m = X;
    for(int i=0;i<N;i++){
        if(min_m > m.at(i)){
            min_m = m.at(i) ;
        }
    }
    cout << N +  x/min_m << endl;
    
    
}

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

int main() {
	string s;
	cin>>s;
	int n;
	n=s.length();
	    if(s[2]==s[3] && s[4]==s[5])
	    cout<<"Yes";
	    else
	    cout<<"No";
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
 
class Main {
	int n;
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		Main m = new Main(sc);
		m.solve();
		sc.close();
	}
	Main(Scanner sc){
		n = sc.nextInt();
	}
	void solve(){
		int min = Integer.MAX_VALUE;
		int sum;
		int i;
		for(int a=1;a<n;a++){
			sum = 0;
			i = a;
			while(i>0){
				sum += i%10;
				i /= 10;
			}
			i = n-a;
			while(i>0){
				sum += i%10;
				i /= 10;
			}
			min = Math.min(min, sum);
		}
		System.out.println(min);
	}
}

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

string s, t;
vector<char> ans;
int dp[3005][3005];
int sl, tl;

// dp[i][j] = length of lcs for s[0...i] and t[0...j]

int rec(int sp, int tp)
{
    if (sp == sl || tp == tl)
        return 0;

    if (dp[sp][tp] != -1)
        return dp[sp][tp];

    if (s[sp] == t[tp])
    {
        dp[sp][tp] = max(rec(sp + 1, tp), rec(sp, tp + 1));
        dp[sp][tp] = max(dp[sp][tp], rec(sp + 1, tp + 1) + 1);
    }
    else
    {
        dp[sp][tp] = max(rec(sp, tp + 1), rec(sp + 1, tp));
    }
    return dp[sp][tp];
}

void print(int sp, int tp)
{
    if (sp == sl || tp == tl)
        return;

    if (s[sp] == t[tp])
    {
        if (dp[sp + 1][tp + 1] + 1 >= dp[sp + 1][tp] && dp[sp + 1][tp + 1] + 1 >= dp[sp][tp + 1])
        {
            cout << s[sp];
            print(sp + 1, tp + 1);
        }
        else if (dp[sp + 1][tp] >= dp[sp + 1][tp + 1] + 1 && dp[sp + 1][tp] >= dp[sp][tp + 1])
            print(sp + 1, tp);
        else
            print(sp, tp + 1);
    }
    else
    {
        if (dp[sp + 1][tp] >= dp[sp][tp + 1])
            print(sp + 1, tp);
        else
            print(sp, tp + 1);
    }
    return;
}

int main()
{
    cin >> s >> t;
    sl = s.size(), tl = t.size();
    for (int i = 0; i < 3005; i++)
        for (int j = 0; j < 3005; j++)
            dp[i][j] = -1;
    ans.clear();

    rec(0, 0);
    print(0, 0);
    cout << endl;
    return 0;
}

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

using namespace std;

#define int long long
#define endl "\n"

const long long INF = (long long)1e18;
const long long MOD = 1'000'000'007; 

string yn(bool f){return f?"Yes":"No";}
string YN(bool f){return f?"YES":"NO";}



signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	int N;
	int sum = 0;
	
	cin>>N;
	
	for(int i = 1; i <= N; i++){
		if(i%2) sum++;
	}
	
	cout<<(double)sum/N<<endl;
	
	
	return 0;
}

Measured memory_bytes: 256
A = input()
B=1
try:
    for i in range(len(A)):
        if A[0] != A[1]:
            B += 1
            A = A[1:]
        elif len(A)>3 and A[0] == A[1] and A[1] == A[2]:
            B += 2
            A = A[3:]
        elif len(A)<=3 and A[0] == A[1] and A[1] == A[2]:
            B += 1
            A = A[3:]
        elif len(A)==3 and A[-1] != A[-2] and A[-3] == A[-2]:
            B += 1
            A = A[3:]
        else:
            B += 2
            A = A[3:]
except IndexError:
    print(B)

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

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

struct Node{
  int p, dist, cost;
  Node(int _p, int _dist, int _cost){
    p = _p;
    dist = _dist;
    cost = _cost;
  }
};

int N, M, L;
vector<Node> v[MAX];

int bfs(){
  int used[MAX][MAX];
  rep(i, MAX){
    rep(j, MAX){
      used[i][j] = (1<<29);
    }
  }
  queue<Node> q;
  q.push( Node(0, L, 0) );
  
  while(!q.empty()){
    Node t = q.front(); q.pop();
    
    if(t.cost >= used[t.p][t.dist]) continue;
    
    used[t.p][t.dist] = t.cost;
    
    rep(i, v[t.p].size()){
      Node next = v[t.p][i];
      if(t.dist >= next.dist){
	q.push( Node(next.p, t.dist - next.dist, t.cost) );
      }
      q.push( Node(next.p, t.dist, t.cost + next.cost) );
    }
  }
  
  int ans = (1<<29);
  rep(i, MAX){
    ans = min(ans, used[N-1][i]);
  }
  return ans;
}

int main(){
  while(cin >> N >> M >> L, N|M|L){
    rep(i, MAX) v[i].clear();
    int a, b, c, d;
    for(int i = 0 ; i < M ; i++){
      cin >> a >> b >> c >> d;
      a--, b--;
      v[a].push_back( Node(b, c, d) );
      v[b].push_back( Node(a, c, d) );
    }
    
    cout << bfs() << endl;
  }
  
  return 0;
}

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

void solve(){
    int a, b, c;
    cin >> a >> b >> c;
    cout << (a+b)*c/2;
}

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

    bool multitest = false;
   // multitest = true;
    if(multitest){
        int t; cin >> t;
        while(t--)
            solve();
    }
    else
        solve();
}






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

#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORR(i, m, n) for (int i = m; i >= n; i--)
#define ALL(x) (x).begin(), (x).end()

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1e15;
const ll MOD = 1e9 + 7;

int main() {
  ll a, b;
  cin >> a >> b;
  FOR(i, 1, 4) {
    if (i != a && i != b) cout << i << endl;
  }
  return 0;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
//using Graph = vector<vector<pair<ll,ll>>>;
const int mod =1e+9+7;

const int dy[4]={0,1,0,-1};
const int dx[4]={1,0,-1,0};
const ll INF=1e10;

int main(){
    ll h,w; cin>>h>>w;
    vector<vector<ll>>c(10,vector<ll>(10));
    rep(i,10){
        rep(j,10)cin>>c[i][j];
    }
    vector<vector<ll>>a(h,vector<ll>(w));
    rep(i,h){
        rep(j,w)cin>>a[i][j];
    }
    rep(k,10){
        rep(i,10){
            rep(j,10){
                if(c[i][j]>c[i][k]+c[k][j])c[i][j]=c[i][k]+c[k][j];
            }
        }
    }
    ll ans=0;
    rep(i,h){
        rep(j,w){
            if(a[i][j]>=0){
                ans+=c[a[i][j]][1];
            }
        }
    }
    cout<<ans<<endl;
}











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

#define ll long long
#define fw(p) for(int w=0;w<(p);w++)
#define fx(p) for(int x=0;x<(p);x++)
#define fy(p) for(int y=0;y<(p);y++)
#define fz(p) for(int z=0;z<(p);z++)
#define fyg(p,g) for(int y=(g);y<(p);y++)
#define fzg(p,g) for(int z=(g);z<(p);z++)
#define ce(d) cout<<d<<endl;
#define vecp(p) int aa;cin>>aa;(p).push_back(aa);
#define vecpl(p) long long aa;cin>>aa;(p).push_back(aa);
#define vecps(p) string aa;cin>>aa;(p).push_back(aa);
#define vecp2(p) cin>>aa;(p).push_back(aa);
#define vecpl2(p) long long a	b;cin>>ab;(p).push_back(ab);
#define vecps2(p) string ab;cin>>ab;(p).push_back(ab);
#define set0(k,n) for(int nn=0;nn<(n);nn++){ (k).push_back(0); }
#define sorts(c) sort((c).begin(),(c).end());
#define reverses(c) reverse((c).begin(),(c).end());
#define vec(b) vector<int> (b);
#define vecl(b) vector<long long> (b);
#define vecs(b) vector<string> (b);
#define vecsize(b,size) vector<int> (b)((size));
#define pb(b,a) (b).push_back((a));
#define doublece(a,b) cout<<(a)<<' '<<(b)<<endl;
#define pairs(s) vector<pair<int,int>> (s);
#define pairsl(s) vector<pair<ll,ll>> (s);
#define pairss(s) vector<pair<string,string>> (s);
#define pairsp(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairspl(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsps(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsREV(s) (s).push_back(make_pair(bb,aa));
#define pairslREV(s) (s).push_back(make_pair(bb,aa));
#define pairssREV(s) (s).push_back(make_pair(bb,aa));
#define MOD 1000000007

int main()
{
	double a, b, x;
	cin >> a >> b >> x;
	if (x<=a*a*b/2) {
		cout << fixed << setprecision(10) << 180 * atan(b / (x * 2.0 / (a * b))) / 3.1415926535 << endl;
	}
	else {
		double y = a * a * b - x;
		cout << fixed << setprecision(10) << 180 * atan((2.0*y)/(a*a*a)) / 3.1415926535 << endl;
	}

    return 0;
}



Measured memory_bytes: 256
//#include "pch.h" 
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <stdio.h>
#include <vector>
#include <time.h>
#include <iomanip>
#include <thread>
#include <atomic>
#include <mutex>
#include <future>
#define double long double
#define int long long
#define low lower_bound
#define upp upper_bound
#define mod (int)(1e9 + 7)
#define inf (int)1e16
#define rep(i,n) for(int i=0;i<n;i++)
#define all(vec) vec.begin(),vec.end()
#define vsort(vec) sort(all(vec))
#define vrever(vec) reverse(all(vec));
#define vunsort(vec) vsort(vec); vrever(vec);
#define bisea binary_search
using namespace std;
signed main() {
	int a, b, c, d, e, k;
	cin >> a >> b >> c >> d >> e >> k;
	if (k < b - a)  cout << ":(" << endl;
	else if(k<c-a)   cout << ":(" << endl;
	else if(k<d-a)  cout << ":(" << endl;
	else if(k<e-a) cout << ":(" << endl;
	else if (k < c - b) cout << ":(" << endl;
	else if (k < d - b) cout << ":(" << endl;
	else if(k<e-b) cout << ":(" << endl;
	else if(k<e-c) cout << ":(" << endl;
	else if(k<e-d) cout << ":(" << endl;
	else if(k<d-c) cout << ":(" << endl;
	else cout << "Yay!" << endl;
}

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

ll dp[100001];

ll solve(ll n){
  if(n==0)return 0;
  
  if(dp[n]!=-1)return dp[n];


  ll res=(1LL<<60);
  
  for(ll a=1;a<=n;a*=6)
    res=min(res, solve(n-a)+1);
  
  for(ll a=1;a<=n;a*=9)
    res=min(res, solve(n-a)+1);
  return dp[n]=res;
}
int main(){
  ll n;
  cin>>n;

  for(int i=0;i<=n;i++)
    dp[i]=-1;
  
  cout<< solve(n) <<endl;
  return 0;
}


Measured memory_bytes: 4096