akhauriyash/Code-Regression huggingface dataset:
from bisect import bisect_right
s = input()
t = input()

sdict = {}
for i,c in enumerate(s):
    if c not in sdict:
        sdict[c] = []
    sdict[c].append(i)

ans = 0
spos = -1
for c in t:
    if c not in sdict:
        print(-1)
        exit()
    tt = bisect_right(sdict[c], spos)
    if tt == len(sdict[c]):
        # print('-',tt)
        tt = bisect_right(sdict[c], -1)
        ans += len(s)
    # print(c, spos, sdict[c], tt)
    spos = sdict[c][tt]

print(ans + spos + 1)


Measured memory_bytes: 7540
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <cassert>
using namespace std;
using ll = long long;
const int INF = 1<<30;
const int MOD = (int)1e9 + 7;
const int MAX_N = (int)1e5 + 5;
#define debug(x) cout << #x << ": " << x << endl
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2>& p) { os << p.first << " " << p.second; return os; }
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) { for(int i = 0; i < (int) v.size(); i++) os << v[i] << (i + 1 != v.size() ? " " : ""); return os; }

void solve()
{
    int a, b, m; cin >> a >> b >> m;
    vector<int> A(a), B(b);
    for(int i = 0; i < a; i++) cin >> A[i];
    for(int i = 0; i < b; i++) cin >> B[i];
    int ans = INF;
    for(int i = 0; i < m; i++)
    {
        int x, y, c; cin >> x >> y >> c;
        x--, y--;
        int tmp = A[x] + B[y] - c;
        ans = min(ans, tmp);
    }
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    ans = min(ans, A.front() + B.front());
    cout << ans << endl;
}

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
    return 0;
}

Measured memory_bytes: 1024
N, K, Q = map(int, input().split())
A = [int(input()) for i in range(Q)]
poi = [K-Q]*N
for i in range(Q):
    poi[A[i]-1] += 1

for i in range(N):
    if poi[i] > 0:  print('Yes')
    else:           print('No')

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

int main() {

	vector<int> x(5);
	for (int i = 0; i < 5; i++) {
		cin >> x[i];
	}
	cout << find(x.begin(), x.end(), 0) - x.begin() + 1 << endl;
	return 0;
}

Measured memory_bytes: 3580
K=int(input())

#now: str
def bfs():
  
  q=[""]
  count=0
  while count<K:
    now=q.pop(0)
    if now=="":
      for n in range(1,10):
        new=now+str(n)
        q.append(new)
        count+=1
        if count==K:
          return new
    elif now[-1]=="0":
      for n in ["0","1"]:
        new=now+n
        q.append(new)
        count+=1
        if count==K:
          return new
    elif now[-1]=="9":
      for n in ["8","9"]:
        new=now+n
        q.append(new)
        count+=1
        if count==K:
          return new
    else:
      s=int(now[-1])
      for n in [s-1,s,s+1]:
        new=now+str(n)
        q.append(new)
        count+=1
        if count==K:
          return new
      
print(bfs())

Measured memory_bytes: 7724
import numpy as np
import numpy.linalg as la
import math


def BC133_B():
    n, d = map(int, input().split())
    l = []
    for i in range(n):
        l.append(np.array(list(map(int, input().split()))))
    a = 0
    for i in range(n):
        for j in range(i):
            d = la.norm(l[i] - l[j])
            if int(d + 0.5)**2 == d**2: a += 1
    print(a)


BC133_B()

Measured memory_bytes: 12504
import itertools

N,M = map(int, input().split())
path = [[False] * N for x in range(N)]

for i in range(M):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    path[a][b] = True
    path[b][a] = True

count = 0
for j in itertools.permutations(range(N)):
    if j[0] != 0:
        continue
    for k in range(N):
        if k == N-1:
            count += 1
            break
        if not path[j[k]][j[k+1]]:
            break
print(count)

Measured memory_bytes: 3064
num = list(input())
ans = 7
for i in range(2 ** len(num)):
    total = 0
    ans_num = []
    ans_op = []
    for j in range(len(num)):
        if((i >> j) & 1):
            ans_num.append(num[j])
            if(j >= 1):
                ans_op.append('+')
            total += int(num[j])
        else:
            ans_num.append(num[j])
            if (j >= 1):
                ans_op.append('-')
            total -= int(num[j])
    if(total == ans):
        print(ans_num[0]+ans_op[0]+ans_num[1]+ans_op[1]+ans_num[2]+ans_op[2]+ans_num[3]+'=7')
        break


Measured memory_bytes: 38256
s = input()


def is_kaibun(s):
    """
    if len(s) == 1:
        return True

    l = [0] * (ord("z") - ord("a") + 1)
    for c in s:
        l[ord(c)-ord("a")] += 1

    odd_cnt = 0
    for i in range(len(l)):
        if l[i] % 2 == 1:
            odd_cnt += 1
            if odd_cnt >= 2:
                return False
    return True
    """
    rev_s = s[::-1]
    if rev_s == s:
        return True
    else:
        return False


n = len(s)
if len(s) < 3:
    print("No")
