akhauriyash/Code-Regression huggingface dataset:
# nCk % MOD
def getComb(n, k, MOD):
    if n < k:
        return 0
    if n-k < k:
        k = n-k
    # n!/(n-k)!
    comb = 1
    for x in range(n-k+1, n+1):
        comb = (comb * x) % MOD
    # k!
    d = 1
    for x in range(1, k+1):
        d = (d * x) % MOD
    # n!/((n-k)!*k!)
    comb *= pow(d, MOD-2, MOD)
    return comb % MOD

N, K = map(int,input().split())
MOD = 10**9 + 7

"""
赤いボールを一列に並べる。
赤いボールと赤いボールの間、左端、右端の
(N-K+1)箇所の中からi箇所を選ぶ -> (N-K+1) C i

K個の青いボールをi箇所に割り当てる。
1箇所に少なくとも1個割り当てる必要があるので、
(K-i)個の青いボールをi箇所に割り当てる。
これは、「(K-i)個のボールを(i-1)個の区切りで分ける」のと同じ。
よって、(K-1)!/((i-1)! * (K-i)!) = (K-1)C(K-i)
"""

for i in range(1,K+1):
    answer = (getComb(N-K+1, i, MOD) * getComb(K-1, K-i, MOD)) % MOD
    print(answer)

Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll x;
    cin>>x;
    ll ans = 0;
    ll curr = 5;
    ll count = 0;
    ll value[7] = {0,5,6,6,6,6,5};
    count = (x/11)*11;
    ans += (x/11)*2;
    while(count<x) {
        ans++;
        curr = value[curr];
        count += curr;
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

vector<int> get_prime(int n){
    if(n <= 1) return vector<int>();
    vector<bool> is_prime(n+1, true);
    vector<int> prime;
    is_prime[0] = is_prime[1] = 0;
    for (int i = 2; i <= n; ++i) {
        if(is_prime[i]) prime.emplace_back(i);
        for (auto &&j : prime){
            if(i*j > n) break;
            is_prime[i*j] = false;
            if(i % j == 0) break;
        }
    }
    return prime;
}

int main() {
    auto v = get_prime(50000);
    vector<int> val(100001);
    for (int i = 0; i < v.size(); ++i) {
        for (int j = i; j < v.size(); ++j) {
            val[v[i]+v[j]]++;
        }
    }
    int n;
    while(cin >> n, n){
        cout << val[n] << "\n";
    }
    return 0;
}


Measured memory_bytes: 3224
input()
S = input()
oc, cc = 0, 0
ans = ''
for s in S:
    if s == '(':
        oc += 1
        ans += s
    else:
        cc += 1
        if cc > oc:
            ans = '(' + ans
            oc += 1
        ans += ')'

print(ans + ')' * (oc - cc))


Measured memory_bytes: 2940
N = int(input())
X = N // 1.08
result1 = int(X) * 1.08
result2 = (int(X)+1) * 1.08
result3 = (int(X)-1) * 1.08

if int(result1) == N:
  result = int(X)
elif int(result2) == N:
  result = int(X) + 1
elif int(result3) == N:
  result = int(X) -1
else:
  result = ':('

print(result)

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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const ll INF = 1e15;
const int MOD = 1e9+7;
const ll LINF = 1e18;



signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n,m; cin>>n>>m;
  vll a(n);
  ll sum=0;
  rep(i,n){
    cin>>a[i];
    sum+=a[i];
  }
  ll ans=0;
  rep(i,n){
    if(4*a[i]*m>=sum) ans++;
  }
  if(ans>=m)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

X, Y = map(int, input().split())

sum = 0
if(X == 1):
  sum = 300000
elif(X == 2):
  sum = 200000
elif(X == 3):
  sum = 100000

if(Y == 1):
  sum += 300000
elif(Y == 2):
  sum += 200000
elif(Y == 3):
  sum += 100000

if(X == 1 and Y == 1):
  sum += 400000

print(sum)


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

deque<int>f,r;
int p=2;
void rec(ll n){
	if(n==2){
		f={1};r={1};
		return;
	}
	if(n&1){
		rec(n-1);
		f.push_back(p);
		r.push_front(p);
		p++;
	}
	else{
		rec(n/2);
		f.push_back(p);
		r.push_back(p);
		p++;
	}
}

int main(){
	ll n;cin>>n;n++;
	rec(n);
	for(int i:r)f.push_back(i);
	cout<<f.size()<<endl;
	rep(i,f.size()){
		if(i)printf(" ");
		cout<<f[i];
	}
	cout<<endl;
}


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

#define INF 200000000
#define FER 0.0000000001

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;

int dp[10001];

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

	int N, W;
	cin >> N >> W;
	
	int v, w, m;
	for (int i = 0; i < N; i++)
	{
		cin >> v >> w >> m;
		for (int k = 0; m > 0; k++)
		{
			int num = min(m, 1 << k);
			m -= num;
			for (int j = W; j >= w*num; j--)
			{
				dp[j] = max(dp[j], dp[j - w*num] + v*num);
			}
		}
	}

	cout << dp[W] << endl;
	return 0;
}


Measured memory_bytes: 3276
from math import gcd

MOD = 998244353

N, A, B, K = map(int, input().split())

