akhauriyash/Code-Regression huggingface dataset:
//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;

// ?????¬???????????¬??????
#pragma region MACRO
#define P(x) cout << (x) << endl
#define p(x) cout << (x)
#define PED cout << "\n"
#define rep(i,n) for(int i=0; i<(int)n; ++i)
#define REP(i,x,n) for(int i=x; i<(int)n; ++i)
#define repi(i,n) for(int i=0; i<=(int)n; ++i)
#define REPI(i,x,n) for(int i=x; i<=(int)n; ++i)
#define ILP while(true)
#define FOR(i,c) for(__typeof((c).begin())!=(c).begin(); i!=(c).end(); ++i)
#define ALL(c) (c).begin(), (c).end()
#define mp make_pair
#pragma endregion

// ???
#pragma region TYPE_DEF
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<string, string> pss;
typedef pair<string, int> psi;
typedef pair<int, string> pis;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long double> vld;
typedef vector<long> vl;
typedef vector<long long> vll;
typedef vector<string> vs;
#pragma endregion

// Effective std
#pragma region ESTD
template<typename C, typename T> int count(C& c, T t) { return count(ALL(c), t); }
template<typename C, typename F> int count_if(C& c, F f) { return count_if(ALL(c), f); }
template<typename C, typename T> void erase(C& c, T t) { remove(ALL(c), t), c.end(); }
template<typename C> void remove(vector<C>& c, unsigned int index) { c.erase(c.begin()+index); }
template<typename C, typename T, typename U> void replace(C& c, T t, U u) { replace(ALL(c), t, u); }
template<typename C, typename F, typename U> void replace_if(C& c, F f, U u) { (ALL(c), f, u); }
template<typename C> void reverse(C& c) { reverse(ALL(c)); }
template<typename C> void sort(C& c) { sort(ALL(c)); }
template<typename C, typename Pred> void sort(C& c, Pred p) { sort(ALL(c), p); }
#pragma endregion

// ?????°
#pragma region CONST_VAL
constexpr int PI = (2*acos(0.0));
constexpr int EPS = (1e-9);
constexpr int MOD = (int)(1e9+7);
constexpr int INF = 100000000;
#pragma endregion


int main()
{
    int n, m, p;
    while(cin>>n>>m>>p, n) {
        int a, sum=0, win;
        rep(i,n) {
            cin >> a;
            if(i+1==m) win = a;
            sum += a*100;
        }
        sum *= 100-p;
        sum /= 100;
        if(win==0) cout << '0' << endl;
        else cout << sum/win << endl;
    }
    return 0;
}

Measured memory_bytes: 2932
#include<bits/stdc++.h>
using namespace std;
 
int main()
{
  int m, small, big, P[201];
 
  while(cin >> m >> small >> big, m) {
    for(int i = 1; i <= m; i++) {
      cin >> P[i];
    }
    int calc = 0;
    for(int i = big; i >= small; i--) {
      calc = max(calc, P[i] - P[i + 1]);
    }
    for(int i = big; i >= small; i--) {
      if(calc == P[i] - P[i + 1]) {
        cout << i << endl;
        break;
      }
    }
  }
  return(0);
}

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

string s;

int main() {
	cin >> s;
	int n = s.size(), p = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'p')
			p++;
	}
	cout << (n - p * 2) / 2 << endl;
}


Measured memory_bytes: 512
EOL = '0 0'
stdin = [line for line in iter(input, EOL)]
lines = (map(int, line.split()) for line in stdin)

for H, W in lines:
    for i in range(H):
        edge = '#' * W
        mid_point = '#{}#'.format('.' * (W - 2))
        if i in [0, H - 1]:
            print(edge)
        else:
            print(mid_point)
    print()


Measured memory_bytes: 5624
N = int(input())

d = []
cnt = 0
for i in range(1,N+1):
    if i % 2 == 1:
        for j in range(1,int(i**0.5)+1):
            if i % j == 0:
                d.append(j)
                if j != i//j:
                    d.append(i//j)
        if len(d) == 8:
            cnt +=1
        d = []
print(cnt)

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

int main(int argc, char const *argv[]) {
    int A, B, K;
    scanf("%d %d %d", &A, &B, &K);
    if (B - A + 1 <= K*2) {
        for (int i = A; i <= B; i++) {
            printf("%d\n", i);
        }
    } else {
        for (int i = A; i < A + K; i++) {
            printf("%d\n", i);
        }
        for (int i = B - K + 1; i <= B; i++) {
            printf("%d\n", i);
        }
    }
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int a,b;
    int count=0;
    int loopcheck=0;
    char c;
    while (cin>>a>>b) {
        if (a==0&&b==0) {
            break;
        } else {
            std::vector<vector<char>> vec(a,vector<char>(b));
            for (int i=0;i<a;i++) {
                for (int j=0;j<b;j++) {
                    cin>>c;
                    vec[i][j]=c;
                }
            }
            int tate=0;
            int yoko=0;
            while (vec[tate][yoko]!='.') {
                if (vec[tate][yoko]=='>') {
                    yoko++;
                    count++;
                } else if (vec[tate][yoko]=='<') {
                    yoko--;
                    count++;
                } else if (vec[tate][yoko]=='^') {
                    tate--;
                    count++;
                } else if (vec[tate][yoko=='v']) {
                    tate++;
                    count++;
                }
                if (count>a*b) {
                    cout<<"LOOP"<<endl;
                    loopcheck=1;
                    break;
                }
            }
            if (loopcheck!=1) {
                cout<<yoko<<" "<<tate<<endl;
                tate=0;
                yoko=0;
            }
            loopcheck=0;
            count=0;
        }
    }
}



Measured memory_bytes: 3176
#include<bits/stdc++.h>
typedef long long ll;
#define sz(x) int(x.size())
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define MOD 1000000007

using namespace std;

int main() {
    int N;
    int A[3][3];
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            cin >> A[i][j];
        }
    }
    cin >> N;
    int b[11];
    for (int i = 0; i < N; i++)
    {
        cin >> b[i];
    }
    int bingo[3][3];
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            bingo[i][j] = 0;
        }
        
    }
    for (int k = 0; k < N; k++)
    {
        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                if(A[i][j] == b[k]) bingo[i][j] = 1;
            }
            
        }
    }
    int cnt;
    for (int i = 0; i < 3; i++)
    {
        cnt = 0;
        for (int j = 0; j < 3; j++)
        {
            if(bingo[i][j] == 1) cnt++;
        }
        if(cnt == 3){
            cout << "Yes" << endl;
            return 0;
        }
    }

    for (int i = 0; i < 3; i++)
    {
        cnt = 0;
        for (int j = 0; j < 3; j++)
        {
            if(bingo[j][i] == 1) cnt++;
        }
        if(cnt == 3){
            cout << "Yes" << endl;
            return 0;
        }
    }

    if(bingo[0][0] == 1 && bingo[1][1] == 1 && bingo[2][2] == 1){
        cout << "Yes" << endl;
        return 0;
    }
    if(bingo[0][2] == 1 && bingo[1][1] == 1 && bingo[2][0] == 1){
        cout << "Yes" << endl;
        return 0;
    }
    
    cout << "No" << endl;
    return 0;
}

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

