akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>

int main(void)
{
	int H, W;
	int i, n;

	while (1)
	{
		scanf("%d %d", &H, &W);
		if (H == 0 && W == 0)
		{
			break;
		}
		for (i = 0; i < W; i++){
			printf("#");
		}
		putchar('\n');

		for (i = 0; i < H - 2; i++)
		{
			printf("#");
			for (n = 0; n < W - 2; n++)
			{
				printf(".");
			}
			printf("#");
			putchar('\n');
		}
		for (i = 0; i < W; i++){
			printf("#");
		}
		printf("\n\n");
	}
	return 0;
}

Measured memory_bytes: 592
#include <iostream>
#include <climits>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
 
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

#define MOD 1000000007LL

int k;
int main()
{
  ll an=0;
  ll ans;

  cin >> k;

  for (ans=1; ans <= 1000000; ans++) {
    an = (an*10+7)%k;
//printf("an = %lld\n", an);
    if (an==0) break;
  }

  if (ans > 1000000) ans = -1;

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

/*
  a_0=7, a_1=77, a_2=777, ... とすると
  a_n+1 = a_n * 10+7

  a_n = 7 * Σ10^i (i=0..n)

  2の倍数はない
  3の倍数は777、777777、77777777, ... であり 3つ置き
  5の倍数はない
  7の倍数はすべて
  9の倍数は777777777,.. であり 9個置き
  11の倍数は77,7777,777777, .. であり2つ置き
  13の倍数はない？
  */


Measured memory_bytes: 3600
N, Q = map(int, input().split())
S = input()
count = 0
counts = [0 for _ in range(N)]

for i in range(N - 1):
    if S[i] == "A" and S[i + 1] == "C":
        count += 1
        counts[i + 1] = count
    else:
        counts[i + 1] = count

for _ in range(Q):
    li, ri = map(int, input().split())
    print(counts[ri - 1] - counts[li - 1])


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

#define MAX 100000

int visit[MAX];

int main() {
	int N;

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

	long long ans = 0;
	for( int c = 1; c < N; c++ ) {
		memset( visit, 0, sizeof( visit ) );
		long long f = 0;
		for( int k = 0; c * (k + 1) < N - 1; k++ ) {
			int next = N - 1 - k * c;
			if( visit[next] ) {
				break;
			}
			visit[next] = 1;
			f += s[next];
			if( visit[k * c] ) {
				break;
			}
			visit[k * c] = 1;
			f += s[k * c];
			ans = max( ans, f );
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 1024
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int h=sc.nextInt();
		int w=sc.nextInt();
		while (h!=0||w!=0){
			StringBuilder sb1=new StringBuilder("");
			for(int m=0;m<w;m++)sb1.append("#");
			sb1.append("\n");
			for(int n=0;n<h-2;n++){
				sb1.append("#");
				for(int m=0;m<w-2;m++)sb1.append(".");
				sb1.append("#");
				sb1.append("\n");
			}
			for(int m=0;m<w;m++)sb1.append("#");
			sb1.append("\n");
			System.out.println(sb1);
			h=sc.nextInt();
			w=sc.nextInt();
		}
	}
}

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

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

  vector<int> n(N);
  for (int i = 0; i < Q; ++i)
    ++n[A[i] - 1];

  for (int i = 0; i < N; ++i)
    if (K - Q + n[i] > 0)
      cout << "Yes" << endl;
    else
      cout << "No" << endl;
}

Measured memory_bytes: 1408
n = int(input())
cards = list(input().split())
cards1 = cards.copy()
# cnt = 0
# for i in range(n):
#     minj = i
#     for j in range(i,n):
#         if int(cards[minj][1]) > int(cards[j][1]):
#             minj = j
#     if i != minj:
#         cnt += 1
#     cards[i], cards[minj] = cards[minj], cards[i]
#     print(cards)

#['D2', 'C3', 'S4', 'H4', 'C9']




def BubbleSort(cards):

    for i in range(n):
        for j in range(n-1,i,-1):
            if int(cards[j][1]) < int(cards[j-1][1]):
                cards[j],cards[j-1] = cards[j-1],cards[j]

    return cards


def SelectionSort(cards):
    cnt = 0
    for i in range(n):
        minj = i
        for j in range(i,n):
            if int(cards[minj][1]) > int(cards[j][1]):
                minj = j
        if i != minj:
            cnt += 1
        cards[i], cards[minj] = cards[minj], cards[i]

    return cards

a = BubbleSort(cards)
b = SelectionSort(cards1)

print(*a)
print("Stable")
print(*b)
if a == b:
    print("Stable")
else:
    print("Not stable")







Measured memory_bytes: 5612
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>

using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template<typename T> using VT = vector<T>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define FIND(s, e) ((s).find(e) != (s).end())
#define EB emplace_back
template<typename T> inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

int main(void) {
    int n;
    scanf("%d", &n);
    map<int, int> cnt;
    REP(i, n) {
        int a;
        scanf("%d", &a);
        cnt[a]++;
    }
    int ans = 0;
    FORE(e, cnt) {
        if (e.first > e.second) ans += e.second;
        else ans += e.second - e.first;
    }
    cout << ans << endl;
}


Measured memory_bytes: 4736
n=gets.to_i
ss=$<.map &:chomp

a=b=ab=c=0
ss.map{|s|
	c+=s.scan('AB').size
	if s[0]=='B'&&s[-1]=='A'
		ab+=1
	elsif s[0]=='B'
		b+=1
	elsif s[-1]=='A'
		a+=1
	end
}

if a==0&&b==0
	p c+[ab-1,0].max
elsif a==0||b==0
	p c+ab
else
	p c+[b,a].min+ab
end

Measured memory_bytes: 3068
import math
def P(n, r):
    return math.factorial(n)//math.factorial(n-r)
def C(n, r):
    return P(n, r)//math.factorial(r)
N = int(input())
arr = list(map(int, input().split()))
cnt = [0]*(1+N)
ans = [0]*(1+N)
ans_less = [0]*(1+N)
for i in range(N):
    cnt[arr[i]] += 1
for i in range(1,N+1):
    if cnt[i] == 0 or cnt[i] == 1:
        continue
    ans[i] = C(cnt[i],2)
    if cnt[i] >= 3:
        ans_less[i] = C(cnt[i]-1,2)
    else:
        ans_less[i] = 0
su = sum(ans)
for i in range(N):
    print(su-ans[arr[i]]+ans_less[arr[i]])

Measured memory_bytes: 121804
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define pb push_back
#define ll long long
#define ld long double
#define fi first
#define se second
#define INF 1e18

const ll mod = 1000000000+7;
const int N = 3000+5;

ll dp[N][N];
ll a[N];

ll go(int i, int j)
{
	if(i==j)return a[i];
	if(dp[i][j]!=-INF)return dp[i][j];
	return dp[i][j] = max(a[i]-go(i+1,j),a[j]-go(i,j-1));
}

main()
{ 
	SPEED;
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	int n;
	cin >> n;
	for(int i = 1; i<=n; i++)
	{
		cin >> a[i];
	}
	for(int i = 0 ;i<=n; i++)
	{
		for(int j = 0; j<=n; j++)
		{
			dp[i][j] = -INF;
		}
	}
	cout << go(1,n) << endl;
	
}

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

//#define int long long
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define exrep(i, a, b) for(ll i = a; i < b; i++)
#define out(x) cout << x << endl
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<bool> > vvb;
typedef vector<vector<double> > vvd;
typedef vector<vector<string> > vvs;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

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;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

signed main()
{   
  gearup;
  string s; cin >> s;
  if(s == "zyxwvutsrqponmlkjihgfedcba"){
    out(-1);
    return 0;
  }
  vl a(26);
  int n = s.size();
  rep(i,n)a[s[i] - 'a']++;
  rep(i,26){
    if(a[i] == 0){
      string ans = s + char('a'+i);
      out(ans);
      return 0;
    }
  }
  string t = s;
  next_permutation(t.begin(),t.end());
  rep(i,n){
    cout << t[i];
    if(s[i] != t[i])break;
  }
  cout << endl;
}


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

using namespace std;

int main(){
  long long n, a[100009], mx=0, mn=1e9;
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> a[i];
    mx = max(a[i], mx);
  }
  for(int i=0;i<n;i++){
    if(mx==a[i])continue;
    if(abs(a[i]-mx/2)<abs(mn-mx/2)){
      mn=a[i];
    }
  }
  cout << mx << ' ' << mn << endl;
}