#precompute combination(N, t)
inv = [1, 1]
comb_N = [1, N]
for i in range(2, N//2 + 3):
    inv.append(-inv[MOD%i] * (MOD//i) % MOD)
    comb_N.append(comb_N[-1] * (N-i+1) * inv[i] % MOD)

#reduce A*m + B*n == K to easier one.
g = gcd(A, B)
if K % g != 0:
    print(0)
    exit()

a = A // g
b = B // g
k = K // g

#Solve a*m + b*n == k (m >= 0, n >= 0)
#if (a, b, k) = (5, 11, 83) then the first pair is (m, n) == (10, 3)
for n in range(A):
    if (K - B * n) % A == 0:
        m = (K - B * n) // A
        break

#let m <= N
if m > N:
    times = -((N - m) // b) # == ceil((m-N) / b)
    m -= b * times
    n += a * times

ans = 0
while m >= 0 and n <= N:
    ans += comb_N[min(m, N-m)] * comb_N[min(n, N-n)] % MOD
    ans %= MOD
    m -= b
    n += a
    
print(ans)

Measured memory_bytes: 20804
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cstring>
#include<string>
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define SZ(a) (int)((a).size())
using namespace std;
typedef long long ll;
typedef double db;
typedef pair <int, int> Pii;
typedef pair <ll, int> Pli;
typedef unsigned long long ull;
const double eps = 1e-8;
const ll infll = 0x7fffffffffffffff;
const int mod = (int)(1e9) + 7;
const int inf = 0x7fffffff;
const int maxn = (int)(2e5) + 7;
const int maxm = 300;

char s[110], t[110];

int main() {
	
	// freopen("in.in", "r", stdin);
	scanf("%s%s", s, t);
	int lens = strlen(s), lent = strlen(t);
	if (lent != lens + 1) return puts("No"), 0;
	for (int i = 0; i < lens; i++) if (s[i] != t[i]) return puts("No"), 0;
	puts("Yes");

	return 0;
}		


Measured memory_bytes: 3176
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);

    int n = Integer.parseInt(sc.next());
    long k = Long.parseLong(sc.next());
    long[] a = new long[100010];

    for (int i = 0; i < n; i++) {
      int x = Integer.parseInt(sc.next());
      int y = Integer.parseInt(sc.next());
      a[x] += (long) y;
    }

    long sum = 0;
    for (int i = 1; i < a.length; i++) {

      sum += (long) a[i];
      if (sum >= k) {
        System.out.println(i);
        break;
      }
    }

    sc.close();
  }
}

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

ll func(ll l, ll x, vector<ll>& len, vector<ll>& d) {
	if (l >= x) { 
		ll res = 0;
		return res; 
	}
	if (l == 1) {
		ll res = x - 1LL;
		if (x == len[l]) { return 3LL; }
		return x - 1;
	}

	ll res;
	if (len[l] / 2 > x) {
		res = func(l - 1, x - 1, len, d);
	} else if (len[l] / 2 == x) {
		res = d[l - 1];
	} else if ((len[l] / 2 + 1) == x) {
		res = 1 + d[l - 1];
	} else if (len[l] - l > x) {
		res = func(l - 1, x - len[l] / 2 - 1, len, d) + 1 + d[l - 1];
	} else if (len[l] - l <= x) {
		res = d[l];
	}

	return res;
}

int main() {
	ll N, X;
	cin >> N >> X;
	vector<ll> len(N + 1, 0);
	vector<ll> d(N + 1, 0);
	len[0] = 1;
	d[0] = 1;
	for (int i = 1; i <= N; ++i) {
		len[i] = 2 * len[i - 1] + 3;
		d[i] = 2 * d[i - 1] + 1;
	}

	ll res = func(N, X, len, d);
	cout << res << endl;

	return 0;
}


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

int cn(int n) {
    int z = 0;
    for(int i = 0; i < t.size(); i++) {
        if(t.at(i) == s.at(i + n)) z++;
    }
    return z;
}

int main() {
    cin >> s >> t;
    int a = s.size();
    int b = t.size();
    int c = a - b + 1;
    vector<int> x(c);
    for(int i = 0; i < c; i++) {
        x.at(i) = cn(i);
    }
    sort(x.begin(), x.end());
    int d = x.at(x.size() - 1);
    int ans = b - d;
    cout << ans << endl;
}

Measured memory_bytes: 3636
# coding: utf-8
N,K=map(int,input().split())
A=list(map(int,input().split()))
MOD=10**9+7

ans=1

if K==N:
    for i in range(N):
        ans*=A[i]
        if ans>0:
            ans=ans%MOD
elif max(A)<=0 and K%2==1:
    A.sort(reverse=True)
    for i in range(K):
        ans*=A[i]
        if ans>0:
            ans=ans%MOD
else:
    Ap=[]
    Am=[]
    
    for i in range(N):
        if A[i]>0:
            Ap.append(A[i])
        else:
            Am.append(A[i])
        

    Ap.sort(reverse=True)
    Am.sort()
    
    if K%2==1 and Ap:
        ans*=Ap.pop(0)
    
    P=[]
    
    for i in range(len(Ap)//2):
        P.append(Ap[i*2]*Ap[i*2+1])
    
    for i in range(len(Am)//2):
        P.append(Am[i*2]*Am[i*2+1])
    
    P.sort(reverse=True)
    
    for i in range(K//2):
        ans*=P[i]
        ans=ans%MOD

print(ans%MOD)

Measured memory_bytes: 31720
import sys


def solve(i, m):
    if dp[i][m] > -1:
        return dp[i][m]
    
    if m == 0:
        return 1
    elif i >= n:
        dp[i][m] = 0
    elif solve(i+1, m):
        dp[i][m] = 1
    elif solve(i+1, m-a_list[i]):
        dp[i][m] = 1
    else:
        dp[i][m] = 0
    
    return dp[i][m]


input = sys.stdin.readline
n = int(input())
a_list = list(map(int, input().split()))
q = int(input())
m_list = list(map(int, input().split()))

dp = [[-1]*2000 for i in range(n+1)]

for m in m_list:
    if solve(0, m):
        print('yes')
    else:
        print('no')



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

using namespace std;

int main() 
{
    int n;
    string s;
    cin >> n;
    cin >> s;
    
    int x = 0;
    int max = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'I') {
            x++;
        }   
        else {
            x--;
        }   
        if (x > max) {
            max = x;
        }   
    }   
    cout << max << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>

using namespace std;

int main(){
    int N,M,C,A;
    cin >> N >> M >> C;
    
    int B[M];
    
    for(int i = 0;i<M;i++){
        cin >> B[i];
    }
    long long int total = 0;
    long long int count = 0;
    for(int i = 0;i<N;i++){
        total = 0;
        for(int j = 0;j < M;j++){
            cin >> A;
            total += A*B[j];
        }
        total += C;
        if(total > 0){
            count++;
        }
    }

    cout << count <<"\n";
    return 0;
}


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


int main() {
  ll a,b,c; cin >> a >> b >> c;
  if(a+b+c >= 22) cout << "bust" << endl;
  else cout << "win" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <climits>
#include <set>
#include <map>
#include <iomanip>
#include <cassert>
#include <functional>

using namespace std;

typedef pair<int, int> P;
#define FOR(i, a, b) for(int (i)=a;(i)<(b);++(i))
#define rep(i, n)  FOR(i,0,n)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define all(c) (c).begin(),(c).end()
#define ll long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define vs vector<string>
#define vc vector<char>
#define vvc vector<vector<char>>
#define Print(p) cout<<(p)<<endl
#define _1 first
#define _2 second
#define pb push_back
#define mod 1000000007
#define INF 1050000000

const int maxn = 1e5 + 10;
int a,s[10005];

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

	int n; cin >> n;

	int i = 0;
	int tm = 2;
	while (1) {
		if (tm > n)break;
		tm *= 2;
		i++;
	}
	cout << tm/2 << endl;


	return 0;
}

Measured memory_bytes: 256
mod = 10 ** 9 + 7
#約数の和（自分自身も含む)
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    # divisors.sort()
    return divisors
def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res
N,K = map(int,input().split())
ans = K ** N
divdic = {1:1} 
for i in range(2,K+1):
    A = make_divisors(i)
    A.remove(i)
    X = i
    for j in A:
        X -= divdic[j]
    divdic[i] = X
    Y = K // i
    Z = X * (power_func(Y,N,mod)) % mod
    #print(i,X,Y,Z)
    ans = (ans + Z) % mod
print(ans)

Measured memory_bytes: 85756
k, n = map(int,input().split())
a = list(map(int,input().split()))

da =[-1] * n
da[n-1] = k - a[n-1] + a[0]
for i in range(n-1):
    da[i] = a[i+1] - a[i]
    
print(sum(da)-max(da))

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

// M A F I A - M A F I A - M A F I A - M A F I A - M A F I A - M A F I A //

#define int                                       long long
#define lop(i,s,e)                                for(int i=s;i<(int)e;i++)
#define rlop(i,e,s)                               for(int i=e;i>=s;i--)
#define prvec(v)                                  lop(R15,0,v.size())cout << v[R15] <<" "; cout << endl;
#define prarr(arr,s1,e1)                          lop(R15,s1,e1)cout << arr[R15] << " "; cout << endl;

#define endl                                      '\n'
#define ff                                        first
#define ss                                        second
#define pii                                       pair<int,int>

#define pb                                        push_back
#define all(v)                                    v.begin(),v.end()         

#define bug(...)                                  __f (#__VA_ARGS__, __VA_ARGS__)
#define rtn                                       if(0)return;
template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { rtn cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{     rtn 
     const char* comma = strchr (names + 1, ',');
     cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

// M A F I A - M A F I A - M A F I A - M A F I A - M A F I A - M A F I A //

inline void INP();
const int N = 3e6 + 7, M = 1000000007, inf = INT_MAX;
const long long INF = LLONG_MAX;

int n, Q;
int arr[N+2];


void solve()
{
      int k, n;
      cin >> k >> n;
      lop(i,0,n) cin >> arr[i];
      sort(arr, arr+n);

      int mn = 0;
      lop(i,1,n) mn = max(mn, arr[i] - arr[i-1]);
      mn = max(mn, arr[0]-arr[n-1]+k);

      cout << k - mn << endl;
      
}

int32_t main()
{
      ios_base::sync_with_stdio(0);   cin.tie(0);   cout.tie(0);
    //  INP(); 
      int test = 1;
      // cin >> test;

      // cout << setprecision(9) << fixed;
      // clock_t z = clock();
      while(test--)solve();
      // cerr << "Run Time : " << ((double)(clock() - z) / CLOCKS_PER_SEC);
}











inline void INP()
{
      #ifndef ONLINE_JUDGE
          freopen("input.txt",  "r",  stdin);
          freopen("output.txt", "w", stdout);
      #endif
}


// M A F I A - M A F I A - M A F I A - M A F I A - M A F I A - M A F I A //






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

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

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

    int sum = 0;
    if (N % 10 != 0) {
        cout << findSumDigits(N);
    } else {
        cout << 10;
    }
}

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

int main() {
    lint x;
    cin >> x;

    lint c500 = x/500;
    lint c5 = (x - (c500 * 500)) / 5;

    cout << c500 * 1000 + c5 * 5 << endl;
}

Measured memory_bytes: 256
n = int(input())

a = [[], []]
a[0] = [int(i) for i in input().split()]
a[1] = [int(i) for i in input().split()]

for i in range(n):
  if i == 0:
    a[1][i] += a[0][i]
  if i != 0:
    a[0][i] += a[0][i - 1]
    a[1][i] += max(a[0][i], a[1][i - 1])

print(a[1][n - 1])

Measured memory_bytes: 3064
#include <algorithm>
    #include <bits/stdc++.h>
    #include <cctype>
    #include <cmath>
    #include <cstdio>
    #include <iomanip>
    #include <iostream>
    #include <list>

    #include <stack>
    #include <string>
    #include <vector>
    #include <bits/stdc++.h>
    #define INFINI (1000 * 1000 * 1000)

    using namespace std;
    //#define s(T) scanf("%d", &T)
    #define sl(T) scanf("%lld", &T)
    #define fill(a, val) memset(a, val, sizeof(a))
    #define mp make_pair
    #define pb push_back
    #define all(x) x.begin(), x.end()
    #define DREP(x) sort(all(x)); x.erase(unique(all(x)), x.end())
    #define INDEX(a, val) (lower_bound(all(a), val) - a.begin())

    typedef long long ll;


    bool compare_first(pair<int,int>a,pair<int,int >b)
    {
        return a.first<b.first;
    }

     bool compare_second(pair<int,pair<int , int> > a,pair<int,pair<int , int> > b)
    {
        return a.second.first<b.second.first;
    }


    ll min(ll a,ll b)
    {
        if(a>b)return b;
        return a;
    }
     ll max(ll a,ll b)
    {
        if(a>b)return a;
        return b;
    }

    ll toINT(string s)
    {
        ll a=0;
        for(ll index=0;index<s.size();index++)
            a=a*10+(s[index]-'0');
        return a;
    }



    int main() {
      ios::sync_with_stdio(false);


int w,h,n;
cin>>w>>h>>n;

int xmn=0,ymn=0,xmx=w,ymx=h;
while(n--)
{
    int x,y,a;
    cin>>x>>y>>a;

    if(a==1)
        xmn=max(x,xmn);
    else if(a==2)
        xmx=min(x,xmx);
    else if(a==3)
        ymn=max(y,ymn);
    else if(a==4)
        ymx=min(y,ymx);
}

cout<<max(0, xmx - xmn) * max(0, ymx - ymn)<<endl;
return 0;
    }

/*

 }
 */


Measured memory_bytes: 256
import java.util.*;
 
public class Main {
 	public static void main(String[] args){
    	
    	Scanner sc = new Scanner(System.in);
		String S = sc.next();
		int count =0;
		int max =0;
		
		for(int i= 0; i<S.length(); i++){
		    if(S.charAt(i) == 'A' || S.charAt(i) == 'C'|| S.charAt(i) == 'G' || S.charAt(i) == 'T'){
		        count++;
		        if(max<count){
		            max = count;
		        }
		    }
		    
		    else{
		        count = 0;
		    }
		    
		}
		
		System.out.println(max);
	}
 
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<int(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define show(x) cout<< #x << " = " << x << endl
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

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

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}	

const ll mod=998244353;
const int INF=INT_MAX/2;
const int N_MAX=100010;
const double PI=3.14159265359;

//xのy乗%mod（繰り返し二乗法)
ll powll(ll x, ll y){
	ll res=1LL;
	while(y){
		if(y&1LL){
			res*=x;
		}
		res%=mod;
		x=(x*x)%mod;
		y>>=1LL;
	}
	return res;
}

int main(){
	int n;
	cin>>n;
	ll d[n];
	REP(i,n)cin>>d[i];
	ll ans = 1;
	vector<ll> num = vector<ll>(n,0);
	REP(i,n){
		num[d[i]]++;
	}
	if(d[0]!=0){
		cout<<0<<endl;
		return 0;
	}
	if(num[0]!=1){
		cout<<0<<endl;
		return 0;
	}
	for(int i=1;i<n-1;i++){
		if(num[i]==0 && num[i+1]>0){
			cout<<0<<endl;
			return 0;
		}
	}
	for(int i=1;i<n;i++){
		if(num[i]==0)break;
		ans *= powll(num[i-1],num[i]);
		ans %= mod;
	}
	cout<<ans<<endl;
	return 0;
}


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

#include <set>
#include <iterator>
using namespace std;
using namespace __gnu_pbds;


#define ft first
#define sd second
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()

#define ll long long int
#define vi vector<int>
#define vii vector<pair<int,int> >
#define pii pair<int,int>
#define plii pair<pair<ll, int>, int>
#define piii pair<pii, int>
#define viii vector<pair<pii, int> >
#define vl vector<ll>
#define vll vector<pair<ll,ll> >
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define mp make_pair
#define ms(x, v) memset(x, v, sizeof x)
#define pr_vec(v) for(int i=0;i<v.size();i++) cout << v[i] << " " ;

#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)

#define INF INT_MAX

#define fr(i, a, b) for(i=a; i<=b; i++)
#define fb(i, a, b) for(i=a; i>=b; i--)
#define ASST(x, l, r) assert( x <= r && x >= l )

typedef tree<pll, null_type, less<pll>, rb_tree_tag,
             tree_order_statistics_node_update>
    new_data_set;
const int N=1e5+10, M=(ll)1e6+10 ;
const int mod = 998244353  ;

// vl compute(string s){
//         vl has(s.length());
//         ll i;

//         for(i=0;i<s.length();i++){
//             if(i==0){
//                 has[i]=((s[i]-'a'+1))%mod;
//             }
//             else
//                 has[i]=(has[i-1]*p + (s[i]-'a'+1))%mod;
//         }
//         return has;
// }
vl a(N),b(N),col(N,0),vis(N,0);
ll n,m;
vll g[N];

int main(){
 ios_base::sync_with_stdio(0);
  ll i,n,k;
  cin >> n >> k;
  double ans,temp;
  ans=temp=0.0;
  ll cur;
  for(i=1;i<=n;i++){
    cur=i;
    temp=1.0/n;
    while(cur<k){
        temp/=2;
        cur*=2;
    }
    ans+=temp;
  }
  // cout << ans;
  printf("%.12f\n",ans);
 return 0;
}

Measured memory_bytes: 5760
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        String p = br.readLine();

        String ss = s + s;

        if (ss.contains(p)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 24420
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
    int n,x,y;
    cin>>n>>x>>y;
    int b[n+1];
    rep(i,n)cin>>b[i];
    b[n]=n+1;
    vector<ll> dp(n+2,longinf);
    dp[0]=0;
    rep(i,n+1){
        ll sum=0;
        for(int j = i-1;j>=0;--j){
            if(b[j]>b[i])sum+=x;
            if(b[j]<b[i]){
                dp[i+1]=min(dp[i+1],dp[j+1]+sum);
                sum+=y;
            }
        }
        dp[i+1]=min(dp[i+1],sum);
    }
    cout<<dp[n+1]<<endl;
    return 0;
}

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

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

	long long N;
	int result = 0;
	scanf("%lld", &N);
	for (int i = 2; i <= N && i < 1000000; i++)
	{
		int count = 0;
		while (true)
		{
			if (N % i == 0)
			{
				count++;
				N = N / i;
			}
			else
			{
				break;
			}
		}
		// cout << "i=" << i << " count=" << count;
		for (int j = 1; true; j++)
		{
			if (count >= j)
			{
				count -= j;
				result++;
			}
			else
			{
				break;
			}
		}
		// cout << " result=" << result << "\n";
	}

	// cout << "N=" << N << "\n";
	if (N != 1)
	{
		result++;
	}
	cout << result;
	return 0;
}

Measured memory_bytes: 3692
#include<bits/stdc++.h>
using namespace std;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef vector<long long> vlong;
typedef vector<string> vstring;
#define vpush(a,x) a.push_back(x);
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)
const int INF = 1 << 30;
const int dx[] = {1,0,-1,0,1,1,-1,-1};
const int dy[] = {0,-1,0,1,1,-1,-1,1};
#define stp(x)  setprecision(x)
int a[10000001];
int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int k;
  cin>>k;
  a[1]=7%k;
  for(int i=2;i<=k;i++) a[i]=(a[i-1]*10+7)%k;

  for(int i=1;i<=k;i++){
    if(a[i]==0){
      cout<<i;
      return(0);
    }
  }
  cout<<-1<<'\n';
  return(0);
}


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

using namespace std;

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

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

    vector<long long> l_max(3 * n, 0);
    multiset<long long> l_set;
    long long l_sum = 0;
    for (int i = 0; i < n; i++) {
        l_sum += a[i];
        l_set.insert(a[i]);
        l_max[i] = l_sum;
    }
    for (int i = n; i <= 2 * n; i++) {
        multiset<long long>::iterator ite = l_set.begin();
        if (a[i] > *ite) {
            l_sum += a[i] - *ite;
            l_set.insert(a[i]);
            l_set.erase(ite);
        }

        l_max[i] = l_sum;
    }

    vector<long long> r_min(3 * n, 0);
    multiset<long long> r_set;
    long long r_sum = 0;
    for (int i = 3 * n - 1; i >= 2 * n; i--) {
        r_sum += a[i];
        r_set.insert(a[i]);
        r_min[i] = r_sum;
    }
    for (int i = 2 * n - 1; i >= n - 1; i--) {
        multiset<long long>::reverse_iterator ite = r_set.rbegin();
        if (a[i] < *ite) {
            r_sum += a[i] - *ite;
            r_set.insert(a[i]);
            r_set.erase(r_set.find(*ite));
        }

        r_min[i] = r_sum;
    }

    long long res = l_max[n - 1] - r_min[n];
    for (int i = n; i < 2 * n; i++) {
        res = max(res, l_max[i] - r_min[i + 1]);
    }

    cout << res << endl;
}


Measured memory_bytes: 16640
#include<bits/stdc++.h>
using namespace std;
int n,m;
char S[100005],T[100005];
int main(){
	scanf("%d%d",&n,&m);
	scanf("%s%s",S+1,T+1);
	int G=__gcd(n,m);
	for(int k=1,i=1,j=1;k<=G;++k,i+=n/G,j+=m/G)
		if(S[i]!=T[j]) return puts("-1"),0;
	printf("%lld",(long long)n*m/G);
	return 0;
}

Measured memory_bytes: 384
def get_i() #空白区切の入力を数値(整数)の配列で返す
  return gets.chomp.split(" ").map(&:to_i)
end
def get_f() #空白区切の入力を数値(実数)の配列で返す
  return gets.chomp.split(" ").map(&:to_f)
end
def get() #空白区切の入力を文字列の配列で返す
  return gets.chomp.split(" ")
end
def get_nsp() #入力されたものを一文字ずつに区切った文字列の配列で返す
  return gets.chomp.split("")
end
def yn_judge(bool,y="Yes",n="No") #boolに真偽を投げることで、trueならy、falseならnの値を出力する
  return bool ? y : n 
end
def array(size1,init=nil,size2=1) #size2に二次元配列時の最初の要素数、size1に次の配列の大きさ、initに初期値を投げることでその配列を返す
  if size2==1
    return Array.new(size1){init}
  else
    return Array.new(size2){Array.new(size1){init}}
  end
end

N=gets.to_i
puts N**3

Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please


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


	int N, M;
	cin >> N >> M;
	int S[2000], T[2000];
	rep(i, N) cin >> S[i];
	rep(i, M) cin >> T[i];

	ll mod = 1e9 + 7;
	ll dp[2001];
	ll dp2[2001] = {};

	rep(i, M + 1) dp[i] = 1;
	rep1(i, N) {
		rep1(j, M) {
			if (S[i - 1] == T[j - 1]) {
				dp2[j] = dp[j];
				dp[j] = dp[j - 1] + dp[j];
			}
			else {
				dp[j] = dp[j - 1] + dp2[j];
			}
			dp[j] %= mod;
		}
	}
	co(dp[M] % mod);

	Would you please return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)n; i++)
