akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>

using namespace std;

#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000000000000LL
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define pf push_front
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
#define Eunique(v) v.erace(unique(all(v)),v.end())
#define pvec(v)　rep(i,v.size()){cout << v[i] << " ";}
#define INF 0x3f3f3f3f
#define mset(m,v) memset(m,v,sezeof(m))
#define mod (int)(1e9 +7);

const double pi = acos(-1.0);

typedef vector<int> vi;
typedef string ss;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef deque<ll> dll;
typedef pair<ll,ll> P;
ll dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};

ll gcd(ll x,ll y)
{
    ll r;
    while((r = x % y) != 0)
    {
        x = y;
        y = r;
    }
    return y;
}

ll lcm(ll a,ll b){
    ll g = gcd(a,b);
    return a / g * b; // Be careful not to overflow
}

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

    ll ans = 0;
    vll a(n);
    rep(i,n){
        cin >> a[i];
        ans += a[i] - 1;
    }

    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)

rowrange = 0
colrange = 0
ans = 1
for i in reversed(range(1, N * M + 1)):
    if A == []:
        r = False
    else:
        if A[0] == i:
            r = True
        else:
            r = False

    if B == []:
        c = False
    else:
        if B[0] == i:
            c = True
        else:
            c = False

    if r is True and c is True:
        rowrange += 1
        colrange += 1
        A.pop(0)
        B.pop(0)
    elif r is True and c is False:
        rowrange += 1
        ans = (colrange * ans) % (10 ** 9 + 7)
        A.pop(0)
    elif r is False and c is True:
        colrange += 1
        ans = (rowrange * ans) % (10 ** 9 + 7)
        B.pop(0)
    else:
        ans = ((rowrange * colrange - (N * M - i)) * ans) % (10 ** 9 + 7)
print(ans)