const int MOD = 998244353, N = 200005;

int n;
string s;
long long ans = 0, cnt[N];
vector<int> ve;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> s;
    for (int i = 1; i <= n; i += 2) {
        if (n % i == 0) {
            ve.push_back(i);
        }
    }
    reverse(ve.begin(), ve.end());
    for (int &u : ve) {
        int len = n / u;
        for (int i = 0; i < len; i++) {
            ((cnt[u] *= 2) += s[i] - '0') %= MOD;
        }
        cnt[u]++;
        for (int i = 0; i < n; i++) {
            char c = s[i % len];
            if ((i / len) & 1) {
                c ^= '0' ^ '1';
            }
            if (c > s[i]) {
                cnt[u]--;
                break;
            } else if (c < s[i]) {
                break;
            }
        }
        for (int &v : ve) {
            if (v > u && v % u == 0) {
                (cnt[u] -= cnt[v]) %= MOD;
            }
        }
        (ans += cnt[u] * len) %= MOD;
    }
    cout << ((ans + MOD) * 2) % MOD;
}


Measured memory_bytes: 720
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int x = sc.nextInt();
		int y = sc.nextInt();
			if(n < k){
				System.out.println(x * n);
			}else
				System.out.println(x * k + y * (n - k));
	}

}


Measured memory_bytes: 8788
#include<stdio.h>
#include<string.h>
int main(){
	int n[101],t,i,max=0;
	memset(n,0,sizeof(n));
	for(;scanf("%d",&t)!=EOF;){
		n[t]++;
		if(max<n[t])max=n[t];
	}
	for(i=1;i<101;i++)if(max==n[i])printf("%d\n",i);
	exit(0);
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define int long long
#define multi_test true and false
using namespace std;

void solve()
{
    string s;
    cin >> s;
    map<string, string> mp;
    mp["ABC"] = "ARC";
    mp["ARC"] = "ABC";
    cout << mp[s] << endl;
}

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

    int test = 1;
    if (multi_test)
        cin >> test;

    while (test--)
        solve();
    return 0;
}

Measured memory_bytes: 3660
#include <iostream>
using namespace std;
int main()
{
    long int res;
    int i, N;
    cin >> N;
    res = 0;
    for (i = 0; i <= N; i++)
    {
        if (i % 3 != 0 && i % 5 != 0)
        {
            res += i;
        }
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3632
#include<stdio.h>
int main(void)
{
	int a, b;
	char op;

	scanf("%d %c %d", &a, &op, &b);

	while (op != '?') {
		if (op == '+') {
			printf("%d\n", a + b);
		}
		else if (op == '-') {
			printf("%d\n", a - b);
		}
		else if (op == '*') {
			printf("%d\n", a * b);
		}
		else if (op == '/') {
			printf("%d\n", a / b);
		}
		scanf("%d %c %d", &a, &op, &b);

	}

	return(0);
}


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

using namespace std;

const int max_n = 100111;
const long long inf = 1000111222000111222LL;

int n, m, used[max_n], z[max_n];
long long a[max_n];
int b1, b2;
vector<int> g[max_n], s[max_n];

bool bad(int v, int col) {
    used[v] = col;
    for (int to : g[v]) {
        if (used[to]) {
            if (used[v] == used[to]) {
                b1 = v;
                b2 = to;
                return true;
            }
        } else {
            if (bad(to, 3 - used[v])) {
                return true;
            }
        }
    }
    return false;
}

void dfs(int v, long long x, int zz) {
    z[v] = zz;
    a[v] = x;
    for (int i = 0; i < g[v].size(); ++i) {
        int to = g[v][i];
        if (z[to] == 0) {
            dfs(to, s[v][i] - x, -zz);
        }
    }
}

bool positive() {
    for (int i = 1; i <= n; ++i) {
        if (a[i] <= 0) {
            return false;
        }
    }
    return true;
}

bool ok() {
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < g[i].size(); ++j) {
            int to = g[i][j];
            if (s[i][j] != a[i] + a[to]) {
                return false;
            }
        }
    }
    return true;
}

long long solve() {
    if (bad(1, 1)) {
        dfs(1, 1, 1);
        long long cost;
        for (int i = 0; i < g[b1].size(); ++i) {
            if (g[b1][i] == b2) {
                cost = s[b1][i];
                break;
            }
        }
        if (z[b1] != z[b2]) {
            exit(228);
        }
        long long sum = a[b1] + a[b2];
        long long pl = (cost - sum) / (2 * z[b1]);
        memset(z, 0, sizeof(z));
        dfs(1, 1 + pl, 1);
        return ok() && positive();
    } else {
        dfs(1, 1, 1);
        if (!ok()) {
            return 0;
        }
        long long l = 1, r = inf;
        for (int i = 1; i <= n; ++i) {
            if (z[i] == 1) {
                l = max(l, 2 - a[i]);
            } else {
                r = min(r, a[i]);
            }
        }
        //cout << l << " " << r << endl;
        return max(0LL, r - l + 1);
    }
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    scanf("%d%d", &n, &m);
    while (m--) {
        int u, v, x;
        scanf("%d%d%d", &u, &v, &x);
        g[u].push_back(v);
        g[v].push_back(u);
        s[u].push_back(x);
        s[v].push_back(x);
    }
    printf("%lld\n", solve());
    return 0;
}


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

using namespace std;

multiset<int> s;
int a[1000010];
int main(){

	int N, L;
	cin >> N >> L;

	for(int i = 0 ;i < L; i++){
		cin >> a[i];
		s.insert(a[i]);
	}

	cout << *s.begin();

	for(int i = L; i < N; i++){
		cin >> a[i];
		s.insert(a[i]);
		s.erase(s.find(a[i-L]));
		cout << ' ' <<*s.begin();  
	}

	cout << '\n';

	return 0;
}



