akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(Int x = start; x > end; x--)

using namespace std;

#define MAX_V 10000

vector<Int> graph[MAX_V];
bool used_v[MAX_V],used_e[MAX_V][MAX_V];
Int ord[MAX_V],lowlink[MAX_V];
Int k=0;
vector<pair<Int, Int> > bridges;

bool compare (pair<Int, Int> a, pair<Int, Int> b) {
  if (a.first != b.first)  return a.first < b.first;
  if (a.second != b.second) return a.second < b.second;
  return false;
}

void dfs(Int v, Int parent) {
  used_v[v] = true;
  ord[v]=lowlink[v]=k++;
  
  for (Int u: graph[v]) {
    if(!used_v[u]) {
      used_e[v][u] = true;
      dfs(u, v);
      lowlink[v] = min(lowlink[v], lowlink[u]);
      if (ord[v] < lowlink[u]) {
        if (v < u) bridges.push_back(make_pair(v, u));
        else bridges.push_back(make_pair(u, v));
      }
    }
    else if(!used_e[u][v]) {
      lowlink[v] = min(lowlink[v], ord[u]);
    }
  }
}

Int main(void) {
  Int n, e, u, v;
  cin >> n >> e;
  loop(i,0,e) {
    cin >> u >> v;
    graph[u].push_back(v);
    graph[v].push_back(u);
  }
  dfs(0, -1);
  sort(bridges.begin(), bridges.end(), compare);
  for (auto b: bridges) cout << b.first << ' ' << b.second << endl;
}



Measured memory_bytes: 44668
import heapq

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

big_a = []  # 前半のデータをheapで収納 popで小さいものが出る
for i in range(n):
    heapq.heappush(big_a,a[i])

small_a = []  # 後半のデータをheapで収納
for i in range(n):
    heapq.heappush(small_a,-a[3*n-1-i])  # popで大きいものが出るようにマイナスをかけている

now_big = sum(big_a)
now_small = -sum(small_a)
big_data = [now_big]  # kを固定した時の値　最初はk=n
small_data = [now_small]  # kを固定した時の値　最初はk=2*n

for k in range(n):
    # 前半のデータの推移
    heapq.heappush(big_a, a[k+n])
    now_big += a[k+n] - heapq.heappop(big_a)  # [0,k+n]の上位n個の総和
    big_data.append(now_big)

    # 後半のデータの推移
    heapq.heappush(small_a, -a[2*n-1-k])
    now_small += a[2*n-1-k] + heapq.heappop(small_a)  # [2*n-1-k,3*n]の下位n個の総和
    small_data.append(now_small)



ans = -10**18
for k in range(n+1):
    ans = max(ans, big_data[k]-small_data[n-k])

print(ans)