#define all(x) (x).begin(),(x).end()
typedef long long int ll;
using namespace std;
int main()
{
  int N, M, X, Y;
  cin >> N>>M>> X>> Y;
  int maxx, minx;
  int maxy, miny;
  maxx = maxy =-1000;
  minx = miny =1000;
  int tmpx, tmpy;
  REP(i, N){
    cin >> tmpx;
    maxx = max(maxx, tmpx);
  }
  REP(i, M){
    cin >> tmpy;
    miny = min(miny, tmpy);
  }
  // cout << minx << " " << maxx <<endl;
  // cout << miny << " " << maxy <<endl;
    
  if(max(maxx,X)<min(miny, Y)){
    cout << "No War" << endl;
  }else{
    cout << "War" << endl;
  }
}


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

int main() {
  int N;
  cin >> N;
  
  int s;
  s = 0;
  
  int a;
  
  for(int i = 1; i < N + 1; i++) {
  	cin >> a;
    if(i % 2 == 1 && a % 2 == 1) {
    	s++;
    }
  }
  
  cout << s << endl;
 
}

Measured memory_bytes: 3588
import sys
sys.setrecursionlimit(100000)

def intinput(): return map(int,sys.stdin.readline().split())

n,l=intinput()
li=[l+i for i in range(n)]
k=sum(li)
ans=float("inf")
for i in range(len(li)):
    v=sum(li[:i]+li[i+1:])
    if abs(ans-k) > abs(v-k):
        ans=v
