akhauriyash/Code-Regression huggingface dataset:
#標準入力を高速に
import sys
input = sys.stdin.readline

def factorial_mod(x, y, mod):
    factorial = 1
    for i in range(x,y+1):
        factorial *= i
        factorial %= mod
    return factorial



def n_C_k(n, k, mod, fact):
    return (fact[n] * pow(fact[n-k], mod-2, mod) * pow(fact[k], mod-2, mod)) % mod

"""
#main関数(若干早くなる)
def main():
    mod = 10**9+7
    n, k = map(int, input().split())         
    ans = 1+n*(n-1)

    a = n
    b = n-1

    for i in range(1, min(n, k)):
        temp1 = (n-i)*pow(i+1, mod-2, mod)%mod
        a *= temp1
        a %= mod
        temp2 = (n-1-i)*pow(i+1, mod-2, mod)%mod
        b *= temp2
        b %= mod
        temp3 = a*b%mod
        ans += temp3
        ans %= mod

    print(ans)
"""


#main関数(若干早くなる)
def main():
    mod = 10**9+7
    n, k = map(int, input().split())
    ans = (1+n*(n-1))%mod

    #階乗を使いまわすver.
    fact = [1]*(n+1)
    for i in range(1, n+1):
        fact[i] = fact[i-1]*i
        fact[i] %= mod

    for i in range(2, min(n-1, k)+1):
        ans += n_C_k(n, i, mod, fact)*n_C_k(n-1, i, mod, fact)
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 43756
#include <iostream>
#include <iomanip>

int main()
{
    using namespace std;
    // 自然数
    // a + b + c = l
    // abcの最大値
    // a^3
    double l, a, s;

    cin >> l;
    a = l / 3.0;

    s = a * a * a;

    cout << fixed << setprecision(12) << s;

    return 0;
}


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

int main() {

  int a,b;
  cin >> a >> b;

  if(a+b==15)
    cout << '+' << endl;
  else if(a*b==15)
    cout << '*' << endl;
  else
    cout << 'x' << endl;

  return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
void solve(){
	int n;
	cin>>n;
	long long ans=0;
	for(int i=1;i<n;i++){
		long long Mx=n/i;
		if(n%i==0) Mx--;
		ans+=Mx;
	}
	cout<<ans;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	solve();

}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define REP(i, n) for(int i=0; i<(int)(n); ++i)
#define FOR(i, s, n) for(int i=(int)(s); i<(int)(n); ++i)
#define ALL(n) (n).begin(), (n).end()
#define pb push_back

using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> mat;
// mat dtable(M, vl(N, 0)); M行N列 のサイズで,0で初期化


const ll MAX = 200000;
const ll INF = 1e9;
const ll MOD = 1e9+7;

ll fact[MAX+1], fact_inv[MAX+1];

ll pow_mod(ll n, ll r, ll p){
    // n^r mod p   O(logn)
    if (r == 0) return 1;
    if (r % 2 == 0) return pow_mod(n*n%p , r/2, p) % p;
    else return n * pow_mod(n, r-1, p) % p;
}

void factorial(ll n, ll p){
    fact[0] = 1;
    fact[1] = 1;
    FOR(i, 2, n+1) fact[i] = i * fact[i-1] % p;
    fact_inv[n] = pow_mod(fact[n], p-2, p);
    for(int i=n-1; i>=0; --i) fact_inv[i] = fact_inv[i+1] * (i+1) % p;
}

ll comb(ll n, ll r, ll p){
    // nCr mod p
    if (n < 0 || r < 0 || r > n) return 0;
    return (fact[n] * fact_inv[r] % p) * fact_inv[n-r] % p;
}

int main(){
    ll n, k; cin >> n >> k;
    factorial(n, MOD);
    ll ans = 0;
    REP(i, min(n-1, k)+1) {
        if (i == 0) {
            ans += 1;
        } else {
            ll t = (comb(n, i, MOD) * comb((n-1), i, MOD)) % MOD;
            ans = (ans + t) % MOD;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3328
N=int(input())
S=str(input())
flg = True
if len(S)%2 != 0:
    print("No")
else:
    for i in range(len(S)//2):
        if S[i] != S[i+len(S)//2]:
            print("No")
            flg = False
    if flg == True:
        print("Yes")


Measured memory_bytes: 61908
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 1e5 + 5;
const ll LINF = 1e18 + 5;
int to[N], n;
bool vis[N];
struct node
{
	int val, pos;
	bool operator < (const node& x) const { return val < x.val; }
}a[N], b[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) 
	{
		scanf("%d",&a[i].val);
		a[i].pos = i;
	}
	for(int i=1;i<=n;i++) 
	{
		scanf("%d",&b[i].val);
		b[i].pos = i;
	}
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++) if(a[i].val>b[i].val) return puts("No"), 0;
	for(int i=2;i<=n;i++) if(a[i].val<=b[i-1].val) return puts("Yes"), 0;
	for(int i=1;i<=n;i++) to[a[i].pos] = b[i].pos;
	int cnt = 0;
	for(int i=1;i<=n;i++)
	{
		int now = i;
		if(vis[now]) continue;
		int loop = 1;
		vis[now] = 1;
		while(1)
		{
			now = to[now];
			if(now==i) break;
			loop++;
			vis[now] = 1;
		}
		cnt += loop - 1;
	}
	if(cnt<n-1) puts("Yes");
	else puts("No");
	return 0;
}


Measured memory_bytes: 2304
#include <bits/stdc++.h>
 
using namespace std;
 
const int MOD=1e9+7;

//const int MOD=998244353;
const double PI=3.14159265359;




int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n,h,w;
    cin>>n>>h>>w;
    
    int ans=0;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            ans+=(i+h-1<n && j+w-1<n);
        }
    }
    
    cout<<ans;
    
    
    return 0;
}

Measured memory_bytes: 256
N,A,B,C = map(int,input().split())
L = []
for i in range(N):
    L.append(int(input()))

def dfs(cnt,a,b,c):
    if cnt==N:
        if a>0 and b>0 and c>0:
            return abs(a-A)+abs(b-B)+abs(c-C)-30
        else:
            return float('inf')
    ret0 = dfs(cnt+1,a,b,c)
    ret1 = dfs(cnt+1,a+L[cnt],b,c)+10
    ret2 = dfs(cnt+1,a,b+L[cnt],c)+10
    ret3 = dfs(cnt+1,a,b,c+L[cnt])+10
    return min(ret0,ret1,ret2,ret3)
print(dfs(0,0,0,0))


Measured memory_bytes: 3064
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <stack>
#include <queue>
#include <functional>
#include <limits.h>
#include <set>
#include <map>
#include <tuple>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rep(i,N) for (ll i=0;i<N;i++)
#define loop(i,N,M) for(ll i=N;i<M;i++)
#define MAX(v) *max_element(v.begin(),v.end())
#define MIN(v) *min_element(v.begin(),v.end())
#define SORTL2S(type,v) sort(v.begin(),v.end(),greater<type>())
#define SORTS2L(type,v) sort(v.begin(),v.end())
#define SORTMF(v,func) sort(v.begin(),v.end(),func)
#define MP(a,b) make_pair(a,b)

#if __has_include("debug.hpp")
#include "debug.hpp"
#else
template<typename T>
void debug(T& obj) {}
#endif

//----------------------------------------------------------------------
void solve() {

	ll A,B,K;
	cin >> A >> B >> K;
	
	ll tmp = min(A,K);
	A -= tmp;
	K -= tmp;
	tmp = min(B,K);
	B -= tmp;
	cout << A << " " << B;

}
//----------------------------------------------------------------------

int main(int argc, char* argv[]) {
	solve();
	return 0;
}


Measured memory_bytes: 3620
#include <stdio.h>

int main(){
    int n, m, col, matrix[30][30], sum[31], ans = 0;
    for(int i = 0;i < n; i++){
        for(int j = 0; j < m; j++){
            matrix[i][j] = 0;
        }
    }

    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++){
        scanf("%d", &col);
        for(int j = 0; j < col; j++){
            scanf("%d", &matrix[i][j]);
        }
        for(int j = col; j < m; j++){
            matrix[i][j] = 0;
        }        
    }

    for(int i = 0; i < 31; i++)sum[i] = 0;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            sum[matrix[i][j]]++;
        }
    }

    for(int i = 1; i < m+1; i++){
        if(sum[i] == n){
            ans++;
        } 
    }
    printf("%d", ans);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <cctype>