Measured memory_bytes: 4332
// https://atcoder.jp/contests/dp/submissions/8562895
// By mcalancea
#include <bits/stdc++.h>
using namespace std;

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

    vector<vector<int>> a(n, vector<int> (n, 0));

    for (int i = 0; i < n; i += 1)
        for (int j = 0; j < n; j += 1)
            cin >> a[i][j];

    vector<int64_t> value((1 << n), 0);

    for (int mask = 0; mask < (1 << n); mask += 1) {
        vector<int> rabbits;
        for (int i = 0; i < n; i += 1)
            if ((1 << i) & mask)
                rabbits.push_back(i);

        int k = rabbits.size();
        for (int i = 0; i < k; i += 1)
            for (int j = i + 1; j < k; j += 1)
                value[mask] += a[rabbits[i]][rabbits[j]];
    }

    vector<int64_t> dp((1 << n), 0);

    for (int mask = 0; mask < (1 << n); mask += 1) {
        dp[mask] = value[mask];
        for (int sub = mask; sub > 0; sub = (sub - 1) & mask)
            dp[mask] = max(dp[mask], dp[sub] + dp[mask ^ sub]);
    }

    cout << dp[(1 << n) - 1] << "\n";
}


Measured memory_bytes: 1280
#include <iostream>
#include <vector>
using namespace std;
const int INF = 1010000000;

int main() {
	int n, m, l;
	cin >> n >> m >> l;
	int d[n][n]; fill((int *)d, (int *)d + sizeof(d)/sizeof(int), INF);
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		d[a][b] = c;
		d[b][a] = c;
	}
	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (d[i][j] <= l) d[i][j] = 1;
			else d[i][j] = INF;
		}
	}

	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}

	int Q;
	cin >> Q;
	for (int q = 0; q < Q; q++) {
		int s, t;
		cin >> s >> t;
		s--; t--;
		if (d[s][t] >= INF) {
			cout << -1 << endl;
			continue;
		}
		int ans = d[s][t] - 1;
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 3944
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

string a[10];

int h, w;

bool dfs(int x, int y) {
    a[x][y] = '.';
    if (x == h - 1 && y == w - 1) {
        bool flag = false;
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++)
                if (a[i][j] == '#')
                    flag = true;
        if (!flag)
            return true;
    } else if (x == h - 1) {
        if (a[x][y + 1] == '#' && dfs(x, y + 1))
            return true;
    } else if (y == w - 1) {
        if (a[x + 1][y] == '#' && dfs(x + 1, y))
            return true;
    } else {
        if (a[x + 1][y] == '#' && dfs(x + 1, y))
            return true;
        if (a[x][y + 1] == '#' && dfs(x, y + 1))
            return true;
    }
    a[x][y] = '#';
    return false;
}

int main()
{
    cin >> h >> w;
    for (int i = 0; i < h; i++)
        cin >> a[i];

    if (dfs(0, 0))
        cout << "Possible";
    else
        cout << "Impossible";

    return 0;
}

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