print(ans)

Measured memory_bytes: 38384
N,L = map(int, input().split())
A = [int(a) for a in input().split()]

l = 0
r = N-1
s = sum(A)
ans = []
while l < r:
    if s < L:
        break
    if r-l > 1:
        if A[l]+A[l+1] < L:
            s -= A[l]
            ans.append(l+1)
            l += 1
            continue
        if A[r]+A[r-1] < L:
            s -= A[r]
            ans.append(r)
            r -= 1
            continue
    if A[l] < A[r]:
        ans.append(l+1)
        s -= A[l]
        l += 1
    else:
        ans.append(r)
        s -= A[r]
        r -= 1
        
if len(ans) == N-1:
    print("Possible")
    for a in ans:
        print(a)
else:
    print("Impossible")

Measured memory_bytes: 14596
#pragma GCC optimize("Ofast")
#pragma comment(linker, "/stack:200000000")
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <cmath>
#include <set>
#include <iomanip>
#include <ctime>
#include <cstring>
#include <map>

using namespace std;

const int N = 5100;
const int MOD = 1e9 + 7;

vector <int> now;
set <vector<int>> vis;

void cur(vector <int> stuff) {
	if (stuff.empty()) {
		reverse(now.begin(), now.end());
		for (auto x : now) {
			cout << x << "\n";
		}
		exit(0);
	}
	if (vis.count(stuff)) {
		return;
	}
	vis.insert(stuff);
	vector <int> check = stuff;
	sort(check.begin(), check.end());
	for (int i = 0; i < check.size(); ++i) {
		if (check[i] > i + 1) {
			return;
		}
	}
	for (int i = 0; i < stuff.size(); ++i) {
		if (stuff[i] > i + 1) {
			return;
		}
	}
	for (int i = stuff.size() - 1; i >= 0; --i) {
		if (stuff[i] == i + 1) {
			vector <int> stuff2 = stuff;
			stuff2.erase(stuff2.begin() + i);
			now.push_back(i + 1);
			cur(stuff2);
			now.pop_back();
		}
	}
}