using namespace std;
int main() {
int N; 
cin >> N; 
long long int A[200010]; 
for (int i = 0; i < N; i++){
cin >> A[i]; 
}
long long int B = 0; 
int R = 0; 
long long int count = 0; 
for (int L = 0; L < N; L++){
while (R < N && (A[R] ^ B) == A[R] + B){
B += A[R];
R ++; 
}
count += R - L; 
if(L == R) R++; 
else B -= A[L];
}
cout << count << endl; 
}

Measured memory_bytes: 1792
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int total;

        Scanner inp = new Scanner(System.in);
        total = inp.nextInt();

        String a[] = new String[total];

        for (int k = 0; k < total; k++) {
            a[k] = inp.next() + inp.nextInt();
        }

        quicksort(a, 0, total-1);

        validate(a);

        for (String item : a){
            String i = item.substring(0, 1) + " " + item.substring(1);
            System.out.print(i + "\n");
        }
    }

    public static void validate(String[] a) {
        ArrayList<String> check = new ArrayList<>();
        String c = "";
        int currentNum = 0;
        for (int i = 0; i < a.length; i++) {
            int num = Integer.parseInt(a[i].substring(1));

            if (currentNum != num) {
                currentNum = num;
                if (c != "") {
                    check.add(c);
                }
                c = "";
            }

            c += a[i].substring(0,1);
        }

        check.add(c);

        String last = "";
        for (String txt : check) {
            if (last.equals("")) {
                last = txt;
            } else if(!txt.equals(last)) {
                System.out.println("Not stable");
                return;
            }
        }

        System.out.println("Stable");
    }

    public static int partition(String[] a, int p, int r) {
        String x = a[r];
        int i = p-1;
        for (int j = p; j < r; j++) {
            int num1 = Integer.parseInt(a[j].substring(1));
            int num2 = Integer.parseInt(x.substring(1));
            if (num1 <= num2) {
                i = i+1;
                String temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }

        String temp = a[i+1];
        a[i+1] = a[r];
        a[r] = temp;

        return i+1;
    }

    public static void quicksort(String[] a, int p, int r) {
        if (p < r) {
            int q = partition(a, p, r);

            quicksort(a, p, q-1);
            quicksort(a, q+1, r);
        }
    }
}



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

int main()
{
	int n, i = 3, tmp;
	cin >> n;

	while (i <= n) {
		if (i % 3 == 0) {
			cout << ' '<< i ;
		}
		else{
			for (tmp = i; tmp != 0; tmp /= 10) {
				if (tmp % 10 == 3) { 
					cout << ' '<< i ; 
					break;
				}
			}
		}
		i++;
	}
	cout << endl;
    return 0;
}

Measured memory_bytes: 1160
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template <class T> inline void chmin(T &a, const T& b) { if (b < a) a = b; }
template <class T> inline void chmax(T &a, const T& b) { if (b > a) a = b; }
/* clang-format on */

int main() {
#ifdef DEBUG
  ifstream ifs("in.txt");
  cin.rdbuf(ifs.rdbuf());
#endif
  int R, G, B, N;
  while (cin >> R >> G >> B >> N) {
    ll res = 0;
    for (int r = 0; r * R <= N; r++) {
      for (int b = 0; r * R + b * B <= N; b++) {
        int rem = N - r * R - b * B;
        if (rem % G == 0) {
          ++res;
        }
      }
    }
    cout << res << endl;
  }
  return 0;
}


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

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