int main(){
  int N;
  bool flag=true;
  cin >> N;
  vector<long> A(N);
  for(int i=0;i<N;++i) cin >> A[i];
  sort(A.begin(),A.end());
  for(int i=0;i<N-1;++i){
    if(A[i]==A[i+1]) flag = false;
    else continue;
  }
  if(flag) cout << "YES" << endl;
  else cout << "NO" << endl;
}

Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<math.h>
using namespace std;
int main()
{
    int n,m,s=0,i,j;
    cin >> n;
    m=n;
    while(m)
    {
        s+=m%10;
        m/=10;
    }
    if(n%s==0)
        cout << "Yes"<< endl;
    else
        cout << "No" <<endl;
    return 0;
}


Measured memory_bytes: 256
using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;
class Program
{
    static void Main(string[] args)
    {
      string[] input = ReadLine().Split();
      int n = int.Parse(input[0]);
      int m = int.Parse(input[1]);
      List<int> x = ReadLine().Split().ToList().ConvertAll(x=>int.Parse(x));
      x.Sort();
      List<int> y = new List<int>();
      
      for (int i=0;i<m-1;i++)
      {
        y.Add(x[i+1]-x[i]);
      }
      
      y.Sort();
      int K = Math.Min(n-1,m-1);
      for (int i=0;i<K;i++)
      {
        y.RemoveAt(y.Count-1); 
      }
      WriteLine(y.Sum());

    }
}

Measured memory_bytes: 37344
#include<iostream>
using namespace std;
int main()
{
  
  char c;
  int s[100000];  
  int count = 0;
  int sumA = 0;
  int sumB = 0;
  
  while(cin >> c)
  {
    s[count] = c - '0';
    count++;
  }

  // A　
  int target_a = s[0];
  int r_count_a = 0;
  for (int i = 0; i < count; i++)
  {
    if (target_a == s[i])
    {
    }
    else
    {
      r_count_a++;
    }
    
    target_a = (target_a + 1) % 2;
  }
  
  // B reverse
  int target_b = (s[0] + 1) % 2;
  int r_count_b = 0;

  for (int i = 0; i < count; i++)
  {
    if (target_b == s[i])
    {
    }
    else
    {
      r_count_b++;
    }
    
    target_b = (target_b + 1) % 2;
  }
  
  int result_f = r_count_a > r_count_b ? r_count_b : r_count_a;
  
  cout << result_f;
  
  return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long ll;

bool check(int n){
	int p=n%10;
	n/=10;
	while(n>0){
		if(n%10!=p-1){
			return false;
		}
		p=n%10;
		n/=10;
	}
	return true;
}

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n; cin >> n;
	vector<int> a(n);
	for(int i=0;i<n;i++){
		cin >> a[i];
	}
	int ans=-1;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(check(a[i]*a[j])&&ans<a[i]*a[j]){
				ans=a[i]*a[j];
			}
		}
	}
	cout << ans << endl;
}


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

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
const ll MOD = 1e9 + 7;
const int INF = 1e9;

int dx4[4] = { 0, -1, 1, 0 };
int dy4[4] = { -1, 0, 0, 1 };
int dx8[8] = { 0, -1, 1, 0, -1, 1, -1, 1 };
int dy8[8] = { -1, 0, 0, 1, -1, -1, 1, 1 };