int main() {
	::ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	vector <int> v(n);
	for (int i = 0; i < n; ++i) {
		cin >> v[i];
	}
	cur(v);
	cout << -1 << endl;
	return 0;
}

Measured memory_bytes: 384
N, K = gets.split.map(&:to_i)
P = gets.split.map(&:to_i)

IP = [nil]*N
N.times{|i|
	IP[P[i]] = i
}

UP = [1]*N
(N-2).downto(0){|i|
	UP[i] += UP[i+1] if P[i] < P[i+1]
}

def NextIndex(_N, _IP)
	li = (-1..(_N-2)).to_a + [-1,-1]
	ri = (1.._N).to_a + [_N,_N]
	_IP.each{|i|
		l, r = li[i], ri[i]
		li[r], ri[l] = l, r
	}
	li.pop(2)
	ri.pop(2)
	return li, ri
end

LU,_ = NextIndex(N, IP)
_,RL = NextIndex(N, IP.reverse)

pm, n = K <= UP[0] ? [1,0] : [0,1]
(N-K).times{|i|
	if K <= UP[i+1]
		pm += 1
	elsif RL[i] < i+K or i < LU[i+K]
		n += 1
	end
}

p n+[pm,1].min


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

stack<int> s;

int calc(string op){
    int a, b;
    b = s.top();
    s.pop();
    a = s.top();
    s.pop();
    if(op == "+"){
        return a+b;
    }else if(op == "-"){
        return a-b;
    }else if(op == "*"){
        return a*b;
    }
}