int main() {
  int H, W, M;
  cin >> H >> W >> M;
  vector<int> h(M), w(M), bomb_h(H, 0), bomb_w(W, 0);
  set<pair<int, int>> bomb;
  for (int i = 0; i < M; i++) {
    cin >> h[i] >> w[i];
    bomb_h[h[i]-1]++;
    bomb_w[w[i]-1]++;
    bomb.insert({h[i]-1, w[i]-1});
  }
  auto copy_h = bomb_h, copy_w = bomb_w;
  sort(copy_h.begin(), copy_h.end());
  sort(copy_w.begin(), copy_w.end());
  int max_h = copy_h[H-1], max_w = copy_w[W-1];
  vector<int> location_h(0), location_w(0);
  for (int i = 0; i < H; i++) {
    if (max_h == bomb_h[i]) {
      location_h.push_back(i);
    }
  }
  for (int i = 0; i < W; i++) {
    if (max_w == bomb_w[i]) {
      location_w.push_back(i);
    }
  }
  bool flag = false;
  int length1 = location_h.size(), length2 = location_w.size();
  for (int i = 0; i < length1; i++) {
    for (int j = 0; j < length2; j++) {
      if (!bomb.count({location_h[i], location_w[j]})) {
        flag = true;;
        break;
      }
    }
  }
  int ans = max_h + max_w;
  if (!flag) ans--;
  cout << ans << endl;
}


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


const int MAX = 3005;



int dp[MAX][MAX];

int main()
{

    string str1, str2;
    cin >> str1 >> str2;

    int n = str1.size(), m = str2.size();

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(str1[i-1] == str2[j-1])
                dp[i][j] = 1 + dp[i-1][j-1];
            else
                dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
        }
    }

    string ans = "";
    int i = n, j = m;
    while(i > 0 && j > 0){
            if(dp[i][j] != dp[i][j-1] && dp[i][j] != dp[i-1][j]){
                ans += str1[i-1];
                i--; j--;
            }
            else{
                if(dp[i][j] == dp[i][j-1]) j--;
                else i--;
            }
    }

    reverse(ans.begin(), ans.end());

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 35456
#include<iostream>
#include<string>
#include<vector>
#include<unordered_map>
#include<algorithm>
#include<cmath>
#include<climits>
#include<iomanip>
#include<bitset>
#include<cstdlib>
#include<queue>
#include<utility> //pair
using namespace std;

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

typedef long long ll;

int main() {
	//入力;
	int t, x;
	cin >> t >> x;
	

	//小数点以下の桁数表示;
	cout << fixed << setprecision(15);

	cout << (double)t / x << endl;

	return 0;
}

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
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;
}
int vector_finder(std::vector<ll> vec, int number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}
struct edge {
  ll to, cost;
};

int main() {
  ll N, M; cin >> N >> M;
  vector<ll> p(M); vector<string> S(M); REP(i, M) cin >> p[i] >> S[i];
  map<int, int> m; ll ac = 0; ll wa = 0;
  REP(i, M) {
    if(S[i] == "WA" && m[p[i]] != -1) m[p[i]]++;
    else if(S[i] == "AC" && m[p[i]] != -1) {
      ac++;
      wa += m[p[i]];
      m[p[i]] = -1;
    }
  }
  cout << ac << " " << wa << endl;
}

Measured memory_bytes: 11904
#include <cstdio>
#include <utility>
#include <typeinfo>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <tuple>
#define REP(i,n) for(int i=0;i<n;i++)
typedef long long int ll;
using namespace std;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
typedef vector<string> vs;

int main()
{
    string s;
    cin >> s;
    int pc = -1;
    int pf = -1;
    for (int i=s.length()-1;i>=0;i--)
        if(s[i]=='F')
        {
            pf = i;
            break;
        }
    for (int i=0;i<s.length();i++)
        if(s[i]=='C')
        {
            pc = i;
            break;
        }
    if (pc != -1 && pf != -1)
    {
        if(pc < pf)
        {
            cout << "Yes" <<endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0 ;

}



Measured memory_bytes: 256
import itertools
import math

n = int(input())
D = [list(map(int, input().split())) for _ in range(n)]

A = list(itertools.permutations(list(range(n))))
ans = 0
for a in A:
    for i in range(len(a)-1):
        ans += math.sqrt((D[a[i]][0]-D[a[i+1]][0])**2+(D[a[i]][1]-D[a[i+1]][1])**2)

print(ans/len(A))

Measured memory_bytes: 80020
s_list=list(input())

def out_wa():
  print('WA')

if s_list[0]!='A':
  out_wa()
else:
  count=0
  for i in range(2,len(s_list)-1):
    if s_list[i] == 'C':
      count+=1

  if count != 1:
    out_wa()
  else:
    s = ''.join(s_list)
    s=s.replace('A','')
    s=s.replace('C','')
    l_s=s.lower()
    if l_s !=s:
      out_wa()
    else:
      print('AC')
   

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int count = sc.nextInt();
        int sum = 0;
        for (int i = 0; i < count; i++) {
            sum += isPrimeNumber(sc.nextLong()) ? 1 : 0;
        }
        System.out.println(sum);
    }

    private static boolean isPrimeNumber(long a) {
        if (a == 2) {
            return true;
        } else if (a < 2 || a % 2 == 0) {
            return false;
        }

        long sqrt = (long) Math.sqrt(a);
        for (int i = 3; i <= sqrt; i += 2) {
            if (a % i == 0) {
                return false;
            }
        }
        return true;
    }
}

Measured memory_bytes: 41060
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
struct unifnd{
  VI ht,pr;
  in fnd(in a){
    in ta=a;
    while(a!=pr[a])a=pr[a];
    in tt=ta;
    while(ta!=a){
      tt=pr[ta];
      pr[ta]=a;
      ta=tt;
    }
    return a;
  }
  void uni(in a, in b){
    a=fnd(a);
    b=fnd(b);
    if(a==b)return;
    if(ht[b]<ht[a])swap(a,b);
    pr[a]=b;
    ht[b]+=(ht[a]==ht[b]);
  }
  void ini(in n){
    ht.resize(n);
    pr.resize(n);
    forn(i,n){
      ht[i]=0;
      pr[i]=i;
    }
  }
};
unifnd tfd;
VI a,b,c;
struct cand{
  in id;
  cand(in z=0){
    id=z;
  }
  bool operator<(const cand cp)const{
    return c[id]>c[cp.id];
  }
};
priority_queue<cand> q;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  in n,qq;
  cin>>n>>qq;
  tfd.ini(n);
  in sm=0;
  in ta,tb,tc;
  forn(z,qq){
    cin>>ta>>tb>>tc;
    a.PB(ta%n);
    b.PB(tb%n);
    c.PB(tc);
    a.PB((ta+1)%n);
    b.PB(tb%n);
    c.PB(tc+1);
    q.push(cand(2*z));
    q.push(cand(2*z+1));
  }
  in u;
  while(!q.empty()){
    u=q.top().id;
    q.pop();
    if(tfd.fnd(a[u])==tfd.fnd(b[u]))
      continue;
    tfd.uni(a[u],b[u]);
    sm+=c[u];
    a[u]=(a[u]+1)%n;
    b[u]=(b[u]+1)%n;
    c[u]+=2;
    q.push(cand(u));
  }
  cout<<sm<<endl;
  return 0;
}


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