int main() {
  ll n; cin >> n;
  ll a, b, c, d, e; cin >> a >> b >> c >> d >> e;
  ll minval = INF;
  minval = min(a, min(b, min(c, min(d, e))));
  ll res = 0;
  if (minval < n) {
    res = ceil((double)n / minval) + 4;
  } else {
    res = 5;
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ld long double
#define ll long long
#define st first
#define nd second
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define pb push_back
using namespace std;
const int N = 5e3+5;
const ll mod = 1e9+7;
ll cover[N][2], sum_cover[N], sum_cover1[N];
ll dp[N][N], col[N], col_suf[N][N];
ll fpow(ll a, ll p) {
	if(p==0) return 1;
	ll b = fpow(a, p/2);
	if(p%2==0) {
		return b*b%mod;
	}
	return b*b%mod*a%mod;
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n, a, b;
	cin>>n>>a>>b;
	if(a < b) swap(a, b);
	ll ans=0;
	cover[0][0] = 1;
	for(int i=1; i<=a; ++i) {
		cover[i][0] = (cover[i-1][0] + cover[i-1][1])%mod;
		cover[i][1] = cover[i-1][1];
		if(i-b >=0 ) {
			cover[i][1] += cover[i-b][0];
			cover[i][1] %= mod;
		}
	}
	for(int i=b-1; i>=1; --i) {
		sum_cover[i] = sum_cover[i+1];
		sum_cover[i] += cover[a-1-i][0];
		sum_cover[i] %= mod;
		sum_cover1[i] = sum_cover1[i+1];
		sum_cover1[i] += cover[a-1-i][0] + cover[a-1-i][1];
		sum_cover1[i] %= mod;
	}
	dp[0][0] = 1;
	dp[1][0] = 1;
	col_suf[0][0] = 1;
	col_suf[0][1] = 2;
	// bug in dp probably
	for(int i=2; i<=n; ++i) { // row - index
		for(int k=0; k<i-1; ++k) { // column - .st pos <b
			if(i-k < a) dp[i][k] = dp[i-1][k];	
			if(i-b-1 >= 0 && i-k < a) dp[i][k] += col_suf[k][i-b-1];
			dp[i][k] %= mod;
			dp[i][i-1] += (col_suf[k][i-1] - ((i-b-1<0)?0:col_suf[k][i-b-1]) - dp[i-1][k] + 2*mod)%mod;
			dp[i][i-1] %= mod;
			col_suf[k][i] = (col_suf[k][i-1] + dp[i][k] ) % mod;
		}
		col_suf[i-1][i] = dp[i][i-1];
	}
	/*cout<<"debug dp: \n";
	for(int i=0; i<=n; ++i) {
		for(int j=0; j<=n; ++j) {
			cout<<dp[i][j]<<' ';
		}
		cout<<'\n';
	}
	cout<<"computing answer\n";*/
	for(int i=1; i<=n-a+1; ++i) {
		int l = n-(i+a-1)+1;
		ans += fpow(2, i-1) * ((i+a-1<n)?cover[a][0]:cover[a][0]+cover[a][1]) % mod
		* dp[l][l-1] % mod;
		ans %= mod;
		//cerr<<i<<' '<<i+a-1<<'\n';
		//cerr<<fpow(2, i-1)<<' '<<((i+a-1<n)?cover[a][0]:cover[a][0]+cover[a][1])<<' '<<dp[l][l-1]<<'\n';
		for(int j=i+a; j<=n; ++j) {
			if(j-i+1 > a+b-1) break;
			l = n-j+1;
			//ans += fpow(2, i-1) * ((j<n)?sum_cover[max(1, b-(j-(i+a-1)))]:
			//sum_cover1[max(1, b-(j-(i+a-1)))])% mod
			//* dp[l][l-1] % mod;
			//ans %= mod;
			//cerr<<i<<' '<<j<<'\n';
			//cerr<<fpow(2, i-1)<<' '<<sum_cover[max(1, b-(j-(i+a-1)))]<<' '<<dp[l][l-1]<<'\n';
			ans += fpow(2, i-1) * ((j<n)?cover[j-i-b][0]:cover[j-i-b][0]+cover[j-i-b][1])%mod* dp[l][l-1]%mod;
//			cerr<<i<<' '<<j<<' '<<fpow(2, i-1)<<' '<<cover[j-i-b][0]
		}
	}
	cout<<ans;
}


Measured memory_bytes: 236960
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <ctime>
#include <map>
#include <queue>

using namespace std; using ll=long long; using P=pair<ll,ll>; const int INF=1e9; const ll LNF=1e18;

int main(){
  ll n,a,b; cin>>n>>a>>b;
  if (a==b) {
    cout<<1<<endl; return 0;
  }
  if (a>b) {
    cout<<0<<endl;
    return 0;
  }
  if (n==1) {
    cout<<0<<endl;
    return 0;
  }
  ll sm1 = a + b * (n-1);
  ll sm2 = a * (n-1) + b;
  cout << sm1 - sm2 + 1 << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int i,n,count;
    long min=1000000,max=-1000000,sum=0;
    scanf("%d",&count);
    for(i=0;i<count;i++)
{
    scanf("%d",&n);
    if(min>n) min=n;
    if(max<n) max=n;
    sum+=n; 
}
    printf("%ld %ld %ld\n",min,max,sum);
    return 0;
}

Measured memory_bytes: 600
import java.util.*;

class Main {
  public static void main (String[] args) {
    Scanner scanner = new Scanner(System.in);
    String out = "";
    while (scanner.hasNext()) {
      double l = scanner.nextDouble();
      double w = scanner.nextDouble();
      double h = scanner.nextDouble();
      if (l == 0 && w == 0 && h == 0) {
        break;
      }
      l /= 2;
      w /= 2;
      h /= 2;
      int n = scanner.nextInt();
      for (int ii = 0; ii < n; ii++) {
        double r = scanner.nextDouble();
        out += r * r > l * l + w * w || r * r > l * l + h * h || r * r > h * h + w * w ? "OK\n" : "NA\n";
      }
    }
    System.out.print(out);
  }
}

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


using namespace std;
using ll = int64_t;
#define int int64_t

 
/* ==== declarations ====== */
// functions
void solve();
void getInput();
 
// global variables
int W, H;
double pi = 3.1415926535;
/* ======================== */
void getInput() {
    
}
 
 
void solve() {
    int R;
    cin>>R;
    cout<<2*R*pi<<endl;
}
 
 
 
signed main(){
    getInput();
    solve();
    return 0;
}

Measured memory_bytes: 3788
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include<math.h>
#include<bitset>
using namespace std;

int main() {
	int a, b, c, x, y; cin >> a >> b >> c >> x >> y;
	int ans = a * x + b * y;
	for (int i = 0; i <= 100000; i++) {
		if (i * 2 * c + max(0, x - i) * a + max(0, y - i) * b < ans) {
			ans = i * 2 * c + max(0, x - i) * a + max(0, y - i) * b;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 3600
use std::env;
use std::io::*;
use std::str::*;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let s = stdin.bytes().map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok().unwrap()
}

fn main() {
    // main の引数
    /*
        引数なしのときargs.len() = 1;
    */
    let args: Vec<String> = env::args().collect();

    let N = read::<i32>();
    println!("{}", 48 - N);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define rep1(i, n) for(int i=1; i<=(int)(n); i++)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> wi;
typedef vector<ll> vl;
const ll INF=1LL << 60;
const ll MOD=1e9+7;

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

  int x;
  cin >> x;
  if(x==1)cout << 0 << endl;
  else cout << 1 << endl;

  return 0;
}

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

int main(){
  int N,M,C;
  cin>>N>>M>>C;

  int b[M];
  for(int i=0;i<M;i++) cin>>b[i];

  int a[N][M];

  for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
      cin>>a[i][j];
    }
  }
  int count=0,sum=0;

  for(int i=0;i<N;i++){
    sum=0;
    for(int j=0;j<M;j++){
      sum += a[i][j]*b[j];
    }
    sum += C;
    if(sum>0) count++;
  }
  cout<<count;
  return 0;

}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
int max(int a,int b){return (a>b ? a:b);}
int min(int a,int b){return (a<b ? a:b);}
int compare_int(const void *a, const void *b){return *(int*)a - *(int*)b;}
//qsort(配列, 長さ, sizeof(int), compare_int);
double BS(int array[],int len,int target);

//////////////////////////////////////////
int N,Q;
char blank;
char S[200010],t[200010],d[200010];
int mid,g;

int zero1(){
    for(int i = 0;i < Q;i++){
        if(d[i]=='L' && t[i]==S[1]) return 1;
    }
    return 0;
}
int nibun1(int n,int M){
    //printf("%d\n",M-n);
    mid = (M+n+1)/2;
    g = mid;
    for(int i = 0;i < Q;i++){
        if(d[i]=='R' && t[i]==S[g] && g>0 && g<N+1)g++;
        if(d[i]=='L' && t[i]==S[g] && g>0 && g<N+1)g--;
    }
    if(g != 0 && M-n <= 1)return n;
    if(g == 0 && M-n <= 1)return M;
    if(g != 0)return nibun1(n,(mid+M)/2);
    if(g == 0)return nibun1((n+mid+1)/2,M);
}
int zero2(){
    for(int i = 0;i < Q;i++){
        if(d[i]=='R' && t[i]==S[N]) return 1;
    }
    return 0;
}
int nibun2(int n,int M){
    //printf("%d\n",M-n);
    mid = (M+n)/2;
    g = mid;
    for(int i = 0;i < Q;i++){
        if(d[i]=='R' && t[i]==S[g] && g>0 && g<N+1)g++;
        if(d[i]=='L' && t[i]==S[g] && g>0 && g<N+1)g--;
    }
    if(g != N+1 && M-n <= 1)return M;
    if(g == N+1 && M-n <= 1)return n;
    if(g != N+1)return nibun2((n+mid+1)/2,M);
    if(g == N+1)return nibun2(n,(mid+M)/2);
}

///////////////////////////////////
int main(){
    scanf("%d%d",&N,&Q);
    scanf("%s",S);
    for(int i = 0;i < Q;i++){
        scanf("%c%c%c%c",&blank,&t[i],&blank,&d[i]);
    }
    for(int i = N;i > 0;i--){
        S[i] = S[i-1];
    }


    int count = N;
    if(zero1()){
        g = 1;
        for(int i = 0;i < Q;i++){
            if(d[i]=='R' && t[i]==S[g] && g>0 && g<N+1)g++;
            if(d[i]=='L' && t[i]==S[g] && g>0 && g<N+1)g--;
        }
        if(g == 0)count -= nibun1(1,N);
        //printf("%d %d\n",count,g);
    }
    if(zero2()){
        g = N;
        for(int i = 0;i < Q;i++){
            if(d[i]=='R' && t[i]==S[g] && g>0 && g<N+1)g++;
            if(d[i]=='L' && t[i]==S[g] && g>0 && g<N+1)g--;
        }
        if(g == N+1)count -= N - nibun2(1,N) + 1;
        //printf("%d\n",count);
    }
    printf("%d\n",count);
    return 0;
}


///////////////////////////////////////////


double BS(int array[],int len,int target){ //(配列,長さ,見つける値)
    int low,mid,high;

    low = 0;
    high = len-1;

    int mark;

    while(low <= high){
        mid = (low + high) / 2;
        if(array[mid] == target){
            mark = 0;
            break;
        }else if(array[mid] < target){
            low = mid + 1;
            mark = 1;
        }else{
            high = mid - 1;
            mark = -1;
        }
    }
    if(mark == 0){
        return mid; //配列の何番目か（０から）
    }else if(mark == 1){
        return (double)mid + 0.5;//なかったらどこのあいだか
    }else{
        return (double)mid - 0.5;
    }
}


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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair

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 C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;

#define INF 10'000'000
using Edge = pair<i64, i64>;
i64 G[100][100];
i64 d[100][100];

int main() {
    i64 N, M; cin >> N >> M;
    REP(i, N) REP(j, N) {
        if (i == j) G[i][j] = 0;
        else G[i][j] = INF;
    }
    REP(i, M) {
        i64 u, v, c; cin >> u >> v >> c;
        u--, v--;
        G[u][v] = c, G[v][u] = c;
    }

    REP(i, N) REP(j, N) d[i][j] = G[i][j];

    REP(k, N) {
        REP(i, N) {
            REP(j, N) {
                chmin(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    i64 cnt = 0;
    REP(i, N) {
        for (i64 j = i + 1; j < N; j++) {
            if (G[i][j] == INF) continue;
            if (G[i][j] != d[i][j]) cnt++;
        }
    }
    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 3852
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD 1000000007
#define ALL(obj) (obj).begin(),(obj).end()
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;}
const long long INF = 1LL << 60;
bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.first < secondElof.first;
}
bool pairCompareSecond(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.second < secondElof.second;
}
//四方向への移動ベクトル
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

struct edge{//グラフに使うヤツ
    ll from,to,cost;
};

typedef vector<vector<edge> > G;
ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}

int main() {
    ll n;
    cin >> n;
    ll a[n];
    for (ll i=0;i<n;i++){
        cin >> a[i];
    }
    ll x=a[0],ans1=0,ans2=0;
    if (x<=0){
        ans1+=abs(x)+1;
        x=1;
    }
    for (ll i=1;i<n;i++){
        x+=a[i];
        if (i%2){
            if (x>=0){
                ans1+=x+1;
                x=-1;
            }
        }else{
            if (x<=0){
                ans1+=abs(x)+1;
                x=1;
            }
        }
    }
    x=a[0];
    if (x>=0){
        ans2+=x+1;
        x=-1;
    }
    for (ll i=1;i<n;i++){
        x+=a[i];
        if (i%2==0){
            if (x>=0){
                ans2+=x+1;
                x=-1;
            }
        }else{
            if (x<=0){
                ans2+=abs(x)+1;
                x=1;
            }
        }
    }
    cout << min(ans1,ans2) << endl;
    return 0;
}


Measured memory_bytes: 4384
#include<map>
#include<set>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<vector>
#include<complex>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<numeric>
#include<sstream>
#include<iostream>
#include<algorithm>
#include<functional>

using namespace std;

int main(){
	string str;
	cin >> str;
	reverse(str.begin(),str.end());
	cout << str << endl;
	return 0;
}

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

int main()
{
	int n, m, A[100][100], b[100],c;
	for (int i = 0;i < 100;i++) {
		for (int j = 0;j < 100;j++) {
			A[i][j] = 0;
		}
		b[i] = 0;
	}
	cin >> n >> m;

	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			cin >> A[i][j];
		}
	}

	for (int i = 0;i < m;i++) {
		cin >> b[i];
	}

	for (int i = 0;i < n;i++) {
		c = 0;
		for (int j = 0;j < m;j++) {
			c += A[i][j] * b[j];
		}
		cout << c << endl;
	}
	return 0;
}

Measured memory_bytes: 1200
from sys import stdin, stdout
from collections import deque

s = raw_input().strip()
q = input()
inp = stdin.readlines()

Q = deque(list(s))
rev = 0
for line in inp:
    x = line.strip().split()
    if x[0] == '1':
        rev ^= 3
    else:
        f = int(x[1])
        ch = x[2]
        f ^= rev
        if f == 1:
            Q.appendleft(ch)
        else:
            Q.append(ch)

l = []
while Q:
    if rev == 0: l.append(Q.popleft())
    else: l.append(Q.pop())

print ''.join(l)

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;

static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const ll INF = 1023456789;

#define REP(i,n)	for(int i=0;i<n;++i)
#define REPR(i,n)	for(int i=n-1;i>=0;--i)
#define FOR(i,s,n)	for(int i=s;i<n;++i)
#define FORR(i,s,n)	for(int i=n-1;i>=s;--i)
#define ALL(c)		(c).begin(),(c).end()
#define CLEAR(v)	memset(v,0,sizeof(v))
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define F			first
#define S			second

int main(int argc, char **argv) {
	string s;
	cin >> s;
	REP(i, s.length()) if (i % 2 == 0) cout << s[i];
	cout << endl;
	return 0;
}


Measured memory_bytes: 512
//============================================================================
// Name        : abc70d.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<cmath>
#include<list>
#include<set>
#include<map>

using namespace std;

map<int, bool> mp;
void dfs(vector<vector<pair<int, long long>>> &A, vector<long long> &dist, int n){
	mp[n] = 1;
	for(int i = 0; i < A[n].size(); ++i){
		dist[A[n][i].first] = min(dist[n] + A[n][i].second, dist[A[n][i].first]);
		if(mp[A[n][i].first] == 0)dfs(A, dist, A[n][i].first);
	}
}

int main() {
	int N;
	cin >> N;
	vector<vector<pair<int, long long>>> A(N + 1);
	for(int i = 0; i < N - 1; ++i){
		int a, b;
		long long c;
		scanf("%d %d %lld", &a, &b, &c);
		A[a].push_back(make_pair(b, c));
		A[b].push_back(make_pair(a, c));
	}

	int Q, K;
	cin >> Q >> K;

	vector<long long> dist(N + 1, 1ll << 62);
	dist[K] = 0;
	for(int i = 0; i < A[K].size(); ++i){
		dist[A[K][i].first] = min(dist[A[K][i].first] + A[K][i].second, A[K][i].second);
		dfs(A, dist, A[K][i].first);
	}

	vector<int> a(Q), b(Q);
	for(int i = 0; i < Q; ++i){
		scanf("%d %d", &a[i], &b[i]);
		printf("%lld\n", dist[a[i]] + dist[b[i]]);
	}

	return 0;
}


Measured memory_bytes: 21376
#include<iostream>
#include<vector>
#include<string>
#include<math.h>
#define ll long long
using namespace std;

int main(){
    ll n;
    ll a=1,b;
    cin>>n;
    for(int i=1; i<sqrt(n)+1; i++){
        if(n%i==0 && i>a){
            a=i;
        }
    }
    b=n/a;
    //cout<<a<<endl;
    //cout<<b<<endl;
    cout<<a+b-2<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fastIO                        \
	ios_base::sync_with_stdio(false); \
	cin.tie(NULL);                    \
	cout.tie(NULL);
// g++ -std=c++11 -O2 -Wall *.cpp -o *
#define eps 1e-9
#define MAX 1e12 + 10
#define MOD 1000000007
#define PI 3.14159265358979323846
#define Fi first
#define Se second
#define PB push_back
#define MP make_pair
#define all(a) a.begin(), a.end()
#define maxof(a) *max_element(all(a))
#define rep(i, n) for (i = 0; i < n; ++i)
#define REP(i, k, n) for (i = k; i < n; ++i)
#define REPR(i, k, n) for (i = k; i > n; --i)
typedef long long ll;
typedef pair<int, int> pr_int;


int main()
{
	// freopen("input.txt", "r", stdin);
	// freopen("output.out", "w", stdout);
	// fastIO

	string s, t;
	cin >> s >> t;
	int n = s.size();
	int c = 0, i;
	rep(i, n) c += s[i] != t[i];
	cout << c;

	printf("\n");
}


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

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

  map<string, int> score;
  string sbuff;
  for (int i=0; i<N; i++) {
    cin >> sbuff;
    score[sbuff] = 1;
  }

  cout << score.size() << endl;
}


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

int X,Y,Z,A,B,C,N;
typedef long long ll;

vector<ll> getxy(ll w,ll h,int st){
  vector<ll> a=vector<ll>(N);
  if( w > h ) swap(w,h);
  if( w <= 0 ) return a;
  ll cnt = 1;
  for(int i=0;i<w+h-1;i++){
    a[(st+i)%N]+=cnt;
    if( i < w-1 )
      cnt++;
    else if( i >= h-1 )
      cnt--;
  }
  return a;
}

void view(const vector<ll> v){
  for(int i=0;i<(int)v.size();i++) cout << v[i] << " ";
  cout << endl;
}


vector<ll> get(){
  vector<ll> ret = getxy(X-A,Y-B,0);
  vector<ll> a = getxy(X-A,B,1%N);
  for(int i=0;i<N;i++) ret[i] += a[i];
  a = getxy(A,B,2%N);
  for(int i=0;i<N;i++) ret[i] += a[i];
  a = getxy(A,Y-B,1%N);
  for(int i=0;i<N;i++) ret[i] += a[i];
  return ret;
}

vector<ll> solve(ll h,vector<ll> v){
  vector<ll> nv = vector<ll>(N);
  vector<ll> ret = vector<ll>(N);
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++)
      nv[(i+j)%N] += v[j];
  }
  for(int i=0;i<N;i++)
    ret[i] = nv[i]*(h/N);
  for(int i=0;i<h%N;i++){
    for(int j=0;j<N;j++)
      ret[(i+j)%N] += v[j];
  }
  return ret;
}


