akhauriyash/Code-Regression huggingface dataset:
def solve(s):
    if len(s) == 2:
        return 1 if s[0] == s[1] else 2
    elif len(s) == 3:
        if s[0] == s[1] == s[2]:
            return 1
        elif s[0] == s[1] or s[1] == s[2]:
            return 6
        elif s[0] == s[2]:
            return 7
        else:
            return 3
    if all(a == b for a, b in zip(s, s[1:])):
        return 1
    dp = [[[0] * 3 for _ in range(3)] for _ in range(2)]
    dp[0][0][0] = 1
    dp[0][1][1] = 1
    dp[0][2][2] = 1
    MOD = 998244353
    for _ in range(len(s) - 1):
        ndp = [[[0] * 3 for _ in range(3)] for _ in range(2)]
        ndp[0][0][0] = (dp[0][1][0] + dp[0][2][0]) % MOD
        ndp[0][0][1] = (dp[0][1][1] + dp[0][2][1]) % MOD
        ndp[0][0][2] = (dp[0][1][2] + dp[0][2][2]) % MOD
        ndp[0][1][0] = (dp[0][0][2] + dp[0][2][2]) % MOD
        ndp[0][1][1] = (dp[0][0][0] + dp[0][2][0]) % MOD
        ndp[0][1][2] = (dp[0][0][1] + dp[0][2][1]) % MOD
        ndp[0][2][0] = (dp[0][0][1] + dp[0][1][1]) % MOD
        ndp[0][2][1] = (dp[0][0][2] + dp[0][1][2]) % MOD
        ndp[0][2][2] = (dp[0][0][0] + dp[0][1][0]) % MOD
        ndp[1][0][0] = (dp[0][0][0] + dp[1][0][0] + dp[1][1][0] + dp[1][2][0]) % MOD
        ndp[1][0][1] = (dp[0][0][1] + dp[1][0][1] + dp[1][1][1] + dp[1][2][1]) % MOD
        ndp[1][0][2] = (dp[0][0][2] + dp[1][0][2] + dp[1][1][2] + dp[1][2][2]) % MOD
        ndp[1][1][0] = (dp[0][1][2] + dp[1][0][2] + dp[1][1][2] + dp[1][2][2]) % MOD
        ndp[1][1][1] = (dp[0][1][0] + dp[1][0][0] + dp[1][1][0] + dp[1][2][0]) % MOD
        ndp[1][1][2] = (dp[0][1][1] + dp[1][0][1] + dp[1][1][1] + dp[1][2][1]) % MOD
        ndp[1][2][0] = (dp[0][2][1] + dp[1][0][1] + dp[1][1][1] + dp[1][2][1]) % MOD
        ndp[1][2][1] = (dp[0][2][2] + dp[1][0][2] + dp[1][1][2] + dp[1][2][2]) % MOD
        ndp[1][2][2] = (dp[0][2][0] + dp[1][0][0] + dp[1][1][0] + dp[1][2][0]) % MOD
        dp = ndp
    return (sum(dp[1][x][sum(map(ord, s)) % 3] for x in range(3)) + all(a != b for a, b in zip(s, s[1:]))) % MOD


s = input()
print(solve(s))


Measured memory_bytes: 3820
#include <bits/stdc++.h>
using namespace std;
#define rep2(i,m,n) for (int i = (m); i < (n); ++i)
#define rep(i,n) rep2(i,0,n)
#define debug(x) cout << x << endl
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> P;
template<typename T> struct V : vector<T> { using vector<T>::vector; };
V() -> V<int>;
V(size_t) -> V<int>;
template<typename T> V(size_t, T) -> V<T>;
template<typename T> vector<T> make_vec(size_t n, T a) { return vector<T>(n, a); }
template<typename... Ts> auto make_vec(size_t n, Ts... ts) { return vector<decltype(make_vec(ts...))>(n, make_vec(ts...)); }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << ' '; return os; }
struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
const int INF = 1<<30;
const ll LINF = 1LL<<61;
const ll MOD = 1000000007;
const int M = 1010101;

int main()
{
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    vector<int> sieve(M, 0);
    rep(i,n)
    {
        sieve[a[i]]++;
    }
    bool is_cop = true;
    for(ll i = 2; i < M; i++)
    {
        int cnt = 0;
        for(ll j = i; j < M; j+=i)
        {
            cnt += sieve[j];
        }
        if(cnt > 1) is_cop = false;
    }

    bool is_setcop = false;
    ll gg = a[0];
    rep(i,n-1) gg = gcd(gg, a[i+1]);
    if(gg == 1) is_setcop = true;
    
    if(is_cop)
    {
        cout << "pairwise coprime" << endl;
    }
    else if(is_setcop)
    {
        cout << "setwise coprime" << endl;
    }
    else
    {
        cout << "not coprime" << endl;
    }
    

}


Measured memory_bytes: 14940
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;

#define X first
#define Y second

//#include <boost/unordered_map.hpp>
//using namespace boost;

/*
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
rbtree T;
*/

namespace io{
	const int L = (1 << 20) + 1;
	
	char buf[L], *S , *T, c;
	 
	char getchar() {
		if(__builtin_expect(S == T, 0)) {
			T = (S = buf) + fread(buf, 1, L, stdin);
			return (S == T ? EOF : *S++);
		}
		return *S++;
	}
	
	int inp() {
		int x = 0, f = 1; char ch;
		for(ch = getchar(); !isdigit(ch); ch = getchar())
			if(ch == '-') f = -1;
		for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
		return x * f;
	}
	
	unsigned inpu()
	{
		unsigned x = 0; char ch;
		for(ch = getchar(); !isdigit(ch); ch = getchar());
		for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
		return x;
	}
	
	ll inp_ll() {
		ll x = 0; int f = 1; char ch;
		for(ch = getchar(); !isdigit(ch); ch = getchar())
			if(ch == '-') f = -1;
		for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
		return x * f;
	}
	
	char B[25], *outs=B+20, *outr=B+20;
	template<class T>
	inline void print(register T a,register char x=0){
		if(x) *--outs = x, x = 0;
		
		if(!a)*--outs = '0';
		else 
			while(a)
				*--outs = (a % 10) + 48, a /= 10;
		
		if(x)
			*--outs = x;
		
		fwrite(outs, outr - outs , 1, stdout);
		outs = outr;
	}
};