int main(){
    long long int k, n;
    cin >> k >> n;

    vector<pair<long long int, long long int>> prime_power;
    for (long long int p=2; p*p<=n; p++) {
        if(n % p != 0) continue;// break and proceed to p+1

        int power = 0;
        while(n % p == 0){
            power += 1;
            n /= p;
        }
        prime_power.push_back(make_pair(power, p));
    }

    // n has been divided by all primes (with power) smaller than sqrt(n)
    if(n != 1) prime_power.push_back(make_pair(1, n));

    sort(prime_power.begin(),prime_power.end());
    long long int ans = 1;
    for(auto pp : prime_power){
        int times = pp.first;
        while(times >= k){
            ans *= pp.second;
            times -= k;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
#include <algorithm>
#include <functional>
#include <stack>
#include <set>
#include <queue>
#include <map>
using namespace std;
#define rep(i, m, n) for (int(i) = (int)(m); i < (int)(n); ++i)
#define rep2(i, m, n) for (int(i) = (int)(n)-1; i >= (int)(m); --i)
#define REP(i, n) rep(i, 0, n)
#define REP2(i, n) rep2(i, 0, n)
#define all(hoge) (hoge).begin(), (hoge).end()
#define en '\n'
using ll = long long;
using ull = unsigned long long;
typedef vector<ll> vec;
typedef vector<vector<ll>> mat;
typedef vector<vector<vector<ll>>> mat3;
typedef vector<string> svec;
typedef vector<vector<string>> smat;
typedef pair<ll, ll> P;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
constexpr long long MOD = (ll)1e9 + 7;
// constexpr long long MOD = 998244353LL;
using ld = long double;
static const ld pi = 3.141592653589793L;
template <class T> bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T> bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
// ~~~~~~~~~~~~~~memo~~~~~~~~~~~~~~
// for (int i = 0; i < n; ++i)
// vector<long long> v(n), c(n);
// cout << res << endl;
// cout << res << '\n';
// int型の2次元配列(h×w要素の)の宣言
// vector<vector<int>> data(h, vector<int>(w));
// rotate(s.begin(), s.begin() + 1, s.end());
// sort(all(a),greater<int>());
// s.substr(0,2) 先頭から2文字切り出す
// for (auto it = mp.rbegin();it != mp.rend(); ++it)
int N,M,Q;
vector<ll> a,b,c,d;

ll calc(vector<int> &L) {
    ll res = 0;
    rep(i,0,Q) if (L[b[i]]-L[a[i]] == c[i]) res += d[i];
    return res;
}

ll dfs(vector<int> &L) {
    if (L.size() == N) {
        return calc(L);
    }
    ll res = 0;
    int prev_last = 0;
    if (L.empty()) {
        prev_last = 0;
    } else {
        prev_last = L.back();
    }
    for (int i = prev_last;i < M; ++i) {
        L.push_back(i);
        res = max(res,dfs(L));
        L.pop_back();
    }
    return res;
}



int main() {
    cin >> N >> M >> Q;
    a.resize(Q);b.resize(Q);c.resize(Q);d.resize(Q);
    rep(i,0,Q) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        --a[i];--b[i];
    }
    vector<int> L;
    cout << dfs(L) << '\n';
    return 0;
}


Measured memory_bytes: 3624
import sys
n, k = [int(i) for i in sys.stdin.readline().split()]
a_ls = [int(i) for i in sys.stdin.readline().split()]
memo_ls = [[0 for i in range(k+1)] for j in range(n)]
memo_ls[0][0] = 1
for i in range(n):
    for j in range(k+1):
        if i == 0:
            if j <= a_ls[i]:
                memo_ls[i][j] = 1
            continue
        if j == 0:
            memo_ls[i][j] = 1
            continue
        if a_ls[i] < j:
            memo_ls[i][j] = (- memo_ls[i-1][max(0,j-a_ls[i]-1)] + memo_ls[i][j-1] + memo_ls[i-1][j]) % (10**9+7) #sum(memo_ls[i-1][max(0,j - a_ls[i]):j+1]) % (10**9 + 7)
        else:
            memo_ls[i][j] = (memo_ls[i][j-1] + memo_ls[i-1][j]) % (10**9+7)
print(memo_ls[-1][-1])

Measured memory_bytes: 171656
#include"bits/stdc++.h"
#define rep(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define int long long
#define INF (1<<29)
using namespace std;
typedef pair<int,int> P;
const int mod=1000000007;

int mpow(int a,int x);
int m_inv(int n){return mpow(n,mod-2);}

int gcd(int x,int y){return y?gcd(y,x%y):x;}
int lcm(int x,int y){return x*y/gcd(x,y);}

signed main(){
	int N,M,R;
	cin>>N>>M>>R;
	vector<int> r(R);
	rep(i,R){
		int a;
		cin>>a;
		r[i]=a-1;
	}
	vector<vector<int>> d(N,vector<int>(N));
	rep(i,N) rep(j,N) if(i!=j) d[i][j]=INF;
	rep(i,M){
		int a,b,c;
		cin>>a>>b>>c;
		a--;b--;
		if(d[a][b]>c){
		    d[a][b]=c;
		    d[b][a]=c;
		}
	}
	
	rep(k,N) rep(i,N) rep(j,N){
		if(d[i][j]>d[i][k]+d[k][j]) d[i][j]=d[i][k]+d[k][j];
	}
	int ans=INF;
        sort(r.begin(),r.end());
	do{
		int tmp=0;
		rep(i,R-1) tmp+=d[r[i]][r[i+1]];
		ans=min(ans,tmp);
		}while(next_permutation(r.begin(),r.end()));
	cout<<ans<<endl;
}

int mpow(int a,int x){
	int ans=1;
	while(x>0){
		if(x%2==1) (ans*=a)%=mod;
		(a*=a)%=mod;
		x>>=1;
	}
	return ans;
}


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

int main() {
  int H1, M1, H2, M2, K;
  cin >> H1 >> M1 >> H2 >> M2 >> K;
  int studytime;
  H1 = H1 * 60;
  H2 = H2 * 60;
  int HM1 = H1 + M1;
  int HM2 = H2 + M2;
  studytime = HM2 - HM1 - K;
  cout << studytime;
}

Measured memory_bytes: 3636
// "include" {{{
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cstring>
#include <iomanip>
#include <tuple>
// }}}
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int> 
#define int long long
#define setout(n,x) setw(n) << setfill(x)
#define Fixed fixed << setprecision(10)
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const long long mod = 1000000007;

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	int l[n];
	rep(i,n){
		cin >> l[i];
	}
	sort(l,l+n,greater<int>());
	int cnt = 0;
	for(int i = 0;i < n-2;++i){
		for(int j = i+1;j < n-1;++j){
			for(int k = j+1;k < n;++k){
				if(l[j] + l[k] > l[i]) ++cnt;
				else break;
			}
		}
	}
	cout << cnt << '\n';
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {

    void run() {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int aEndCount = 0;
        int bStartCount = 0;
        int aEndBStartCount = 0;
        int abInnerCount = 0;


        for (int i = 0; i < n; i++) {
            String s = sc.next();

            if (s.charAt(0) == 'B' && s.charAt(s.length() - 1) == 'A') aEndBStartCount++;
            else if (s.charAt(0) == 'B') bStartCount++;
            else if (s.charAt(s.length() - 1) == 'A') aEndCount++;

            for (int j = 0; j < s.length() - 1; j++) {
                if (s.substring(j, j + 2).equals("AB")) abInnerCount++;
            }
        }

        int concatCount = 0;

        if (aEndBStartCount > 0) {
            if (aEndCount > 0) {
                concatCount++;
                aEndCount--;
            }
            if (bStartCount > 0) {
                concatCount++;
                bStartCount--;
            }
            concatCount += aEndBStartCount - 1;
        }

        concatCount += Math.min(aEndCount, bStartCount);

//        System.out.println(aEndCount);
//        System.out.println(bStartCount);
//        System.out.println(aEndBStartCount);
//        System.out.println(abInnerCount);
//        System.out.println("-------");
//        System.out.println(concatCount);
//        System.out.println(abInnerCount);

        // write your code
        System.out.println(abInnerCount + concatCount);
    }

    void debug(Object... os) {
        System.err.println(Arrays.deepToString(os));
    }

    public static void main(String[] args) {
        new Main().run();
    }
}


Measured memory_bytes: 33040
N,K=map(int,input().split())
p=10**9 + 7
ans=0
for i in range(K-1,N+1):
  L_min=i*(i+1)//2
  L_max=(N*(N+1)//2)-((N-i-1)*(N-i)//2)
  ans += (L_max-L_min+1)%p
print(ans%p)

Measured memory_bytes: 9168
MOD=998244353
A,B,C,D=map(int,input().split())
dp=[[0]*(D+1) for i in range(C+1)]

dp[A][B]=1
for i in range(A,C+1):
    for j in range(B,D+1):
        if i==A and j==B:
            continue
        elif i==A:
            dp[i][j]=dp[i][j-1]*i%MOD
        elif j==B:
            dp[i][j]=dp[i-1][j]*j%MOD
        else:
            dp[i][j]=(dp[i][j-1]*i+dp[i-1][j]*j-dp[i-1][j-1]*(i-1)*(j-1))%MOD
print(dp[C][D])

Measured memory_bytes: 133968
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+1;
int n;
int a[N];
int dp[N];
int solve(int i){
    if(i==1)return 0;
    if(i==2)return abs(a[1]-a[2]);
    if(dp[i]+1){
        return dp[i];
    }
    return dp[i]=min(solve(i-1)+abs(a[i]-a[i-1]),solve(i-2)+abs(a[i]-a[i-2]));
}
main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }memset(dp,-1,sizeof(dp));
    cout<<solve(n);
}


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

typedef long long int LL;
typedef long long int LLint;
typedef pair<int,int> intpair;
typedef pair<bool,bool> boolpair;
typedef pair<string,string> strpair;
typedef pair<LL,LL> LLpair;
typedef pair<double,double> doublepair;
typedef pair<float,float> floatpair;
typedef vector<int> intvector;
typedef vector<bool> boolvector;
typedef vector<string> strvector;
typedef vector<LL> LLvector;
typedef vector<double> doublevector;
typedef vector<float> floatvector;
#define ED return 0;
#define UP(a,b) ((a+(b-1))/b)
#define SORT(vec) sort(vec.begin(),vec.end());
#define DOUBLECHANGE(count) cout << setprecision(count);
#define REV(vec) reverse(vec.begin(),vec.end());
#define ipow(x,y) ll(pow(x,y))
#define INF 999999999
const long long mod = 1000000007;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<vector<int>> stations (N-1,vector<int> (3,0));
    for(int i = 0;i < N-1;i++){
        cin >> stations[i][0] >> stations[i][1] >> stations[i][2];
    }
    for(int i = 0;i < N-1;i++){
//        cout << "From station " << i << endl;
        int time = 0;
        int pos = i;
        while(pos != N-1){
            if(time < stations[pos][1] || (time-stations[pos][1]) % stations[pos][2] != 0){
                if(time < stations[pos][1]){
                    time = stations[pos][1];
                }
                else{
                    time += stations[pos][2] - time % stations[pos][2];
                }
            }
            time += stations[pos][0];
            pos++;
//            cout << "Now time is " << time << endl;
        }
        cout << time << endl;
    }
    cout << 0 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
int n;
main(){
	cin>>n;
	vector<int>a(n),b(n),c(n);
	r(i,n)cin>>a[i];
	r(i,n)cin>>b[i];
	r(i,n)cin>>c[i];
	sort(a.begin(),a.end());
	sort(b.begin(),b.end());
	sort(c.begin(),c.end());
	int sum=0,b1=0,c1=0,cc[100001]={};
	r(i,n){
		cc[i]=c.end()-upper_bound(c.begin(),c.end(),b[i]);
		//cout<<cc[i]<<endl;
	}
	for(int i=n-1;i>=1;i--)cc[i-1]+=cc[i];
	r(i,n){
		int x=lower_bound(b.begin(),b.end(),a[i]+1)-b.begin();

		sum+=cc[x];
	}
	cout<<sum<<endl;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,a,n) for(ll i = a;i < n;i++)
#define rrep(i,a,n) for(ll i = n; i >= a;i--)
#define index_check(i,n) if(i > n-1 || i < 0) continue; 
#define LINF 1e18
#define INF 1e9
using namespace std;

#define fs first
#define sc second

using P = pair<ll,ll>;
using Pll = pair<P,ll>;
using PQ = priority_queue<P,vector<P>,greater<P>>;


const ll MOD = 1e9+7;

signed main(){
    ll N,W;
    cin >> N >> W;
    ll dp[N+1][W+1] = {};
    ll w[N],v[N];
    rep(i,0,N) cin >> w[i] >> v[i];

    rep(i,0,N){
        rep(j,0,W+1){
            if(j-w[i] >= 0) dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i]);
            else dp[i+1][j] = dp[i][j];
        }
    }

    ll ans = 0;
    rep(i,0,W+1){
        ans = max(ans,dp[N][i]);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 82500
import sys
import re
sys.setrecursionlimit(10**7)
input = lambda: sys.stdin.readline().strip()

def main():
    S = input()
    words = ["eraser","erase","dreamer","dream"]
    for w in words:
        S = re.sub(w,"",S)
    if S=="":
        print("YES")
    else:
        print("NO")

main()

Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
typedef long long LL; 
const int base=2000,P=1e9+7,N=200010;
int dp[4010][4010],a[N],b[N];
namespace Comb{
    const int U=8000;
    int f[U+3],rf[U+3];
    LL inv(LL a,LL m){return(a==1?1:inv(m%a,m)*(m-m/a)%m);} 
    void init(){
        f[0]=1;for(int i=1;i<=U;i++)f[i]=(LL)f[i-1]*i%P;
        rf[U]=inv(f[U],P);
        for(int i=U;i;i--)rf[i-1]=(LL)rf[i]*i%P;
    }
    LL C(int n,int m){
        if(m<0||m>n)return 0;
        return (LL)f[n]*rf[m]%P*rf[n-m]%P;
    }
}
using namespace Comb;
inline void up(int &x){while(x<0)x+=P;while(x>=P)x-=P;}
int main(){
    int n; 
	init();
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i],&b[i]);
        dp[base-a[i]][base-b[i]]++;
    }
    for(int i=0;i<=base+base;i++){
        for(int j=0;j<=base+base;j++){
            if(i)dp[i][j]+=dp[i-1][j],up(dp[i][j]);
            if(j)dp[i][j]+=dp[i][j-1],up(dp[i][j]);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=dp[a[i]+base][b[i]+base]; up(ans);
        ans-=C(a[i]+a[i]+b[i]+b[i],a[i]+a[i]); up(ans);
    }
    printf("%lld\n",1ll*ans*rf[2]%P);
    return 0;
}