int main(){
  cin >> X >> Y >> Z >> A >> B >> C >> N;
  vector<ll> G = get();
  vector<ll> res=solve(Z-C,G);
  vector<ll> K = vector<ll>(N);
  for(int i=0;i<N;i++)
    K[(i+1)%N] = G[i];
  vector<ll> ps=solve(C, K);
  for(int i=0;i<N;i++){
    if( i ) cout << " ";
    cout << ps[i] + res[i];
  }
  cout << endl;
    
  
}

Measured memory_bytes: 1264
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
#include <tuple>
#include <numeric>
#include <assert.h>
#include <functional>
#include <unordered_map>

using namespace std;

/*-----------------------------------------------------------------------------
　定義
 -------------------------------------------------------------------------------*/
#define REP(i, n)				for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n)			for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define INF						(int)2e9
#define MOD						(1000 * 1000 * 1000 + 7)
#define Ceil(x, n)				(((((x))+((n)-1))/n))		/* Nの倍数に切り上げ割り算 */
#define CeilN(x, n)				(((((x))+((n)-1))/n)*n)		/* Nの倍数に切り上げ */
#define FloorN(x, n)			((x)-(x)%(n))				/* Nの倍数に切り下げ */
#define IsOdd(x)				(((x)&0x01UL) == 0x01UL)			
#define IsEven(x)				(!IsOdd((x)))						
#define ArrayLength(x)			(sizeof( x ) / sizeof( x[ 0 ]))
#define	MAX_QWORD				((QWORD)0xFFFFFFFFFFFFFFFF)
#define M_PI					3.14159265358979323846
typedef long long				ll;
typedef unsigned long long int	QWORD;
typedef pair<ll, ll>			P;