using io :: print;
using io :: inp;
using io :: inpu;
using io :: inp_ll;

using i32 = int;
using i64 = long long;
using u8 = unsigned char;
using u32 = unsigned;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;

ll power(ll a, ll b, ll p)
{
	if (!b) return 1;
	ll t = power(a, b/2, p);
	t = t*t%p;
	if (b&1) t = t*a%p;
	return t;
}

const int MAXN = 100010;
const int MAXP = 10000000;
const u64 MOD = 1000000007;
const f80 MI = f80(1)/MOD;
const int INF = 1000000010;

int n, m;
vector<pii> v[MAXN];
ll ans[MAXN];
int p[MAXN], y[MAXN];

int main()
{
	
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++ i)
	{
		scanf("%d%d", &p[i], &y[i]);
		v[p[i]].emplace_back(y[i], i);
	}
	for (int i = 1; i <= n; ++ i)
	{
		sort(v[i].begin(), v[i].end());
		for (int j = 0; j < v[i].size(); ++ j)
		{
			ans[v[i][j].Y] = i*1000000LL+j+1;
		}
	}
	for (int i = 1; i <= m; ++ i)
		printf("%012lld\n", ans[i]);
	
	return 0;
}


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

typedef long long ll;

const int MAX_N = 100;
const int MAX_W = 10000;

int dp[MAX_N+1][MAX_W+1];

int n, W;
int w[MAX_N], v[MAX_N];

int main() {
    cin >> n >> W;
    for(int i=0; i<n; i++) cin >> v[i] >> w[i];
    
    for(int i=0; i<n; i++){
        for(int j=0; j<=W; j++){
            if(j<w[i]){
                dp[i+1][j] = dp[i][j];
            }
            else {
                dp[i+1][j] = max(dp[i][j], dp[i+1][j-w[i]]+v[i]);
            }
        }
    }
    
    cout << dp[n][W] << endl;
    
}



Measured memory_bytes: 7028
#include<bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T>
void read(T &res) {
  int f = 1; res = 0;
  char c = getchar();
  while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
  while(c >= '0' && c <= '9') { res = res * 10 + c - '0'; c = getchar(); }
  res *= f;
}
int main() {
  fio
  int n;
  string s;
  cin >> n >> s;
  int res = 1;
  char mid = s[0];
  for(int i = 1; i < n; ++i) {
    if(s[i] != mid) res++;
    mid = s[i];
  }
  cout << res << endl;
	return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)
#define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)

using namespace std;

typedef long long LL;
typedef pair <int, int> PII;
typedef pair <int, PII> PIII;

template <typename T>
inline T gi()
{
	T f = 1, x = 0; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f * x;
}

const int INF = 0x3f3f3f3f, N = 100003, M = N << 2;

LL x;

int main()
{
	//File("");
	x = gi <LL> ();
	LL ans = 2 * (x / 11), y = x % 11;
	if (y > 0) ++ans;
	if (y > 6) ++ans;
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 3716
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func main() {
	scanner.Split(bufio.ScanWords)

	for {
		l := nextString()
		if l == "0" {
			break
		}

		s := 0
		for i := range l {
			n, _ := strconv.Atoi(l[i:(i + 1)])
			s += n
		}
		fmt.Println(s)
	}
}



Measured memory_bytes: 1124
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<utility>
#include<algorithm> // sort
#include<map> // pair
#include<cmath>
#include<cstring>
#include<set>
using namespace std;
using ll = long long;
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 (a>b) { a=b; return 1; } return 0; }
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define all(x) (x).begin(),(x).end()
const ll mod = 1e9+7;
const int INF = 1e9;
const ll INFLONG = 1e18;
int main(){
  ll d;
  cin >> d;
  cout << "Christmas";
  REP(i,d,25){
    cout << " Eve";
  }
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const long long INF=INT_MAX/4;
const long long MOD=1'000'000'007;
const double EPS=1e-14;
const bool DEBUG=true;

const string YES = "YES";
const string NO = "NO";
const string Yes = "Yes";
const string No = "No";

template<class T>
void debug(T head){
    if(DEBUG){
        cout<<head<<endl;
    }
}

template <class Head, class... Body>
void debug(Head head, Body... body){
    if(DEBUG){
        cout<<head<<" ";
        debug(body...);
    }
}

/////
void answer(){
    unsigned long long n;
    cin>>n;
    vector<long> v(n);
    for(auto &a : v){
        cin>>a;
    }

    map<int, int> odds, evens;
    for(int i=0; i<n; i+=2){
        auto itr_odd = odds.find(v[i]);
        auto itr_even = evens.find(v[i+1]);
        if(itr_odd != odds.end()) {
            odds[v[i]]++;
        }else{
            odds[v[i]] = 1;
        }

        if(itr_even != evens.end()) {
            evens[v[i+1]]++;
        }else{
            evens[v[i+1]] = 1;
        }
    }

    vector<pair<int, int>> odd_pairs, even_pairs;
    for(auto const& [key, value] : odds){
        odd_pairs.push_back(make_pair(-value, key));
    }
    for(auto const& [key, value] : evens){
        even_pairs.push_back(make_pair(-value, key));
    }
    sort(odd_pairs.begin(), odd_pairs.end());
    sort(even_pairs.begin(), even_pairs.end());

    int odds_max_key = odd_pairs[0].second;
    int odds_max_value = -odd_pairs[0].first;
    int evens_max_key = even_pairs[0].second;
    int evens_max_value = -even_pairs[0].first;
    if(odds_max_key == evens_max_key && odds_max_value == evens_max_value){
        if(-odd_pairs[1].first < -even_pairs[1].first){
            evens_max_value = -even_pairs[1].first;
        }else{
            odds_max_value = -odd_pairs[1].first;
        }
    }

    cout<<n-odds_max_value-evens_max_value<<endl;

    return;
}

/////

int main(int argc, char* argv[]){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout.precision(16);

    answer();

    return 0;
}


Measured memory_bytes: 9556
#53 ABC133E
n,k=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n-1)]

mod=10**9+7

path=[[] for i in range(n)]
for a,b in ab:
	path[a-1].append(b-1)
	path[b-1].append(a-1)

abc=[False for _ in range(n)]