Measured memory_bytes: 124560
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define FOR(i, a, n) for (int i = (a); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
using namespace std;

const int MAX_N = 3000000;
const int MOD = 1000000007;
long long inv[MAX_N + 1], fac[MAX_N + 1], finv[MAX_N + 1];

void init() {
    inv[1] = fac[0] = fac[1] = finv[0] = finv[1] = 1;
    for (int i = 2; i <= MAX_N; ++i) {
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        fac[i] = fac[i - 1] * i % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

long long nPk(int n, int k) {
    if (n < k || n < 0 || k < 0) return 0;
    return fac[n] * finv[n - k] % MOD;
}

long long nCk(int n, int k) {
    if (n < k || n < 0 || k < 0) return 0;
    return nPk(n, k) * finv[k] % MOD;
}

long long nHk(int n, int k) {
    if (n < 0 || k < 0) return 0;
    return nCk(n + k - 1, k);
}

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

    init();
    int r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;
    int ans = 0;
    FOR (i, r1, r2 + 1) {
        (ans += nCk(i + 1 + c2, i + 1)) %= MOD;
        (ans += MOD - nCk(i + c1, i + 1)) %= MOD;
    }
    cout << ans << endl;
}

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

int main()
{
    int N;
    cin >> N;
    int A;
    for(int i = 0; i < N; i++){
        cin >> A;
        if(A % 2 == 0){
            if(A % 3 == 0 || A % 5 == 0){

            }else{
                cout << "DENIED" << endl;
                return 0;
            }
        }
    }

    cout << "APPROVED" << endl;

    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
public class ABC135B {
    public static void Main() {
        int N, ans = 0;
        List<int> p = new List<int>();
        N = int.Parse(Console.ReadLine());
        string[] str = Console.ReadLine().Split(' ');
        for (int i = 0; i < N; i++) {
            p.Add(int.Parse(str[i]));
            if (p[i] != i + 1) ans++;
        }
        if (ans <= 2) Console.WriteLine("YES");
        else Console.WriteLine("NO");
    }
}


Measured memory_bytes: 11092
import sys
input = lambda: sys.stdin.readline().rstrip()

#MOD
P = 10**9 + 7
N = 200001 #使う最大値+1以上にする、値に注意3*10^5とかにしとくと安心
inv = [0] + [1] # 1/x
finv = [1] + [1] # 1/x!
fac = [1] + [1] # x!
for i in range(2, N):
  inv += [inv[P % i] * (P - int(P / i)) % P]
  fac += [(fac[i-1] * i) % P]
  finv += [(finv[i-1] * inv[i]) % P]

def comb(a, b): return (fac[a] * ((finv[b] * finv[a-b]) % P)) %P

#全方位木dp
#-------------------------------------------------------------------
#扱うクラス
class T:
    num = 1
    child = 0

    def __init__(self, a, b):
        self.num = a
        self.child = b

#零元
zero = T(1, 0)
#一個上に遷移した時の変化
def step(x):
    return T(x.num, x.child+1)
#マージ
def merge(x, y):
    return T((x.num*y.num*comb(x.child+y.child, x.child))%P, x.child+y.child)

G = [[] for _ in range(N)]
down_data = [zero for _ in range(N)]
dat = [zero for _ in range(N)]
rev_data = [zero for _ in range(N)]


node_list = []
def makeNodeList(root):
    #dfsでの探索順の作成
    stack = []
    stack.append([root, -1])
    while len(stack) != 0:
        now = stack.pop()
        node_list.append(now)
        for to in G[now[0]]:
            if to == now[1]: continue
            stack.append([to, now[0]])

def dfs(root):
    for i in range(len(node_list)):
        now = node_list[len(node_list)-1-i]
        for to in G[now[0]]:
            if to == now[1]: continue
            down_data[now[0]] = merge(down_data[now[0]], step(down_data[to]))

def dfs_rev(root):
    for now in node_list:
        #累積
        rev = rev_data[now[0]]
        left = []
        right = []
        cnt = 0
        for to in G[now[0]]:
            if to==now[1]: continue
            if len(left)==0: left.append(step(down_data[to]))
            else: left.append(merge(left[cnt-1], step(down_data[to])))
            cnt += 1
        cnt = 0
        for to in reversed(G[now[0]]):
            if to==now[1]: continue
            if len(right)==0: right.append(step(down_data[to]))
            else: right.append(merge(right[cnt-1], step(down_data[to])))
            cnt += 1
        dat[now[0]] = merge(rev, down_data[now[0]])
        cnt = 0
        for to in G[now[0]]:
            if to==now[1]: continue
            x = zero if cnt==0 else left[cnt-1]
            y = zero if cnt==len(right)-1 else right[len(right)-2-cnt]
            rev_data[to] = step(merge(rev, merge(x, y)))
            cnt += 1

def calc(data_num):
    root = -1
    for i in range(1, data_num+1):
        if len(G[i]) == 1:
            root = i
            break
    makeNodeList(root)
    dfs(root)
    dfs_rev(root)
#-------------------------------------------------------------------
def main():
    n = int(input())
    for i in range(n-1):
        a, b = map(int, input().split())
        G[a].append(b)
        G[b].append(a)
    calc(n)
    for i in range(1, n+1): print(dat[i].num)

if __name__ == "__main__": main()


Measured memory_bytes: 177416
def solve():
    n,w = map(int,input().split())
    w_list,v_list = [0]*n,[0]*n
    for i in range(n):
        w_list[i],v_list[i] = map(int,input().split())
    dp = [[0]*(w+5) for i in range(n+5)]
    for i in range(n):
        for j in range(w+1):
            if j >= w_list[i]:
                dp[i][j] = max(
                    dp[i-1][j],
                    dp[i-1][j-w_list[i]]+v_list[i]
                    )
            else:
                dp[i][j] = dp[i-1][j]
    print(dp[n-1][w])
    return 0

if __name__ == "__main__":
    solve()


Measured memory_bytes: 119536
N = gets.to_i
s1 = gets
s2 = gets

idx = 0
ans = 1
state = ""
m = 1000000007

# 最初のところは特別
if s1[0] == s2[0] then
	ans *= 3
	idx += 1
	state = "t"
else
	ans *= 6
	idx += 2
	state = "y"
end

while idx < N do
	if s1[idx] == s2[idx] then
		if state == "t" then
			# 縦→縦
			ans *= 2
		else
			ans *= 1
			# 横→縦
		end
		state = "t"
		idx += 1
		ans %= m
	else
		if state == "t" then
			# 縦→横
			ans *= 2
		else
			ans *= 3
		end
		state = "y"
		idx += 2
		ans %= m
	end
end

puts ans


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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	long long n;
	cin >> n;
	long long sum = 0;
	for (long long i = 1; i <= n; i++) {
		if (i % 3 == 0 && i % 5 == 0) {
			continue;
		} else if (i % 3 == 0) {
			continue;
		} else if (i % 5 == 0) {
			continue;
		} else {
			sum += i;
		}
	}
	cout << sum << '\n';
	
	return 0;
}


Measured memory_bytes: 3628
n,k = map(int,input().split())
def gcd(a,b):
  if b == 0:
    return a
  return gcd(b,a % b)
def lcm(a,b):
  return a * b // gcd(a,b)
if k % 2 != 0:
  elements = n // k
  print(elements**3)
else:
  a = n // k
  b = (n + (k//2)) // k
  print(a**3 + b ** 3)

Measured memory_bytes: 3060
import sys
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
#リストの最小公倍数
def lcm(a):    
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

N = ir()
A = lr()
A.sort()
if N == 1:
    print(1)
    exit()
MOD = 10 ** 9 + 7
l = []
first = A[0]
l = [x//gcd(x, first) for x in A[1:]]
x = lcm(l) #B[0]
answer = x%MOD

for i in range(1, N):
    answer += first * x // A[i]
    if i % 100 == 0:
        answer %= MOD

print(answer%MOD)


Measured memory_bytes: 4208
#!/home/ryo/.pyenv/versions/anaconda3-2019.03/envs/hoge/bin/python
import sys

lim=10**9+7
N,M = map(int,input().split())
A = set([int(input()) for _ in range(M)])
memo = [0] * (N+1)
memo[0]=1

if not 1 in A:
    memo[1]=1
for i in range(2, N+1):
    if not i in A:
        memo[i] = (memo[i - 1] + memo[i - 2]) % lim
print(memo[-1])

Measured memory_bytes: 13216
#include <stdio.h>

int main(){
  int i,j,n;
  int *tkyk;
  int total=0;
  
  scanf("%d",&n);
  tkyk=(int*)malloc(sizeof(int)*n);
  for(i=0;i<n;i++){
    scanf("%d",&tkyk[i]);
  }
  
  for(i=0;i<n-1;i++){
    for(j=i+1;j<n;j++){
      total+=tkyk[i]*tkyk[j];
    }
  }
  printf("%d",total);
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define int long long int
typedef long double ld;
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define endl '\n'
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define mxe max_element
#define mne min_element
#define vi vector<int>
#define vvi vector<vi>
#define pi pair<int,int>
#define size(a)  (int)(a.size())
#define fill(s,x,n) vector
 x(n); rep(i,0,n) cin>>x[i];
#define mod 1000000007
#define inf 1000000005
void solve(){
	int h,w;
	cin>>h>>w;
	vector<vector<char>> grid(h,vector<char> (w));
	vector<vector<int>> dp(h,vector<int> (w));
	dp[0][0]=1;
	rep(i,0,h){
		rep(j,0,w){
			cin>>grid[i][j];
		}
	}
	rep(i,0,h){
		rep(j,0,w){
			if(i==0 && j==0) continue;
			if(grid[i][j]=='#') continue;
			if(i-1>=0){
				if(grid[i-1][j]=='.'){
					(dp[i][j]+=dp[i-1][j])%=mod;
				}
			}
			if(j-1>=0){
				if(grid[i][j-1]=='.'){
					(dp[i][j]+=dp[i][j-1])%=mod;
				}
			}
		}
	}
	cout<<dp[h-1][w-1];
}
 

signed main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    /*
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout);  
    #endif
    */
	int test;
	//cin>>test;
	test=1;
	while(test--){
         solve();
         cout<<endl;
	}
	return 0;
}


Measured memory_bytes: 9088
N = int(input())
P = [list(map(int,input().split())) for i in range(N)]
flag = False
for tmp in P:
  t,x,y = tmp
  sum_ = x + y
  if (t % 2 == 0 and sum_ % 2 != 0) or (t % 2 != 0 and sum_ % 2 == 0) or t < sum_:
    flag = True
    break
if flag:
  print('No')
else:
  print('Yes')

Measured memory_bytes: 27380
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define ll long long
#define ull unsigned long long
#define ld long double
#define vl vector<long long>
#define vvl vector<vector<long long>>
#define rbf(a, x) for (auto& a : x)
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define drep(i, x) for (ll i = ((ll)(x)-1); i >= 0; i--)
#define pll pair<long long,long long>
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define vvc vector<vector<char>>
#define vc vector<char>
#define vvb vector<vector<bool>>
#define vb vector<bool>
#define Maxe(x) *max_element(all(x))
#define Mine(x) *min_element(all(x))
#define Size(x) ((ll)(x).size())
#define umap unordered_map
const long long INF = 1LL << 60;
const long double pi = 3.1415926535897932;
#define Fi first
#define Se second
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

    template<typename Num>
        constexpr Num mypow(Num a, long long b) {
            if(b==0)return 1;
            if (a==0)return 0;
            Num x = 1;
              while (b > 0) {
                if(b & 1)x*=a;
                a*=a;
                b >>= 1;
              }
              return x;
        }

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

//lis,modpow,uf,modncr,soinsubunkai,yakusurekkyo
//mint,dijkstra,gyakugen

    bool isPrime(ll x){
        if(x==1)return false;
        for(ll i=2;i*i<=x;i++){
            if(x%i==0)return false;
        }
        return true;
    }

    signed main(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        ll q;
        cin>>q;
        vl Ans(100005,0);
        rep(i,100004){
            if(i%2==1){
                if(isPrime(i)){
                    if(isPrime((i+1)/2)){
                        Ans[i]++;
                    }
                }
            }
            Ans[i+1]+=Ans[i];
        }
        rep(i,q){
            ll l,q;
            cin>>l>>q;
            cout<<Ans[q]-Ans[l-1]<<endl;
        }
    }

Measured memory_bytes: 3956
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

#define DEBUG_ //!!$BDs=P;~$K%3%a%s%H%"%&%H(B!!
#ifdef DEBUG_
#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
#define dump(x)  ;
#endif

#define equals(a,b) (fabs((a)-(b)) < EPS)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

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 T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

template <typename T>
void print_array(const T &ary, int size){
    REP(i,size){
        cout << ary[i] << " ";
    }
    cout << endl;
}

const int mod = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;
const double EPS = (1e-10);
const long double PI = 3.14159265358979323846264338327950288419716939937510582097494459230781640628620899;
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};

VVI g;

int dfs(int v, int p){
    if(SZ(g[v]) == 1 and p != -1) return 0;
    VI dep;
    for(int u : g[v]){
        if(u == p) continue;
        dep.eb(dfs(u,v));
    }
    sort(dep.begin(),dep.end());
    int res = 0;
    for(int x : dep){
        res = max(res, x) + 1;
    }
    return res;
}

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(12);
    int N; cin >> N;
    g.resize(N);
    REP(i,N-1){
        int a; cin >> a;
        a--;
        g[i+1].eb(a);
        g[a].eb(i+1);
    }

    int ans = dfs(0,-1);
    cout << ans << endl;

}

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

const int maxn=2e5+10;
const int maxm=6e5+10;

int n,deg[maxn],Ans[maxn];
int tote=1,FIR[maxn],TO[maxm],NEXT[maxm];
bool vis[maxm];

void addedge(int u,int v)
{
	TO[++tote]=v;
	NEXT[tote]=FIR[u];
	FIR[u]=tote;
}

void findpath(int u)
{
	for (int &p=FIR[u];p;p=NEXT[p])
		if (!vis[p]&&!vis[p^1])
		{
			int v=TO[p];
			vis[p]=vis[p^1]=1;
			Ans[u]+=v==u+n;
			Ans[v]-=u==v+n;
			findpath(v);
		}
}

int main()
{
#ifdef h10
	freopen("F.in","r",stdin);
	freopen("F.out","w",stdout);
#endif
	int i,f;
	scanf("%d",&n);
	for (i=1;i<=n;i++)
	{
		scanf("%d",&f);
		if (f==-1) f=0;
		deg[f]++; deg[i]++;
		addedge(f,i);
		addedge(i,f);
	}
	for (i=1;i<=n;i++)
	{
		scanf("%d",&f);
		if (f==-1) f=0;
		else f+=n;
		deg[f]++; deg[i+n]++;
		addedge(f,i+n);
		addedge(i+n,f);
	}

	for (i=1;i<=n;i++)
		if ((deg[i]&1)^(deg[n+i]&1))
		{
			puts("IMPOSSIBLE");
			return 0;
		}

	for (i=1;i<=n;i++)
		if (deg[i]&1) addedge(i,i+n),addedge(i+n,i);
	findpath(0);
	puts("POSSIBLE");
	for (i=1;i<=n;i++)
		printf("%d ",Ans[i]);
}


Measured memory_bytes: 17536
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNextInt()) {
			int n = sc.nextInt();
			int c = 0;
			for (int i = 0; i < 10000; i++) {
				int s = i % 10 + (i / 10) % 10 + (i / 100) % 10 + (i / 1000) % 10;
				if (s == n)
					c += 1;
			}
			System.out.println(c);
		}
	}
}

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