Measured memory_bytes: 3188
/*https://atcoder.jp/contests/abc074/tasks/abc074_b*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
#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
	int n, k, x[100];
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> x[i];
	int dist = 0;
	for (int i = 0; i < n; i++)
	{
		dist += min(2 * abs(k - x[i]), 2 * x[i]);
	}
	cout << dist;

}

Measured memory_bytes: 3652
// abc133c: Remainder Minimization 2019
#include <bits/stdc++.h>
using namespace std;

#define upto(i,s,e,d) for(int i=(s);i<(e);i+=(d))

int main(){
  int l,r; cin>>l>>r;
  int min = 0;
  if(r-l<2019){ // 1周すれば余り0となる数が必ずある
    int a = l%2019, b = r%2019;
    if(a<=b){ //余りの大小が逆転する間に余り0となる数が必ずある
      min = 2018;
      upto(i,a,b,1){
        upto(j,i+1,b+1,1){
          int x = (i*j)%2019;
          if(min>x) min = x;
          if(min==0) break;
        }
        if(min==0) break;
      }
    }
  }
  cout<<min<<endl;
}

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


int main() {

    int n;
    cin >> n;
    if (n % 2 == 0) cout << n/2 - 1 << endl;
    else cout << n/2 << endl;
    return 0;
}

Measured memory_bytes: 256
def inputs(): return [int(x) for x in input().split()]
from collections import defaultdict
def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c
h,w,k= inputs()
s = [list(input()) for _ in range(h)]
res = 10**8
for bit in range(0,1<<h):
    l = popcnt(bit)
    cnt = [0]*(l+1)
    cnt2 = []
    ans = 0
    for i in range(w):
        cnt1=0
        cnt2=[]
        for j in range(h):
            if bit&1<<j and j!=0:
                cnt1+=1
            if s[j][i]=="1":
                cnt[cnt1]+=1
                cnt2.append(cnt1)
                #print(cnt,cnt1,cnt2,j,i)
                if k<cnt[cnt1]:
                    cnt = [0]*(l+1)
                    ans+=1
                    for m in cnt2:
                        cnt[m]+=1
                        if k<cnt[m]:
                            ans+=10**9
    #print(res,ans,l,bit)
    res = min(res,ans+l)
print(res)



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

using namespace std;

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


int main(){
 long k,a,b;
  cin >> k >> a >> b;
  
  if(b-a<=2) {
    cout << k+1 << endl;
  }
    else {
     
      cout << max(long(0),(k-(a-1))/2)*(b-a)+a+((k-(a-1))%2) << endl;
    
    }
  
  }

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstddef>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

// clang-format off
template <typename T> T gcd(T a, T b) { return b == 0 ? a : gcd(b, a % b); }
template <typename T> T lcm(T a, T b) { return a * b / gcd(a, b); }
template <typename T> T clamp(T val, T min, T max) { return val < min ? min : (max < val ? max : val); }
template <typename T> size_t max_index(T begin, T end) { return distance(begin, max_element(begin, end)); }
template <typename T> size_t min_index(T begin, T end) { return distance(begin, min_element(begin, end)); }
// clang-format on

#define int long long
#define YES "Yes"
#define NO  "No"

using namespace std;

signed main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  int num;

  int n; cin >> n;
  int m = 0;
  vector<int> a(n);
  for (auto it = a.begin(); it != a.end(); ++it) {
    cin >> *it;
    if (*it <= 0) ++m;
  }

  num = 0;
  if (m % 2 == 0) {
    for (int i = 0; i < n; ++i) num += abs(a[i]);
  } else {
    int tmp = abs(a[0]); // min abs(a[i])
    for (int i = 0; i < n; ++i) {
      num += abs(a[i]);
      tmp = min(abs(a[i]), tmp);
    }
    num -= 2 * tmp;
  }
  
  cout << num << endl;
  
  return 0;
}


Measured memory_bytes: 1024
#include <cstdio>
long long n, s, x, y, a[100005];
int main() {
	int i;
	scanf("%lld", &n);
	for(i=0; i<n; i++) scanf("%lld", &a[i]);
	for(i=0; i<n; i++) {
		s += a[i];
		if(i%2) {
			if(s<=0) x += 1-s, s=1;
		} else {
			if(s>=0) x += s+1, s=-1;
		}
	}
	for(i=s=0; i<n; i++) {
		s += a[i];
		if(i%2) {
			if(s>=0) y += s+1, s=-1;
		} else {
			if(s<=0) y += 1-s, s=1;
		}
	}
	printf("%lld", x<y ? x:y);
	return 0;
}

Measured memory_bytes: 896
n, m = gets.chomp.split.map(&:to_i)
demands = m.times.map do
  gets.chomp.split.map(&:to_i)
end.sort_by{|d| [d[0],d[1]]}

cnt = 0
max = demands[0][1]
(demands.size - 1).times do |i|
  if max <= demands[i + 1][0]
    cnt += 1
    max = Float::INFINITY
  end

  max = [max, demands[i + 1][1]].min
end

puts(cnt + 1)

Measured memory_bytes: 26256
#include<iostream>
using namespace std;
int main(){
  int n;
  long long array[100];
  long long money=1000;
  long long cnt=0;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>array[i];
  }
  
  int index=0;
  while(array[index]==array[index+1]){
    index++;
  }
  if(array[index]<array[index+1]){
    long long a=money/array[index];
    money-=a*array[index];
    cnt+=a;
  }
  for(int i=index;i<n-1;i++){
    if(array[i-1]>=array[i]&&array[i]<array[i+1]){
      long long a=money/array[i];
      money-=a*array[i];
      cnt+=a;
    }else if(array[i-1]<=array[i]&&array[i]>=array[i+1]){
      money+=cnt*array[i];
      cnt=0;
    }
  }
  
  money+=cnt*array[n-1];
  cout<<money<<endl;
  return(0);
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, a, b) for(int i = (a); i <= (b); i++)
#define PER(i, a, b) for(int i = (a); i >= (b); i--)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define all(S) (S).begin(), (S).end()
#define pf push_front
#define pb push_back
#define mk make_pair
#define S second
#define F first
typedef long long ll;
typedef long double lf;
typedef pair<int, int> ii;
const int MAX = 2e5+5;

int main(int argc, char** argv) {
	int N; scanf("%d", &N);
	while(N > 0) N -= 1000;
	printf("%d\n", -N);
	return 0;
}


Measured memory_bytes: 3828
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<int, int>;
using VI = vector<int>;

const ll MAX = 1e9 + 10;

struct node {
  node(ll a, ll b) : a(a), b(b) {}

  ll a, b;
  bool operator<(const node& other) const {
    return b * other.a < a * other.b;
  }
  ll advance(ll t) const {
    return min(MAX, (a + 1) * (t + 1) + b - 1);
  }
};

int main() {
#ifdef LOCAL_EXEC
//	freopen("sample.in", "r", stdin);
//	freopen("sample.out", "w", stdout);
#else
  ios_base::sync_with_stdio(false); cin.tie(NULL);
#endif

  int n; ll T; cin >> n >> T;
  vector<node> vals;
  vector<ll> zero;
  while (n--) {
    ll a, b; cin >> a >> b;
    ++b;
    if (a == 0) zero.push_back(b);
    else vals.emplace_back(a, b);
  }
  sort(vals.begin(), vals.end());

  n = vals.size();
  const int LOG = 40;
  vector<vector<ll>> best(n + 1, vector<ll>(LOG, MAX));
  best[0][0] = 0;
  for (int i = 1; i <= n; i++) {
    best[i][0] = 0;
    for (int j = 1; j < LOG; j++) {
      best[i][j] = min(best[i - 1][j], vals[i - 1].advance(best[i - 1][j - 1]));
    }
  }

  sort(zero.begin(), zero.end());
  ll extra = 0;
  for (ll z: zero) extra += z;
  int ans = 0;
  for (int j = 0, e = zero.size(); j < LOG; j++) {
    ll rem = T - best[n][j];
    if (rem < 0) break;
    while (extra > rem) {
      extra -= zero[--e];
    }
    ans = max(ans, j + e);
  }
  cout << ans << endl;

  return 0;
}


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

using namespace std;

#define FOR(i, n) for(int i = 0; i < (int) n; i++)
#define all(x) x.begin(), x.end()
#define PB push_back
#define F first
#define S second

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

struct FT{
	int n;
	vi v;
	FT(int n){
		this->n = n;
		v.assign(n+1, 0);
	}
	int sum(int i){
		int ans = 0;
		for(; i>0; i-=(i&(-i)))
			ans += v[i];
		return ans;
	}
	void add(int i, int x){
		for(; i<=n; i+=(i&(-i)))
			v[i]+=x;
	}
};

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

	int n; cin >> n;
	string s; cin >> s;
	//n = s.size();
	vector<FT> v(26, FT(n));

	FOR(i, n){
		v[s[i]-'a'].add(i+1, 1);
	}

	int m; cin >> m;
	FOR(i, m){
		int op; cin >> op;
		if(op == 2){
			int a, b; cin >> a >> b;
			int cnt = 0;
			FOR(j, 26){
				if(v[j].sum(b)-v[j].sum(a-1) > 0){
					cnt++;
				}
			}
			cout << cnt << '\n';
		}else{
			int idx; cin >> idx;
			idx--;
			char c; cin >> c;
			v[s[idx]-'a'].add(idx+1, -1);
			v[c-'a'].add(idx+1, 1);
			s[idx] = c;
		}
	}

	return 0;
}

Measured memory_bytes: 53660
#include <iostream>
#include <vector>

#include <map>
using namespace std;
int getEqualNum(vector<int> &v1,int &noequal,int &equal)
{
	noequal=0;
	equal=0;
	int num=v1.size();
	if (num==0){
		return 0;
	}
	map<int,int> mapV;
	map<int,int>::iterator mit;
	for (int i=0;i<num;i++){
		mit=mapV.find(v1[i]);
		if (mit==mapV.end()){
			mapV.insert(map<int,int>::value_type(v1[i],1));
		}else{
			(*mit).second++;
		}
	}

	for (mit=mapV.begin();mit!=mapV.end();mit++){
		if ((*mit).second==1){
			noequal++;
		}else{
			noequal+=(*mit).second%2;
			equal+=(*mit).second/2;
		}
	}
	mapV.clear();
	return 0;
}
int getPair(vector<int> &v1,vector<int> &v2)
{
	int num1=v1.size();
	int num2=v2.size();
	if (num1==0 || num2==0){
		return 0;
	}
	if (num1==num2){
		v1.clear();
		v2.clear();
		return num1;
	}
	vector<int> *pMax;
	int maxNum=max(num1,num2);
	int minNum=min(num1,num2);
	if (num1>num2){
		pMax = &v1;
	}else{
		pMax=&v2;
	}
	int num;
	int noequal;
	int equal;
	getEqualNum(*pMax,noequal,equal);
	if (noequal<minNum){
		equal-=(minNum-noequal+1)/2;
	}
	num= minNum+equal;
	v1.clear();
	v2.clear();
	return num;
}


int main(int argc, char* argv[])
{
	int N,M;
	cin>>N>>M;
	if (M==1){
		cout<<N/2<<endl;
		return 0;
	}
	int i;
	int v;
	vector<int> *Mod = new vector<int>[M+1];
	for (i=0;i<N;i++){
		cin>>v;
		Mod[v%M].push_back(v);
	}
	size_t aw=0;
	aw+=Mod[0].size()/2;
	Mod[0].clear();
	for (i=1;i<M;i++){
		if (Mod[i].size()>0){
			if (i==M-i){
				aw += Mod[i].size()/2;
				continue;
			}else{
				aw+=getPair(Mod[i],Mod[M-i]);
			}
			int noequal;
			int equal;
			getEqualNum(Mod[i],noequal,equal);
			aw+=equal;
		}
	}
	cout<<aw<<endl;
	delete[] Mod;
	return 0;
}

Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    for (int i = 0; i < n;i++){
        int q;
        cin >> q;
        p.at(q-1)++;
    }
    
    sort(p.begin(), p.end());
    reverse(p.begin(), p.end());
    int ans=n;
    for (int i = 0; i < k;i++){
        ans -= p.at(i);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
### constant

MAX_INT = (1 << 31) - 1

### main

while true
  n = gets.strip.to_i
  break if n == 0

  m = 0
  rs = []

  n.times.each do
    ri = gets.strip.split(' ').map{|s| s.to_i}
    rs << ri

    m = ri[0] if m < ri[0]
    m = ri[1] if m < ri[1]
  end

  edges = (m + 1).times.map{(m + 1).times.map{nil}}

  rs.each do |ai, bi, ci|
    edges[ai][bi] = edges[bi][ai] = ci
  end

  cities = (0..m).map{|i| i}

  min_st = -1
  min_sum = MAX_INT

  for st in cities
    q = cities.clone
    dists = cities.map{MAX_INT}
    dists[st] = 0

    while ! q.empty?
      u = q.min{|a, b| dists[a] <=> dists[b]}
      q.delete(u)

      for v in cities
        c = edges[u][v]
        next if c.nil?

        if dists[v] > dists[u] + c
          dists[v] = dists[u] + c
        end
      end
    end

    sum = dists.inject(0){|s, d| s + d}

    if min_sum > sum
      min_sum = sum
      min_st = st
    end
  end

  puts [min_st, min_sum].join(' ')
end

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



int getDigitSum(int x){
	int sum = 0;
	while(x>0){
		sum += x%10;
		x = x/10;
	}
	return sum;
}

int N,A,B;

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

    int sum;

    for (int i = 1; i <= N; i++)
    {
        int digitSum = getDigitSum(i);
        if(A<=digitSum && digitSum<=B) sum += i;
    }
    cout << sum << endl;
    return 0;
}


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

int main() {
    int n,m;
    cin>>n>>m;
    long long max=0,min=1000000;
    vector<int> lr(2*m);
    for(int i=0;i<2*m;i++){
        cin>>lr.at(i);
    }
    for(int i=0;i<2*m;i+=2){

        if(max<lr.at(i)){
            max=lr.at(i);
        }
    }
    for(int i=1;i<2*m;i+=2){
        if(min>lr.at(i)){
            min=lr.at(i);
        }
    }
    if(min>=max){
        cout<<min-max+1<<endl;
    }else{
        cout<<"0"<<endl;
    }
    

}

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

int main(){
    int n; cin >> n;
    set<string> s;
    rep(i,n){
        string t;
        cin >> t;
        s.insert(t);
    }

    put(s.size());
}

Measured memory_bytes: 19120
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define INF 2 << 29
#define MOD 1000000007
#define Yes(f) puts((f)? "Yes" : "No")
#define YES(f) puts((f)? "YES" : "NO")
int gcd(int a, int b) {
	if (b != 0)return gcd(b, a % b);
	return a;
}
int lcm(int a, int b) {
	return a / gcd(a, b) * b;
}
using Graph = vector<vector<int>>;

int main(){
    int ans = 0;
    string s, t;
    cin >> s >> t;
    rep(i, 3) if(s[i] == t[i]) ans++;
    cout << ans << endl; 
}

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

template <unsigned mod>
struct Z_p {
    unsigned val;

    Z_p() : val(0) {}
    Z_p(long long y) : val(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

    Z_p &operator+=(const Z_p &p) {
        if ((val += p.val) >= mod) val -= mod;
        return *this;
    }
    Z_p &operator-=(const Z_p &p) {
        if ((val += mod - p.val) >= mod) val -= mod;
        return *this;
    }
    Z_p &operator*=(const Z_p &p) {
        val = (unsigned)(1LL * val * p.val % mod);
        return *this;
    }
    Z_p &operator/=(const Z_p &p) {
        *this *= p.inverse();
        return *this;
    }

    Z_p operator-() const {
        return Z_p(val == 0 ? 0 : mod - val);
    }
    Z_p operator+(const Z_p &p) const {
        return Z_p(*this) += p;
    }
    Z_p operator-(const Z_p &p) const {
        return Z_p(*this) -= p;
    }
    Z_p operator*(const Z_p &p) const {
        return Z_p(*this) *= p;
    }
    Z_p operator/(const Z_p &p) const {
        return Z_p(*this) /= p;
    }

    bool operator==(const Z_p &p) const {
        return val == p.val;
    }
    bool operator!=(const Z_p &p) const {
        return val != p.val;
    }

    Z_p inverse() const {
        int a = val, b = mod, u = 1, v = 0, t;
        while (b > 0) {
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return Z_p(u);
    }

    Z_p pow(int64_t n) const {
        Z_p res(1), mul(val);
        while (n > 0) {
            if (n & 1) res *= mul;
            mul *= mul;
            n >>= 1;
        }
        return res;
    }

    friend ostream &operator<<(ostream &os, const Z_p &p) {
        return os << p.val;
    }
    friend istream &operator>>(istream &is, Z_p &a) {
        int64_t t;
        is >> t;
        a = Z_p<mod>(t);
        return (is);
    }

    static int get_mod() {
        return mod;
    }
};

const lint mod = 1e9 + 7;
lint n, m;
vector<lint> x, y;

int main() {
    cin >> n >> m;
    x.resize(n);
    y.resize(m);
    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> y[i];
    }
    Z_p<mod> s = 0;
    for (int i = 0; i < n - 1; i++) {
        Z_p<mod> left = 1 + i;
        Z_p<mod> right = n - 1 - i;
        s += left * right * (x[i + 1] - x[i]);
    }
    Z_p<mod> ans = 0;
    for (int i = 0; i < m - 1; i++) {
        Z_p<mod> left = 1 + i;
        Z_p<mod> right = m - 1 - i;
        Z_p<mod> height = y[i + 1] - y[i];
        ans += s * left * right * height;
    }
    cout << ans << endl;
}

Measured memory_bytes: 4796
n = gets.to_i

#計算を簡単にするためa[0] = a[n+1] = 0とする
a = gets.split.map(&:to_i)
a << 0
a.unshift(0)

#予定通りに行動した場合のコスト
s = 0
0.upto(n) do |i|
  s += (a[i+1] - a[i]).abs
end

1.upto(n) do |i|
  puts s - (a[i]-a[i-1]).abs - (a[i+1]-a[i]).abs + (a[i+1] - a[i-1]).abs
end


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

void check(int N)
{
  while(N){
    int a  = N%10 ;
    if(a==7){
        cout << "Yes" ;
        return ;
    } 
    N = N/10;
  }
  cout << "No" ;
}

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


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


int main() {
	int n, k;
	cin >> n >> k;
	vector<int> a(n) ,mx(n, n);
	rep(i, n) cin >> a[i];
	rep(q, k) {
		vector<int> b(n);
		rep(i, n) {
			int l = max(0, i-a[i]);
			int r = min(n, i+a[i]+1);
			b[l]++;
			if (r < n) b[r]--;
		}
		for(int i = 1; i < n; i++) b[i] += b[i-1];
		a = b;
		if (a == mx) break;
	}
	rep(i, n) cout << a[i] << ((i == n-1) ? '\n': ' ');
	return 0;
}

Measured memory_bytes: 5640
#include <iostream>
#include <cstdio>
#define size 32
using namespace std;
int N,M,A,B,C,D,x1,x2,y1,y2;
int cost;
int K[size][size];
const int inf = 1001001001;

int main(){
	for(int i=1; i<size ; i++){
		for(int j=1 ; j<size ; j++){
			K[i][j]=inf;
		}
	}// 行列初期化

	scanf("%d %d",&N,&M);
	for(int i=0; i< M ;++i){
	scanf("%d,%d,%d,%d",&A,&B,&C,&D);
	K[A][B]=C;
	K[B][A]=D;
	}//初期化完了


	for(int k=1 ; k<N+1 ; k++){
		for(int i=1 ; i<N+1; i++){
			for(int j=1 ; j<N+1; j++){
				if(K[i][j] > K[i][k] + K[k][j]){
					K[i][j] = K[i][k]+K[k][j];
				}
			}
		}
	}//i-j間最短路のコスト計算

	scanf("%d,%d,%d,%d",&x1,&x2,&y1,&y2);
	cost= y1-y2-K[x1][x2]-K[x2][x1];
	cout << cost << endl;
}

Measured memory_bytes: 1212
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <tuple>
#include <set>
#include <map>
#include <complex>
#include <iomanip>
#include <cmath>
using namespace std;
typedef long long ll;

int main()
{
  string s;
  cin >> s;
  s[5] = ' ';
  s[13] = ' ';

  cout << s << endl;
}


Measured memory_bytes: 256
#最大増加部分列（Longest Increasing Subsequence）
def LIS(N,a,H):
  """数列の長さN, 数列a→最大増加部分列の長さ
  計算量はNlogN"""
  dp = [H+1]*len(a)#??
  for i,f in enumerate(a):
    dp[bisect(dp,f)] = f
  return bisect(dp,H)

import math 
x1,y1,x2,y2=map(int,input().split())
N=int(input())
W=abs(x2-x1)
H=abs(y2-y1)
xsgn=2*(x2>x1)-1
ysgn=2*(y2>y1)-1
XY=[]
for i in range(N):
  x,y=map(int,input().split())
  if (x-x1)*(x-x2)<=0 and (y-y1)*(y-y2)<=0:
    XY+=[[xsgn*(x-x1),ysgn*(y-y1)]]
N=len(XY)
short=20-5*math.pi
long=10*math.pi-20
straight=100*(W+H)
from bisect import bisect
 
# find LIS
XY.sort()
Y = [y for x,y in XY]

fountain=LIS(N,Y,H)

if fountain<min(W,H)+1:
  print(straight-short*fountain)
else:
  print(straight-short*(fountain-1)+long)

Measured memory_bytes: 40164
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(),(obj).end()
#define RALL(obj) (obj).rbegin(),(obj).rend()
#define REP(i, n) for(int i=0;i<(n);++i)
#define RANGE(i, a, b) for(int i=(a);i<(b);++i)
#define RREP(i, n) for(int i=(n)-1;i>= 0;--i)

#define endl '\n'
#define pb push_back
#define eb emplace_back
#define pque priority_queue
#define umap unordered_map
#define uset unordered_set
#define BIG 2000000000
#define VERYBIG 1000000000000000ll
#define PI 3.141592653589793238
#define dcout cout<<fixed<<setprecision(20)

const long long dx[]={1,0,-1,0,1,1,-1,-1}, dy[]={0,-1,0,1,1,-1,1,-1};
const long long MOD = 1e9+7;

// typedef long long ll;
#define int long long
#define double long double

template<typename T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template<typename T> inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template<typename T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template<typename T> inline T nHr(T a,T b){return nCr(a+b-1,b);}
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 pair<int, int> INTP;
typedef vector<int> INTV;
struct edge2 {int to, cost;};
struct edge3 {int from, to, cost;};

int dp[3010][3010];

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

  string S, T; cin >> S >> T;
  const int N = S.size(), M = T.size();

  string ans = "";
  REP(i, N) REP(j, M){
  	if(S[i] == T[j]){
  		chmax(dp[i+1][j+1], dp[i][j]+1);
  	} else {
  		chmax(dp[i+1][j+1], max(dp[i][j+1], dp[i+1][j]));
  	}
  }
  cerr << dp[N][M] << endl;
  {
  	int i = N, j = M;
  	while(i >= 1 and j >= 1){
  		if(S[i-1] == T[j-1]){
  			ans = S[i-1] + ans;
  			i--; j--;
  		} else {
  			if(dp[i][j] == dp[i-1][j]) i--;
  			else j--;
  		}
  	}
  }
  cout << ans << endl;
}


Measured memory_bytes: 70784
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
using vll=vector<ll>;
using vvll=vector<vll>;
using vpii=vector<pii>;


void max_u(int&m, int v)
{
	if(m<v) m=v;
}


void min_u(int&m, int v)
{
	if(m>v) m=v;
}


int calc(char*s, vpii&td, int p)
{
	for(auto mtd:td)
	{
		if(mtd.first==s[p])
		{
			p+=mtd.second;

			if(s[p]=='\0') return 1-2*(p<0);
		}
	}
	return 0;
}


int bs(char*s, vpii&td, int n)
{
	int a=0, b=n-1;
	int ret=-1;

	while(a<=b)
	{
		int c=(a+b)/2;
		int r=calc(s, td, c);

		if(r<0)
		{
			a=c+1;
			ret=c;
		}
		else
		{
			b=c-1;
		}
	}
	return ret;
}


int bs2(char*s, vpii&td, int n)
{
	int a=0, b=n-1;
	int ret=n;

	while(a<=b)
	{
		int c=(a+b)/2;
		int r=calc(s, td, c);

		if(r>0)
		{
			b=c-1;
			ret=c;
		}
		else
		{
			a=c+1;
		}
	}
	return ret;
}


int main(void)
{
	int n, q;
	char sa[200000+3], *s=sa+1;


	while(scanf("%d%d%200000s", &n, &q, s)==3)
	{
		vpii td(q);

		s[-1]=s[n]='\0';

		for(int i=0;i<q;i++)
		{
			char t[1+2], d[1+2];
			scanf("%1s%1s", t, d);

			td[i]=make_pair((int)t[0], (d[0]=='R')?1:-1);
		}

		int ans=n-min(bs(s, td, n)+1+n-bs2(s, td, n), n);
		printf("%d\n", ans);
	}
	return 0;
}


Measured memory_bytes: 2048
#include <stdio.h>
#include <string.h>
 
int main(void){
  int i,n = 0;
  char w[11], t[1001];
 
  scanf("%s", w);
 
  do{
    scanf("%s",t);
    if(!strcmp(t,"END_OF_TEXT")) break;
      for(i=0;t[i]!='\0';i++)
        if(t[i]<91) t[i] += 32;
    if( !strcmp(w,t) ) n++;
  }while(1);
 
  printf("%d\n",n);
 
  return 0;
}


Measured memory_bytes: 2044
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

#define INF 1000000021
#define MOD 1000000007
#define pb push_back
#define sqr(a) (a)*(a)
#define M(a, b) make_pair(a,b)
#define T(a, b, c) make_pair(a, make_pair(b, c))
#define F first
#define S second
#define all(x) (x.begin(), x.end())
#define deb(x) cerr << #x << " = " << x << '\n'
#define N 222222

using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

const ld pi = 2 * acos(0.0);
template<class T> bool umin(T& a, T b){if(a>b){a=b;return 1;}return 0;}
template<class T> bool umax(T& a, T b){if(a<b){a=b;return 1;}return 0;}
template<class T, class TT> bool pal(T a, TT n){int k=0;for(int i=0;i<=n/2;i++){if(a[i]!=a[n-i-1]){k=1;break;}}return k?0:1;}

//int month[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

int main()
{
	int a, b, c, k;
	cin >> a >> b >> c >> k;
	while(b <= a && k)
	{
		k --;
		b *= 2;
	}
	while(c <= b && k)
	{
		c *= 2;
		k --;
	}
	cout << (b > a && c > b ? "Yes" : "No");




	





	getchar();
	getchar();
	return 0;
	//ios::sync_with_stdio(false);
	//cin.tie(0);
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define FOR(i, a, n) for(int (i) = (int)(a); (i) < (int)(n); ++(i))
#define FORe(i, a, n) for(int (i) = (int)(a); (i) <= (int)(n); ++(i))
#define rFOR(i, a, n) for(int (i) = (int)(n)-1; (i) >= (int)(a); --(i))
#define rFORe(i, a, n) for(int (i) = (int)(n); (i) >= (int)(a); --(i))
#define REP(i, n) FOR((i), 0, (n))
#define REPe(i, n) FORe((i), 1, (n))
#define REPo(i, n) FORe((i), 0, (n))
#define rREP(i, n) rFOR((i), 0, (n))
#define rREPe(i, n) rFORe((i), 1, (n))
#define rREPo(i, n) rFORe((i), 0, (n))
#define rep(i, n) FOR((i), 0, (n))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second
#define dup(x, y) (((x)+(y)-1)/(y))
#define vc(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
using ll = long long;
using P = pair<int,int>;
using pll = pair<ll,ll>;
using T = tuple<int,int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vs = vector<string>;
using vp = vector<P>;
using vt = vector<T>;

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; }

int main() {
  string s,t;
  cin>>s>>t;
  int ans = 0;
  REP(i, s.size()) {
    if(s[i] != t[i]) ans++;
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3912
from bisect import bisect_left
A, B, Q = map(int, input().split())
s = [int(input()) for _ in range(A)]+[10**15]
t = [int(input()) for _ in range(B)]+[10**15]

for _ in range(Q):
    x = int(input())

    # x -> s -> t
    dist1, dist2 = 0, 0
    p1 = bisect_left(s, x)
    x1, x2 = s[p1-1], s[p1]
    dist1 += abs(x-x1)
    dist2 += abs(x-x2)

    p3 = bisect_left(t, x1)
    x3, x4 = t[p3-1], t[p3]
    dist1 += min(abs(x1-x3),abs(x1-x4))

    p3 = bisect_left(t, x2)
    x3, x4 = t[p3-1], t[p3]
    dist2 += min(abs(x2-x3),abs(x2-x4))

    dist_st = min(dist1, dist2)

    # x -> t -> s

    dist1, dist2 = 0, 0
    p1 = bisect_left(t, x)
    x1, x2 = t[p1-1], t[p1]
    dist1 += abs(x-x1)
    dist2 += abs(x-x2)

    p3 = bisect_left(s, x1)
    x3, x4 = s[p3-1], s[p3]
    dist1 += min(abs(x1-x3),abs(x1-x4))

    p3 = bisect_left(s, x2)
    x3, x4 = s[p3-1], s[p3]
    dist2 += min(abs(x2-x3),abs(x2-x4))

    dist_ts = min(dist1, dist2)

    print(min(dist_st, dist_ts))

Measured memory_bytes: 14872
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define ull unsigned long long int
#define ll long long int
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define MOD (ull)(double)(1e9 + 7)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vb vector<bool>
#define vd vector<double>
#define vll vector<ll>
#define vpii vector<pii>
#define vpll vector<pll>
#define vvi vector<vi>
#define vvll vector<vll>
#define vs vector<string>
#define pull pair<ull, ull>
#define F first
#define S second
#define m_p make_pair
#define debug(x) cout << #x << " " << x << endl
#define printArr(a, start, end)for(int i=start ; i<end ; ++i)cout << a[i] << " ";cout << '\n';
#define readArr(a, start, end)for(int i=start ; i<end ; ++i)cin >> a[i];
#define read2D(mat, n, m)for(int i=0 ; i<n ; ++i)for(int j=0 ; j<m ; ++j)cin >> mat[i][j];

const long double PI = 3.141592653589793238462643383279502884197169399;

// Find Set LSB = (x&(-x)), isPowerOfTwo = (x & (x-1))

void solve(){
	int n;
	cin >> n;
	
	vll a(n);
	for(ll& x : a)cin >> x;
	
	ll mon=1000, stocks=0;
	for(int i=0 ; i<n ; ++i){
		if(!stocks){
			ll mn=a[i];
			++i;
			while(i < n && a[i] <= mn){
				mn = a[i];
				++i;
			}
			if(i == n)break;
			--i;
			stocks = mon / a[i];
			mon = mon % a[i];
		}
		else{
			ll mx = a[i];
			++i;
			while(i<n && a[i] >= mx){
				mx = a[i];
				++i;
			}
			--i;
			mon += stocks * a[i];
			stocks=0;
		}
	}
	
	cout << mon;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int tt=1;
	//cin >> tt;
	
	while(tt--){
		solve();
	}
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
const int64_t INF=9999999999999999;
int main() {
 int N;
 cin>>N;
 int v[30];
 int c[30];
 int ans=0;
 for(int i=0;i<N;i++){
    cin>>v[i];
 }
 for(int i=0;i<N;i++){
    cin>>c[i];
 }
 for(int i=0;i<N;i++){
    if(v[i]-c[i]>0){ans+=v[i]-c[i];}
 }
 cout<<ans<<endl;
 return 0;}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
#define PI 3.14159265
#define pb push_back
int main()
{
	while(1)
	{
		int h,r;
		double x[105];
		double y[105];
		cin >> h >> r;
		if(h == 0 && r == 0) return 0;
		for(int i=0;i<h;i++)
		{
			scanf("%lf %lf",&x[i],&y[i]);
		}
		int u,m,s;
		double du,dm,ds;
		scanf("%d%d%d%lf%lf%lf",&u,&m,&s,&du,&dm,&ds);
		double ux[15],uy[15];
		double mx[15],my[15];
		double sx[15],sy[15];
		for(int i=0;i<u;i++) scanf("%lf %lf",&ux[i],&uy[i]);
		for(int i=0;i<m;i++) scanf("%lf %lf",&mx[i],&my[i]);
		for(int i=0;i<s;i++) scanf("%lf %lf",&sx[i],&sy[i]);
		double w[105],a[105];
		for(int i=0;i<r;i++)
		{
			scanf("%lf %lf",&w[i],&a[i]);
		}
		vector<int>ans;
		int res = 1;
		for(int i=0;i<h;i++)
		{
			bool ok[105]={};
			{
				double ang = atan2(y[i],x[i])*180.0/PI;
				if(ang < 0.0) ang += 360.0;
				for(int k=0;k<r;k++)
				{
					double beg = w[k]-du/2.0;
					double en = w[k]+du/2.0;
					if(beg < 0.0) {beg += 360.0; en += 360.0;}
					if( (beg <= ang && ang <= en) || (beg <= ang+360.0 && ang+360.0 <= en) )
					{
						if((x[i])*(x[i])+(y[i])*(y[i]) <= a[k]*a[k])
						{
							ok[k] = true;
						}
					}
				}
			}
			for(int j=0;j<u;j++)
			{
				double ang = atan2(y[i]-uy[j],x[i]-ux[j])*180.0/PI;
				if(ang < 0.0) ang += 360.0;
				for(int k=0;k<r;k++)
				{
					double beg = w[k]-du/2.0;
					double en = w[k]+du/2.0;
					if(beg < 0.0) {beg += 360.0; en += 360.0;}
					if( (beg <= ang && ang <= en) || (beg <= ang+360.0 && ang+360.0 <= en) )
					{
						if((x[i]-ux[j])*(x[i]-ux[j])+(y[i]-uy[j])*(y[i]-uy[j]) <= a[k]*a[k])
						{
							ok[k] = false;
						}
					}
				}
			}
			for(int j=0;j<m;j++)
			{
				double ang = atan2(y[i]-my[j],x[i]-mx[j])*180.0/PI;
				if(ang < 0.0) ang += 360.0;
				for(int k=0;k<r;k++)
				{
					double beg = w[k]-dm/2.0;
					double en = w[k]+dm/2.0;
					if(beg < 0.0) {beg += 360.0; en += 360.0;}
					if( (beg <= ang && ang <= en) || (beg <= ang+360.0 && ang+360.0 <= en) )
					{
						if((x[i]-mx[j])*(x[i]-mx[j])+(y[i]-my[j])*(y[i]-my[j]) <= a[k]*a[k])
						{
							ok[k] = false;
						}
					}
				}
			}
			for(int j=0;j<s;j++)
			{
				double ang = atan2(y[i]-sy[j],x[i]-sx[j])*180.0/PI;
				if(ang < 0.0) ang += 360.0;
				for(int k=0;k<r;k++)
				{
					double beg = w[k]-ds/2.0;
					double en = w[k]+ds/2.0;
					if(beg < 0.0) {beg += 360.0; en += 360.0;}
					if( (beg <= ang && ang <= en) || (beg <= ang+360.0 && ang+360.0 <= en) )
					{
						if((x[i]-sx[j])*(x[i]-sx[j])+(y[i]-sy[j])*(y[i]-sy[j]) <= a[k]*a[k])
						{
							ok[k] = false;
						}
					}
				}
			}
			int c = count(ok,ok+r,true);
			if(res == c) ans.pb(i+1);
			else if(res < c)
			{
				ans.clear(); res = c; ans.pb(i+1);
			}
		}
		if(ans.empty()) puts("NA");
		else for(int i=0;i<ans.size();i++) printf("%d%c",ans[i],(i==ans.size()-1)?'\n':' ');
	}
}

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

#define FOR(i, j, k) for(int i = j; i < k; i++)
#define REP(i, j) FOR(i, 0, j)
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;

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> istream &operator>>(istream &is, vector<T> &vec) {
    for(T &x : vec)
        is >> x;
    return is;
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, x;
    cin >> n >> x;
    vi l(n);
    cin >> l;

    int ans = 1;
    int d = 0;
    FOR(i, 1, n + 1) {
        d += l[i - 1];
        if(d <= x)
            ans++;
    }

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
constexpr int MOD = 1e9 + 7;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int s;
	cin >> s;
	vector<int> dp(2020);
	dp[0] = 1;
	for (int i = 0; i <= s; i++) {
		for (int j = 3; j + i <= s; j++) {
			(dp[i + j] += dp[i]) %= MOD;
		}
	}
	cout << dp[s] << "\n";
	return 0;
}

Measured memory_bytes: 3588
#include <stdio.h>
int main(){
    int a,b;
    scanf("%d %d",&a,&b);
    if(a==b){
    printf("a == b\n");
    }
    if(a<b){
    printf("a < b\n");
    }
    if(a>b){
    printf("a > b\n");
    }
    return 0;
}






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

using ll = long long;

constexpr ll MOD = 1e9+7;
constexpr ll INF = 1ll<<60;

#define FOR(i,a,b) for (ll i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()




int main(int argc, char **argv)
{
	ll S; cin >> S;
	ll x2 = 1e9;
	ll x3 = (x2-S%x2)%x2;
	ll y3 = (S + x3) / x2;

	std::cout << "0 0 1000000000 1 " << x3 << " " << y3 << std::endl;
}

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

#define all(v)   v.begin(), v.end()
#define endl "\n";
#define pb push_back
#define F first
#define S second
#define JULEE_DO_THE_THING fast()
#define to_str to_string
#define isOdd(n)    (n&1)
#define LLMAX LLONG_MAX
#define LLMIN LLONG_MIN
#define IMIN INT_MIN
#define IMAX INT_MAX
#define pow POW

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double dd;
typedef string str;
typedef vector<int> vecint;
typedef vector<ll> vecll;
typedef pair<int, int> pii;

void fast() {
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(0);
}

bool compare(int &a, int &b) {
	return a > b;
}

ll numOfDigits(ll n) {
	if (!n)
		return 1;
	return (ll) (log10(n)) + 1;
}

ull POW(ll a, ll b);

/*
1 2 3 4 5 6 7
c o n t e s t

          s o n
indexes : 7 2 3

2 and 3 are consecutive so they form one subsequence
and 7 forms one subsequence
*/