int main(void){
    string str;
    
    while(cin >> str){
        if(str == "+" || str == "-" || str == "*"){
            s.push(calc(str));
        }else{
            s.push(stoi(str));
        }
    }
    if(getchar()=='\n'){
      cout << s.top() << endl;
      return 0;
    }
    cout << s.top() << endl;
}


Measured memory_bytes: 3152
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/integer/common_factor.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>

using std::string;
using std::vector;
using std::set;
using std::multiset;
using std::unordered_set;
using std::map;
using std::multimap;
using std::unordered_map;
using std::pair;
using std::cin;
using std::cout;

using boost::multiprecision::cpp_int;
using cpp_dec_float_1000 = boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1000>>;

typedef uintmax_t    ull;
typedef intmax_t     ll;
typedef uint64_t     ul;
typedef uint32_t     ui;
typedef uint8_t      uc;

constexpr char CRLF  = '\n';
constexpr char SPACE = ' ';
constexpr char VECTOR_COUT_SEPARATOR = SPACE;
constexpr ll INF = 1000'000'007;
constexpr int MOD = 1000'000'007;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> std::ostream& operator<< (std::ostream& os, const std::vector<T>& vc) { for(auto it = vc.begin(); it != vc.end(); ++it) { if (std::next(it) == vc.end()) os << *it; else os << *it << VECTOR_COUT_SEPARATOR; } return os; }
template<class T1, class T2> inline std::ostream & operator<< (std::ostream & os, const std::pair<T1, T2> & p) { return os << p.first << ' ' << p.second; }
template<class T> T modinv(T a, T m) { T b = m, u = 1, v = 0; while (b) { T t = a / b; a -= t * b; boost::swap(a, b); u -= t * v; boost::swap(u, v); } u %= m; if (u < 0) u += m; return u; }

struct Tmp
{
public:
  Tmp(int N);
};

Tmp::Tmp(int N){}

void solve(void)
{
  int N; cin >> N;
  vector<string> A(N);
  vector<int> B(N);
  map<string, int> m{};
  for (auto& a : A) {
    cin >> a;
    ++m[a];
  }
  for (int i = 0; i < N; ++i) {
    B[i] = m[A[i]];
  }
  auto cnt = *boost::max_element(B);
  set<string> res{};
  for (int i = 0; i < N; ++i) {
    if (B[i] == cnt) {
      // res.emplace(A[i]);
      res.insert(A[i]);
    }
  }
  vector<string> ans(res.begin(), res.end());
  boost::for_each(ans, [](const auto& s){
    cout << s << CRLF;
  });
  return;
}

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

  solve();

  return 0;
}


Measured memory_bytes: 37120
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int n;
  cin>> n;
  long long mina,maxa;
  cin >> mina;
  maxa=(-1)*mina;
  for(int i=1;i<n;i++){
    long long a;
    cin >>a ;
    maxa=max(maxa,a-mina);
    mina=min(mina,a);
  }
    
  cout<<maxa<<endl;
  return 0;
}
      