int main(){
    
    string S;
    cin >> S;
    vector<long long> vecl;
    long long cont = 0;
    vecl.push_back(0);
    for(int i = 0; i < S.size();i++){
        
        if(S[i]=='<'){
            cont++;
        }else{
            cont = 0;
        }
        vecl.push_back(cont);
    }
    
    // for(auto u:vecl)cout << u;
    // cout <<endl;
    
    
    vector<long long> vecr;
    cont = 0;
    vecr.push_back(0);
    for(int i = S.size()-1; i >= 0;i--){
        
        if(S[i]=='>'){
            cont++;
        }else{
            cont = 0;
        }
        vecr.push_back(cont);
    }    
    
    reverse(vecr.begin(),vecr.end());
    
    long long sum = 0;
    for(int i = 0; i < S.size() + 1;i++){
        sum += max(vecl[i],vecr[i]); 
        //cout << max(vecl[i],vecr[i])<<" "; 
    }
    cout <<endl;
    
    cout << sum <<endl;
    
}

    
    



Measured memory_bytes: 12916
def calcs(x,y,ax,ay,bx,by) ((ax-x)*(by-y)-(bx-x)*(ay-y))/2.0 end
def inpf() a=gets.chomp.split(" ").map(&:to_f)end
def inps() a=gets.chomp.split(" ")end  
def copy(a) Marshal.load(Marshal.dump(a)) end
def kaizyo(n)(n < 2)? 1 : (2..n).inject(:*) end
def scount(a) b=na(a.max+1);a.each{|n|b[n]+=1};return b end
def na(n=0,d=0) Array.new(n,d)end
def na2(n=0,m=0,d=0) Array.new(n){Array.new(m,d)}end
def na3(n=0,m=0,l=0,d=0) Array.new(n){Array.new(m){Array.new(l,d)}}end
def bit(n) n.to_s(2).split("").map(&:to_i) end
def inp() a=gets.chomp.split(" ").map(&:to_i)end
n,w=inp
d=[]
n.times do |i|
  d[i] = inp