ll BN();
int main() {
	JULEE_DO_THE_THING;
	//freopen("test cases\\Strings of Impurity.txt", "r", stdin) ;
	str s, t; cin>>s>>t;
    int n = s.size(), m = t.size();

    //check if it's invalid
    map<char, bool> vis;
    for(int i=0; i<n; i++)vis[s[i]] = 1;
    for(int i=0; i<m; i++){
        if(vis.find(t[i])==vis.end())
            return cout<<-1, 0;
    }

    map<char, set<int>> mp;
    t = " " + t; m++;
    for(int i=0; i<n; i++) mp[s[i]].insert(i);
    int index[m+1]={IMAX}; index[m] = IMAX;
    for(int i=1; i<m; i++){
        int up;
        auto it = mp[t[i]].upper_bound(index[i-1]);//first index after last char
        if(it==mp[t[i]].end()) up = *mp[t[i]].begin();
        else up = *it;
        index[i] = up;
    }

    //counting subsequences
    ull subSequnce = 0;
    for(int i=1; i<m; i++){
       if(index[i]<=index[i-1])subSequnce++;
    }

    int j = m-1, x;
    while(j>=1 && index[j]<index[j+1]) j--;
    str lastSequence = t.substr(j+1);

    //we need to know how many chars we need from the last copy of S
    ull lastSubLenght  = 0 ;
    for( j=0, x = 0; j<n && x<lastSequence.size(); j++){
       if(s[j]==lastSequence[x])x++;
    }
    lastSubLenght = j;

    //we need number of copies without last copy + substring of last copy
    cout<<(subSequnce-1)*s.size() + lastSubLenght;
	return 0;
}