Measured memory_bytes: 3092
#include<stdio.h>

int main(){

    int N=0;
    float kaku=0;
    scanf("%d",&N);
    if(N%2==1){
        kaku=N/2+1;
    }else{
        kaku=N/2;
    }
    kaku=kaku/N;
    printf("%f\n",kaku);

    return 0;
}

Measured memory_bytes: 128
from sys import stdin

def main():

    input = stdin.readline

    A,B = map(int,input().split())

    for i in range(1,1001):
        if(int(i * 0.08) == A) and (int(i * 0.1) == B):
            print(i)
            return
    else:
        print("-1")

if __name__ == "__main__":
    main()

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define mod 1000000007
#define mod998 998244353
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define mkp make_pair
typedef long long ll;
using namespace std;

ll L, R, res, pow3[60];

int main() {
	cin >> L >> R;
	pow3[0] = 1;
	for (int i = 1; i < 60; ++i) {
		pow3[i] = pow3[i - 1] * 3 % mod;
	}
	for (ll i = 0; i < 60; ++i) {
		if (L <= (1ll << i + 1) - 1 && (1ll << i) <= R) {
			ll l = max(L, (1ll << i));
			ll r = min(R, (1ll << i + 1) - 1);
			ll dp[3];
			dp[0] = dp[2] = 0;
			dp[1] = 1;
			for (ll j = i - 1; j >= 0; --j) {
				if (r&(1ll << j)) {
					if (l&(1ll << j)) {
						res += dp[0] * pow3[j];
						dp[0] *= 2;
						dp[0] %= mod;
					}
					else {
						res += dp[0] * pow3[j];
						res += dp[2] * pow3[j];
						dp[0] *= 2;
						dp[2] *= 2;
						dp[0] += dp[1];
						dp[2] += dp[1];
						dp[0] %= mod;
						dp[2] %= mod;
					}
				}
				else {
					if (l&(1ll << j)) {
						dp[1] = 0;
					}
					else {
						res += dp[2] * pow3[j];
						dp[2] *= 2;
						dp[2] %= mod;
					}
				}
				res %= mod;
			}
			res += dp[0] + dp[1] + dp[2];
		}
	}
	cout << res % mod << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int dp[200005];
vector<int> G[200005];
int n;
int a[200005];
int ans[200005];
const int inf = 0x3f3f3f3f;
void dfs(int u,int p){
	int ind = (int)(lower_bound(dp,dp+n,a[u]) - dp);
	int cnt = dp[ind];
	dp[ind] = a[u];
	ans[u] = (int)(lower_bound(dp,dp+n,inf) - dp);
	for(int i:G[u]){
		if(i!=p){
			dfs(i,u);
		}
	}
	//undo
	dp[ind] = cnt;
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	for(int i=0;i<n-1;i++){
		int t1,t2;
		cin>>t1>>t2;
		t1--,t2--;
		G[t1].push_back(t2);
		G[t2].push_back(t1);
	}
	fill(dp,dp+n+2,inf);
	dfs(0,-1);
	for(int i=0;i<n;i++) cout<<ans[i]<<endl;
	return 0;
}

Measured memory_bytes: 31160
using System;

namespace A___ι_l
{
    class Program
    {
        static void Main(string[] args)
        {
            var a_b_c = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int a = a_b_c[0], b = a_b_c[1], c = a_b_c[2];

            Console.WriteLine(c - b == b - a ? "YES" : "NO");
        }
    }
}


Measured memory_bytes: 11092
import sys
input = sys.stdin.readline
from heapq import heappush, heappop


n, m = map(int, input().split())

m_list = [[] for _ in range(m+1)]

for _ in range(n):
    a, b = map(int, input().split())

    if a <= m:
        m_list[a].append(b)


all_r = 0
hq = []

for i in range(1, m+1):
    for v in m_list[i]:
        heappush(hq, -1*v)

    if len(hq) != 0:
        max_v = -1 * heappop(hq)
        all_r += max_v

print(all_r)

Measured memory_bytes: 18376
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <vector>
using namespace std;
int main(){
  cin.tie(NULL);
  ios::sync_with_stdio(false);
  string s;
  cin>>s;
  cout<<"2018/01/"<<s[8]<<s[9]<<"\n";
  return 0;
}

Measured memory_bytes: 3620
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        new Main().start();
    }

    void start() throws Exception {
        start(new Scanner(System.in));
    }

    void start(Scanner sc) throws Exception{
        int n = sc.nextInt();
        int k = sc.nextInt();
        int v = 1;
        for (int i = 0; i < n; ++i) {
            int a = v * 2;
            int b = v + k;

            if (a < b) {v = a;} else {v = b;}
        }
        System.out.println(v);
    }
}


Measured memory_bytes: 22356
n,k = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
b,m,num,mod = sorted(a),0,0,10**9+7
for i in range(1,n):
    if b[i]==b[i-1]: num+=m
    else: num,m = num+i,i
d,ans = [0]*2001,0
def add(i,x):
	while i<=2000:
		d[i] += x
		i += i & -i
def get(i):
	s = 0
	while i:
		s += d[i]
		i -= i & -i
	return s
for i in range(n):
    add(a[i],1)
    ans = (ans-get(a[i])+i+1)%mod