end
dp = na2(n+1,3*n+1,-1)
ww = d[0][0]
n.times do |i|
  wd = d[i][0] - ww
  (0..(i+1)).reverse_each  do |k|
    (0..(i*3+1)).reverse_each do |j|
      if(dp[k][j]!= -1)
        dp[k+1][j+wd] = [dp[k][j]+d[i][1],dp[k+1][j+wd]].max
      end
    end
  end
  dp[0][wd] = [dp[0][wd],d[i][1]].max
end
hi = w / ww
hihi = w % ww
max = 0
n.times do |j|
  
  ru = [w - (j+1)*ww,3*n].min
#p [j,ru]
  max = [dp[j][0..ru].max,max].max if(ru >= 0)
end
p max

=begin
6 3
1 5
3 85
2 5
1 8
1 999
2 5
=end

Measured memory_bytes: 4092
from itertools import product


def main():
    """
    A op1 B op2 C op3 D = 7
    op: +, -
    """

    _input = input()
    op1, op2, op3 = f(_input)
    A, B, C, D = list(_input)
    print(A + op1 + B + op2 + C + op3 + D + "=7")


def f(_input):
    A, B, C, D = map(int, list(_input))
    ans = 7 - A

    op = ("+", "-")
    op_p = product(op, op, op)
    bcd_p = product((B, -B), (C, -C), (D, -D))
    for ops, bcd in zip(op_p, bcd_p):
        if sum(bcd) == ans:
            return ops

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
local n, m = io.read("*n", "*n")
local s, e = {}, {}
for i = 1, m do
  local a, b = io.read("*n", "*n")
  if(a == 1) then table.insert(s, b) end
  if(b == n) then e[a] = true end
end
local found = false
for k, v in pairs(s) do
  if(e[v]) then found = true break end
end
print(found and "POSSIBLE" or "IMPOSSIBLE")


Measured memory_bytes: 8556
X, Y = map(int, input().split())

Turu = 0
Kame = X

while 'true':
    if Turu * 2 + Kame * 4 == Y:
        print('Yes')
        break
    else:
        Turu += 1
        Kame -= 1
    
    if Kame < 0:
        print('No')
        break

Measured memory_bytes: 9176
a,b = map(int,input().split())
c = 0
d = 0

if a>=b:
    c = a
    a -= 1
else:
    c = b
    b -= 1

if a>=b:
    d = a
    a -= 1
else:
    d = b
    b -= 1

print(c+d)


Measured memory_bytes: 2940
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<math.h>
#include<vector>
#include<queue>
using namespace std;
int main(void){

	int a[100000];
	int b[100000];
	int c, d;
	int k;
	int n, m;
	int s, t;
	int x, y, z;


	scanf("%d", &n);



	if(n%10==9||n/10==9)printf("Yes\n");
	else printf("No\n");

	return 0;
}


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

using namespace std;

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)

#define S 0
#define W 1

signed main(){

	lli n;
	cin>>n;

	string s;
	cin>>s;

	REP(start,0,2)REP(side,0,2){
		lli ans[100100];
		REP(i,0,100100)ans[i]=-1;
		ans[0]=start;
		ans[1]=side;
		ans[n+2] = (ans[0]+ans[1]+(s.at(0)!='o'))%2;

		REP(i,1,n){
			ans[i+1] = (ans[i-1]+ans[i]+(s.at(i)!='o'))%2;
		}
		if(ans[0]==ans[n] && ans[n-1] == ans[n+2]){
			REP(i,0,n){
				if(ans[i]==0)cout<<"S";
				else cout<<"W";
			}
			cout<<endl;
			return 0;
		}
	}
	cout<<-1<<endl;

	return 0;
}

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