Measured memory_bytes: 11708
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma warning(disable : 4996)
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<time.h>
#include<random>
#include<array>


using namespace std;

#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, m, n) for(int i = m;i < n;++i)
#define FORR(i, m, n) for(int i = m-1;i >= n;--i)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define print(x) cout<<(x)<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define lb(v,n) lower_bound(v.begin(), v.end(), (n))
#define ub(v,n) upper_bound(v.begin(), v.end(), (n))
#define int long long
//#define double long double
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i,v.size())cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
typedef pair<int, int>P;
typedef array<int, 3> arr3;
std::random_device rd;
std::mt19937 mt(rd());
constexpr int MOD = 1e9 + 7; constexpr int MAX = 200020;
const double pi = acos(-1); constexpr double EPS = 1e-8;
constexpr ll INF = 1e18;

int A[32] = { 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51 };
void solve() {
	int K; cin >> K;
	print(A[K - 1]);
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//int q; cin >> q;
	//while (q--)
	solve();
}



Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <random>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

i64 n;
vector<i64> a, b, c;
int main() {
  cin >> n;
  read_n(a, n);
  read_n(b, n, 1);
  read_n(c, n - 1, 1);

  i64 ans = 0;
  for (i64 i = 0; i < n; ++i) {
    i64 x = a[i];
    ans += b[x];
    if (a[i + 1] == a[i] + 1) ans += c[a[i]];
  }
  cout << ans << endl;
  return 0;
}


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

int main() {
    int n, k, r, s, p;
    string t;
    cin >> n >> k >> r >> s >> p >> t;

    long long ans = 0;
    string past[n];
    for (int i = 0; i < n; i++) {
        string t_ = t.substr(i, 1);
        if (i < k || t_ != past[i - k]) {
            past[i] = t_;
            if (t_ == "r") {
                ans += p;
            } else if (t_ == "p") {
                ans += s;
            } else if (t_ == "s") {
                ans += r;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;

const int N = 123456;

int n, a[N], son[N], d[N];
vector<int> values[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 2; i <= n; ++i) {
    cin >> a[i];
    ++son[a[i]];
  }
  queue<int> q;
  for (int i = 1; i <= n; ++i) {
    if (!son[i]) {
      q.push(i);
    }
  }
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    sort(values[x].begin(), values[x].end());
    int t = 0;
    while (values[x].size()) {
      d[x] = max(d[x], ++t + values[x].back());
      values[x].pop_back();
    }
    values[a[x]].push_back(d[x]);
    if (--son[a[x]] == 0) {
      q.push(a[x]);
    }
  }
  cout << d[1] << '\n';
  return 0;
}

Measured memory_bytes: 7680
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include<complex>
#include <cassert>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repd(i, n) for (int i = n; i > 0; i--)
#define mod 1000000007
#define MOD 998244353
#define inf 1e20
typedef long long int ll;
typedef pair<ll, ll> pr;
typedef complex<double> com;


int main(){
	string s, t;
	cin >> s >> t;
	string ans = "H";
	if (s == "D" || t == "D") {
		ans = "D";
	}
	if (s == "D"&&t == "D") {
		ans = "H";
	}
	cout << ans << endl;
	return 0;
}
//Ctrl+Aを使わない

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define INT_MAX INT64_MAX
#define INT_MIN INT64_MIN
#define PI 3.14159265358979323846
#define CLK clock_t clk = clock();//Start of main
#define OCLK cerr << "Time (in ms): " << (double)(clock() - clk) * 1000.0 / CLOCKS_PER_SEC << '\n';//End of main
#define MOD 1000000007
/* DEFINE cout */
#define pln cout << "===============================\n"
#define on cout<<"\n"
#define os cout<<" "
#define o2(a,b) cout<<a<<" "<<b
#define o(a) cout << a
#define bitcount __builtin_popcount
/* DEFINE cout */
#define endl "\n"
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);//fastio
using namespace std;
struct hash_pair { // use pair as key in unordered_map<pair<int,int>,int,hash_pair>;
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
        return hash1 ^ hash2;
    }
};
bool prime[10000001];
int P=MOD-2;
int factorial[10000001]={0};
int powerFunction(int x,int y){
    int res = 1;
    int p = MOD;
    x = x % p;
    while (y > 0){
        if (y & 1)
            res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}
void sieveFunction(int maxLimit){
    memset(prime, true, sizeof(prime));
    prime[0] = prime[1]=false;
    for(int i=2; maxLimit >= i ; i++){
        if(prime[i]){
            for(int j=2*i ; maxLimit >= j ; j+=i)
                prime[j]=false;
        }
    }
}
void factorialFunction(int maxLimit){
    factorial[0]=1;
    for(int i=1 ; i <= maxLimit ; i++)
        factorial[i]=(factorial[i-1]*i)%MOD;
    return;
}
int gcd(int a, int b){
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
signed main(){
    int l, r, d;;
    cin >> l >> r >> d;
    cout << r/d - (l-1)/d << endl;
}






Measured memory_bytes: 3632
#include<cstdio>
int n,p[100010],m,x,r[100010],v[100010],beg[100010],cnt1,cnt2;
long long a[100010],k,ans[100010];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%lld",a+i),a[i-1]=a[i]-a[i-1],p[i-1]=i-1;
	scanf("%d%lld",&m,&k);
	for(int i=1;i<=m;++i)scanf("%d",&x),p[x]^=p[x-1],p[x-1]^=p[x],p[x]^=p[x-1];
	for(int i=0;i<n;++i)if(!r[i]){
		v[beg[++cnt2]=++cnt1]=i;r[i]=cnt2;
		for(int j=p[i];j!=i;j=p[j])v[++cnt1]=j,r[j]=cnt2;
	}beg[cnt2+1]=n+1;
	for(int i=1;i<=cnt2;++i){
		int len=beg[i+1]-beg[i];
		for(int j=beg[i];j<beg[i+1];++j)ans[v[j]]=v[(j-beg[i]+k)%len+beg[i]];
	}
	ans[0]=a[ans[0]];for(int i=1;i<n;++i)ans[i]=a[ans[i]]+ans[i-1];
	for(int i=0;i<n;++i)printf("%lld.0\n",ans[i]);
	return 0;
}

Measured memory_bytes: 4480
#include <cstdio>
#include <iostream>
#include <queue>
#include <set>

using namespace std;

template<typename C, typename C::value_type low, typename C::value_type high>
class PalindromeTree{
  const static int m = high - low + 1;
  typedef typename C::value_type T;

  struct node{
    int next[m];
    int len;
    int sufflink;
  };

  const C s;
  int len;
  int num;

  void initTree(){
    num = 2; suff = 2;
    tree[1].len = -1; tree[1].sufflink = 1;
    tree[2].len = 0; tree[2].sufflink = 1;
  }

public:
  vector<node> tree;
  int suff;

  bool addLetter(int pos){
    int cur = suff;
    int curLen = 0;
    const int let = s[pos] - low;

    while(true){
      curLen = tree[cur].len;
      if(pos - 1 - curLen >= 0 && s[pos - 1 - curLen] == s[pos]) break;
      cur = tree[cur].sufflink;
    }

    if(tree[cur].next[let]){
      suff = tree[cur].next[let];
      return false;
    }

    num++;
    suff = num;
    tree[num].len = tree[cur].len + 2;
    tree[cur].next[let] = num;

    if(tree[num].len == 1){
      tree[num].sufflink = 2;
      return true;
    }

    while(true){
      cur = tree[cur].sufflink;
      curLen = tree[cur].len;
      if(pos - 1 - curLen >= 0 && s[pos - 1 - curLen] == s[pos]){
	tree[num].sufflink = tree[cur].next[let];
	break;
      }
    }

    return true;
  }

  PalindromeTree(const C &s)
    : s(s), len(s.size()), tree(s.size() + 3){
    initTree();
  }

  void build(){
    for(int i = 0; i < len; i++){
      addLetter(i);
    }
  }

  static long long countSamePalindrome(const C &s, const C &t, const C &sp){
    long long ans = 0;
    const C sum = s + sp + t;
    PalindromeTree tree(sum);
    vector<long long> scnt(sum.size() + 3);
    vector<long long> tcnt(sum.size() + 3);

    for(int i = 0; i < (int)sum.size(); i++){
      tree.addLetter(i);

      int pos = tree.suff;
      const node &nd = tree.tree[pos];
      if(i - nd.len + 1 < (int)s.size()){
	scnt[pos]++;
      }else if(i - nd.len + 1 >= (int)(s.size() + sp.size())){
	tcnt[pos]++;
      }
    }

    for(int i = 0; i < 2; i++){
      vector<long long> &v = i == 0 ? scnt : tcnt;

      vector<int> ref(v.size());
      for(int j = 3; j < (int)v.size(); j++){
	if(v[j] > 0 && tree.tree[j].sufflink >= 3){
	  ref[tree.tree[j].sufflink]++;
	}
      }

      queue<int> q;
      for(int j = 3; j < (int)v.size(); j++){
	if(v[j] > 0 && ref[j] == 0) q.push(j);
      }

      while(q.size()){
	const int pos = q.front(); q.pop();
	const int suff = tree.tree[pos].sufflink;
	if(suff >= 3){
	  v[suff] += v[pos];
	  ref[suff]--;
	  if(ref[suff] == 0) q.push(suff);
	}
      }
    }

    for(int i = 3; i < (int)scnt.size(); i++){
      ans += scnt[i] * tcnt[i];
    }

    return ans;
  }
};

typedef PalindromeTree<string, 'a', 'z'> SPalindromeTree;

char buff[50000 + 10];
string getStr(){
  scanf("%s", buff);
  return buff;
}

int main(){
  const string s = getStr();
  const string t = getStr();

  typedef PalindromeTree<string, 'A' - 2, 'Z'> SPalindromeTree;
  printf("%lld\n", SPalindromeTree::countSamePalindrome(s, t, "@?"));
  return 0;
}

Measured memory_bytes: 15172
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll a,b,c,d;
int main()
{
	cin>>a>>b>>c>>d;
	ll m,n;
	if(a%d==0) m=a/d;
	else m=a/d+1;
	n=(c+b-1)/b;
	if(m>=n)
	{
		cout<<"Yes";
	}
	else
	cout<<"No";
    return 0;
}

Measured memory_bytes: 3580
N,A,B,C = map(int, input().split())
bamboos = [int(input()) for _ in range(N)]
#print("---", bamboos)
INF = float("inf")
ans = INF
def solve(idx, cnt_merge, a, b, c):

    if idx == N:
        if min(a,b,c) > 0:
            return abs(A - a) + abs(B - b) + abs(C - c) + 10 * (cnt_merge-3)
        else:
            return INF

    pa = solve(idx+1, cnt_merge+1, a+bamboos[idx], b, c)
    pb = solve(idx+1, cnt_merge+1, a, b+bamboos[idx], c)
    pc = solve(idx+1, cnt_merge+1, a, b, c+bamboos[idx])
    pn = solve(idx+1, cnt_merge, a, b, c)
    return min(pa, pb, pc, pn)


print(solve(0,0,0,0,0))

Measured memory_bytes: 44892
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    int a, ans;
    Scanner sc = new Scanner(System.in);

    a = sc.nextInt();
    sc.close();
    ans = a + a * a + a * a * a;
    System.out.printf("%d", ans);
  }
}