print((ans*k+num*k*(k-1)//2)%mod)

Measured memory_bytes: 3188
a,b,c,x,y = map(int,input().split())
ab = a*x+b*y
if x==y:
  conly = c*x*2
  print(min(ab,conly))
elif x>y:
  conly = c*x*2
  ac = c*y*2+(x-y)*a
  print(min(ab,conly,ac))
else:
  conly = c*y*2
  bc = c*x*2+(y-x)*b
  print(min(ab,conly,bc))

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using E = pair<int, int>;
const ll inf = numeric_limits<ll>::max()/3;
const ll mod = 1e9 + 7;

int main(void){
  int n;
  vector< P > balls;
  cin >> n;
  for(int i = 0;i < n;++i){
    ll x,y;
    cin >> x >> y;
    balls.push_back(P(x,y));
  }
  if(n == 1){
    cout << 1 << endl;
    return 0;
  }
  sort(balls.begin(),balls.end());
  int res = n;
  for(int i = 0;i < n;++i){
    for(int j = i+1;j < n;++j){
      ll p = balls[j].first - balls[i].first;
      ll q = balls[j].second - balls[i].second;
      int calc = n;
      for(int a = 0;a < n-1;++a){
        for(int b = a+1;b < n;++b){
          if(balls[a].first + p == balls[b].first &&
             balls[a].second + q == balls[b].second){
            --calc;
            break;
          }
        }
      }
      res = min(res,calc);
    }
  }
  cout << res << endl;
  return 0;
}


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

int main() {
  string s;
  cin>>s;
  int n=s.size();
  bool ans=true;
  for (int i=0;i<n;i++) {
    if (i%2==0) {
      if (s.at(i)=='L') {
        ans=false;
      }
    }
    else {
      if (s.at(i)=='R') {
        ans=false;
      }
    }
  }
  if (ans) {
    cout<<"Yes"<<endl;
  }
  else {
    cout<<"No"<<endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define M 1000000007
int s[13] , h[13] , c[13] , d[13];
int main(){

    int n;
    scanf("%d" , &n);
    int ms = 52 - n;
    int t = n;
    char f;
    int x;
    while(t--){
        cin >> f >> x;
        if(f == 'S') s[--x]++;
        else if(f == 'H') h[--x]++;
        else if(f == 'C') c[--x]++;
        else if(f == 'D') d[--x]++;
    }

    for(int i = 0 ; i < 13 ; i++ )
        if(s[i] == 0) cout << 'S' << ' ' << i+1 << endl;
    for(int i = 0 ; i < 13 ; i++ )
        if(h[i] == 0) cout << 'H' << ' ' << i+1 << endl;
    for(int i = 0 ; i < 13 ; i++ )
        if(c[i] == 0) cout << 'C' << ' ' << i+1 << endl;
    for(int i = 0 ; i < 13 ; i++ )
        if(d[i] == 0) cout << 'D' << ' ' << i+1 << endl;

    //for(int i = 0 ;i < 13 ;i++) cout << s[i] << ' ';
    return 0;
}
/// s h c d




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

int T;
typedef long long ll;
ll N;

ll p3[50], h[50];
ll MAX = (1LL<<50);

int main()
{
    p3[0] = 1;
    h[0] = 1;
    int mxh;
    for(int i = 1; ; i++)
    {
        p3[i] = p3[i-1]*3;
        h[i] = h[i-1]+p3[i-1]+p3[i];
        if( p3[i] > MAX )
        {
            mxh = i;
            break;
        }
    }

    T=1;
    while(T--)
    {
        cin>>N;
        if(N==0)
        {
            cout<<0<<'\n';
            continue;
        }
        N++;
        ll ans = 0;
        int H = 0;
        while( h[H+1] <= N )H++;
        N-=h[H];
        ans+=H*2+1;
        //cout<<ans<<'\n';
        for( int i = H; i>=0; i-- )
        {
            if( N >= p3[i] )
            {
                ans+=N/p3[i];
                N%=p3[i];
            }
            //cout<<N<<' '<<ans<<'\n';
        }
        cout<<ans-1<<'\n';
    }

    return 0;
}



Measured memory_bytes: 3124
import itertools
N=int(input())
P=list(map(int,input().split()))
Q=list(map(int,input().split()))
p=P.copy()
p.sort()
p=itertools.permutations(p)
j=0
for i in p:
    j+=1
    if list(i)==P:
        pcount=j
    if list(i)==Q:
        qcount=j
print(abs(pcount-qcount))

Measured memory_bytes: 9080
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pb push_back
#define fori(a,b) for(int i=a;i<b;i++)
#define forj(a,b) for(int j=a;j<b;j++)
#define ford(b,a) for(int i=b;i>=a;i--)
typedef pair<int, int> pi;
#define PI 3.14159265359
#define vi vector<int>
long long mod=1000000007;
//int count=INT_MAX;
 
struct hash_pair { 
    template <class T1, class T2> 
    size_t operator()(const pair<T1, T2>& p) const
    { 
        auto hash1 = hash<T1>{}(p.first); 
        auto hash2 = hash<T2>{}(p.second); 
        return hash1 ^ hash2; 
    } 
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int testcases=1;
    //cin>>testcases;
    //cout<<t;
    //scanf("%d",&t);
    int t=testcases;
    while(testcases--){  
        string s;
        cin>>s;
        int c=0;
        int ans=0;
        fori(0,3){
            if(s[i]=='R'){
                c++;
            }
            else{
                ans=max(ans,c);
                c=0;
            }
        }
        ans=max(ans,c);
        cout<<ans<<endl;
    }               

    
    return 0;
}

Measured memory_bytes: 3636
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<list>
#include<set>
#include<map>
#include<utility>


#define rep(i,x) for(int i=0;i<(int)(x);i++)
#define reps(i,x) for(int i=1;i<=(int)(x);i++)
#define rrep(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define rreps(i,x) for(int i=((int)(x));i>0;i--)

#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define INF 2e9

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; }
typedef long long ll;
int gcd(int a,int b){return b?gcd(b,a%b):a;}

using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    rep(i, n){
        ll tmp;
        cin >> tmp;
    }
    ll ans = 1;
    ll flag = k;
    while(flag < n){
        flag += (k-1);
        ans++;
    }
    cout << ans;
}

Measured memory_bytes: 256
#include<cstdio>
#include<map>
using namespace std;

const int MAX_N = 1e5;
int n, m;
int a[MAX_N];
map<int, int> sum;

int main() {
    scanf("%d %d", &n, &m);
    scanf("%d", &a[0]);
    a[0] %= m;
    sum[a[0]] = 1;
    for (int i = 1; i < n; i++) {
        int x;
        scanf("%d", &x);
        a[i] = (static_cast<long>(a[i - 1]) + x) % m;
        sum[a[i]] += 1;
    }
    
    long ans = 0;
    for (auto &i : sum) {
        ans += static_cast<long>(i.second) * (i.second - 1) / 2;
    }
    ans += sum[0];

    printf("%ld\n", ans);
    return 0;
}


Measured memory_bytes: 3584