#define pb push_back
#define ll long long int
#define mpi map<int, int>
#define vi vector<int>
#define si set<int>
#define pii pair<int, int>
#define vpi vector<pii>
#define vs vector<string>
#define pri priority_queue<int>
#define mp make_pair
#define ff first
#define ss second
#define mod 1000000007
#define For(i, n) for (int i = 0; i < n; i++)
#define Ford(i, a, b) for (int i = a; i >= b; i--)
#define Rep(i, x, y) for (int i = x; i <= y; i++)
#define mem(a, b) memset(a, b, sizeof(a))
#define fastio                    \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0)

double tick()
{
    static clock_t oldt, newt = clock();
    double diff = 1.0 * (newt - oldt) / CLOCKS_PER_SEC;
    oldt = newt;
    return diff;
}

int main()
{
    int n, m, a, b;
    cin >> n >> m;

    int h[n];
    Rep(i, 1, n) cin >> h[i];
    vi v[n + 1];
    while (m--)
    {
        cin >> a >> b;
        v[a].pb(b);
        v[b].pb(a);
    }
    int flag = 0, c = 0;
    Rep(i, 1, n)
    {
        flag = 0;
        For(j, v[i].size())
        {
            if (h[i] <= h[v[i][j]])
            {
                flag = 1;
                break;
            }
        }
        if (flag == 0)
            c++;
    }
    cout << c << endl;

    cerr << "execution time is: " << tick() << "\n";
}


Measured memory_bytes: 9344
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (ll i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define m1(x) memset(x,-1,sizeof(x))
const int INF = 1000000001;
const ll MOD = 1000000007;

int main(){
  int k;
  cin >> k;
  queue<ll> que;
  for(int i = 1; i < 10; i++) que.push(i);
  rep(i, k-1){
    ll a = que.front();
    que.pop();
    if(a%10 == 0){
      que.push(a*10);
      que.push(a*10 + 1);
    }else if(a%10 == 9){
      que.push(a*10 + 8);
      que.push(a*10 + 9);
    }else{
      que.push(a*10 + a%10 - 1);
      que.push(a*10 + a%10);
      que.push(a*10 + a%10 + 1);
    }
  }
  cout << que.front() <<endl;
}
  



Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define sqr(x) ((x)*(x))
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define vi vector<int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define debuge cerr<<"isok"<<endl
#define debug(x) cerr<<#x<<"="<<x<<endl
#define SS second
#define FF first
#define ls (k<<1)
#define rs (k<<1|1)
#define inf 0x3f3f3f3f
#define clr(a,x) memset(a,x,sizeof(a))
#define cpy(a,x) memcpy(a,x,sizeof(a))
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout);
using namespace std;
 
const int N=405,M=100005,mod=1e9+7;
template<class T> inline void gmin(T &x,const T &y){if(x>y) x=y;}
template<class T> inline void gmax(T &x,const T &y){if(x<y) x=y;}
inline void ch(int &x,int y){x=(x+y)%mod;}
inline void read(int &x){
	x=0;char ch=getchar(),rev=0;
	while(ch>'9'||ch<'0') rev=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	x=rev?-x:x;
}
inline int exp(int x,int y){
	int ans=1;
	while(y){
		if(y&1) ans=(ll)ans*x%mod;
		x=(ll)x*x%mod;y>>=1;
	}return ans;
}
 
int n,m,u[M],v[M],ans;
bool res[N][N],dead[N],vis[N],ill[N];
 
bool check(){
	for(int j=1;j<=m;j++){
		if(vis[u[j]]&&vis[v[j]]) return 0;
		if(vis[u[j]]) vis[v[j]]=1,dead[v[j]]=1;
		else if(vis[v[j]]) vis[u[j]]=1,dead[u[j]]=1;
	}
	return 1;
}
 