Measured memory_bytes: 35808
#include <bits/stdc++.h>
 
#define A_MAX 1000000
 
using namespace std;
 
int scanint() { 
	char c = getchar_unlocked();
    int x = 0;
    for(; (c<48)||(c>57);c = getchar_unlocked());
    for(; (c>47)&&(c<58);c = getchar_unlocked())
        x = 10 * x + c - 48;
    return x;
} 
 
int min_factor[A_MAX + 1];
int q[A_MAX + 1];
int a[A_MAX + 1];
int primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997 };
 
int main() {
 
    for (int i = 2; i <= A_MAX; ++i) {
        if (!min_factor[i]) {
            min_factor[i] = i;
        }
        int j = 0;
        for (int p = primes[0]; ; p = primes[++j]) {
            int n = i * p;
            if (n > A_MAX) {
                break;
            }
            min_factor[n] = p;
            if (p == min_factor[i]) {
                q[n] = q[i];
                break;
            } else {
                q[n] = i;
            }
        }
    }
 
    int N = scanint();
    for (int i = 0; i < N; ++i) {
        ++a[scanint()];
    }
 
    bool is_pairwise_coprime = true;
    for (int n = A_MAX; n > 1; --n) {
        int an = a[n];
        if (an) {
            if (an > 1) {
                if (an == N) {
                    printf("not coprime\n");
                    return 0;
                }
                is_pairwise_coprime = false;
            }
            a[min_factor[n]] += an;
            a[q[n]] += an;
        }
    }
    if (is_pairwise_coprime) {
        printf("pairwise coprime\n");
    } else {
        printf("setwise coprime\n");
    }

    return 0;
}