elif is_kaibun(s) and is_kaibun(s[:(n-1) // 2]) and is_kaibun(s[(n+3)//2-1:]):
    print("Yes")
else:
    print("No")


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

int main() {
  while (true) {
    int n;
    cin >> n;
    if (n == 0) return 0;
    while (n--) {
      int a[4], b[4], c[4];
      for (int i = 0; i < 4; i++)
	cin >> a[i];
      for (int i = 0; i < 4; i++)
	cin >> b[i];

      c[0] = a[0] * b[0];
      c[1] = a[0] * b[1];
      c[2] = a[0] * b[2];
      c[3] = a[0] * b[3];

      c[1] += a[1] * b[0];
      c[0] -= a[1] * b[1];
      c[3] += a[1] * b[2];
      c[2] -= a[1] * b[3];

      c[2] += a[2] * b[0];
      c[3] -= a[2] * b[1];
      c[0] -= a[2] * b[2];
      c[1] += a[2] * b[3];

      c[3] += a[3] * b[0];
      c[2] += a[3] * b[1];
      c[1] -= a[3] * b[2];
      c[0] -= a[3] * b[3];

      cout << c[0] << ' ' << c[1] << ' ' << c[2] << ' ' << c[3] << endl;
    }
  }
}

Measured memory_bytes: 3052
n=int(input())
a=[0]*n
b=[0]*n
for i in range(n):
  a[i],b[i] = map(int,input().split())
a.sort(reverse=True)
b.sort()
if n%2:
  a_med = a[n//2]
  b_med = b[n//2]
  print(b_med - a_med + 1)
else:
  a_med = (a[n//2-1] + a[n//2])/2
  b_med = (b[n//2-1] + b[n//2])/2
  print(int((b_med - a_med)*2)+1)

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

signed main() {
    string s; cin >> s;
    int K; cin >> K;
    vector<string> vec;
    int N = s.size();
    for(int i = 1; i <= 5; i++){
        for(int j = 0; j <= N - i; j++){
            vec.push_back(s.substr(j, i));
        }
    }
    sort(vec.begin(), vec.end());
    if(K == 1) cout << vec[0] << endl;
    else{
        int x = 1;
        for(int i = 0; i < vec.size(); i++){
            if(vec[i] != vec[i + 1]) x++;
            if(x == K){
                cout << vec[i + 1] << endl;
                return 0;
            }
        }
    }
}

Measured memory_bytes: 1660
s                  = gets.chomp.split(//)
n                  = s.size
ans                = Array.new(n, 0)
count              = 0
gathering_children = -> {
  s.each_with_index do |c, i| #前から
    if c == "R"
      count += 1
    elsif count != 0
      ans[i]     += count / 2
      ans[i - 1] += (count + 1) / 2
      count      = 0
    end
  end
}
gathering_children.call
s.reverse!.map! { |c| c == "R" ? "L" : "R" } # 後ろから
ans.reverse!
gathering_children.call
puts ans.reverse.join(" ") # 答えをリバースして出力



Measured memory_bytes: 16252
#include <bits/stdc++.h>
using namespace std;
int main() {
	int m,d;
	cin >> m >> d;
	int res = 0;
	for(int i=2;i<10;i++) {
		for(int j=2;j<10;j++) {
			if (i * 10 + j <= d && i * j <= m) {
				res++;
			}
		}
	}
	cout << res;
	return 0;
}


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

int main()
{
    int n, k;
    string s;
    cin >> n >> k >> s;
    k--;
    if (s[k] == 'A')
    {
        s[k] = 'a';
    }
    else if (s[k] == 'B')
    {
        s[k] = 'b';
    }
    else
    {
        s[k] = 'c';
    }
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
int main(void){
    char s[100+1];
    scanf("%s",s);
    int n = strlen(s);
    for(int i= 0;i<n;i++){
        if (i%2 == 0){
            if(s[i]=='L'){
                puts("No");
                return 0;
            }
        }else{
            if(s[i]=='R'){
                puts("No");
                return 0;
            }
        }
    }
    puts("Yes");
    return 0;

}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <functional>
#include <numeric>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
using namespace std;
#define INT_MAX 2147483647
#define INT_MIN (-2147483647 - 1)
#define INF (int)1e8
#define _INF (int)-1e8
#define INFLL (long long)1e14
#define _INFLL (long long)-1e14
#define Loop(i, n) for(int i = 0; i < (int)n; i++)
#define Loop1(i, n) for(int i = 1; i <= (int)n; i++)
#define Loopr(i, n) for(int i = (int)n - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = (int)n; i >= 1; i--)
#define bitmanip(m,val) static_cast<bitset<(int)m>>(val)
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef pair<int, int> P;

int main() {
	int n; cin >> n;
	vll a(n);
	Loop(i, n) {
		cin >> a[i];
	}
	sort(a.begin(), a.end(), greater<ll>());
	vll b;
	Loop(i, n - 1) {
		if (b.size() == 2) break;
		if (a[i] == a[i + 1]) {
			b.push_back(a[i]);
			++i;
		}
	}
	if (b.size() == 2) cout << b[0] * b[1] << endl;
	else cout << 0 << endl;
	return 0;
}

Measured memory_bytes: 1024
while True:
    hosuu = {}
    hosu = []
    i = int(input())
    if i == 0:
        break
    else:
        for num in range(i):
            a,b,c = input().split(" ")
            num1 = int(b) + int(c)
            a = int(a)
            hosuu[num1] = a
            hosu.append(num1)
        hosu.sort()
        hosu.reverse()
        print(str(hosuu[hosu[0]]) + " " + str(hosu[0]))


Measured memory_bytes: 6680
#include <iostream>
#include <iomanip>
#include <cmath>
#include <queue>
#include <map>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <queue>
#include <string>
#include <functional>
#define rep(i, a, b) for(int i=a;i<b;++i)
#define MOD 1000000007
#define RAND 1000
//#define LLONG_MIN -9223372036854775808
using namespace std;

int main(void)
{
	int h, w;
	char s[102][102];
	cin >> h >> w;
	for (int i = 0; i < h; ++i)
		cin >> s[i];
	for (int i = 0; i < w + 2; ++i)
		cout << '#';
	cout << endl;
	for (int i = 0; i < h; ++i) {
		cout << '#' << s[i] << '#' << endl;
	}
	for (int i = 0; i < w + 2; ++i)
		cout << '#';
	cout << endl;

	//system("pause");
	return 0;
}



Measured memory_bytes: 256
#include<vector>
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <iostream>
#include <algorithm>
#define INF 100000000000000
using namespace std;

int main() {
    long long x;
    long long cnt=1;
    vector<long long> X;
    while(1){
        cin >> x;
        if(x==0){
            break;
        }
        X.push_back(x);
    }
    for(int i=0; i<X.size(); i++){
        cout << "Case " << i+1 << ": "<< X.at(i) << endl;

    }
    return 0;
}




Measured memory_bytes: 3252
#include <iostream>
#include <cstdio>
using namespace std;
int h, w, c4, c2, c1, a[30];
string t;
int main() {
	int i, j;
	cin>>h>>w;
	for(i=0; i<h; i++) {
		cin>>t;
		for(j=0; t[j]; j++) a[t[j]-'a']++;
	}
	c4 = (h/2) * (w/2);
	c2 = (h%2) * (w/2) + (h/2) * (w%2);
	c1 = (h%2) * (w%2);
	for(i=0; c4 && i<26; ) {
		if(a[i]>=4) a[i] -= 4, c4--;
		else i++;
	}
	for(i=0; c2 && i<26; ) {
		if(a[i]>=2) a[i] -= 2, c2--;
		else i++;
	}
	for(i=0; c1 && i<26; ) {
		if(a[i]>=1) a[i] -= 1, c1--;
		else i++;
	}
	puts(c4+c2+c1 ?  "No" : "Yes");
	return 0;
}

Measured memory_bytes: 256
#! /usr/bin/perl
use strict;
use warnings;
use utf8;

my $N = <>;
my %word;


for(my $i = 0;$i<$N;$i++){
    $word{<>}++;
}

my $cnt = 0;
for(keys %word){
    $cnt++;
}    

print $cnt, "\n";


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

int shop[110][110];
int p[110][11];
int main(){
  int n;
  cin >> n;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < 10; j++){
      cin >> shop[i][j];
    }
  }
  for(int i = 0; i < n; i++){
    for(int j = 0; j < 11; j++){
      cin >> p[i][j];
    }
  }
  int ans = -1e9;
  for(int bit = 1; bit < (1<<10); bit++){
    int pro = 0;
    for(int i = 0; i < n; i++){
      int cnt = 0;
      for(int j = 0; j < 10; j++){
        if((bit >> j & 1) && shop[i][j]) cnt++;
      }
      pro += p[i][cnt];
    }
    ans = max(ans, pro);
  }
  cout << ans << endl;
  return 0;
}


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

int main(){
    int N, num = 0, i;
    char c = 'I';
    string S;

    cin >> N >> S;
    for(i = 0; i < N; i++){
        if(S[i] != c)num++;
        c = S[i];
    }
    cout << num << endl;
}

Measured memory_bytes: 512
import math


def main():
    k = int(input())
    ans = 0

    for a in range(1, k+1):
        for b in range(1, k+1):
            for c in range(1, k+1):
                ans += math.gcd(a, math.gcd(b, c))

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 69532
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define INF 1000000000
#define mod 1000000007
using ll=long long;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    int n;cin>>n;
    string s;cin>>s;

    ll ans=0;
    rep(i,n){
        if(s[i]=='R'){
            ll gl=0,bl=0,gr=0,br=0;
            for(int j=1;i-j>=0;j++){
                if(s[i-j]=='G') gl++;
                if(s[i-j]=='B') bl++;
            }
            for(int j=1;i+j<n;j++){
                if(s[i+j]=='G') gr++;
                if(s[i+j]=='B') br++;
            }
            ans+=gl*br+bl*gr;
            for(int j=1;i-j>=0 and i+j<n;j++){
                if(s[i]!=s[i+j] and s[i]!=s[i-j] and s[i+j]!=s[i-j]) ans--;
            }
        }
        if(s[i]=='G'){
            ll gl=0,bl=0,gr=0,br=0;
            for(int j=1;i-j>=0;j++){
                if(s[i-j]=='R') gl++;
                if(s[i-j]=='B') bl++;
            }
            for(int j=1;i+j<n;j++){
                if(s[i+j]=='R') gr++;
                if(s[i+j]=='B') br++;
            }
            ans+=gl*br+bl*gr;
            for(int j=1;i-j>=0 and i+j<n;j++){
                if(s[i]!=s[i+j] and s[i]!=s[i-j] and s[i+j]!=s[i-j]) ans--;
            }
        }
        if(s[i]=='B'){
            ll gl=0,bl=0,gr=0,br=0;
            for(int j=1;i-j>=0;j++){
                if(s[i-j]=='R') gl++;
                if(s[i-j]=='G') bl++;
            }
            for(int j=1;i+j<n;j++){
                if(s[i+j]=='R') gr++;
                if(s[i+j]=='G') br++;
            }
            ans+=gl*br+bl*gr;
            for(int j=1;i-j>=0 and i+j<n;j++){
                if(s[i]!=s[i+j] and s[i]!=s[i-j] and s[i+j]!=s[i-j]) ans--;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}


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

int getDist(int toX, int toY, int fromX, int fromY) {
	return abs(toX - fromX) + abs(toY - fromY);
}

int main() {

	int h, w, d; cin >> h >> w >> d;
	int u = h * w;
	vector<pair<int, int>> coordinate(u + 1);
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			int a; cin >> a;
			coordinate[a] = { i,j };
		}
	}
	vector<int> accum(u + 1, 0);
	for (int i = 1; i <= u; i++) {
		if (i <= d) {

		}
		else {
			int toX = coordinate[i].first;
			int toY = coordinate[i].second;
			int fromX = coordinate[i - d].first;
			int fromY = coordinate[i - d].second;;
			accum[i] += getDist(toX, toY, fromX, fromY);
			accum[i] += accum[i - d];
		}
	}
	int q; cin >> q;
	for (int i = 0; i < q; i++) {
		int l, r; cin >> l >> r;
		cout << accum[r] - accum[l] << endl;
	}
	return 0;
}

Measured memory_bytes: 4260
# -*- coding: utf-8 -*-

class Node():
    def __init__(self, key, parent=None, left=None, right=None):
        self.key = key
        self.parent = parent
        self.left = left
        self.right = right
        

class BinarySearchTree(list):
    def __init__(self):
        list.__init__(self)
        self.root = None
        
    def insert(self, z):
        z = Node(z)
        y = None
        x = self.root
        
        while x is not None:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y
        
        if y is None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

    def preorder(self):
        def preParse(u):
            if u == None:
                return
            print(" " + str(u.key), end="")
            preParse(u.left)
            preParse(u.right)
        preParse(self.root)
        print("")

    def inorder(self):
        def inParse(u):
            if u == None:
                return
            inParse(u.left)
            print(" " + str(u.key), end="")
            inParse(u.right)
        inParse(self.root)
        print("")

if __name__ == '__main__':
    
    n = int(input())
    command = [input().split(" ") for _ in range(n)]
    T = BinarySearchTree()

    for c in command:
        if c[0] == "insert":
            T.insert(int(c[1]))
        else:
            T.inorder()
            T.preorder()



Measured memory_bytes: 244072
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
cd = [list(map(int, input().split())) for _ in range(m)]

for a, b in ab:
    ans = []
    for c, d in cd:
        tmp = abs(a - c) + abs(b - d)
        ans.append(tmp)
    print(ans.index(min(ans)) + 1)

Measured memory_bytes: 3060
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>

using namespace std;

typedef long long ll;

typedef std::pair<int, int> ipair;
bool lessPair(const ipair& l, const ipair& r){return l.second < r.second;}
bool morePair(const ipair& l, const ipair& r){return l.second > r.second;}

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

const ll MOD = 1e9 + 7;
void add(long long &a, long long b) { a += b; if (a >= MOD) a -= MOD; }

vector<int> places[210000];
ll dp[210000];

int main() {
   
   int N;
   cin >> N;
   vector<int> c(N);
   for (int i = 0; i < N; i++) cin >> c[i];

   for (int i = 0; i < 210000; i++) places[i].clear();
   for (int i = 0; i < N; i++) places[c[i]].push_back(i);

   dp[0] = 1;
   for (int i = 1; i <= N; i++) {
      add(dp[i], dp[i - 1]);

      int color = c[i - 1];
      int it = lower_bound(places[color].begin(), places[color].end(), i - 1) - places[color].begin();
      if (it > 0) {
         int j = places[color][it - 1];
         if ((i - 1) - j > 1) add(dp[i], dp[j + 1]);
      }
   }
   cout << dp[N] << endl;
   return 0;
}


Measured memory_bytes: 13824
// #include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <numeric>
#include <cmath>

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

const int MAX = 100;
const int INF = (1<<12);

int main() {
  int N;
  cin >> N;
  int pay = 0;
  int ans;
  while(pay < N){
    pay += 1000;
  } 
  cout << (pay - N) << endl;
  return 0;
}

Measured memory_bytes: 3224
/* AUTHOR :  SHIVANK JAIN */

#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false)
#define itt cin.tie(0)
#define now cout.tie(0)

using namespace std;

#define ll long long
#define li long int

#define pb push_back
#define rep(i,a,n) for(int i=a;i<n;i++)
#define reprev(i,n,a) for(int i=n;i>=a;i--)
#define endl "\n"

#define vi vector<int>
#define vll vector<ll>
#define vpi vector< pair<int , int> >
#define mapi map<int , int>
#define mapll map<ll ,ll >
#define seti set<int> 

#define fr first
#define se second
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define mp make_pair
#define sort(v) sort(v.begin() , v.end())

#define BIG 1000000007
int gcd(int a, int b) 
{ // builtin function __gcd(a,b)
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 
int main(){

     fast;itt;now;
 
//    #ifndef ONLINE_JUDGE
//    // for getting input from input.txt
//    freopen("input.txt", "r", stdin);
//    // for writing output to output.txt
//     freopen("output.txt", "w", stdout);
//    #endif
    
     ll a,b,c,k;  cin>>a>>b>>c>>k;
     ll s = 0;
     if(a >= k)
      cout<<k<<endl;
     else{
     	s = a;
     	k -= a;
     	
        if(b >= k)
		 cout<<s<<endl;
		else{
			k -= b;
			s -= k;
			cout<<s<<endl;
		} 	
	 } 
     
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define mod 1000000007
#define ull unsigned ll
#define ll long long int
#define ld long double
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define pi acos(-1)
#define nui 100
#define INF 100000000000
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#define F(i,a,n) for(ll i=a;i<n;i++)
#define B(i,a,n) for(ll i=n-1;i>=a;i--)
#define tc int t;cin>>t;while(t--)
#define tcf int t;cin>>t;for(int w=1;w<=t;w++)



using namespace std;

void dex(int a)
{
    if (a == 1)
    {
        cout << "1\n";
    }
    else if (a == -1)
    {
        cout << "-1\n";
    }
    else if (a == 0)
    {
        cout << "0\n";
    }
    else if (a == 2)
    {
        cout << "YES\n";
    }
    else if (a == 3)
    {
        cout << "NO\n";
    }

}

ll binpow(ll a, ll b)
{
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
        {
            res = (res * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}




int main()
{

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    string s, t;
    cin >> s >> t;
    ll ans = t.size();
    for (int i = 0; i < s.size() - t.size() + 1; i++)
    {
        ll ct = 0;
        for (int j = 0; j < t.size(); j++)
        {
            if (s[i + j] != t[j])
            {
                ct++;
            }
        }
        ans = min(ans, ct);

    }

    cout << ans << "\n";

    return 0;

}


Measured memory_bytes: 3664
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <valarray>
#include <vector>

#define EPS 1e-9
#define INF 1070000000LL
#define MOD 1000000007LL
#define fir first
#define foreach(it,X) for(__typeof((X).begin()) it=(X).begin();it!=(X).end();it++)
#define ite iterator
#define mp make_pair
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define pb push_back
#define sec second
#define sz(x) ((int)x.size())

using namespace std;

struct timer{
	time_t start;
	timer(){start=clock();}
	~timer(){cerr<<1.*(clock()-start)/CLOCKS_PER_SEC<<" secs"<<endl;}
};

typedef istringstream iss;
typedef long long ll;
typedef pair<int,int> pi;
typedef stringstream sst;
typedef vector<int> vi;

//
#define MN 10010
int V_bm;
vi G[MN];
int match[MN];
bool used[MN];

void init(int V){
	V_bm=V;
	rep(i,V)G[i].clear();
}

void add_edge(int u,int v){
	G[u].pb(v);
	G[v].pb(u);
}

bool dfs(int v){
	used[v]=1;
	rep(i,sz(G[v])){
		int u=G[v][i], w=match[u];
		if(w<0 || !used[w] && dfs(w)){
			match[v]=u;
			match[u]=v;
			return 1;
		}
	}
	return 0;
}

int bmatch(){
	int res=0;
	memset(match,-1,sizeof(match));
	rep(v,V_bm){
		if(match[v]<0){
			memset(used,0,sizeof(used));
			if(dfs(v))res++;
		}
	}
	return res;
}
//

int h,w,c[111][111];
int vsum[111][111],hsum[111][111];

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	
	while(cin>>h>>w && h){
		h+=2,w+=2;
		memset(c,0,sizeof(c));
		rep2(i,1,h-1)rep2(j,1,w-1){
			char C;cin>>C;
			c[i][j]= C=='#';
		}
		rep2(i,1,h+1)rep(j,w){
			vsum[i][j] = vsum[i-1][j] + c[i][j];
		}
		rep(i,h)rep2(j,1,w+1){
			hsum[i][j] = hsum[i][j-1] + c[i][j];
		}
		
		vector<pi> p;
		rep(i,h-1)rep(j,w-1){
			if(c[i][j]+c[i][j+1]+c[i+1][j]+c[i+1][j+1]==3){
				p.pb(mp(i,j));
			}
		}
		
		vector<pair<pi,pi> > vcut,hcut;
		
		rep(i,sz(p))rep2(j,i+1,sz(p)){
			int y0=p[i].fir,x0=p[i].sec;
			int y1=p[j].fir,x1=p[j].sec;
			if(y0==y1 &&
			hsum[y0][x1]-hsum[y0][x0]==x1-x0 &&
			hsum[y0+1][x1]-hsum[y0+1][x0]==x1-x0){
				hcut.pb(mp(p[i],p[j]));
			}
			if(x0==x1 &&
			vsum[y1][x0]-vsum[y0][x0]==y1-y0 &&
			vsum[y1][x0+1]-vsum[y0][x0+1]==y1-y0){
				vcut.pb(mp(p[i],p[j]));
			}
		}
		
		init(sz(vcut)+sz(hcut));
		rep(i,sz(vcut))rep(j,sz(hcut)){
			int y0=vcut[i].fir.fir,y1=vcut[i].sec.fir;
			int y2=hcut[j].fir.fir;
			int x0=hcut[j].fir.sec,x1=hcut[j].sec.sec;
			int x2=vcut[i].fir.sec;
			if(y0<=y2 && y2<=y1 && x0<=x2 && x2<=x1){
				add_edge(i,j+sz(vcut));
			}
		}
		
		cout<<1+sz(p) - (sz(vcut)+sz(hcut)-bmatch())<<endl;
	}
}

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

int main() {
  int N,ans=0;
  string S;

  cin >> N >> S;

  for (int i = 0; i < S.size()-2;i++){
    if(S.at(i)=='A' && S.at(i+1)=='B' && S.at(i+2)=='C')
      ans++;
  }
  cout << ans;
}


Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) debug(x) debug(y);
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))

template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	string s;
	cin >> s;
	int q;
	cin >> q;
	int cnt = 0;
	deque<char> le, ri;
	int rev = 0;
	rep(i, q){
		int t;
		cin >> t;
		if(t == 1){
			cnt++;
		}
		else{
			int f;
			char c;
			cin >> f >> c;
			if(f == 1){
				if(cnt & 1) ri.push_back(c);
				else le.push_front(c);
			}
			else{
				if(cnt & 1) le.push_front(c);
				else ri.push_back(c);
			}
		}
	}
	if(cnt & 1) reverse(all(s));
	if(cnt & 1) swap(le, ri);
	if(cnt & 1) reverse(all(le)), reverse(all(ri));
	for(char x : le) cout << x;
	cout << s;
	for(char x : ri) cout << x;
	cout << endl;
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/


Measured memory_bytes: 848
def count_section_by_zero(data):
  count = 0
  flg = False
  start = 0
  for i, d in enumerate(data):
    if flg is False and d != 0:
      count += 1
      flg = True
      
    if d == 0:
      flg = False
  return count

def input_list():
  return list(map(int, input().split()))

def input_list_str():
  return list(map(str, input().split()))

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

# 2で割り切れる回数
def divide_two(arg):
  c = 0
  while True:
    if c >= 2:
      break
    if arg % 2 != 0:
      break
    arg //= 2
    c += 1
  return c

# 素因数分解
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def main():
  n, a, b, c, d = input_list()
  s = input()
  dp = []
  has_space = False
  if s[c-1] == '#':
    print('No')
    exit(0)
  if s[d-1] == '#':
    print('No')
    exit(0)
  if c < d:
    for i in range(a-1, c):
      if s[i] == '#' and s[i+1] == '#':
        print('No')
        exit(0)
    for i in range(b-1, d):
      if s[i] == '#' and s[i+1] == '#':
        print('No')
        exit(0)
  else:
    for i in range(a-1, c):
      if s[i] == '#' and s[i+1] == '#':
        print('No')
        exit(0)
     
    for i in range(b-1, d):
      if s[i] == '#' and s[i+1] == '#':
        print('No')
        exit(0)
      if s[i-1] == '.' and s[i+1] == '.' and s[i] == '.':
        has_space = True
    if has_space is False:
      print('No')
      exit(0)

  print('Yes')
  
import math
import fractions
import collections
import itertools
from functools import reduce
main()

Measured memory_bytes: 65644
from bisect import bisect_left

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

l.sort()

ans = 0

for i in range(n):
    for j in range(i+1, n):
        tmp = bisect_left(l, l[i]+l[j]) - 1
        ans += tmp - j

print(ans)


Measured memory_bytes: 74580
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INF INT_MAX // 2147483647
#define INFLL LLONG_MAX // 9223372036854775807
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define per(i, n) for(ll i=((ll)(n))-1; i>=0; i--)
#define perf(i, n) for(ll i=((ll)(n)); i>0; i--)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
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; }
using namespace std;

ll n, m ,q;
vector<tuple<ll, ll, ll, ll>> t;

ll score(const vi &v){
    ll ans = 0;
    rep(i, q){
        ll a = get<0>(t[i]), b = get<1>(t[i]), c = get<2>(t[i]), d = get<3>(t[i]);
        if((v[get<1>(t[i])]-v[get<0>(t[i])]) == get<2>(t[i])) ans += get<3>(t[i]);
    }
    return ans;
}

ll dfs(vi &v){
    if(v.size() == n) return score(v);
    ll ans = 0, back = (v.empty() ? 0 : v.back());
    for(ll i=back; i<m; i++){
        v.push_back(i);
        chmax(ans, dfs(v));
        v.pop_back();
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);
    cin >> n >> m >> q;
    rep(i, q){
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        t.push_back(make_tuple(a-1, b-1, c, d));
    }
    vi v;
    cout << dfs(v) << endl;
}

Measured memory_bytes: 3620
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

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

using namespace std;

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

int nextInt() {int a; cin >> a; return a;}
char nextChar() {char a; cin >> a; return a;}
double nextDouble() {double a; cin >> a; return a;}
string nextString() {string a; cin >> a; return a;}

void inputVector(vector<int> &v, int &n) {rep(i,n){v.push_back(nextInt());}}
void inputVector(vector<double> &v, int &n) {rep(i,n){v.push_back(nextDouble());}}
void inputVector(vector<string> &v, int &n) {rep(i,n){v.push_back(nextString());}}

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

	int K;
	cin >> K;

	rep(i, s.size()) {
		if (i < s.size() - 1 && s[i] == 'a') continue;
		if ('z' - s[i] + 1 <= K) {
			K -= 'z' - s[i] + 1;
			s[i] = 'a';
		}
		
		if (i == s.size() - 1) {
			K %= 26;
			s[i] += K;
			if (s[i] > 'z') {
				s[i] -= 'z';
				s[i] += 'a' - 1;
			}
		}
	}

	cout << s << endl;

    return 0;
}


Measured memory_bytes: 512
#include <stdio.h>
#include <stdbool.h>

bool is_leap_year(int y);

int get_leap_years(int* a, int b, int c);

int main()
{
    int leap_years_list[1000]; //A.D. 0 - A.D. 3000 の間に閏年は高々1000個しかない

    bool first_set = true; //一つ目のセットの前にだけは改行を入れてはいけないので

    while (true) {
        int year_begin, year_end;

        //読み込み
        scanf("%d %d", &year_begin, &year_end);

        //終了判定
        if (year_begin == 0 && year_end == 0) {
            break;
        }

        //閏年を計算する
        int leap_years_count = get_leap_years(leap_years_list, year_begin, year_end);

        //セットとセットの間には空行を入れる
        if (first_set) {
            first_set = false;
        } else {
            putchar('\n'); //putcharは一文字だけ出力する関数です
        }

        //閏年を出力
        if (leap_years_count == 0) {
            puts("NA"); //putsは与えられた文字列を出力した後改行する関数です
        } else {
            for (int i = 0; i < leap_years_count; i++) {
                printf("%d\n", leap_years_list[i]);
            }
        }
        
    }
    return 0;
}

bool is_leap_year(int y)
{
    if (y % 400 == 0) {
        return true; 
    } else if (y % 100 == 0) {
        return false;
    } else {
        return y % 4 == 0;
    }
}

int get_leap_years(int* a, int b, int c)
{
    int s = 0;
    for (int i = 0; b <= c; ++b) {        
        if (is_leap_year(b) == true) {
        a[i] = b;
        ++s;
        ++i;
        }
    }
    return s;
}

Measured memory_bytes: 1044
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <cassert>
#include <cstring>

const int dx[] = {0, 1, 0, -1};
const int dy[] = {-1, 0, 1, 0};
int field[5][5];
using namespace std;
enum FACE{TOP,BOTTOM,NORTH,SOUTH,WEST,EAST};
struct dice{
  int num[6];

  int &operator[](FACE f) { return num[f]; }

  void roll(FACE a, FACE b, FACE c, FACE d) {
    const int tmp = num[a];
    num[a] = num[b];
    num[b] = num[c];
    num[c] = num[d];
    num[d] = tmp;
  }

  void move(int d) {
    switch(d) {
    case 0: roll(TOP, SOUTH, BOTTOM, NORTH); break;
    case 1: roll(TOP, WEST, BOTTOM, EAST);   break;
    case 2: roll(TOP, NORTH, BOTTOM, SOUTH); break;
    case 3: roll(TOP, EAST, BOTTOM, WEST);   break;
    default: assert(false);
    }
  }
};
bool valid(int x,int y){
  return x >= 0 && x < 5 && y >= 0 && y < 5;
}
void dfs(int x,int y,dice &die){
  
  die[BOTTOM] = field[y][x];
  field[y][x] = 0;
  for(int i =0 ;i < 4;i++){
    int nx = x + dx[i];
    int ny = y + dy[i];
    if(valid(nx,ny)){
      if(field[ny][nx]){
		die.move(i);
		dfs(nx,ny,die);
		die.move((i+2)%4);
      }
    }
  }
  
}
bool solve(){
  int cnt[7] = {};
  for(int i = 0;i < 5;i++){
    for(int j = 0;j < 5;j++){
      cin >> field[i][j];
      cnt[field[i][j]]++;
    }
  }
  for(int i = 1;i <= 6;i++){
    if(cnt[i] != 1)return false;
  }
  dice die;
  
  for(int i = 0;i < 5;i++){
    for(int j = 0;j < 5;j++){
      if(field[i][j] != 0){
		dfs(j,i,die);
		goto unloop;
      }
    }
  }
unloop:;

  return die[TOP] + die[BOTTOM] == 7 && die[EAST] + die[WEST] == 7 && die[NORTH] + die[SOUTH] == 7;
}
int main(){
  int n;
  cin >> n;
  while(n--){
    cout << (solve() ? "true" : "false") << endl;
  }
  return 0;
}

Measured memory_bytes: 1152
#include<iostream>
#include<string>
using namespace std;
int main(){
    int m,f,r;
	char a;
	while(true){
		cin>>m>>f>>r;
		if(m==-1&&f==-1&&r==-1)
			break;
		if(m+f>=80)
			a='A';
		if(m+f>=65&&m+f<80)
			a='B';
		if(m+f>=50&&m+f<65)
			a='C';
		if(m+f>=30&&m+f<50){
			a='D';
			if(r>=50)
				a='C';
		}
		if(m+f<30)
			a='F';
		if(m==-1||f==-1)
			a='F';
		cout<<a<<endl;
	}
	return 0;
}

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

char get_grade(int score_m, int score_f, int score_r)
{
  if (score_m == -1 || score_f == -1)
  {
    return 'F';
  }
  if (score_m + score_f >= 80)
  {
    return 'A';
  }
  if (score_m + score_f >= 65)
  {
    return 'B';
  }
  if (score_m + score_f >= 50)
  {
    return 'C';
  }
  if (score_m + score_f >= 30)
  {
    if (score_r >= 50)
    {
      return 'C';
    }
    return 'D';
  }
  return 'F';
}

int main()
{
  while (true)
  {
    int score_m, score_f, score_r;
    cin >> score_m >> score_f >> score_r;
    if (score_m == -1 && score_f == -1 && score_r == -1)
    {
      break;
    }
    cout << get_grade(score_m, score_f, score_r) << endl;
  }
}



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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef long long ll;

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

    if (N % 2 == 1) {
        cout << 0 << endl;
        return 0;
    }

    ll ans = 0;
    ll div = 2 * 5;
    while (N >= div) {
        ans += N / div;
        div *= 5;
    }

    cout << ans << endl;
}

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

#ifdef _DEBUG
#define debug(x) cerr << "line: " << __LINE__ << ", func: " << __func__ << " ->  " << #x << " = " << x << endl
#else
#define debug(x)
#endif

#define all(s) begin(s), end(s)
#define rall(s) rbegin(s), rend(s)
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = ((a)-1); i >= (b); i--)
#define pb push_back
#define sz(a) int((a).size())
#define put(a) ((cout) << (a) << (endl))
#define putf(a, n) ((cout) << (fixed) << (setprecision(n)) << (a) << (endl))
#define deg2rad(x) (((x)*PI) / (180.0))
#define rad2deg(x) (((x) * (180.0)) / PI)
#define fi first
#define se second

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using i_i = pair<int, int>;
using ll_ll = pair<ll, ll>;
using d_ll = pair<double, ll>;
using ll_d = pair<ll, double>;
using d_d = pair<double, double>;
template <class T> using vec = vector<T>;

static constexpr ll LL_INF = 1LL << 60;
static constexpr int I_INF = 1 << 28;
static constexpr double PI = static_cast<double>(3.14159265358979323846264338327950288);
static constexpr double EPS = numeric_limits<double>::epsilon();
static constexpr long double EPSL = numeric_limits<long double>::epsilon();
static constexpr const char* YES = "Yes";
static constexpr const char* NO = "No";

static map<type_index, const char* const> scanType = {
    {typeid(int), "%d"}, {typeid(ll), "%lld"}, {typeid(double), "%lf"}, {typeid(char), "%c"}};

template <class T> static void scan(vector<T>& v);
[[maybe_unused]] static void scan(vector<string>& v, bool isWord = true);
template <class T> static inline bool chmax(T& a, T b);
template <class T> static inline bool chmin(T& a, T b);
template <class T> static inline T gcd(T a, T b);
template <class T> static inline T lcm(T a, T b);
template <class A, size_t N, class T> static void Fill(A (&arr)[N], const T& val);
template <class T> T mod(T a, T m);

int main(int argc, char* argv[]) {
  ll a, b, c;
  cin >> a >> b >> c;

  ll t = c - a - b;
  if ((c - a - b) >= 0 && 4 * a * b < t * t) {
    put(YES);
    return 0;
  }

  put(NO);
  return 0;
}

template <class T> static void scan(vector<T>& v) {
  auto tFormat = scanType[typeid(T)];
  for (T& n : v) {
    scanf(tFormat, &n);
  }
}

static void scan(vector<string>& v, bool isWord) {
  if (isWord) {
    for (auto& n : v) {
      cin >> n;
    }
    return;
  }

  int i = 0, size = v.size();
  string s;
  getline(cin, s);

  if (s.size() != 0) {
    i++;
    v[0] = s;
  }

  for (; i < size; ++i) {
    getline(cin, v[i]);
  }
}

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

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

template <class T> inline T gcd(T a, T b) { return __gcd(a, b); }

template <class T> inline T lcm(T a, T b) {
  T c = min(a, b), d = max(a, b);
  return c * (d / gcd(c, d));
}

template <class A, size_t N, class T> void Fill(A (&arr)[N], const T& val) {
  std::fill((T*)arr, (T*)(arr + N), val);
}

template <class T> T mod(T a, T m) { return (a % m + m) % m; }


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

int main() {
  string t;
  cin >> t;
  
  for (int i = 0; i < t.size(); i++) {
    if (t.at(i) == '?')
      t.at(i) = 'D';
  }
  cout << t << endl;
}

Measured memory_bytes: 3752
#include<iostream>

using namespace std;

void conv(int n, int a[10])
{
	for(int i=0;i<10;i++)
	{
		a[i]=n%2;
		n=n/2;
	}
}

int pow(int x, int n)
{
	int ans=1;
	for(int i=0;i<n;i++)
	{
		ans*=x;
	}
	return ans;
}

int main(void)
{
	int w;
	while(cin>>w)
	{
		int a[10];
		conv(w,a);
		int tmp=0;
		for(int i=0;i<10;i++)
		{	
			if(a[i]==1)
			{
				if(tmp!=0)
				{
					cout<<" ";
				}
				cout<<pow(2,i);
				tmp++;
			}
		}
		cout<<endl;
	}
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
template<class T> inline bool chmax(T&a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T&a,T b){if(a>b){a=b;return 1;}return 0;}
typedef long long ll;

ll n,a,b;
string s,t;

int main() {
  cin >> n >> a >> b;
  ll ans=0;
  if(n==1 && a!=b) ans=0;
  else if(a==b) ans=1;
  else if(a>b) ans=0;
  else ans=(a+(n-1)*b)-((n-1)*a+b)+1;
  cout << ans << endl;
}

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

#define all(container) container.begin(), container.end()
#define sortall(container) (sort(container.begin(), container.end()))
#define yn(cond) ((cond) ? (cout << "Yes" << endl) : (cout << "No" << endl))
#define YN(cond) ((cond) ? (cout << "YES" << endl) : (cout << "NO" << endl))

typedef long long       ll;

typedef vector<int>     vi;
typedef vector<ll>      vll;
typedef vector<double>  vd;
typedef vector<bool>    vb;
typedef vector<char>    vc;
typedef vector<string>  vs;
typedef pair<int, int>  pii;
typedef pair<ll, ll>    pll;
typedef vector<vi>		vvi;
typedef vector<vll>		vvll;
typedef vector<vd>		vvd;
typedef vector<vb>		vvb;
typedef vector<vc>		vvc;
typedef vector<vs>		vvs;
typedef vector<pii>     vpii;
typedef vector<pll>     vpll;

typedef struct edge_ {
	ll to;
	ll cost;
} edge;

typedef struct point_ {
	ll x, y;
	point_(ll x = 0, ll y = 0) : x(x), y(y) {}
} point;

template <typename T>
using mat2d = vector<vector<T>>;

constexpr double	PI = 3.14159265358979323846;
constexpr ll		INF = 1 << 15;
constexpr ll		MOD = (ll)1e9 + 7;
constexpr double	EPS = 1e-7;
constexpr int		dy4[4] = { 0, 1, 0, -1 };
constexpr int		dx4[4] = { 1, 0, -1, 0 };
constexpr int		dy8[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
constexpr int		dx8[8] = { 1, 1, 0, -1, -1, -1, 0, 1 };

template<typename T>
istream& operator >> (istream& is, vector<T>& vec) {
	for (T& x : vec) is >> x;
	return is;
}

template<typename T>
ostream& operator << (ostream& os, const vector<T>& vec) {
	for (const T& x : vec) os << x << "";
	return os;
}

template<typename S, typename T>
istream& operator >> (istream& is, pair<S, T>& p) {
	is >> p.first >> p.second;
	return is;
}

istream& operator >> (istream& is, point& p) {
	is >> p.x >> p.y;
	return is;
}

template<typename S, typename T>
ostream& operator << (ostream& os, const pair<S, T>& p) {
	os << "{" << p.first << " : " << p.second << "}";
	return os;
}

template<typename T>
ostream& operator << (ostream& os, const set<T>& s) {
	for (const T& x : s) os << x << " ";
	return os;
}

ostream& operator << (ostream& os, const edge e) {
	os << "{to: " << e.to << ", cost: " << e.cost << "}";
	return os;
}

ostream& operator << (ostream& os, const point& p) {
	os << "(" << p.x << " " << p.y << ")";
	return os;
}

/******************************************************************************/
/**********************         Don't make WA !!         **********************/
/******************************************************************************/


int main()
{
	int H, W;
	cin >> H >> W;
	vvc C(H, vc(W));
	cin >> C;

	for (auto c : C)
		cout << c << endl << c << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define pll pair<ll,ll>

string s,t;

string lcs_recursive(int index1,int index2,string str){
    if(index1>=s.length() || index2>=t.length())  return str;
    if(s[index1]==t[index2]){
        str.pb(s[index1]);
        return lcs_recursive(index1+1,index2+1,str);
    }
    else{
        string a=lcs_recursive(index1+1,index2,str),b=lcs_recursive(index1,index2+1,str);
        if(a.length()>b.length())   return a;
        return b;
    }
}

string lcs_dp(){
    int dp[s.length()+1][t.length()+1];
    memset(dp,0,sizeof dp);
    int mx=0;
    string ans="";
    for(int i=0;i<s.length();i++){
        for(int j=0;j<t.length();j++){
            if(s[i]==t[j]){
                dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+1);
            }
            dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j]);
            dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1]);
        }
    }
    int i=s.length(),j=t.length();
    while(i>0 && j>0 && dp[i][j]>0){
        while(dp[i][j]==dp[i-1][j]){
            i--;
        }
        while(dp[i][j]==dp[i][j-1]){
            j--;
        }
        ans.pb(s[i-1]);
        i--;j--;
    }
    reverse(ans.begin(),ans.end());
    return ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>s>>t;
    // cout<<lcs_recursive(0,0,"")<<endl;
    cout<<lcs_dp()<<endl;
}


Measured memory_bytes: 35456