Measured memory_bytes: 64512
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
#define SUM(a)  accumulate((a).begin(),(a).end(),0)
#define SORT(a) sort(ALL(a))
#define REV(a) reverse(ALL(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
typedef long long ll;
const int INTINF = 1<<30;
const ll LLINF = 1LL<<62;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;


int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a, n;
  cin >> n;
  int cnt[100001];
  REP(i,100002)cnt[i]=0;
  REP(i,n){
      cin >> a;
      cnt[a]++;
      cnt[a+1]++;
      cnt[a+2]++;
  }
  int mx = 0;
  FOR(i,0,100002){
      mx = max(mx,cnt[i]);
  }
  cout << mx << endl;

}


Measured memory_bytes: 640
a, b = (int(i) for i in input().split())  

def f(a, b):
    num_len = b-a+1

    if num_len == 1:
        return b

    one_check = num_len if a % 2 == 0 else num_len-1

    x = (one_check // 2) % 2
    y = b if one_check % 2 == 1 else 0
    z = 0 if a % 2 == 0 else a
    return x^y^z

print(f(a,b))


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

ll gcd(ll a, ll b){
  if(b == 0)return a;
  else return gcd(b, a%b);
}

ll lcm(ll a, ll b){
  return a/gcd(a,b)*b;
}

int main(){
  int n;
  cin >> n;
  ll ans = 1;
  rep(i,n){
    ll t;
    cin >> t;
    ans = lcm(ans,t);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3564
#include <cstdio>
#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
#include <functional>
#include <tuple>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <utility>
#include <memory>
#include <valarray>

using namespace std;

using ll = long long int;
#define loop(i, N) for (int i = 0; i < N; ++i)
#define scanInt(x) int x; scanf("%d", &x); getchar();
#define scanLLInt(x) ll x; scanf("%lld", &x); getchar();
#define scanVecInt(A, N) vector<int> A(N); loop(i, N){scanf("%d", &(A[i])); getchar();}
#define scanVecLLInt(A, N) vector<ll> A(N); loop(i, N){scanf("%lld", &(A[i])); getchar();}

int main()
{
    scanInt(N);
    scanVecInt(A, N);
    int state = 0;
    int before = A[0];
    int result = 1;
    loop(i, N){
        auto& Ai = A[i];
        if (state == 0){
            if (before > Ai){
                state = -1;
            }else if (before < Ai){
                state = 1;
            }
        }else if (state == 1){
            if (before > Ai){
                ++result;
                state = 0;
            }
        }else{ // state == -1
            if (before < Ai){
                ++result;
                state = 0;
            }
        }
        before = Ai;
    }
    printf("%d\n", result);
}


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

#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define bf(i,s) for(int i = head[s]; i; i = e[i].next)
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define VI vector<int>
#define sf scanf
#define pf printf
#define fp freopen
#define SZ(x) ((int)(x).size())
#define IF_DEBUG 0
typedef long long ll;
typedef double db;
const int inf = 1<<30;
const ll INF = 1ll<<60;
const db Inf = 1e20;
const db eps = 1e-9;

void gmax(int &a,int b){a = (a > b ? a : b);}
void gmin(int &a,int b){a = (a < b ? a : b);}
int x;
int main()
{
	cin >> x;
	if(x%10==9||x/10%10==9)pf("Yes");else pf("No");
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <utility>
using namespace std;

int w, h;
char tiles[20][21];

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

bool isRegion(int x, int y){
    return x >= 0 && x < w && y >= 0 && y < h;
}

int main(){
    while(1){
        cin >> w >> h;
        if(!w && !h) break;
        
        int sx, sy;
        for(int i = 0; i < h; i++){
            cin >> tiles[i];
            for(int j = 0; j < w; j++){
                if(tiles[i][j] == '@'){
                    sx = j; sy = i;
                }
            }
        }
        
        int cnt = 0;
        queue<pair<int, int> > q;
        q.push(make_pair(sx, sy));
        while(!q.empty()){
            cnt++;
            int x = q.front().first, y = q.front().second;
            q.pop();
            
            for(int i = 0; i < 4; i++){
                int nx = x + dx[i], ny = y + dy[i];
                
                if(isRegion(nx, ny) && tiles[ny][nx] == '.'){
                    tiles[ny][nx] = '#';
                    q.push(make_pair(nx, ny));
                }
            }
        }
        cout << cnt << endl;
        
    }
}

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a, b;
  cin >> a >> b;
  cout << max({a + b, a - b, a * b}) << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void swap(long *A, long i, long j) {
  long tmp;
  tmp = A[i];
  A[i] = A[j];
  A[j] = tmp;
}

void up_heap(long *A, long i,long H) {
  long l,r,largest;
  if(i <= 0) return;
  l = 2*i;
  r = 2*i+1;
  if(l <= H && A[l] > A[i]) largest = l;
  else largest = i;
  if(r <= H && A[r] > A[largest]) largest = r;
  if(largest != i) {
    swap(A,i,largest);
    up_heap(A,i/2,H);
  }
}

void down_heap(long *A, long i, long H) {
  long l,r,largest;
  if(i <= 0) return;
  l = 2*i;
  r = 2*i+1;
  if(l <= H && A[l] > A[i]) largest = l;
  else largest = i;
  if(r <= H && A[r] > A[largest]) largest = r;
  if(largest != i) {
    swap(A,i,largest);
    down_heap(A,largest,H);
  }
}

int main()
{
  long i,*A;
  char command[8];
  A = malloc(sizeof(long) * 2000000);
  i = 0;
  while (1) {
    scanf("%s",command);
    if(strcmp(command,"insert") == 0) {
      i++;
      scanf("%ld",A+i);
      up_heap(A,i/2,i);
    }
    if(strcmp(command,"extract") == 0) {
      printf("%ld\n",A[1]);
      swap(A,1,i);
      i--;
      down_heap(A,1,i);
    }
    if(strcmp(command,"end") == 0) break;
  }

  return 0;
}

Measured memory_bytes: 9660
#include <iostream>
#include <string>
using namespace std;
const char* solve() {
	string S;
	cin >> S;
	for (int i = 0; i < S.size(); i += 2) {
		if (S[i] == 'L') return "No";
		if (i + 1 < S.size() && S[i + 1] == 'R') return "No";
	}
	return "Yes";
}
int main() {
	cout << solve() << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const int INF = 1000000005;
const long double EPS = 1e-10;

vector<int> zalgo(string s) {
  int n = s.size();
  vector<int> a(n);
  a[0] = n;
  int i = 1, j = 0;
  int l = s.size();
  while (i < l) {
    while (i + j < l && s[j] == s[i + j]) {
      j++;
    }
    if (j == 0) {
      i++;
      continue;
    }
    a[i] = j;
    int k = 1;
    while (l - i > k && k < j - a[k]) {
      a[i + k] = a[k];
      k++;
    }
    i += k;
    j -= k;
  }
  return a;
}

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

  int ans = 0;
  rep(i, n) {
    string ress;
    FOR(j, i, n) {
      ress += s[j];
    }
    vector<int> resa(n - i);
    resa = zalgo(ress);
    rep(j, n - i) {
      ans = max(ans, min(j, resa[j]));
    }
  }
  cout << ans << endl;



  
  return 0;
}

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

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

Measured memory_bytes: 384
module Main (main) where

import qualified Data.ByteString.Char8 as C8
import Data.Bool
import Data.Maybe

main :: IO ()
main = do
  [n,k] <- readInts
  print . showAnswer $ solve (n,k)

type Input  = (Int, Int)
type Output = Int

solve :: Input -> Output
solve (n,k)
  | n `mod` k == 0 = 0
  | otherwise = 1

showAnswer :: Output -> Answer
showAnswer = Number

-- utils
readInts :: IO [Int]
readInts = map (fst . fromJust . C8.readInt) . C8.words <$> C8.getLine

data Answer
  = YesNo Bool
  | YESNO Bool
  | AB Bool
  | Number Int
  | String String
  | Compare Ordering
  | Compare2 Ordering

instance Show Answer where
  show (YesNo b)    = bool "No" "Yes" b
  show (YESNO b)    = bool "NO" "YES" b
  show (AB b)       = bool "B"  "A" b
  show (Number i)   = show i
  show (String s)   = s
  show (Compare o)  = ordering "<" "=" ">" o
  show (Compare2 o) = ordering "Right" "Balanced" "Left" o

ordering :: a -> a -> a -> Ordering -> a
ordering lt eq gt o = case o of
  LT -> lt
  EQ -> eq
  GT -> gt

Measured memory_bytes: 380
s = int(input())

bi = [1, 2, 4, 8, 16, 32, 64]

a = [s]

for i in range(10000):

    n = a[i] 

    if n%2 == 0:
        a.append(n//2)
    else:
        a.append(3*n + 1)

    if a[i+1] in a[:i]:
        print(i+2)
        exit()

print(0)


Measured memory_bytes: 3060
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
N, K = map(int, input().split())			# "5 7" -> ["5", "7"] -> 5, 7 => N=5,K=7
R,S,P = map(int, input().split())		# 5 7 2
T = input()

def score(s):
	if s=='r': return P
	if s=='s': return R
	if s=='p': return S
	return 0

X=[""]*K
for i in range(K):
	X[i]=T[i::K]

p(X)

def max_score(x):
	a=0
	c=''
	A=x
	for s in A:
		if c==s:
			c=''
		else:
			a+=score(s)
			c=s

	#B=x[1:]+x[0]
	#b=0
	#c=''
	#for s in B:
	#	if c==s:
	#		c=''
	#	else:
	#		b+=score(s)
	#		c=s
	
	#p("A,a=", A,a)
	#p("B,b=", B,b)
	#return max(a,b)
	return a
	
	

ANS=[0]*K
for i,x in enumerate(X):
	ANS[i] = max_score(x)

ans=sum(ANS)
print(ans)


Measured memory_bytes: 12220
r,c,k = map(int, input().split())
rcv = [ [0]*c for _ in range(r) ]

for _ in range(k):
    ri,ci,vi = map(int, input().split())
    rcv[ri-1][ci-1] = vi

dp0 = [ [0]*c for _ in range(r) ]
dp1 = [ [0]*c for _ in range(r) ]
dp2 = [ [0]*c for _ in range(r) ]
dp3 = [ [0]*c for _ in range(r) ]

dp1[0][0] = rcv[0][0]
for i in range(r):
    for j in range(c):
        if i+1 < r:
            dp0[i+1][j] = max(dp0[i][j], dp1[i][j], dp2[i][j], dp3[i][j], dp0[i+1][j])
            if rcv[i+1][j] > 0:
                dp1[i+1][j] = max(dp1[i+1][j],  max(dp0[i][j], dp1[i][j], dp2[i][j], dp3[i][j])+rcv[i+1][j])

        if j+1 < c:
            dp0[i][j+1] = max(dp0[i][j], dp0[i][j+1])
            dp1[i][j+1] = max(dp1[i][j], dp1[i][j+1])
            dp2[i][j+1] = max(dp2[i][j], dp2[i][j+1])
            dp3[i][j+1] = max(dp3[i][j], dp3[i][j+1])
            if rcv[i][j+1] > 0:
                dp1[i][j+1] = max(dp1[i][j+1], dp0[i][j]+rcv[i][j+1])
                dp2[i][j+1] = max(dp2[i][j+1], dp1[i][j]+rcv[i][j+1])
                dp3[i][j+1] = max(dp3[i][j+1], dp2[i][j]+rcv[i][j+1])

ans = max(dp0[r-1][c-1], dp1[r-1][c-1], dp2[r-1][c-1], dp3[r-1][c-1])
print(ans)
# print(dp0)
# print(dp1)
# print(dp2)
# print(dp3)


Measured memory_bytes: 428452
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7


def main():
    N, X, M = map(int, input().split())
    # A = [0] * (M)
    # A[X] = 1
    now = [X]
    nowS = set()
    nowS.add(X)
    loop = -1
    for i in range(N - 1):
        tmp = pow(now[-1], 2, M)
        if tmp in nowS:
            loop = now.index(tmp)
            break
        else:
            now.append(tmp)
            nowS.add(tmp)
    # print(now, loop)
    if loop == -1:
        print(sum(now))
    else:
        ans = sum(now[:loop])
        N -= loop
        # print(N)
        SUM = sum(now[loop:])
        ans += (N // (len(now)-loop)) * SUM
        N %= len(now)-loop
        # print(N)
        ans += sum(now[loop:loop+N])
        print(ans)


if __name__ == "__main__":
    main()


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

int main() { 
    string S; cin >> S;

    string pre_s{S[0], S[1]};
    string suf_s{S[2], S[3]};
    int pre = stoi(pre_s);
    int suf = stoi(suf_s);

    bool is_pre_mon = false;
    bool is_suf_mon = false;

    if (pre > 0 && pre < 13) {
        is_pre_mon = true;
    }
    if (suf > 0 && suf < 13) {
        is_suf_mon = true;
    }

    if (is_pre_mon && ! is_suf_mon) {
        cout << "MMYY" << endl;
    } else if (!is_pre_mon && is_suf_mon) {
        cout << "YYMM" << endl;
    } else if (is_pre_mon && is_suf_mon) {
        cout << "AMBIGUOUS" << endl;
    } else {
        cout << "NA" << endl;
    }
    
    return 0;
}

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

int main(){
  int N; cin >> N;
  vector<int> MY(3*N);
  for(int i=0;i<3*N;i++){
    cin >> MY[i];
  }
  sort(MY.rbegin(),MY.rend());
  long long ans=0;
  for(int i=1;i<2*N;i+=2){
    ans+=MY[i];
  }
  cout << ans << endl;
}
  

Measured memory_bytes: 1408
#include<iostream>
using namespace std;
#define MAX 100005
#define NIL -1
struct Node{int p,l,r;};
Node T[MAX];
int n,D[MAX];
void print(int u){
 int i,c;
 cout<<"node "<<u<<": ";
 cout<<"parent = "<<T[u].p<<", ";
 cout<<"depth = "<<D[u]<<", ";
 if(T[u].p==NIL)cout<<"root, ";
 else if(T[u].l==NIL)cout<<"leaf, ";
 else cout<<"internal node, ";
 cout<<"[";
 for(i=0,c=T[u].l;c!=NIL;i++,c=T[c].r){
  if(i)cout<<", ";
  cout<<c;
 }
 cout<<"]"<<endl;
}
int rec(int u,int p){
 D[u]=p;
 if(T[u].r!=NIL)rec(T[u].r,p);
 if(T[u].l!=NIL)rec(T[u].l,p+1);
}
int main(){
 int i,j,d,v,c,l,r;
 cin>>n;
 for(i=0;i<n;i++)T[i].p=T[i].l=T[i].r=NIL;
 for(i=0;i<n;i++){
  cin>>v>>d;
  for(j=0;j<d;j++){
   cin>>c;
   if(j==0)T[v].l=c;
   else T[l].r=c;
   l=c;
   T[c].p=v;
  }
 }
 for(i=0;i<n;i++){
  if(T[i].p==NIL)r=i;
 }
 rec(r,0);
 for(i=0;i<n;i++)print(i);
 return 0;
}


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

}





Measured memory_bytes: 2044
main = do
  [_, p] <- r
  as <- r
  print $ f p (g as)
 
r = map read . words <$> getLine
 
g as = (x, y)
  where 
    x = length . filter even $ as
    y = length . filter odd $ as
 
f p (x, 0) = 2 ^ x * (1 - p)
f p (x, y) = 2 ^ (x + y - 1)

Measured memory_bytes: 764