Measured memory_bytes: 15352
while True:
    try:
        l=list(map(int, input().split()))
        x=(l[1]*l[5]-l[2]*l[4])/(l[1]*l[3]-l[0]*l[4])
        y=(l[2]-l[0]*x)/l[1]
        if x == 0: x = 0
        print( "{0:.3f} {1:.3f}".format(x,y))
    except:
        break

Measured memory_bytes: 7624
/*
配りDP
*/

# include <iostream>
# include <algorithm>

using namespace std;

int N, K;
long long h[100010], dp[100010];
const long long INF = 1LL << 60;

int main() {
  cin >> N >> K;
  for (int i = 0; i < N; i++) cin >> h[i];
  for (int i = 0; i < N; i++) dp[i] = INF;
  
  dp[0] = 0;
  for (int i = 0; i < N; i++) {
    int repeat = 0;
    if (N < K) repeat = N - 1;
    else repeat = K;
    
    for (int j = 1; j <= repeat; j++) {
      dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]));
    }
  }
  
  cout << dp[N - 1] << endl;
  
  return 0;
}

Measured memory_bytes: 1792
const main = (input) => {
  const n = Number(input.trim())
  let ans = 0
  for (let i=1; i<=n; i++) if (i%3 && i%5) ans += i
  return console.log(ans)
}

process.env.MYTEST
  ? (process.env.MYTEST === 'test' ? test() : main(require('fs').readFileSync('dev/stdin', 'utf8')))
  : main(require('fs').readFileSync('/dev/stdin', 'utf8'))

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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> TUP;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define mp(a,b) make_pair(a,b)
const ll MOD=1000000007;

ll maxx(ll x,ll y,ll z){
	return max(max(x,y),z);
}
ll minn(ll x,ll y,ll z){
	return min(min(x,y),z);
}
ll gcd(ll x,ll y){
	if(x%y==0) return y;
    else return gcd(y,x%y);
}
ll lcm(ll x,ll y){
	return x*(y/gcd(x,y));
}