/*-----------------------------------------------------------------------------
　処理
 -------------------------------------------------------------------------------*/
int main()
{
	ll N;
	cin >> N;
	vector<ll> T(N), A(N);
	REP(i, N) {
		cin >> T[i] >> A[i];
	}

	ll tPrev = T[0];
	ll aPrev = A[0];
	REPN(i, 1, N) {
		ll rate = 1;
		rate = max(rate, tPrev / T[i]);
		rate = max(rate, aPrev / A[i]);
		while (1) {
			ll tNext = T[i] * rate;
			ll aNext = A[i] * rate;
			if ((tPrev <= tNext)&&(aPrev <= aNext)) {
				tPrev = tNext;
				aPrev = aNext;
				break;
			}
			rate++;
		}
	}

	cout << tPrev + aPrev  << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define mod 1000000000
#define ll long long
#define ull unsigned long long
#define vi vector<ll>
#define vs vector<string>
#define psi pair<string,ll>
#define pii pair<ll,ll>
#define vsi vector<psi>
#define vii vector<pii>
#define mp make_pair
#define pb push_back
#define rep(n) for(long i=0;i<n;i++)
#define repr(n) for(long i=(n-1);i>=0;i--)
#define fori(i,a,b) for(auto i=a;i<=b;i++)
#define ford(i,b,a) for(auto i=b;i>=a;i--)
#define mset(a,i) memset(a,i,sizeof(a))
#define minv(a) min_element(a.begin(),a.end())
#define maxv(a) max_element(a.begin(),a.end())
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define sotit(a) sort(a.begin(),a.end());
#define sot(a) sort(a,a+n);
#define ff first
#define maxheap(v) priority_queue<v>
#define minheap(v) priority_queue<v, vector<v>, greater<v>>
#define ss second
#define endl "\n"
#define NL cout<<endl;
#define printmat(a,m,n) for(int i=0;i<m;i++){       \
							for(int j=0;j<n;j++){   \
								cout<<a[i][j]<<" "; \
							}                       \
							cout<<endl;             \
						}