abc[0]=True
c=0
ans=k
t=[] 

for i in range(len(path[0])):
	child=path[0][i]
	if abc[child]:
		continue
	ans=ans*(k-1-c)%mod
	c+=1
	abc[child]=True
	t.append(child)
while len(t)>0:
	a=t.pop()
	c=0
	for i in range(len(path[a])):
		child=path[a][i]
		if abc[child]:
			continue
		ans=ans*(k-2-c)%mod
		c+=1
		abc[child]=True
		t.append(child)
print(ans%mod)

Measured memory_bytes: 81112
MOD = 10**9+7
N, K = map(int, input().split())  # N個の整数列, 要素は1~Kの値を取る
# 数列の最大公約数がk(1<=k<=K)の通りを考える
ans = 0
cnt = [0]*(K+1)
for k in reversed(range(1, K+1)):
    cnt[k] = pow((K//k), N, MOD)
    tmp = k * 2  # 2倍したもの
    while tmp <= K:
        cnt[k] -= cnt[tmp]
        tmp += k
for i in range(K+1):
    ans += cnt[i]*i
    ans %= MOD
print(ans)


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

ll W, H, V, T, X, Y, P, Q;

ll solve(ll p, ll q) {
  ll r = V * T;

  ll ret = 0;
  for(ll n = -2000000; n <= 2000000; n++) {
    ll x = 2 * n * W + p - X;

    if(-r <= x && x <= r) {
      ll init = 334;
      REP(i, -1, 2) {
        ll y = 2 * i * H + q - Y;
        if(x * x + y * y <= r * r) init = i;
      }
      if(init == 334) continue;

      ll ok1 = init, ng1 = 2000000;
      while(abs(ng1 - ok1) > 1) {
        ll m = (ok1 + ng1) / 2;
        ll y = 2 * m * H + q - Y;
        (y <= sqrt(r * r - x * x) ? ok1 : ng1) = m;
      }

      ll ok2 = init, ng2 = -2000000;
      while(abs(ng2 - ok2) > 1) {
        ll m = (ok2 + ng2) / 2;
        ll y = 2 * m * H + q - Y;
        (y >= -sqrt(r * r - x * x) ? ok2 : ng2) = m;
      }

      ret += ok1 - ok2 + 1;

      // ll y1 = 2 * ok1 * H + q - Y, y2 = 2 * ok2 * H + q - Y;
      // cerr << "(" << x << ", " << y1 << "), " << "(" << x << ", " << y2 << ")" << endl;
    }
  }

  return ret;
}

int main(void) {
  cin >> W >> H >> V >> T >> X >> Y >> P >> Q;

  ll ans = 0;
  ans += solve(+P, +Q);
  ans += solve(+P, -Q);
  ans += solve(-P, +Q);
  ans += solve(-P, -Q);
  cout << ans << endl;
}



Measured memory_bytes: 3096
#include<bits/stdc++.h>
using namespace std; 
#define mod 1000000007
#define N 100005
#define ll long long
#define ull unsigned long long
#define loop1(i, j, k, step) for (int i=j; i<k; i+=step)
#define loop(i, j, k) for (int i=j; i<k; i++) 
#define rloop1(i, j, k, step) for (int i=j; i>=k; i-=step)
#define rloop(i, j, k) for(int i=j; i>=k; i--)
#define rep(i, k) for(int i = (0); i < (k); i++ )
#define rrep(i, k) for(int i = k-1; i >= 0; i-- )

#define forall(it, l) for(auto it=l.begin(); it != l.end(); it++)
#define mp make_pair
#define pb push_back
#define pop pop_back
#define F first
#define S second
#define sz(x) (int)(x).size()
#define endl "\n"
#define Max (int)INT_MAX
#define Min (int)INT_MIN
#define MEM(a, b) memset(a, (b), sizeof(a))
#define fast_io ios_base::sync_with_stdio(0), cin.tie(NULL)
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<ll> vl;
typedef pair<ll,ll> pll;


void solve()
{
  int n,i,j,k,l;
  string s;
  cin>>s;
  if(s[s.size()-1]=='s')
    s.append("es");
  else
    s.append("s");
  cout<<s<<endl;

}
int  main() 
{
  auto start=clock();
  fast_io;
    int t=1;
    //cin>>t;
    while(t--){
      solve();
    }
    auto stop =clock();
    cerr<<"time taken:"<<double(stop-start)/double(CLOCKS_PER_SEC)<<" s"<<endl;
  return 0; 
}


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

using namespace std;
using ll =long long;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int,int> PII;
#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
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; }
using P = pair<int,int>;
//Write From this Line

int main()
{
	ll n, m;	
	cin >> n >> m;	
	vector<ll> x(n), y(n), z(n);
	ll ans = -1e17;

	rep(i,n) cin >> x[i] >> y[i] >> z[i];

	for(ll tmp = 0; tmp < (1 << 3); tmp++){
		bitset<3> bit(tmp); 
		vector<pair<ll,ll>> value(0);

		rep(i,n){
			ll now = 0;
			if(bit.test(0)){ //bitが立っている時、x[i]がそのままスコアになる。
				now += x[i];
			} else {
				now += -x[i];
			}
			if(bit.test(1)){
				now += y[i];
			} else {
				now += -y[i];
			}
			if(bit.test(2)){
				now += z[i];
			} else {
				now += -z[i];
			}
			value.push_back({now,i});
		}

		// valueの大きい方からM個取る
		sort(value.rbegin(),value.rend());
		ll x_sum = 0, y_sum = 0, z_sum = 0;
		ll ret = 0;
		rep(i,m){
			ret += value[i].first;
			x_sum += x[value[i].second];
			y_sum += y[value[i].second];
			z_sum += z[value[i].second];
		}
		if(bit.test(0)){
			if(x_sum >= 0) {
				// ok 
			} else {
				continue;
			}
		}
		if(bit.test(1)){
			if(y_sum >= 0) {
				// ok 
			} else {
				continue;
			}
		}
		if(bit.test(2)){
			if(z_sum >= 0) {
				// ok 
			} else {
				continue;
			}
		}
		ans = max(ans,ret);
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
import sys

stdin = sys.stdin
def na(): return map(int, stdin.readline().split())
def ns(): return stdin.readline().strip()


n,ma,mb = na()
abcs = []
for i in range(n):
    abcs.append(list(na()))
I = 9999999999
dp = [[I]*420 for _ in range(420)]
dp[0][0] = 0
sa = 1; sb = 1
for abc in abcs:
    for i in range(sa-1,-1,-1):
        for j in range(sb-1,-1,-1):
            dp[i+abc[0]][j+abc[1]] = min(dp[i+abc[0]][j+abc[1]], dp[i][j] + abc[2])
    sa += abc[0]
    sb += abc[1]
x = ma
y = mb
ret = I
while x < 420 and y < 420:
    ret = min(ret, dp[x][y])
    x += ma
    y += mb
if ret == I:
    print(-1)
else:
    print(ret)

Measured memory_bytes: 4980
#include<iostream>

using namespace std;

int main() {
	int n, i;
	long long a[1000]{ 0 }, b[1000]{ 0 }, aa[1000]{ 0 }, bb[1000]{ 0 }, c, d;

	cin >> n;

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

	aa[0] = a[0];
	bb[0] = b[0];

	for (i = 1; i < n; i++) {
		c = aa[i - 1] / a[i];
		d = bb[i - 1] / b[i];
		if (c < d) c = d;
		aa[i] = a[i] * c;
		bb[i] = b[i] * c;
		while (aa[i] < aa[i - 1] || bb[i] < bb[i - 1]) {
				aa[i] += a[i];
				bb[i] += b[i];
		}
	}

	cout << aa[n - 1] + bb[n - 1] << endl;

	return 0;

}



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

typedef long long ll;
typedef long double ld;
typedef vector<vector<int>> Graph;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
#define pi 3.14159265359
#define inf 2147483647
#define INF 9223372036854775807
#define mod 1000000007
#define mod2 998244353

int main() {
    int N, M; cin >> N >> M;
    Graph G(N);
    for(int i = 0; i < M; i++) {
        int a, b; cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    queue<int> q; q.push(0);
    vector<int> visit(N, -1), dist(N, 0);
    visit[0] = 1;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(auto p: G[u]) {
            if(visit[p] == -1) {
                visit[p] = 1;
                q.push(p);
                dist[p] = dist[u] + 1;
            }
        }
    }
    if(dist[N - 1] == 2) cout << "POSSIBLE" << endl;
    else cout << "IMPOSSIBLE" << endl;
    return 0;
}

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

int main()
{
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    std::map<int,int> mp;
    for(int i = 0; i < n; i++){
        std::cin >> a[i];
        mp[a[i]]++;
    }
    int res = 0;
    for(auto i : mp){
        if(i.first <= i.second){
            res += i.second - i.first;
        }else{
            res += i.second;
        }
    }
    std::cout << res << std::endl;
}

Measured memory_bytes: 5120
#include <stdio.h>
char txt[4002];
int cnt[4001][3];
const char* rgb = "RGB";
int main(){
	int N;scanf("%d",&N);
	scanf("%s",txt+1);
	for(int i=1;i<=N;i++){
		for(int j=0;j<3;j++){
			cnt[i][j]=cnt[i-1][j]+(txt[i]==rgb[j]);
		}
	}
	long long sum = 0;
	for(int i=1;i<=N;i++){
		for(int j=0;j<3;j++){
			if(txt[i]==rgb[j]){
				sum +=1LL*cnt[i-1][(j+1)%3]*(cnt[N][(j+2)%3]-cnt[i][(j+2)%3]);
				sum +=1LL*cnt[i-1][(j+2)%3]*(cnt[N][(j+1)%3]-cnt[i][(j+1)%3]);
			}
		}
	}
	for(int i=1;i<=N;i++){
		for(int l=1;l+2*i<=N;l++){
			int m = l+i;
			int r = m+i;
			sum -= txt[l]!=txt[m]&&txt[m]!=txt[r]&&txt[r]!=txt[l];
		}
	}
	printf("%lld",sum);
}

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

int main(void){
  int N, K;
  cin >> N >> K;
  int h[N];
  for(int i=0; i<N; i++) cin >> h[i];
  sort(h, h+N);
  int ans=1e9;
  for(int i=0; i<=N-K; i++){
    ans = min(h[i+K-1]-h[i], ans);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;
typedef map <str,int> mapsi;
typedef map <str,int> :: iterator mapsitr;
typedef set <int> si;
typedef set <int> :: iterator sitr;
typedef set <ll> :: iterator sltr;
#define mset multiset
typedef mset <int> msi;
typedef mset <ll> msll;
typedef mset <int> :: iterator msitr;
typedef mset <ll> :: iterator msltr;
#define mp make_pair
#define pb push_back
#define pob pop_back
#define fi first
#define se second
#define fs first.second
#define ss second.second
#define ff first.first
#define sf second.first
int dua[30],n,sum[30],current,far;
vector < pair < pii , int> > ans;
vi v;
int node = 1;
int main(){
    dua[0]=1;sum[1]=0;
    for(int i=1;i<=26;i++)dua[i]=2*dua[i-1];
    for(int i=2;i<=26;i++)sum[i]=sum[i-1]+dua[i-2];

    cin>>n;
    n--;

    for(int i=0;i<=22;i++){
        if(current+dua[i]>n){break;}
        else{
            current+=dua[i];
            v.pb(dua[i]);
        }
    }

    for(int i=0;i<v.size();i++){
        ans.pb( mp ( mp(node,node+1) , 0 ) );
        ans.pb( mp ( mp(node,node+1) , v[i] ) );
        node++;
    }

    while(current < n){
        int pl = current+1;
        int idx;
        for(int i=1;i<=26;i++){
            if(pl+sum[i]>n){break;}
            else{
                idx=i;
            }
        }
        ans.pb( mp ( mp(idx,node) , pl ) );
        current = pl + sum[idx];
    }

    cout<<node<<" "<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++){
        printf("%d %d %d\n",ans[i].ff,ans[i].fs,ans[i].se);
    }

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long ;
const ll MOD = 1e9 + 7;
class Graph
{
    public:
    int n;
    vector<vector<int> > adj;
    vector<vector<ll> > dp;

    Graph(int n )
    {
        this->n  = n;
        adj.resize(n+1);
        dp.resize(n+1, vector<ll> (2,1));
    }
    void add_edge(int u, int v)
    {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    void dfs(int u, vector<bool>& visited)
    {
        visited[u] = true;
        for(auto v: adj[u])
        {
            if(!visited[v])
            {
                dfs(v,visited);
                dp[u][0] = (dp[u][0]*dp[v][1])%MOD;
                dp[u][1] = (dp[u][1]*((dp[v][0]+dp[v][1])%MOD))%MOD;
            }
        }
        
    }
    void solve()
    {
        vector<bool> visited(n+1 , false);
        int root = 1;
        dfs(root, visited);
        cout<<(dp[root][0] + dp[root][1])%MOD;
    }
};
int main()
{
    int n;
    cin>>n;
    Graph g(n);
    for(int i =0; i<n- 1; i++)
    {
        int x, y;
        cin>>x>>y;
        g.add_edge(x,y);
    }
    g.solve();

}

Measured memory_bytes: 14464
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//String s= sc.next();
		String buff= "";
		//double n = sc.nextInt()/1000.0;
		int m = sc.nextInt();
		int k = sc.nextInt();
		//String s=sc.next();
		double count=1,flag=0;
		double count1=0,count2=0;
		int count3=9999999;
		int[][] array1 = new int[m][k];
		/*array[0]=n-m;
		array[1]=n*m;
		array[2]=n+m;*/
		//Arrays.sort(array);

		for(int i=0;i<m;i++) {
			for(int j=0;j<k;j++) {
				array1[i][j] = sc.nextInt();
			}
		}
		for(int i=0;i<m-1;i++) {
			for(int j=i+1;j<m;j++) {
				for(int g=0;g<k;g++) {
					count2+=Math.pow((array1[i][g]-array1[j][g]), 2);
				}
				count=Math.sqrt(count2);
				count3=(int)count;
				//System.out.println(count2);
				if(count-count3==0) {
					count1++;
				}
				count2=0;
			}
		}

		/*if(count==0) {
			System.out.println("No");
		}else {
			System.out.println("Yes");
		}*/

		System.out.println((int)count1);
	}
}




Measured memory_bytes: 23252
using System;
using System.Collections.Generic;
using System.Linq;

namespace ProgramingStudying2
{
    class Program
    {

        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var payment = 1000;
            while(payment < n)
            {
                payment += 1000;
            }
            Console.WriteLine(payment - n);
        }
    }
}


Measured memory_bytes: 27540
// AOJ 1241

#include <iostream>
#include <vector>

using namespace std;

vector <long long> data;

int main(void)
{
	for (int i = 0; i < 200; i++){
		data.push_back(i*i);
	}
	int n;
	while (cin >> n, n){
		int ret = 0;
		for (int i = 0; i < data.size(); i++){
			for (int j = i; j < data.size(); j++){
				for (int k = j; k < data.size(); k++){
					for (int l = k; l < data.size(); l++){
						if (data[i] + data[j] + data[k] + data[l] == n){
							ret++;
						}
						if (n < data[i] + data[j] + data[k] + data[l]){
							break;
						}
					}
				}
			}
		}
		cout << ret << endl;
	}

	return 0;
}

Measured memory_bytes: 1216
#include<bits/stdc++.h>
using namespace std;
int n,h,d;
char a;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    	cin>>a;
    	if(a=='I')h++;
    	if(a=='D')h--;
    	d=max(h,d);
    }
    cout<<d<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cassert>
using namespace std;
 
#define fr(i,a,b) for(int i=a;i<b;++i)
typedef long long ll;
/////////////////////////
 
int const N = 141;
 
ll a[N], ans[N];
int n;
ll k;
 
ll calc(){
	ll ans = 0;
	bool f = true;
	while(f){
		f = false;
		int maxii = 0;
		fr(i, 0, n) if(a[i] > a[maxii]){
			maxii = i;
		}
		ll add = a[maxii] / n;
		ans += add;
		a[maxii] %= n;
		fr(i, 0, n){
			if(i != maxii) a[i] += add;
		}
		if(add > 0) f = true;
	}
	return ans;
}
 
void solve(){
	cin >> k;
	n = 50;
	ll r = k % n;
	ll d = k / n + n - 1;
	fr(i, 0, n) a[i] = d;
	while(r--){
		int minii = 0;
		fr(i, 0, n) if(a[i] < a[minii]) minii = i;
		a[minii] += n;
		fr(i, 0, n) if(i != minii) --a[i];
	}

	fr(i, 0, n) ans[i] = a[i];
	assert(k == calc());
	cout << n << endl;
	fr(i, 0, n){
		if(i) cout << " ";
		cout << ans[i];
	}
}
 
int main(){
#ifdef _DEBUG
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
#endif
 
	solve();
 
 
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <numeric>
#include <iomanip>
#include <tuple>

using namespace std;

int main(){
   string s;
   cin>>s;
   int cnt=0;
   int p=0;
   string t="KIHBR";

   for(int i=0;i<s.size();i++){
       if(s[i]==t[p]){
           p++;
           cnt=0;
       }
       else if(cnt==0 && s[i]=='A' && s[i+1]!='I' && s[i-1]!='I')cnt++;
       else {
           cout<<"NO"<<endl;
           return 0;
       }
   }
   if(p!=5){
       cout<<"NO"<<endl;
       return 0;
   }
   cout<<"YES"<<endl;
}

   


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(int)(n); i++)

using namespace std;
typedef long long LL;
const LL mod=1e9+7;

LL dp[100010][2];
int N;
vector<int> G[100010];

void dfs(int per, int v){
  if(v!=0&&G[v].size()==1){
    dp[v][0]=1;
    dp[v][1]=1;
    return;
  }
  LL w=1, b=1;
  rep(i,G[v].size()){
    int next=G[v][i];
    if(next==per) continue;
    dfs(v, next);
    w*=dp[next][0]+dp[next][1];
    b*=dp[next][0];
    w%=mod; b%=mod;
  }
  dp[v][0]=w; dp[v][1]=b;
}

int main(){
  cin >> N;
  rep(i,N-1){
    int x, y;
    cin >> x >> y;
    x--; y--;
    G[x].emplace_back(y);
    G[y].emplace_back(x);
  }
  rep(i,N) dp[i][0]=0, dp[i][1]=0;
  dfs(-1,0);
  cout << (dp[0][0]+dp[0][1])%mod << endl;
  
  return 0;
}

Measured memory_bytes: 14208
using System;
using System.Linq;

namespace ITP1_10_B
{
    class Program
    {
        static void Main(string[] args)
        {
            double[] x = Console.ReadLine().Split().Select(double.Parse).ToArray();
            double s = x[0] * x[1] * Math.Sin(x[2] * (Math.PI / 180)) / 2;
            Console.WriteLine(s);
            double c = x[0] + x[1] + Math.Sqrt(Math.Pow(x[0], 2) + Math.Pow(x[1], 2) - (2 * x[0] * x[1] * Math.Cos(x[2] * (Math.PI / 180))));
            Console.WriteLine(c);
            double h = x[1] * Math.Sin(x[2] * (Math.PI / 180));
            Console.WriteLine(h);
        }
    }
}


Measured memory_bytes: 8312
#ifdef _WIN32
#include "stdc++.h"
#else
#include<bits/stdc++.h>
#endif

#define REP(i,j,k) for(int (i)=(j); (i) < (k); (i)++)
using namespace std;

void solve(int x, int y, int s) {
	int ans = 0;
	REP(i, 1, s) {
		int a = i, b = s - i;
		int k = 0, t = 0;
		REP(j, 1, s) {
			int tmp = j*(100+x)/100;
			if (tmp == a) k = j;
			if (tmp == b) t = j;
		}
		ans = max(ans, k*(100 + y) / 100 + t * (100 + y) / 100);
	}
	cout << ans << endl;
}

signed main() {
	int x, y, s;
	while (cin >> x >> y >> s, x) {
		solve(x, y, s);
	}
}


Measured memory_bytes: 2996
#include <iostream>
#include <string>

using namespace std;

bool ok(const string &small, const string& large){
    for(size_t b=0; b<large.size(); b++){
        for(size_t d=0; b+d*(small.size()-1)<large.size(); d++){
            for(size_t is=0, il=b; is<small.size() && il<large.size(); is++, il+=d){
                if(small[is]!=large[il]) break;
                if(small[is]==large[il] && is==small.size()-1){
                    return true;
                }
            }
        }
    }
    return false;
}

int n;
string small, large;
int main(){
    int n;
    while(cin>>n){
        cin>>small;
        int ans=0;
        while(n--){
            cin>>large;
            ans+=ok(small,large);
        }
        cout<<ans<<endl;
    }
}

Measured memory_bytes: 1208
#include<bits/stdc++.h>
using namespace std;
 
#define ll          long long int
#define ld          long double
#define pb          push_back
#define mp          make_pair
#define ff          first
#define se          second
#define endl        '\n'
#define fd(n)       fixed<<setprecision(n)
#define MAX         100000000000000000
#define MAXN        1000005
#define mod         1000000007  
#define pi          3.1415926535897932384626433
 
ll fun(ll x,ll y){
    ll ans=1;
    while(y>0){
        if(y%2==1){
            ans=ans*1ll*x;
            ans=ans%mod;
        }
        y=y/2;
        x=(x*1ll*x)%mod;
    }
    return ans;
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,i,y,z;
    cin>>n;
    ll a[n];
    for(i=0;i<n;i++){
        cin>>a[i];
    }
    ll ans=0,x=0;
    for(i=0;i<n;i++){
        x=x+a[i];
        x=x%mod;
    }
    // cout<<x<<endl;
    for(i=0;i<n;i++){
        y=x*1ll*a[i];
        y=y%mod;
        // cout<<y<<endl;
        ans+=y;
        ans%=mod;
    }
    ll sum1=0;
    for(i=0;i<n;i++){
        sum1+=a[i]*1ll*a[i];
        sum1%=mod;
    }
    ans-=sum1;
    ans+=mod;
    ans%=mod;
    ll p=2;
    ans=ans*1ll*fun(p,mod-2);
    ans=ans%mod;
    cout<<ans<<endl;
}

Measured memory_bytes: 5172
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include<queue>
#include<set>
using namespace std;

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

  if ((a * b) % 2 == 0)
  {
    cout << "Even" << endl;
  }
  else
  {
    cout << "Odd" << endl;
  }

}

Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <deque>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <ratio>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

using ll = long long;
using ull = unsigned long long;
template<class T> using v = vector<T>;
template<class T, class U> using p = pair<T, U>;

#define REP(i, n) for(int i = 0; i < n; ++i)
#define REP1(i, n) for(int i = 1; i <= n; ++i)

template<class T> T read() { T x{}; cin >> x; return x; }
template<class T> v<T> read(int N){ v<T> x(N); REP(i, N) cin >> x[i]; return x; }

template<class T>
void write(const T &x){ cout << x << endl; }
void write(double x){ printf("%.15f\n", x); }

const ull MOD = 1000'000'007;

ll solve(ll H){
    if(H == 1){ return 1; }
    else { return 1 + 2 * solve(H / 2) ;} ;
}

int main(){
    ll H;
    cin >> H;
    
    cout << solve(H) << endl;
    
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
using ll = long long;
#define vl vector<long long>
#define vvl vector<vector<long long>>
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
using pll = pair<long long,long long>;
#define cY cout<<"Yes"<<endl
#define cN cout<<"No"<<endl
const long long INF = 1LL << 60;
const long long MOD = 1000000007;
const long double pi = (acos(-1));
#define pb push_back

//最大最小の入れ替え
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;
}

//約数列挙
vector<long long> divisor(long long n) {
    vector<long long> ret;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    sort(ret.begin(), ret.end()); // 昇順に並べる
    return ret;
}
//コンビネーション
ll nCr(ll n, ll r) {
    ll ans = 1;
    for (ll i = n; i > n - r; --i) {
        ans = ans*i;
    }
    for (ll i = 1 ; i < r + 1; ++i) {
        ans = ans / i;
    }
    return ans;
}
//素因数分解
map< ll, ll > prime_factor(ll n) {
  map< ll, ll > ret;
  for(ll i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}

//切り上げの割り算は(a + b - 1) / bでできる

//ここから
int main(){
    ll N,M;
    cin>>N>>M;
    vector<vector<bool>> vec(N,vector<bool>(N,false));
    rep(i,M){
        ll a,b;
        cin>>a>>b;
        a--;
        b--;
        vec[a][b]=true;
        vec[b][a]=true;
    }
    vl num(N);
    rep(i,N) num[i]=i;
    ll count=0;
    do{
        if(num[0]!=0) break;
        bool check=true;
        rep(i,N-1){
            if(!vec[num[i]][num[i+1]]){
                check=false;
                break;
            }
        }
        if(check){
            count++;
        }
    }while(next_permutation(all(num)));
    cout<<count<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
    char S[5];
    int alpha['Z' - 'A' + 1] = {0};

    gets(S);

    alpha[S[0] - 'A']++;
    alpha[S[1] - 'A']++;
    alpha[S[2] - 'A']++;
    alpha[S[3] - 'A']++;

    int count = 0;
    for (size_t i = 0; i < sizeof(alpha) / sizeof(int); i++) {
        if (alpha[i]) count++;
    }

    if (count != 2) {
        puts("No");
        return 0;
    }

    for (size_t i = 0; i < sizeof(alpha) / sizeof(int); i++) {
        if (alpha[i] == 0) continue;
        if (alpha[i] != 2) {
            puts("No");
            return 0;
        }
    }

    puts("Yes");

    return 0;
}


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

using namespace std;

typedef long long LL;

LL n,ans;
bool check(LL k,LL n)
{
	if (n%k!=0) return false;
	while (n%k==0) n/=k;
	if ((n-1)%k!=0) return false;
	return true;
}
int main()
{
	cin>>n;
	for (LL i=2;i*i<=n-1;++i)
	{
		if ((n-1)%i==0) 
		{
			ans++;
			if ((n-1)/i!=i) ans++;
		}
	}
	if (n-1!=1) ans++;
	for (LL i=2;i*i<=n;++i)
	{
		if (check(i,n)) ans++;
	}
	ans++;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long LL;
#define SORT(c) sort((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

using namespace std;
// edge e, G[e.to][e.rev].to=e
vector<int> blue,red;
vector<vector<int> > adj;
vector<vector<int> > F;
void addflow(int from,int to,int cap)
{
  adj[from].push_back(to);
  adj[to].push_back(from);
  F[from][to]+=cap;
}
void flow(int from,int to,int cap)
{
  F[from][to]-=cap;
  F[to][from]+=cap;
}
set<int> already;
int FF(int so,int si,int mcap)
{
  //cout << "FF " << so << ' ' << si << ' ' << mcap << endl;
  if(so==si) return mcap;
  if(!already.insert(so).second) return 0;
  REP(i,adj[so].size()){
    //cout << "FF2" << endl;
    int answer;
    if(F[so][adj[so][i]])
      if(answer=FF(adj[so][i],si,min(mcap,F[so][adj[so][i]]))){
	flow(so,adj[so][i],answer);
	return answer;
      }
  }
  return 0;
}
int maxflow(int so,int si)
{
  int answer=0;
  already.clear();
  while(int tmp=FF(so,si,1048576)){
    answer+=tmp;
    already.clear();
    //cout << tmp << endl;
  }
  return answer;
}
int gcd(int a,int b){ return b?gcd(b,a%b):a; }
int main(void)
{
  for(;;){
    int m,n;
    cin >> m >> n;
    if(!m&&!n) return 0;
    blue.resize(m);
    REP(i,m) cin >> blue[i];
    red.resize(n);
    REP(i,n) cin >> red[i];
    adj.assign(m+n+2,vector<int>());
    F.resize(m+n+2);
    REP(i,m+n+2) F[i].assign(m+n+2,0);
    REP(j,n) addflow(m+j,m+n+1,1);
    REP(i,m) REP(j,n) if(gcd(blue[i],red[j])!=1) addflow(i,m+j,1);
    REP(i,m) addflow(m+n,i,1);
    cout << maxflow(m+n,m+n+1) << endl;
  }
}

Measured memory_bytes: 7296
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
    int D, G, p[11], c[11];
    int ans = 1000;
    cin >> D >> G;
    for (int i = 0; i < D; ++i) {
        cin >> p[i] >> c[i];
    }
    for (int m = 0; m < (1 << D); ++m) {
        int score = 0, count = 0;
        for (int i = 0; i < D; ++i) {
            if ((1 << i) & m) {
                score += 100 * (i + 1) * p[i] + c[i];
                count += p[i];
            }
        }
        for (int i = D - 1; i >= 0 && score < G; --i) {
            if ((1 << i) & m) {
                continue;
            }
            for (int j = 0; j < p[i] - 1; ++j) {
                score += 100 * (i + 1);
                ++count;
                if (score >= G) {
                    break;
                }
            }
        }
        if (score >= G) {
            ans = min(ans, count);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
n,m=map(int,input().split())
s=input()
t=input()
from fractions import gcd
def lcm(x,y):
  return (x*y)//gcd(x,y)
g=gcd(n,m)
a=n//g;b=m//g
x=lcm(n,m)
for i in range(g):
  if s[a*i]!=t[b*i]:
    x=-1
    break
print(x)

Measured memory_bytes: 5432
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define EPS 0.0000000001
#define INF 1000000000
#define MOD 1000000007
typedef long long ll;

int main()
{
    int n;
    cin>>n;
    vector<int> x(n);
    for(int i=0;i<n;i++){
        cin>>x[i];
    }
    sort(all(x));
    cout<<x[n-1]-x[0];
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
    public static void main(String[] args) {
        // 自分の得意な言語で
        // Let's チャレンジ！！
	int[]a={105,135,165,189,195};
        Scanner sc = new Scanner(System.in);
        int line = sc.nextInt();
      int an=0;
      for(int i=0;i<5&&a[i]<=line;i++){
      	an++;
      }
        System.out.println(an);
    }
}

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

// definition {{{ 1

// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)

#define Scll(x) scanf("%llu", &x)
#define Scll2(x,y) scanf("%llu%llu", &x, &y)
#define Scll3(x,y,z) scanf("%llu%llu%llu", &x, &y, &z)

#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2

// constants {{{ 2
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
// }}} 2

// systems {{{ 2
#define Rep(x,y) for(int x = 0; x < y; x++)
#define Repe(x,y,z) for(int x = z; x < y; x++)
// }}} 2

// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n");
// }}} 2

// }}} 1

int main() {

    int a,b;

    Scd2(a,b);

    if( a < 9 && b < 9){
        printf ("Yay!\n");
    }else{
        printf (":(\n");
    }

    return 0;
}




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

using namespace std;

typedef long long int ll;

int main() {
	ll n, m, k;

	cin >> n >> m >> k;

	vector <ll> a(n), b(m);

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

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

	vector <ll> p(n+1), q(m+1);

	for (int i = 1; i <= n; i++) {
		p[i] += p[i-1] + a[i-1];
	}

	for (int i = 1; i <= m; i++) {
		q[i] += q[i-1] + b[i-1];
	}

	int ans = 0;
	for (int i = 0; i <= n; i++) {
		if (p[i] > k) {
			break;
		}

		int j = upper_bound(q.begin(), q.end(), k-p[i]) - q.begin();
		ans = max(ans, i+j-1);
		// cout << i << " " << j << " " << p[i] << " " << q[j-1] << "\n";
	}

	for (int i = 0; i <= m; i++) {
		if (q[i] > k) {
			break;
		}

		int j = upper_bound(p.begin(), p.end(), k-q[i]) - p.begin();
		ans = max(ans, i+j-1);
		// cout << i << " " << j << " " << p[i] << " " << q[j-1] << "\n";
	}

	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 9596
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N = int(input())
    S = input()
    cnt0 = S.count("1")

    if cnt0 == 0:
        print(*[1]*N, sep="\n")
        return

    X = int(S, 2)

    def f2():
        cache = [-1] * max(9, cnt0+1)
        cache[0] = 0
        for i in range(4): cache[1<<i] = 1
        def f2(x):
            if cache[x] != -1:
                return cache[x]

            y = bin(x).count("1")
            z = 1 + f2(x % y)
            cache[x] = z

            return z
        f2.cache = cache
        return f2
    f2 = f2()

    dc = {}
    for k, v in (("0", 1), ("1", -1)):
        x = cnt0 + v
        y = X % x if x else 0
        dc[k] = (x, v, y, [1, N-1])

    ans = [0] * N
    for i in reversed(range(N)):
        si = S[i]
        cnt, v, n, m1 = dc[si]

        if cnt == 0:
            ans[i] = 0
            continue

        m2 = (m1[0]<<(m1[1]-i)) % cnt
        n = (n + v*m2) % cnt
        m1[0], m1[1] =  m2, i

        ans[i] = 1 + f2(n)

    print(*ans, sep="\n")


if __name__ == "__main__":
    resolve()


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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int i = 0;i < (n);i++)
#define FOR(i, a, b) for(int i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-6;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

const int64 mod = 1e9+7;

/*
int main(void){
	int32 N;
	cin >> N;
	vector<int64> v(N);
	REP(i, N) cin >> v[i];

	int64 maxi = 0;
	int64 res = 0;
	REP(i, N){
		int64 cnt = (v[i]-1)/(maxi+1);
		if(cnt){ res += cnt; chmax(maxi, 1); }
		else maxi = v[i];
	}
	cout << res << endl;
}
*/

int main(void){
	int32 M, N, K;
	cin >> N >> M >> K;
	vector<int64> A(N);
	deque<PLL> deq[301];
	REP(i, N) cin >> A[i];

	REP(i, N){
		for(int32 j = K-1;j >= 1;j--){
			while(deq[j-1].size() && i-deq[j-1].front().sc > M) deq[j-1].pop_front();
			if(deq[j-1].empty()) continue;
			int64 val = deq[j-1].front().fs+A[i]*(j+1);
			while(deq[j].size() && val > deq[j].back().fs) deq[j].pop_back();

			deq[j].push_back(PLL(val, i));
		}
		while(deq[0].size() && A[i] > deq[0].back().fs) deq[0].pop_back();
		deq[0].push_back(PLL(A[i], i));
	}

	cout << deq[K-1].front().fs << endl;
}

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

int f(int a, int k) {
    if (a < k) {
        return 0;
    } else {
        int x = a / k;
        int y = (a - x * k) / (x + 1);
        a -= y * (x + 1);
        if (a % k == 0) {
            return a / k;
        } else {
            a -= (x + 1);
            return f(a, k);
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);
    int sg = 0;
    for (int i = 0; i < n; i++) {
        int a, k;
        scanf("%d%d", &a, &k);
        sg ^= f(a, k);
    }
    if (sg) {
        puts("Takahashi");
    } else {
        puts("Aoki");
    }
    return 0;
}

Measured memory_bytes: 384
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Random;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author shangu
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        BVotingJudges solver = new BVotingJudges();
        solver.solve(1, in, out);
        out.close();
    }

    static class BVotingJudges {
        public void solve(int testNumber, FastReader in, PrintWriter out) {
            int n = in.nextInt();
            long njudge = in.nextLong(), v = in.nextLong();
            int P = in.nextInt();
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = in.nextLong();
            }
            mySort(a);
            for (int i = 0; i < a.length / 2; i++) {
                long tmp = a[n - 1 - i];
                a[n - 1 - i] = a[i];
                a[i] = tmp;
            }
            int L = 0, R = n;
            while (R - L > 1) {
                int M = (L + R) >> 1;
                long x = a[M];
                if (x + njudge < a[(int) (P - 1)]) R = M;
                else if (M < P) L = M;
                else {
                    long used = (P - 1) * njudge;
                    for (int i = (P - 1); i < n; i++) {
                        used += Math.min(x + njudge - a[i], njudge);
                    }
                    if (used >= njudge * v) L = M;
                    else R = M;
                }
            }
            out.println(L + 1);
        }

        private void mySort(long[] a) {
            Random random = new Random(System.currentTimeMillis());
            for (int i = 0; i < a.length; i++) {
                int j = random.nextInt(i + 1);
                long tmp = a[j];
                a[j] = a[i];
                a[i] = tmp;
            }
            Arrays.sort(a);
        }

    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader(InputStream stream) {
            br = new BufferedReader(new InputStreamReader(stream), 32768);
            st = null;
        }

        public String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
}



Measured memory_bytes: 39024
/*                    */
#include <bits/stdc++.h>
using namespace std;
using lint = int64_t;
char itoc(int i) { return i + '0'; };
int ctoi(char c) { return c - '0'; };
/*                    */

int main() {
  string s;
  cin >> s;
  for (int i = 0; i < 3; i++) {
    if (s.at(i) == '7') {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3632