int main(){
	ll N,M; cin>>N>>M;
	vector<ll> X(M);
	rep(i,M) cin>>X[i];
	vector<ll> D(M-1);
	ll ans=0;
	if(N>=M) cout<<0;
	else{
		sort(X.begin(),X.end());

		rep(i,M-1) D[i]=X[i+1]-X[i];
		sort(D.begin(),D.end());
		rep(i,M-N) ans+=D[i];
		cout<<ans;
	}
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <map>
#include <time.h>

using namespace std;

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

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod (ll)(1e9+7)
#define int ll

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

signed main() {
  string s;
  cin >> s;
  rep(i, 0, s.length() - 1) {
    if(i < s.length() - 2) {
      if(s[i] == s[i + 2]) {
        cout << i + 1 << " " << i + 3 << endl;
        return 0;
      }
    }
    if(s[i] == s[i + 1]) {
      cout << i + 1 << " " << i + 2 << endl;
      return 0;
    }
  }
  cout << -1 << " " << -1 << endl;
}


Measured memory_bytes: 512
#include <iostream>
using namespace std;
int main(){
	for(int i=0;i<3;++i){
		int h1,m1,s1,h2,m2,s2;
		cin>>h1>>m1>>s1>>h2>>m2>>s2;
		int d=(h2-h1)*3600+(m2-m1)*60+s2-s1;
		cout<<d/3600<<" "<<d%3600/60<<" "<<d%3600%60<<"\n";
	}
	return 0;
}

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

int main(){
  int bingo[3][3];
  for(int i = 0; i < 3; i++){
    for(int j = 0; j < 3; j++){
      cin >> bingo[i][j];
    }
  }
  int n; cin >> n;
  int num;
  int flag[8]={};
  for(int k = 0; k < n; k++){
    cin >> num;
    for(int i = 0; i < 3; i++){
      for(int j = 0; j < 3; j++){
        if(bingo[i][j] == num){
          flag[i]++;
          flag[3+j]++;
          if(i==j) flag[6]++;
          if(i==2-j) flag[7]++;
        }
      }
    }
  }
  
  for(int i = 0; i < 8; i++){
    if(flag[i]==3){
      cout << "Yes";
      return 0;
    }
  }
  
  cout << "No";
  return 0; 
}

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

#define fi first
#define se second
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 5e6 + 5;
const int ha = 1e9 + 7;

inline int qpow(int a,int n=ha-2){
	int res = 1;
	while(n){
		if(n & 1) res = 1ll*res*a%ha;
		a = 1ll*a*a%ha;
		n >>= 1;
	}
	return res;
}

int fac[MAXN],inv[MAXN];

inline void prework(){
    fac[0] = 1;FOR(i,1,MAXN-1) fac[i] = 1ll*fac[i-1]*i%ha;
    inv[MAXN-1] = qpow(fac[MAXN-1]);
    ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha;
}

inline int C(int n,int m){
    if(n < m) return 0;
    if(!m) return 1;
    return 1ll*fac[n]*inv[m]%ha*inv[n-m]%ha;
}

inline int calc1(int x,int y){// (0,0) 到 (x,y)
    if(x < 0 || y < 0) return 0;
    return C(x+y,x);
}

inline int calc2(int x,int y){ // (0,0) 到 ([0,x],[0,y])
//    return (C(x+y+2,x+1)+ha-1)%ha;
    return (calc1(x+1,y+1)+ha-1)%ha;
}

inline int calc3(int x1,int x2,int y1,int y2){// (0,0) 到 ([x1,x2],[y1,y2])
//    int res = calc2(x2,y2);
//    (res += ha-calc2(x2,y1-1)) %= ha;
//    (res += ha-calc2(x1-1,y2) %= ha;
//    (res += calc2(x1-1,y1-1)) %= ha;
    int res = calc1(x2+1,y2+1);
    (res += ha-calc1(x2+1,y1)) %= ha;
    (res += ha-calc1(x1,y2+1)) %= ha;
    (res += calc1(x1,y1)) %= ha;
    return res;
}

inline int calc4(int x,int y,int x1,int x2,int y1,int y2){// (x,y) 到 ([x1,x2],[y1,y2])
    return std::min(x1,x2) >= x && std::min(y1,y2) >= y ? calc3(x1-x,x2-x,y1-y,y2-y) : calc3(x-x2,x-x1,y-y2,y-y1);
    // 实际应用是要判包含的 但是这个题不会
}
int x[233],y[233];
int main(){
    prework();
    FOR(i,1,6) scanf("%d",x+i);
    FOR(i,1,6) scanf("%d",y+i);
    int ans = 0;
    FOR(i,x[3],x[4]){
        (ans += 1ll*(ha-(i+y[3])%ha)*calc4(i,y[3]-1,x[1],x[2],y[1],y[2])%ha*calc4(i,y[3],x[5],x[6],y[5],y[6])%ha) %= ha;
        (ans += 1ll*(i+y[4]+1)%ha*calc4(i,y[4],x[1],x[2],y[1],y[2])%ha*calc4(i,y[4]+1,x[5],x[6],y[5],y[6])%ha) %= ha;
    }
    FOR(i,y[3],y[4]){
        (ans += 1ll*(ha-(i+x[3])%ha)*calc4(x[3]-1,i,x[1],x[2],y[1],y[2])%ha*calc4(x[3],i,x[5],x[6],y[5],y[6])%ha) %= ha;
        (ans += 1ll*(x[4]+i+1)%ha*calc4(x[4],i,x[1],x[2],y[1],y[2])%ha*calc4(x[4]+1,i,x[5],x[6],y[5],y[6])%ha) %= ha;
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 39424
#include <iostream>

using namespace std;

const long long int INF = 1000000001;

int main(){
  long long int N, W, V_MAX;
  cin >> N >> W;
  long long int w[N], v[N], dp[N+1][1000*N+1], ans;
  fill(dp[0], dp[0]+1000*N+1, INF);
  dp[0][0] = 0;
  for(int i=0; i<N; i++) cin >> w[i] >> v[i];
  for(int i=0; i<N; i++){
    if(i==0) V_MAX = v[i];
    if(V_MAX < v[i]) V_MAX = v[i];
  }
  for(int i=0; i<N; i++){
    for(int j=0; j<=V_MAX*N; j++){
      if(j-v[i] < 0) dp[i+1][j] = dp[i][j];
      else dp[i+1][j] = min(dp[i][j], dp[i][j-v[i]]+w[i]);
    }
  }

  for(int j=0; j<=V_MAX*N; j++){
    if(dp[N][j] <= W) ans = j;
  }

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


Measured memory_bytes: 79104
#include<iostream>
#include<map>
#include<unordered_map>
#include<set>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef long double ld;
#define mp make_pair
#define pb push_back
const ll mod = 1000000007;
// const ll mod = 998244353;

const ll LLMAX = numeric_limits<long long>::max();

void No() {
	cout << "No" << endl;
}

void Yes() {
	cout << "Yes" << endl;
}

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

	vector<pair<ll, ll>> AB(N);

	for (ll i = 0; i < N; i++) {
		ll a, b;
		cin >> a >> b;
		AB[i] = mp(a, b);
	}
	sort(AB.begin(), AB.end());

	multiset<ll> W;

	ll count = 0;
	ll id = 0;
	ll size = 0;
	for (ll m = 1; m <= M; m++) {

		for (; id < N;) {
			if (AB[id].first <= m) {
				W.insert(AB[id].second);
				size++;
				id++;
			}
			else {
				break;
			}
		}
		if (size >= 1) {
			auto itr = W.end();
			itr--;
			count += *itr;
			W.erase(itr);
			size--;
		}
	}


	cout << count << endl;
	return 0;
}

Measured memory_bytes: 6400
#include<bits/stdc++.h>
using namespace std;
#define all(vec) vec.begin(),vec.end()
typedef long long int ll;
const ll MOD=1000000007;
const ll INF=1000000010;
const ll LINF=4000000000000000010LL;
const int MAX=310;
const double EPS=1e-8;
int dx[4]={0,0,1,-1};
int dy[4]={-1,1,0,0};
int main(){
	double q;
	while(cin>>q,q!=-1){
		double b=q/2;
		while(abs(pow(b,3)-q)>=0.00001*q){
			b=b-(pow(b,3)-q)/(3*pow(b,2));
		}
		printf("%.6lf\n",b);
	}
		
}



Measured memory_bytes: 3048
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
using ll = long long;

int main(){
    string S;
    cin >> S;
    vector<string> ts = {"dreameraser", "dreamerase", "dreamer", "dream", "eraser", "erase"};
    for(int i=0;i<S.size();){
        bool ok = false;
        for(string& t: ts){
            if(S.substr(i, t.size()) == t){
                i += t.size();
                ok = true;
                break;
            }
        }
        if(!ok){
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i, s, n) for (int i = s; i < n; i++)
#define rp(i,n) for (int i=0;i<n;i++)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define all_acc(x) (x).begin(), (x).end(), 0LL
#define int long long
#define absSort(v) sort(a.begin(), a.end(), [](int i, int j) -> bool { return abs(i) < abs(j); });
using namespace std;
using P = pair<int, int>;
using Graph = vector<vector<int>>;
using ll = long long;
double pi=3.14159265359;

//出力するよ
void output_tate(vector<int> s){
    int n = s.size();
    for (int i = 0; i < n; i++){
        //if (i != 0)
        //    cout << " ";
        cout << s[i]<<endl;
    }
    //cout << endl;
}

void output_yoko(vector<int> s){
    int n = s.size();
    for (int i = 0; i < n; i++){
        if (i != 0)
            cout << " ";
        cout << s[i];//<<endl;
    }
    cout << endl;
}
int MOD = pow(10, 9) + 7;

//幅優先探索
//disは各座標への距離。行けない場合は-1にしている。
//chaは各座標の情報。文字で格納している。'.'はすすめる。'#'は壁(黒)。
//sはスタートの座標
//gはゴールの座標
vector<vector<int>> bfs(vector<vector<int>> dis,vector<vector<char>>cha,pair<int,int>s,pair<int,int>g){
    int h=dis.size();
    int w=dis.at(0).size();

    set<pair<int,int>> seen;
    queue<pair<int,int>> Q;
    Q.push(s);
    dis.at(s.first).at(s.second)=0;
    if(cha[0][0]=='#') dis[0][0]=1;
    else dis[0][0]=0;

    while(!Q.empty()){
        int y,x;//今の座標
        //seen.insert(make_pair(y,x));
        y=Q.front().first; x=Q.front().second;
        Q.pop();

        int dy[4]={1,0,-1,0};
        int dx[4]={0,1,0,-1};
        for(int i=0;i<2;i++){
            int ey=y+dy[i];
            int ex=x+dx[i];
            int cs;
            if(ex<0||ey<0||ex>=w||ey>=h) continue;
            //if(dis[ey][ex]!=10000000) continue;
            if(cha[y][x]=='.' && cha[ey][ex]=='#') cs=dis[y][x]+1;
            else cs=dis[y][x];

            if(dis[ey][ex]==-1 || cs<dis[ey][ex]){
                Q.push({ey,ex});
                dis[ey][ex]=cs;
            }
        }
    }

    return dis;
}

signed main() {
    int h,w; cin>>h>>w;
    vector<vector<char>> grid(h,vector<char>(w));
    vector<vector<int>> dis(h,vector<int>(w,-1));
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++) cin>>grid[i][j];
    }

    dis=bfs(dis,grid,make_pair(0,0),make_pair(h-1,w-1));


    //for(int i=0;i<h;i++){
    //    output_yoko(dis[i]);
    //}

    cout<<dis[h-1][w-1]<<endl;
}

Measured memory_bytes: 3776
#include<iostream>
using namespace std;
int n, cnt;
int a[100000];

void _swap(int p, int q, int v, int w) {
	int c, d;
	c = p;
	d = q;
	p = d;
	q = c;
	a[v] = p;
	a[w] = q;
}

int main() {
	while (true){
		cnt = 0;
		cin >> n;
		if (n == 0) { break; }
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		for (int i = n - 1; i >= 0; i--){
			for (int j = 0; j < i; j++) {
				if (a[j] > a[j + 1]) {
					cnt++;
					_swap(a[j], a[j + 1], j, j + 1);
				}
			}
		}
		cout << cnt << endl;
	}
}

Measured memory_bytes: 1164
#include <iostream>
#include <cstdio>

using namespace std;

int main(){
	
	string str, str_a, str_b, str_c;
	
	while(true){
		
		cin >> str;
		
		if(cin.eof()){
			break;
		}
		
		for(int i = 0; i < str.size(); i++){
			if(str[i] == '+'){
				str_a = str.substr(0, i);
			}
			if(str[i] == '='){
				str_b = str.substr(str_a.size() + 1, i - 1 - str_a.size());
				str_c = str.substr(i + 1);
			}
		}
		
		string str_a2, str_b2, str_c2, str_ab;
		
		bool checker;
		
		for(int i = 0; i <= 9; i++){
			str_a2 = str_a;
			str_b2 = str_b;
			str_c2 = str_c;
			str_ab = str_c;
			for(int j = 0; j < str_a2.size(); j++){
				if(str_a2[j] == 'X'){
					str_a2[j] = '0' + i;
				}
			}
			for(int j = str_a2.size(); j < str_ab.size(); j++){
				str_a2 = "0" + str_a2;
			}
			for(int j = 0; j < str_b2.size(); j++){
				if(str_b2[j] == 'X'){
					str_b2[j] = '0' + i;
				}
			}
			for(int j = str_b2.size(); j < str_ab.size(); j++){
				str_b2 = "0" + str_b2;
			}
			for(int j = 0; j < str_c2.size(); j++){
				if(str_c2[j] == 'X'){
					str_c2[j] = '0' + i;
				}
			}
			checker = false;
			if(i == 0){
				for(int j = 0; j < str_a.size() - 1; j++){
					if(str_a[j] >= '1' && str_a[j] <= '9'){
						break;
					}else if(str_a[j] == 'X'){
						checker = true;
						break;
					}
				}
				for(int j = 0; j < str_b.size() - 1; j++){
					if(str_b[j] >= '1' && str_b[j] <= '9'){
						break;
					}else if(str_b[j] == 'X'){
						checker = true;
						break;
					}
				}
				for(int j = 0; j < str_c.size() - 1; j++){
					if(str_c[j] >= '1' && str_c[j] <= '9'){
						break;
					}else if(str_c[j] == 'X'){
						checker = true;
						break;
					}
				}
			}
			if(checker){
				continue;
			}
			for(int j = 0; j < str_ab.size(); j++){
				str_ab[j] = '0';
			}
			
			for(int j = str_ab.size() - 1; j >= 0; j--){
				str_ab[j] = str_ab[j] + str_a2[j] + str_b2[j] - '0' - '0';
				if(str_ab[j] > '9'){
					str_ab[j] -= 10;
					if(j >= 1){
						str_ab[j - 1] += 1;
					}else{
						str_ab = "1" + str_ab;
					}
				}
			}
			//cout << str_c2 << endl << str_ab << endl << endl;
			if(str_c2 == str_ab){
				printf("%d\n", i);
				break;
			}else if(i == 9){
				printf("NA\n");
			}
		}
	}
	
	return 0;
}

Measured memory_bytes: 1212
# |-| | | | |
# のように一番左の一本が決まったとき、残りの
#     | | | |
# には、線を引く場所が3つある
# 線を引く場所がN個あるときの線の引き方の組み合わせは
# A[1] = 2, A[2] = 3, A[N] = A[N - 2] + A[N - 1]
# のほぼフィボナッチ数列
# 2,3,5,8,13...
# これをあらかじめ最大数ぶん求めておく
# 横棒W本に対して、W - 1個の間隔があり、そのうち端の2か所が埋まった状態が最大なのでW - 3
# これを求める

import sys
readline = sys.stdin.readline

DIV = 10 ** 9 + 7
H,W,K = map(int,readline().split())

P = [0] * max(W - 2 + 1,3)
P[1],P[2] = 2,3
for i in range(3, len(P)):
  P[i] = P[i - 1] + P[i - 2]
  
# [0, 2, 3, 5, 8, 13, 21, 34, ...]

# 通らない線は上記で算出できるので、通る線を考える
# 上からi段目まで終えた時点で、縦棒jにいるときの場合の数でDPする

dp = [[0 for j in range(W)] for i in range(H + 1)]

dp[0][0] = 1 # 上から0段目を終えた時点(まだ何もしていない)ときに0にいるので1通り

def calc(L,R): # LとRの間に線を引いた場合の、残りの線の引き方
#  print("calc L",L,"R",R)
  res = 1
  if 1 < L:
    # | | |-| Lが2のときはじめてスペースが1 (L - 1)できる
    res *= P[L - 1]
#    print("P[L - 2]",P[L - 2],"res",res)
    res %= DIV
  if (W - 1) - (R + 1) >= 1:
    # |-| | | R + 2 = W - 1のときはじめてスペースが1(W - R)できる
#    print(min((W - 1) - (R + 1),len(P)))
    res *= P[(W - 1) - (R + 1)]
#    print("P[(W - 1) - (R + 1)]",min((W - 1) - (R + 1),len(P)),"res",res)
    res %= DIV
#  print(res,"通り")
  return res
  
# 右に移動する、左に移動する、何もしない、の3通りでDP
for i in range(H):
  for j in range(W):
    # 右に移動する
    if j + 1 < W:
#      print("i",i,"j",j,"からi + 1",i + 1,"j + 1",j + 1,"に移動する dp[i][j]",dp[i][j],"dp[i + 1][j + 1]",dp[i + 1][j + 1])
      dp[i + 1][j + 1] += dp[i][j] * calc(j, j + 1)
      dp[i + 1][j + 1] %= DIV
#      print("i",i,"j",j,"からi + 1",i + 1,"j + 1",j + 1,"に移動した dp[i][j]",dp[i][j],"dp[i + 1][j + 1]",dp[i + 1][j + 1])
    # 左に移動する
    if j - 1 >= 0:
#      print("i",i,"j",j,"からi + 1",i + 1,"j - 1",j - 1,"に移動する dp[i][j]",dp[i][j],"dp[i + 1][j - 1]",dp[i + 1][j - 1])
      dp[i + 1][j - 1] += dp[i][j] * calc(j - 1,j)
      dp[i + 1][j - 1] %= DIV
#      print("i",i,"j",j,"からi + 1",i + 1,"j - 1",j - 1,"に移動した dp[i][j]",dp[i][j],"dp[i + 1][j - 1]",dp[i + 1][j - 1])
    # 何もしない
#    print("i",i,"j",j,"からi",i,"j",j,"に移動する dp[i][j]",dp[i][j],"dp[i + 1][j]",dp[i + 1][j])
    dp[i + 1][j] += dp[i][j] * calc(j,j) # 左端も右端も同じ
    dp[i + 1][j] % DIV
#    print("i",i,"j",j,"からi",i,"j",j,"に移動した dp[i][j]",dp[i][j],"dp[i + 1][j]",dp[i + 1][j])
#  for d in dp:
#    print(dp)

    
# i = H段目まで終えた時点で、j = K - 1にいる場合の数
print(dp[H][K - 1] % DIV)

Measured memory_bytes: 3064
#include <iostream>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)

int main() {
    long n;
    cin >> n;
    int tmp;
    for(;;){
        tmp=n%10;
        if(tmp==7){
            cout<<"Yes";
            return 0;
        }
        n=n/10;        
        if(n==0){
            cout << "No";
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 3592
import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[] X = new int[N];
    int[] Y = new int[N];
    double Sum = 0;
    for(int i=0;i<N;i++){
      X[i] = sc.nextInt();
      Y[i] = sc.nextInt();
    }
    for(int start=0;start<N-1;start++){
      for(int end = start+1;end<=N-1;end++){
        Sum+=Math.sqrt(Math.pow(X[start]-X[end],2)+Math.pow(Y[start]-Y[end],2));
      }
    }
    double result = 2*Sum/N;
    System.out.println(result);
  }
}

Measured memory_bytes: 35820
#include<bits/stdc++.h>
#define mod 1000000007
#define pb push_back
#define all int i=0; i<n; i++
#define INF 9999999999999999
using namespace std;
typedef long long int ll; 
#define int ll   
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define x first 
#define y second

int32_t main(){
	int h,n;
	cin>>h>>n;

	pair<int, int>a[n];
	for(all){
		cin>>a[i].x>>a[i].y;
	}
	int dp[100000];
	dp[0] = 0;
	int ans = INF;
	
	for(int i=1; i<100000; i++){
		dp[i] = INF;
		for(int j=0; j<n; j++){
			if(i - a[j].x >= 0){
				dp[i] = min(dp[i - a[j].x] + a[j].y, dp[i]);
			}
		}
	}
	
	for(int i=h; i<100000; i++){
		ans = min(ans, dp[i]);
	}
	
	cout<<ans<<endl;
}



Measured memory_bytes: 1024
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)

	if n%10 == 3 {
		fmt.Println("bon")
	} else if n%10 == 0 || n%10 == 1 || n%10 == 6 || n%10 == 8 {
		fmt.Println("pon")
	} else {
		fmt.Println("hon")
	}
}


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

int N , M ;
int c[100005];
int p[100005];
class order{
	public:
		bool operator()(pair<int,int>a,pair<int,int>b){
			return a.first < b.first ;
		}

};
map < int , vector < pair<int,int> > > m ;
map < int , vector < pair<int,int> > > :: iterator it ;

int numdigits(int x){
	int cnt =  1 ;
	while(x/10 != 0 ){
		cnt++;
		x = x/10 ;
	}
	return cnt ;
}

void print(int x ){
	int k = numdigits(x);
	for( int i = 0 ; i < 6-k ; i++ ){
		printf("0");
	}
	printf("%d",x);
}

int main(){
	int i , j ;
	scanf("%d%d",&N,&M);
	int y ;
	for( i = 1 ; i <= M ; i++ ){
		scanf("%d%d",&c[i],&y);
		m[c[i]].push_back(make_pair(y,i));
	}
	for( it = m.begin() ; it != m.end() ; it++ ){
		vector < pair<int,int> > & v = it->second ;
		sort(v.begin(),v.end(),order());
		for( j = 0 ; j < v.size() ;j++ ){
			p[v[j].second] = j+1 ;
		}
	}
	for( i = 1 ; i <= M ; i++ ){
		print(c[i]);
		print(p[i]);
		puts("");
	}

	return 0 ;
}

Measured memory_bytes: 13184
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm> 
#include<cstring>
#define ios ios::sync_with_stdio(false)
#define mem(arr) memset(arr,0,sizeof(arr))
using namespace std;
typedef long long ll;
const ll maxn = 1e6 + 10;
int main()
{
	int n,ans=0;
	char ch[55];
	cin>>n;
	for(int i = 1;i <= n; i++) 
		cin>>ch[i];
	for(int i = 1;i <= n;)
	{
		if(ch[i] == 'A'&& ch[i+1] == 'B'&&ch[i+2] == 'C'){
			i+=3;
			ans++;
		}
		else
			i++;
	}
	cout<<ans<<endl;
	return 0;
} 

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

int main(){
    int a,b,k;
    int n=0,i;
    int ans;

    cin >>a>>b>>k;
    i=min(a,b);
    while (i>0){
        if(a%i==0 && b%i==0)n++;

        if(n==k){
            ans=i;
            break;
        }
        i--;
    }
    

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


Measured memory_bytes: 256