int main(){
#ifdef rqgao2014
	freopen("input.txt","r",stdin);
#endif
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d",&u[i],&v[i]);
	reverse(u+1,u+m+1);
	reverse(v+1,v+m+1);
	for(int i=1;i<=n;i++){
		clr(vis,0);clr(dead,0);
		vis[i]=1;
		ill[i]=check();
		cpy(res[i],dead);
	}
	for(int i=1;i<=n;i++){
		if(!ill[i]) continue;
		for(int j=i+1;j<=n;j++){
			if(!ill[j]) continue;
			bool isok=(!res[i][j]&&!res[j][i]);
			for(int k=1;k<=n&&isok;k++)
				if(i!=k&&j!=k&&res[i][k]&&res[j][k]) isok=0;
			ans+=isok;
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;
int main()
{
  string s;
  int i, j;
  cin>>s;
  int ans=0;
  for(i=0;i<s.size();i++)
    {
        for(j=1;i+j-1<s.size();j++)
          {
          string t=s.substr(i,j);
          bool poss=1;
          for(int k=0;k<t.size();k++)
            if(t[k]!='A'&&t[k]!='T'&&t[k]!='C'&&t[k]!='G')  
        poss=false;
          if(poss)
            ans=max(j,ans);
            }
    }
  cout<<ans<<endl;
}


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

typedef pair<int,int> P;
typedef pair<P,int> P2;

int main(){
  int h,w,sx,sy,gx,gy;
  int g[9][9],d[9][9][9];
  int dy[] = {-1,0,1,0}, dx[] = {0,1,0,-1};

  while(cin >> w >> h,(w||h)){
    for(int i=0;i<h;i++)
      for(int j=0;j<w;j++){
	cin >> g[i][j];
	if(g[i][j] == 2){sy = i; sx = j;}
	if(g[i][j] == 3){gy = i; gx = j;}
	for(int k=0;k<=6;k++)d[i][j][k] = -1;
      }

    d[sy][sx][6] = 0;
    queue<P2> q; q.push(P2(P(sy,sx),6));

    int res = -1;
    while(q.size()){
      P2 p = q.front(); q.pop();
      int y = p.first.first, x = p.first.second, t = p.second;

      if(y==gy && x==gx){res = t; break;}
      if(t==1)continue;

      for(int i=0;i<4;i++){
	int ty = y+dy[i], tx = x+dx[i], tt = t-1;
	if(ty<0 || tx<0 || h<=ty || w<=tx || !g[ty][tx])continue;
	if(g[ty][tx] == 4)tt = 6;
	if(d[ty][tx][tt]<0){
	  d[ty][tx][tt] = d[y][x][t] + 1;
	  q.push(P2(P(ty,tx),tt));
	}
      }
    }
    if(res<0)cout << "-1\n";
    else cout << d[gy][gx][res] << endl;
  }
}
	  
    
    

Measured memory_bytes: 1200
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
signed main(){
  int N,K; cin>>N>>K;
  vi H(N);
  rep(i,0,N) cin>>H[i];
  vi dp(N);
  rep(i,1,N){
    dp[i]=dp[i-1]+abs(H[i]-H[i-1]);
    REP(j,2,min(K,i)){
      dp[i]=min(dp[i],dp[i-j]+abs(H[i]-H[i-j]));
      
    }
  }
  cout<<dp[N-1]<<endl;
  }


Measured memory_bytes: 1792
N,M = (int(i) for i in input().split())
X = [int(i) for i in input().split()]

if N >= M:
    print(0)
else:
    X.sort()
    
    spaces = []
    now = X[0]
    
    for i in range(1,len(X)):
        spaces.append(X[i]-now)
        now = X[i]
    
    sortSpaces = sorted(spaces, reverse = True)
    
    maxN = sortSpaces[:N-1]
    
    print(sum(spaces)-sum(maxN))

Measured memory_bytes: 13832
while(1):
    try:
        slist = list(map(str, input().split()))
    except:
        break

    rot = 0
    for i in range(26):
        for s in slist:
            ch = ""
            for c in s:
                if "a" <= c <= "z":
                    g = chr((ord(c) - ord("a") + i) % 26 + ord("a"))
                else:
                    g = c
                ch += g
            if ch == "this" or ch == "that" or ch == "the":
                rot = i
                break
        if rot != 0:
            break

    for i, s in enumerate(slist):
        ch = ""
        for c in s:
            if "a" <= c <= "z":
                g = chr((ord(c) - ord("a") + rot) % 26 + ord("a"))
            else:
                g = c
            ch += g
        if i == len(slist) - 1:
            print(ch)
        else:
            print(ch + " ", end="")



Measured memory_bytes: 5564
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define RFOR(i,a,b) for(int i=(b-1); i>=(a); i--)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define pb push_back
using ll = long long;
using D = double;
using LD = long double;
using P = pair<int, int>;
const int mod = 1e9+7;
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; }

int main(){
    ll n,p; cin >> n >> p;
    string s; cin >> s;
    ll ans = 0;
    if(p == 2 || p == 5){
        rep(i,n){
            if((s[i] - '0') % p == 0) ans += i+1;
        }
    }
    else{
        vector<ll> cnt(p);
        ll now = 0;
        ll d = 1;
        cnt[0] = 1;
        rrep(i,n){
            now += d * (s[i]- '0');
            now %= p;
            cnt[now]++;
            d *= 10;
            d %= p;
        }
        rep(i,p){
            ans += (cnt[i]*(cnt[i]-1))/2;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
void yes(){ cout << "Yes" << endl; }
void no(){ cout << "No" << endl; }

int main(){
    int n,t; cin >> n >> t;
    int ans = 1e9;
    rep(i,n){
        int a,b; cin >> a >> b;
        if(b <= t) ans = min(ans,a);
    }
    if(ans == 1e9) cout << "TLE" << endl;
    else cout << ans << endl;
    return 0;
}


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

#define ll long long
#define Fi first
#define Se second
#define Pb push_back

#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define Rep(i,n,m) for(int i=(int)(n);i<(int)(m);i++)
#define RepS(i,n,m) for(int i=(int)(n);i<=(int)(m);i++)
#define RRepS(i,n,m) for(int i=(int)(n);i>=(int)(m);i++)
#define RepA(x) for(auto item : (x))
#define output_s(a) printf("%s\n",(a).c_str())

//library----------------------------------------------


int main(){
    int a,b,c; cin>>a>>b>>c;
    printf(a+b+c>=22?"bust":"win");
    return 0;
}

Measured memory_bytes: 256
//auto 関数名 = [(&:ラムダ外の引数をとる時))](引数の型1 引数名1, 引数の型2, 引数名2, ...) { 関数の処理 }; //inside main() define function. take care of };
// for (int tmp = 0; tmp < (1 << ビット数); tmp++) {
//   bitset<ビット数> s(tmp);
//   // (ビット列sに対する処理)
// }
// sort(配列変数.begin(), 配列変数.end());
// do {
//   // 順列に対する処理
// } while (next_permutation(配列変数.begin(), 配列変数.end()));
//const double PI = acos(-1); M_PI
// cout << fixed << setprecision(10);
// set<int>st{ 3,1,4,1,5,9,2,6,5,3,5 };
//     for (auto itr = st.begin(); itr != st.end(); ++itr) {
//         cout << *itr;
//     }
#include <bits/stdc++.h>
#include <regex>
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define _GLIBCXX_DEBUG 
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end() //sort(all(vec)); ,reverse(all(vec));etc
int main(){
 int n,k;
 cin>>n>>k;
 vector<int>h(n);
 rep(i,n){
   cin>>h.at(i);
 }
 sort(all(h));
 int ans=0;
 rep(i,n-k+1){
  if(i==0){
    ans=h.at(i+k-1)-h.at(i);
  }else{
    if(ans>h.at(i+k-1)-h.at(i)){
      ans=h.at(i+k-1)-h.at(i);
    }
  } 
 }
 cout<<ans<<endl;

}


Measured memory_bytes: 3756
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
#include<iomanip>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;


/*
AC
文字列の比較が出来ることを利用して実装を軽くした
*/

bool ok=true;
string s;

int main(void){
	cin>>s;
	cout<<("2019/04/30"<s?"TBD":"Heisei")<<endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
      Scanner sc = new Scanner(System.in);   
      int A = sc.nextInt();
      int B = sc.nextInt();
      int C = sc.nextInt();
      if(A==B && B==C){
        System.out.println("Yes");
      }else{
        System.out.println("No");
      }
    }
}

Measured memory_bytes: 35676
#include<iostream>
#define rep(i,f,t) for(int i=f;i<t;i++)
using namespace std;
int main(){
	int a,b;
  cin>>a>>b;
  if(a<b)rep(i,0,b)cout<<a;
  else rep(i,0,a)cout<<b;
  cout<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
 
int main(){
  int N,d[100];
  cin >> N;
  for(int i=0;i<N;i++){
    cin >> d[i];
  }
  int num[100]={0};
  for(int i=0;i<N;i++){
    num[d[i]]++;
  }
  int res=0;
  for(int i=1;i<=100;i++){
    if(num[i]){
      res++;
    }
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define inf (1ll<<60)
#define Yes(f) cout<<(f?"Yes":"No")<<endl
#define yes(f) cout<<(f?"yes":"no")<<endl
#define YES(f) cout<<(f?"YES":"NO")<<endl
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v), greater<int>())

using namespace std;

const int mod=1e9+7;

void run();

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(12);
}

signed main(){
    init();
    run();
    return 0;
}

void run(){
    int a,b,k;
    cin>>a>>b>>k;
    int g=__gcd(a,b);
    for(int i=g;i>0;i--){
        if(g%i==0)k--;
        if(!k){
            cout<<i<<endl;
            return;
        }
    }
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

r,g,b,n=mii()
arr=sorted([r,g,b])

gg=n//arr[1] +1
bb=n//arr[2] +1
ans=0



for i in range(gg):
    for j in range(bb):
        if (n-(arr[1]*i+arr[2]*j))%arr[0]==0 and (n-(arr[1]*i+arr[2]*j))>=0:
            ans+=1


print(ans)

Measured memory_bytes: 66008
#include<iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <cmath>
#include <math.h>
#include <iomanip>
using namespace std;



int main()
{
    int n;
    long long s;
    cin >> n;
    char ss[n];
    cin.get(ss[0]);
    for(int i=n-1;i>=0;i--){
        cin.get(ss[i]);
    }

    int state = 0,ans=0;
    for(int a=0; a<10 ; a++){
        for(int b=0; b<10; b++){
            for(int c=0; c<10; c++){
                state=0;
                for(int i=n-1;i>=0;i--){
                    if(state==0&&(ss[i]-'0')==a){
                        state++;
                    }
                    else if(state==1&&(ss[i]-'0')==b){
                        state++;
                    }
                    else if(state==2&&(ss[i]-'0')==c){
                        state++;
                    }
                }
                if(state==3){
                    ans++;
                }
            }
        }
    }

    cout << ans;
    

}

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


int main(){
    string s,t;cin>>s>>t;
    int pos=-1,ok=1;
    rep(i,0,s.size()-t.size()+1){
        ok=1;
        rep(j,0,t.size()){
            if(s[i+j]!=t[j]&&s[i+j]!='?')ok=0;
        }
        if(ok==1)pos=i;
    }
    rep(j,pos,pos+t.size()){
        s[j]=t[j-pos];
    }
    rep(i,0,s.size())if(s.at(i)=='?')s.at(i)='a';
    
    if(pos!=-1)cout<<s<<endl;
    else cout<<"UNRESTORABLE"<<endl;
}






Measured memory_bytes: 256
def read_input():
    s = input().strip()
    return s

def submit():
    s = read_input()

    count_marble = 0
    for bigram in zip(s, s[1:]):
        if bigram[0] != bigram[1]:
            count_marble += 1

    print(count_marble)


if __name__ == '__main__':
    submit()


Measured memory_bytes: 39792
// Template
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <functional>
#include <numeric>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;
const int MOD = 1000000007;

#define v_exists(elem, v) find(v.begin(),v.end(),elem)!=v.end()
#define s_exists(elem, s) s.find(elem)!=s.end()
#define mod_mul(x, y) x*y%MOD
#define mod_add(x, y) (x+y)%MOD
#define mod_sub(x, y) (x-y)%MOD
#define REP(i, n) for(int i = 0;i < n;i++)
#define INF 100000


long gcd(long a, long b) {
    return b == 0 ? a : gcd(b, a % b);
}

long lcm( long m, long n ){
    if ( ( 0 == m ) || ( 0 == n ) )
        return 0;

    return ((m / gcd(m, n)) * n);
}


long nCr(long n, long r){
    if(n==r || r==0){
        return 1;
    } else {
        return nCr(n-1,r) + nCr(n-1,r-1);
    }
}

long long c[51][51];

void comb_table(int N){
    for(int i=0; i<=N; ++i){
        for(int j=0; j<=i ;++j){
            if(j == 0 || j == i){
                c[i][j] = 1LL;
            } else {
                c[i][j] = c[i-1][j-1]+c[i-1][j];
            }
        }
    }
}



int main(){
    int N,A,B; cin >> N >> A >> B;
    long long v[50];

    for (int i = 0; i < N; i++) {
        cin >> v[i];
    }
    comb_table(N);
    sort(v, v+N);
    reverse(v, v+N);

    double sum_v = 0.0;
    for(int i=0; i<A; ++i){
        sum_v += v[i];
    }
    sum_v/=A;

    long long ans = 0LL;

    if(v[A-1]==v[0]){
        int num = 0;
        REP(i, N){
            if(v[i]==v[0]){
                num++;
            }
        }

        for(int n=A; n<=B; n++){
            ans += c[num][n];
        }

    } else {
        int num = 0;
        int r = 0;
        for(int i=0; i<N; ++i){
            if(v[i]==v[A-1]){
                num++;
                if(i<A){
                    r++;
                }
            }
        }

        ans += c[num][r];

    }

    cout.precision(20);

    cout << fixed << sum_v << endl;
    cout << ans << endl;


    return 0;

}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
  	cin.tie(0);
	ios::sync_with_stdio(false);
    int N, L;
    cin >> N >> L;
    string S[N];
    for(int i = 0; i < N; i++) {
        cin >> S[i];
    }
    sort(&S[0], &S[N]);
    string ans;
    for(string &s:S) {
        ans += s;
    }
    cout << ans;
    return 0;
}

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

const ll MOD = 1000000007;

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

long long pow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    map<pair<ll, ll>, int> mp;
    int zero_num = 0;
    rep(i, n) {
        ll a, b;
        cin >> a >> b;
        if (a == 0 && b == 0) {
            zero_num++;
        } else if (a == 0) {
            mp[make_pair(0ll, 1ll)]++;
        } else if (b == 0) {
            mp[make_pair(1ll, 0ll)]++;
        } else {
            ll g = gcd(a, b);
            a /= g;
            b /= g;
            if (a < 0) {
                a = -a;
                b = -b;
            }
            mp[make_pair(a, b)]++;
        }
    }
    ll ans = 1;
    for(auto itr = mp.begin(); itr != mp.end(); ++itr) {
        pair<ll, ll> p = itr->first;
        if (p.second < 0) p = make_pair(-p.second, p.first);
        else p = make_pair(p.second, -p.first);
        ll tmp = pow(2ll, (ll)itr->second) + pow(2ll, (ll)mp[p]) - 1;
        ans *= tmp;
        ans %= MOD;
        itr->second = 0;
        mp[p] = 0;
    }
    ans--;
    ans += zero_num;
    ans %= MOD;
    ans += MOD;
    ans %= MOD;
    cout << ans << endl;
    return 0;
}

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

int main()
{
	int n, a, b, c, d;

	cin >> n >> a >> b >> c >> d;

	int x = ((n - 1) / a + 1) * b, y = ((n - 1) / c + 1) * d;

	if (x < y)
		cout << x << endl;
	else
		cout << y << endl;
	
	return 0;
}


Measured memory_bytes: 3120
function Main(input: string) {
  const lines = input.split('\n');
  const params1 = lines[0].split(' ').map(x => parseInt(x));
  const params2 = lines[1].split(' ').map(x => parseInt(x));

  const n = params1[0];
  const m = params1[1];
  const a = params2;

  const sum = a.reduce((x, y) => x + y);

  const b = a.filter(x => 4 * m * x >= sum);

  const msg = (b.length >= m) ? 'Yes' : 'No';

  console.log(msg)
}

Main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7372
import itertools

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = []
max_h = 0
for i, num in enumerate(a):
    b.append(max_h)
    max_h = max(max_h, num)

ans = 9999999999999999999999
for lst in itertools.combinations(range(1, n), k - 1):
    total = 0
    before = a[0]
    for num in lst:
        if a[num] <= b[num] or a[num] <= before:
            total += max(b[num], before) - a[num] + 1
            before = max(b[num], before) + 1
            
    ans = min(ans, total)
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

const ll mod = 1000000007;

int main() {
    ll n;
    cin >> n;
    cout << (n - 1) * n / 2 << endl;
    return 0;
}


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

int main(){
  int w,h,p,x1,x2,y1,y2,n;
  bool road[21][21][21][21];
  cin >> n;
  while(n--){
    cin >> w >> h >> p;
    memset(road,true,sizeof(road));
    long int dp[21][21] = {{0}};
    while(p--){
      cin >> x1 >> y1 >> x2 >> y2;
      road[y1][x1][y2][x2] = false;
      road[y2][x2][y1][x1] = false;
    }
    dp[0][0] = 1;
    for(int i=0;i<h;i++){
      if(road[i][0][i+1][0]) dp[i+1][0] = 1;
      else break;
    }
    for(int i=0;i<w;i++){
      if(road[0][i][0][i+1]) dp[0][i+1] = 1;
      else break;
    }
    for(int i=0;i<=h;i++){
      for(int j=0;j<=w;j++){
	if(road[i][j][i][j+1]) dp[i][j+1] = dp[i][j] + ((i-1 < 0)? 0 : ((road[i][j+1][i-1][j+1])? dp[i-1][j+1] : 0));
	if(road[i][j][i+1][j]) dp[i+1][j] = dp[i][j] + ((j-1 < 0)? 0 : ((road[i+1][j][i+1][j-1])? dp[i+1][j-1] : 0));
      }
    }
    if(dp[h][w] > 0) cout << dp[h][w] << endl;
    else cout << "Miserable Hokusai!\n";
  }
}

Measured memory_bytes: 1360
#include<bits/stdc++.h>
using namespace std;
int n,m,b[1000001]={0},d[1000001];//
int L,R,D;
struct node{
    int v,c,next;
};
node a[3000001];
int head[1000001],e;
void addnode(int from,int to,int c){
    e++;
    a[e].c=c;//边权
    a[e].v=to;//下一个
    a[e].next=head[from];//
    head[from]=e;//记下标 
}//喜闻乐见的建表 

bool dfs(int x)
{
	b[x]=1;//走过标记 
	int v,c;
	for(int i=head[x];i!=0;i=a[i].next)
	{
		v=a[i].v;
		c=a[i].c;
		if(d[v]>d[x]+c)
		{
			if(b[v]==1)	return 1;//判断负环，走过即为负环 
			d[v]=d[x]+c;
			if(dfs(v))	return 1;
		}
	}
	b[x]=0;
	return 0;
}

int main()
{
	scanf("%d%d",&n,&m);
	
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&L,&R,&D);
		addnode(R,L,D);//逆向建边
		addnode(L,R,-D);//正向建边
	}
	for(int i=1;i<=n;i++)
	{
		addnode(0,i,0);//万一图不联通，分为两个部分，一边有负环一边没有，只搜了没有的那一边就GG
		//所以把0和所有点连起来，每个点找一遍就ok了 
	}
	
	//于是我们从零开始dfs 
	memset(d,1000000,sizeof(d));
	d[0]=0;
	if(dfs(0)) printf("No");
    else printf("Yes");
	return 0;
}
//思路：应该建一个图，题目相当于说如果本来一条连点A的边连到点B去了的话就no 

Measured memory_bytes: 16768
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define INF 1000000000000000007
#define pb emplace_back
typedef vector<int> vi;

void solve(){
int a=0,w=0,l=0,q=0,m=0,r=0,p=0,x=0,y=0,n=0;
string s,t;
cin>>s>>t;
for(int i=0;i<s.size();i++)
if(s[i]!=t[i])
a++;
cout<<a<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
  int t=1;
  //cin>>t;
  while(t--){
  	solve();
  }
  return 0;
} 	

Measured memory_bytes: 3820