#define dbgn(x) cout<<" $ "<<x<<" $ "<<endl;
#define dbg(x) cout<<" $ "<<x<<" $ ";
#define all(v) v.begin(),v.end()
#define len(s) (ll)(s.size())
#define show(a,n) for(int i=0;i<n;i++){ cout<<a[i]<<" "; } NL
#define fast_io() cin.sync_with_stdio(false);cout.sync_with_stdio(false);cin.tie(NULL);
 
// lower_bound - which does not compare less than val
// upper_bound - which compares greater than val

int main() {
	fast_io()
 
	ll t;
	//cin>>t;
	t=1;
	while(t--){
		ll n,k;
		cin>>n>>k;
		ll h[n],dp[n];
		rep(n){
			cin>>h[i];
		}
		mset(dp,0);
		dp[1]=abs(h[1]-h[0]);
		ll ans;
		fori(i,2,n-1){
			ans=LLONG_MAX;
			fori(j,1,k){
				if(i-j>=0)
					ans=min(ans,dp[i-j]+abs(h[i]-h[i-j]));
			}
			dp[i]=ans;
		}
		cout<<dp[n-1];
	}
	return 0;
}

Measured memory_bytes: 1792
#define LOCAL

#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <vector>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <functional>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <iomanip>

using namespace std;

// From Errichto's Youtube stream
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

using int64 = long long;