ll BN() {
	ll low = 0;
	ll up = 0;
	ll ans = 0;
	while (low <= up) {
		ll mid = ((low + up) / 2);
		if (mid) {
			ans = mid;
			low = mid + 1;
		} else
			up = mid - 1;
	}
	return ans;
}

ull POW(ll a, ll b) {
	ull res = 1;
	while (b > 0) {
		if (b & 1)
			res = res * a;
		a = a * a;
		b >>= 1;
	}
	return res;
}


Measured memory_bytes: 5580
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int x[1010],y[1010];
int d[40],dn;
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&x[i],&y[i]);
		if(((x[i]+y[i])&1)!=((x[1]+y[1])&1))
		{
			printf("-1");
			return 0;
		}
	}
	dn=32;
	d[dn]=d[dn-1]=1;
	for(int i=dn-2;i>=1;i--)
		d[i]=d[i+1]*2;
	if((x[1]+y[1])&1)
		dn--;
	for(int i=1;i<=n;i++)
		if(((x[i]+y[i])&1)==0)
			x[i]--;
	printf("%d\n",dn);
	for(int i=1;i<=dn;i++)
		printf("%d ",d[i]);
	printf("\n");
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=31;j++)
		{
			if(abs(x[i])>abs(y[i]))
			{
				if(x[i]>0)
				{
					x[i]-=d[j];
					printf("R");
				}
				else
				{
					x[i]+=d[j];
					printf("L");
				}
			}
			else
			{
				if(y[i]>0)
				{
					y[i]-=d[j];
					printf("U");
				}
				else
				{
					y[i]+=d[j];
					printf("D");
				}
			}
		}
		if(dn==32)
			printf("R");
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
int main()
{
    int N, M;
    std::cin >> N >> M;
    std::vector<int> D;
    for (int d = 1; d * d <= M; d++) {
        if (M % d != 0) {
            continue;
        }
        D.push_back(d);
        if (d * d != M) {
            D.push_back(M / d);
        }
    }
    std::sort(D.begin(), D.end(), std::greater<int>{});
    for (const int d : D) {
        if (M / d >= N) {
            return std::cout << d << std::endl, 0;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1000000007;
struct edge {int to,costa,costb;};

signed main() {
string s;
cin>>s;int ans=MOD;
for(int i=2;i<s.size();i++){
    ans=min(ans,abs(753LL-(s[i-2]*100+s[i-1]*10+s[i]-'0'*111)));
}
cout<<ans;


return 0;
}


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

using namespace std;
#define DBG(x)                         \
    (void)(cout << "L" << __LINE__     \
                << ": " << #x << " = " \
                << (x) << '\n')
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
typedef long long ll;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const long double PI = (acos(-1));
const long double EPS = 0.0000000001;
const int INF = 0x3f3f3f3f;
const int maxn = 1100000;
const int mod = 1e9 + 7;
ll power(ll a, ll b)
{
    ll ans = 1 % mod;
    while (b > 0)
    {
        if (b & 1)
        {
            ans = ans * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
ll cac(ll n)
{
    if (n == 1)
        return 0;
    else
    {
        ll ans = ((power(10, n) - power(9, n) - power(9, n) + power(8, n)) % mod + mod) % mod;
        return ans;
    }
}
void run_case()
{
    ll n;
    cin >> n;
    ll ans = cac(n);
    cout << ans << "\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setiosflags(ios::fixed) << setprecision(12);
    run_case();
    cout.flush();
    return 0;
}

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

const ll INF = 1ll<<60;

typedef pair<ll,ll> P;

int main() {
  ll n, x, d;
  cin >> n >> x >> d;
  if (d==0){
    if(x==0){
      cout<<1;
      return 0;
    }
    else{
      cout<<n+1;
      return 0;
    }
  }

  if (d<0){
    d=-d;
    x=-x;
  }

  map<ll,vector<P>> mp;
  rep(i,n+1){
/*
    ll mink=(i-1)*i/2;
    ll maxk=i*(2*n-i-1)/2;
    ll ix=i*x;
    ll rem=(ix+(d<<30))%d;
    ll front=(ix-rem)/d+mink;
    ll len=maxk-mink;
    ll s = ix+mink*d;//初項
    mp[(s+(d<<30))%d].emplace_back(s,len);
*/

    ll s = x*i;
   ll l = (ll)i*(i-1)/2;//iの和のmin
   ll r = l + (ll)i*(n-i);//iの和のmax
   s += l*d;//初項
   r -= l;//初項から最終項までのながさ（dで割っている）
   mp[(s+(d<<30))%d].emplace_back(s,r);//負の値がかえらないように十分大きくしている

  }


  ll cnt=0;
  /*
  for(auto a:mp){
    auto A=a.second;
    sort(A.begin(),A.end());
    ll start=A[0].first;

    ll numA=A.size();
    ll now=start+A[0].second;
    //ll end=now;
    ll cnt1=0;
    rep(i,numA-1){
      if (A[i+1].first>now+1){
        cnt1+=A[i+1].first-now-1;
      }
      now=max(now,A[i+1].first+A[i+1].second);
  //    end=max()
    }

    ll sumall=now-start+1;
  //  cout<<sumall<<'s'<<cnt1<<'c'<<endl;
    cnt+=sumall-cnt1;

  }
  */
  ll ans=0;
  for (auto p : mp) {
    auto a = p.second;//(s,r)
    int m = a.size();
    rep(i,m) a[i].first = (a[i].first-p.first)/d;//初項から初項%dを引いてdで割る
    vector<P> ev;//event first:いつ　second:+1 or -1　
    //１以上になっている区間の長さがわかればok、区間の始まりを+1, 終わりを-1とする

    rep(i,m) {
      ev.emplace_back(a[i].first, 1);//初項を１に
      ev.emplace_back(a[i].first+a[i].second+1, -1);//初項＋長さを−１に
    }
    sort(ev.begin(), ev.end());
    ll cnt = 0, pre = -INF;//cnt:いま何個の区間に覆われているか pre:直前のイベント
    for (auto e : ev) {
      ll len = e.first-pre;//直前のイベントからのながさ
      if (cnt) ans += len;
      cnt += e.second;
      pre = e.first;
    }
  }
cout<<ans;
}


Measured memory_bytes: 22144
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const ll inf =1LL << 62;
const ll mod=1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b,const ll &mod) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b,const ll &mod) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b,const ll &mod) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b,const ll &mod) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
random_device rd;
mt19937 mt(rd());
uniform_int_distribution<int> dice(1,6);
uniform_real_distribution<double> score(0.0,10.0);

int n;
vi H;

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

    int K; cin >> n >> K;
    H = vi(n+1); rep(i, n) cin >> H[i+1];
    H.emplace_back(0);
    n += 2;

    vector<vll> dp = vector<vll>(n, vll(K+1, inf));
    dp[0][0] = 0LL;

    rep(i, n-1){
        rep(j, K+1){
            ll cur = dp[i][j];
            
            rep(ni, i+1, n){
                int nj = j + (ni - i - 1);
                if(nj > K) break;

                ll& nxt = dp[ni][nj];
                chmin(nxt, cur + max(0, H[ni] - H[i]));
            }
        }
    }

    cout << *min_element(_all(dp[n-1])) << endl;

    return 0;
}


Measured memory_bytes: 1024
n=int(input())
al=list(map(int,input().split()))
num=[0 for i in range(n+2)]
num[-1]=3
ans=1

for i in range(n):
    ans*=num[al[i]-1]
    ans=ans%1000000007
    num[al[i]-1]-=1
    num[al[i]]+=1

print(ans)
    
    

Measured memory_bytes: 56684
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define EPS 1e-10

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;

int n, num;
vector<int> p;

int main(){
	while (cin >> n&&n){
		ll sum = 0;
		REP(i, n){
			cin >> num;
			sum += num;
		}
		REP(i, n - 1){
			cin >> num;
			p.push_back(num);
			sum += num;
		}
		sort(ALL(p));
		ll MAX = sum;
		REP(i, p.size()){
			sum -= p[i];
			MAX = max(MAX, sum*(i + 2));
		}
		cout << MAX << endl;
		p.clear();
	}
}

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

int	main()
{
	string	str;
	int	sum;
	while (cin >> str) {
		if (str == "0") break;
		sum = 0;
		for (auto c : str) {
			sum += c - '0';
		}
		cout << sum << "\n";
	}
}


Measured memory_bytes: 3100