/////////////////////
// Code starts here//
/////////////////////
int N;
string S;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> S;
    N = S.size();

    int64 result = 0;

    int at = 0;
    int n0 = 0;

    while(at < N) {
        if (S[at] != 'A') {
            at++;
            continue;
        }

        n0 = 0;

        while (at < N) {
            if (S[at] == 'A') {
                at++;
                n0++;
            } else if (at + 1 < N && S[at] == 'B' && S[at+1] == 'C') {
                result += n0;
                at += 2;
            } else {
                break;
            }
        }
    }

    cout << result << "\n";

    return 0;
}


Measured memory_bytes: 720
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
#include <cassert>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>

#define cauto const auto&
#define ALL(v) begin(v),end(v)
#else
#define ALL(v) (v).begin(),(v).end()
#endif

using namespace std;


namespace{
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
	v.assign(a, vector<T>(b, t));
}
template <class T> inline T &chmin(T &x, const T &y){ return x = min(x, y); }
template <class T> inline T &chmax(T &x, const T &y){ return x = max(x, y); }
template <class F, class T>
void convert(const F &f, T &t){
	stringstream ss;
	ss << f;
	ss >> t;
}


#define REP(i,n) for(int i=0;i<int(n);++i)
#define RALL(v) (v).rbegin(),(v).rend()


#define MOD 1000000007LL
#define EPS 1e-8

LL p3[100010];

LL func(int u, int ofs){
	return ((u ? p3[u - 1] * u : 0LL) + ofs * p3[u]) % MOD;
}

void mainmain(){
	p3[0] = 1;
	for(int i = 1; i < 100010; ++i){ p3[i] = p3[i - 1] * 3 % MOD; }
	string s;
	cin >> s;
	int lt = 0;
	int rt = count(ALL(s), '?');
	int a = 0;
	int c = count(ALL(s), 'C');
	LL ans = 0;
	for(char x : s){
		if(x == '?'){ --rt; }
		if(x == 'C'){ --c; }
		if(x == '?' || x == 'B'){
			LL t = func(lt, a);
			LL u = func(rt, c);
			ans = (ans + t * u) % MOD;
		}
		if(x == '?'){ ++lt; }
		if(x == 'A'){ ++a; }
	}
	cout << ans << endl;
}



}
int main() try{
//	ios::sync_with_stdio(false); cin.tie(0);
	cout << fixed << setprecision(10);
	cerr << fixed << setprecision(4);
	mainmain();
}
catch(...){}


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

#define rep(i,m,n) for(int (i)=(int)(m);i<(int)(n);++i)
#define rep2(i,m,n) for(int (i)=(int)(n)-1;i>=(int)(m);--i)
#define REP(i,n) rep(i,0,n)
#define REP2(i,n) rep2(i,0,n)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define all(hoge) (hoge).begin(),(hoge).end()
#define en '\n'
using ll = long long;
using ull = unsigned long long;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;
typedef pair<ll, ll> P;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
constexpr long long MOD = (ll) 1e9 + 7;
//constexpr long long MOD = 998244353LL;
using ld=long double;
static const ld pi = 3.141592653589793L;
typedef vector<ll> Array;
typedef vector<Array> Matrix;


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

struct Edge {
	ll to, rev;
    long double cap;
	Edge(ll _to, long double _cap, ll _rev) {
	to = _to; cap = _cap; rev = _rev;
	}
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

void add_edge(Graph& G, ll from, ll to, long double cap, bool revFlag, long double revCap) {
	G[from].push_back(Edge(to, cap, (ll)G[to].size()));
	if (revFlag)G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

void solve(){
	ll n;
	cin>>n;
	Array a(n);
	map<ll,ll> mp,mp2;
	REP(i,n){
		cin>>a[i];
		mp[a[i]]++;
	}
	mp2=mp;
	ll max_a=1010101;
	for(auto i:mp){
		if(mp2.find(i.first)==mp2.end()) continue;
		for(ll j=2;j*i.first<max_a;j++){
			if(mp2.find(i.first*j)!=mp2.end()){
				mp2.erase(i.first*j);
			}
		}
	}

	ll con=0;
	for(auto i:mp2){
		//cout<<i.first<<en;
		if(i.second>1) continue;
		con+=i.second;
	}
	cout<<con<<en;
}

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

	solve();
	//ll t;cin>>t;REP(i,t) solve();

    return 0;
}


Measured memory_bytes: 29808
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    int K,A,B,C;
    cin>>K;
    long long sum,X;
    sum=0;
    for(int i=1;i<=K;i++){
        for(int j=1;j<=K;j++){
            X=gcd(i,j);
            for(int l=1;l<=K;l++){
                sum+=gcd(X,l);
            }
        }
    }
    cout<<sum<<endl;
}


Measured memory_bytes: 3636
#include <stdio.h>
#include <string.h>
long long  t[105];
long long  fact(long long a,long long  b)
{

    long long c;
    long long t;
    long long  x;
    long long  y;
    if(a<b)
    {  t=a;
        a=b;

        b=t;
    }

    if(a%b==0)
    {


        return a;
    }

    x=a;
     y=b;

    long long m=x*y;

    do
   {

        c=a%b;
        a=b;
        b=c;

    }while(c);


    return x/a*y;


}
int main()
{

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


          memset(t,0,sizeof(t));
          for(int i=0;i<n;i++)
          {

              scanf("%lld",&t[i]);
          }
          int i;
          long long last;
          long long front=t[0];
           for(i=1;i<n;i++)
           {

               front =fact(front ,t[i]);



           }
             printf("%lld\n",front);



    return 0;
}


Measured memory_bytes: 128
using static System.Console;

class Program {
	static void Main() {
		var s = ReadLine();
		var n = s.Length;

		var ans = n;

		for (var i = 0; i < n && s[i] != 'A'; i++) {
			ans--;
		}

		for (var i = n - 1; i >= 0 && s[i] != 'Z'; i--) {
			ans--;
		}

		WriteLine(ans);
	}
}


Measured memory_bytes: 11616