akhauriyash/Code-Regression huggingface dataset:
N = int(input())
*A, = map(int, input().split())
dp = [[-1]*(N+1-i) for i in range(N+1)]
for i in range(N+1):
    dp[0][i] = 0
t = (N & 1)
for l in range(1, N+1):
    S = dp[l-1]; T = dp[l]
    t ^= 1
    if t:
        T[:] = (min(S[i+1] - A[i], S[i] - A[i+l-1]) for i in range(N-l+1))
    else:
        T[:] = (max(S[i+1] + A[i], S[i] + A[i+l-1]) for i in range(N-l+1))
print(dp[N][0])

Measured memory_bytes: 85852
n = int(input())
W = list(map(int,input().split()))
x = sum(W) / 2
a = 0
for i in range(n):
    if (x-a)*2 > W[i]:
        a += W[i]
        continue
    else:
        break
ans = int(abs(x-a) * 2)
print(ans)

Measured memory_bytes: 3188
import java.util.*;
import java.util.stream.*;

public class Main {

  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int A = in.nextInt(), B = in.nextInt();
    System.out.println(Math.max(Math.max(A + B, A - B), A * B));
  }
}


Measured memory_bytes: 21588
n = int(input())
ab = [list(map(int,input().split())) for _ in range(n)]

ab.sort(key=lambda x: x[1])
t = 0
flag = True
for i in range(n):
    t += ab[i][0]
    if t > ab[i][1]:
        flag = False
    #print(t,ab[i][1])
if flag:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 88280
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
typedef long long ll;

int main(){
  ll N, T; cin >> N >> T;
  ll A[N];
  FOR(i,0,N) cin >> A[i];
  ll mn = 10000000000, mx = 0;
  ll mni = 0, mxi = 0;
  ll sa = 0, tmp = 0;
  ll r, l;
  ll ans = 1;
  FOR(i,0,N){
    if(mn > A[i]){
      mn = A[i];
      mni = i;
      mx = 0;
    }
    else if(mx <= A[i]){
      mx = A[i];
      mxi = i;
      tmp = A[mxi] - A[mni];
      if(tmp > sa){
        sa = tmp;
        r = mxi;
        l = mni;
        ans = 1;
      }
      else if(tmp == sa) ans++;
    }

  }
  int mx_cnt = 0, mn_cnt = 0;
  for(int i = N - 1; i >= 0; i--){
    if(A[i] == A[r] && i > l) mx_cnt++;
    if(A[i] == A[l] && i < r) mn_cnt++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
def c_switches(N, M, Switches, P):
    import numpy as np

    def rank_matrix(matrix):
        """mod2 上で行列の階数を求める"""
        num_row, num_col = matrix.shape[0], matrix.shape[1]
        rank = 0

        for col in range(num_col):
            # ピボット探し
            pivot = -1
            max_element = 0  # 最大の要素(1しかないが)がある場所を探す
            for row in range(rank, num_row):
                if matrix[row][col] > max_element:
                    max_element = matrix[row][col]
                    pivot = row
            if pivot == -1:
                continue  # ピボットが見つからない。次の列へ

            tmp = matrix[pivot, :].copy()
            matrix[pivot, :] = matrix[rank, :]
            matrix[rank, :] = tmp

            # (行列の要素は0または1しかないので、ピボットの値を1にする操作は不要)
            # ピボットのある列の値がすべて0となるように、掃き出しを行う
            for row in range(num_row):
                if row != rank and matrix[row][col] == 1:
                    for col2 in range(num_col):
                        matrix[row][col2] = (matrix[row][col2] - matrix[rank][col2]) % 2
            rank += 1
        return rank

    # 電球iがスイッチjとつながっているとき a_{ij}=1, そうでないなら0とする
    a = np.zeros((M, N), dtype='int8')
    for t, (_, *switches) in enumerate(Switches):
        for s in switches:
            a[t][s - 1] = 1
    p = np.reshape(P, (-1, 1))
    ap = np.concatenate((a, p), axis=1)  # 拡大係数行列
    rank_a, rank_ap = rank_matrix(a), rank_matrix(ap)
    return 2**(N - rank_a) if rank_a == rank_ap else 0
    # 参考: http://drken1215.hatenablog.com/entry/2019/03/20/202800

N, M = [int(i) for i in input().split()]
Switches = [[int(i) for i in input().split()] for j in range(M)]
P = [int(i) for i in input().split()]
print(c_switches(N, M, Switches, P))

Measured memory_bytes: 12260
import java.util.List;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

	public static void main(String[] args) {
		
		Scanner scn=new Scanner(System.in);
		int nodeCount=scn.nextInt(),linkCount=scn.nextInt();
		
		List<Node> nodes=new ArrayList<>(nodeCount);
		for(int i=0;i<nodeCount;i++)
			nodes.add(new Node(i));
		Node home=nodes.get(0);
		home.mark=home;
		
		for(int i=0;i<linkCount;i++) {
			Node n1=nodes.get(scn.nextInt()-1),n2=nodes.get(scn.nextInt()-1);
			n1.links.add(n2);
			n2.links.add(n1);
		}
		
		List<Node> explore=new ArrayList<>(),exploreNext=new ArrayList<>();
		explore.add(home);
		while(!explore.isEmpty()){
			for(Node from:explore) {
				for(Node to:from.links) {
					if(to.mark==null) {
						to.mark=from;
						exploreNext.add(to);
					}
				}
			}
			explore.clear();
			List<Node> swap=explore;
			explore=exploreNext;
			exploreNext=swap;
		}
		
		System.out.println("Yes");
		for(int i=1;i<nodeCount;i++)
			System.out.println(nodes.get(i).mark.id+1);
		
	}
	
	private static class Node{
		Node(int id){
			this.id=id;
		}
		final int id;
		final Set<Node> links=new HashSet<>();
		Node mark=null;
	}

}


Measured memory_bytes: 96012
/*================= *\
|  ID : aman__guta__ |
|      LANG: C++     |
\*==================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double 
#define pb push_back
#define mk make_pair
#define fs first
#define sc second 
#define mod 1000000007
#define sp <<" "<<
#define JOKER ios_base::sync_with_stdio (false) ; cin.tie(0) ; cout.tie(0) ;
int spf[10000001];
long long int fac[200005]; 
void sieve(int n)
{
    spf[1]=1;
    for(int i=2;i<=n;i++) spf[i]=i;
    for(int i=4;i<=n;i+=2) spf[i]=2;
    for(int i=3;i*i<=n;i++)
    {
        if(spf[i]==i)
        {
            for(int j=i*i;j<=n;j+=i)
            {
                if(spf[j]==j) spf[j]=i;
            }
        }
    }
}
long long int power(long long int x, long long int y, long long int p) 
{ 
    long long int res = 1;
    x = x % p;
    while (y > 0) 
    { 
        if (y & 1) 
            res = (res*x) % p; 
        y = y>>1;
        x = (x*x) % p; 
    } 
    return res; 
}
long long int modInverse(long long int n, long long int p) 
{ 
    return power(n, p-2, p); 
} 
long long int nCrModPFermat(long long int n, long long int r, long long int p) 
{ 
   if (r==0) 
      return 1; 
    return (fac[n]* modInverse(fac[r], p) % p * 
            modInverse(fac[n-r], p) % p) % p; 
}
int lps(string s)
{
    int n=s.size();
    int lps[n];
    lps[0]=0;
    int i=1;
    int j=0;
    while(i<n)
    {
        if(s[i]==s[j])
        {
            j++;
            lps[i]=j;
            i++;
        }
        else 
        {
            if(j)
            {
                j=lps[j-1];
            }
            else 
            {
                lps[i]=0;
                i++;
            }

        }
    }
    return min(n/2,lps[n-1]);
}
int arr1[100005],arr2[100005],arr3[400005];
main()  
{
    JOKER
    int x,y,a,b,c;
    cin>>x>>y>>a>>b>>c;
    for(int i=0; i<a; i++)
    {
        cin>>arr1[i];
    }
    for(int i=0; i<b; i++)
    {
        cin>>arr2[i];
    }
    for(int i=0; i<c; i++)
    {
        cin>>arr3[i];
    }
    sort(arr1,arr1+100005);
    sort(arr2,arr2+100005);
    sort(arr3,arr3+400005);
    int idx1=100004,idx2=100004,idx3=400004;
    ll ans=0;
    while(x--)
    {
        if(arr1[idx1]>arr3[idx3])
        {
            ans+=arr1[idx1];
            idx1--;
        }
        else
        {
            ans+=arr3[idx3];
            idx3--;
        }
    }
    for(int i=idx3+1; i<400005; i++)
    {
        arr3[i]=arr1[idx1--];
    }
    sort(arr3,arr3+400005);
    idx3=400004;
    while(y--)
    {
        if(arr2[idx2]>arr3[idx3])
        {
            ans+=arr2[idx2];
            idx2--;
        }
        else 
        {
            ans+=arr3[idx3];
            idx3--;
        }
    }
    cout<<ans<<endl;
    cerr<<"Time elapsed : "<<clock()*1000.0/CLOCKS_PER_SEC<<"ms"<<'\n'; 
    return 0;
} 



Measured memory_bytes: 4352
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

int prime[1000010];
int dp[1000010];

int main() {
  fill(prime, prime+1000010, 1);

  for (int i = 2; i <= sqrt(1000000)+1; i++) {
    if (prime[i]) {
      for (int j = 2*i; j <= 1000000; j+=i) {
	prime[j] = 0;
      }
    }
  }
  prime[0] = prime[1] = 0;

  while (1) {
    int N, X;
    cin >> N >> X;
    if (N == 0 && X == 0) break;
    int price[40];
    for (int i = 0; i < N; i++) cin >> price[i];

    fill(dp, dp+1000010, 0);
    dp[0] = 1;
    for (int i = 0; i < X; i++) {
      if (!dp[i]) continue;
      for (int j = 0; j < N; j++) {
	if (i + price[j] <= X) dp[i+price[j]] = 1;
      }
    }

    bool flag = true;
    for (int i = X; i > 0; i--) {
      if (dp[i] && prime[i]) {
	cout << i << endl;
	flag = false;
	break;
      }
    }
    if (flag) cout << "NA" << endl;
  }
  return 0;
}

Measured memory_bytes: 8972
#include <algorithm>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
  string s;
  cin >> s;
  string keyence = "keyence";
  for (int i = 1; i < 7; i++) {
    string tmp1 = keyence.substr(0, i);
    string tmp2 = keyence.substr(i, 7 - i);
    // cout << tmp1 << "," << tmp2 << endl;
    int s1 = s.find(tmp1);
    int s2 = s.rfind(tmp2);
    if (s1 == 0 && s2 + tmp2.size() == s.size()) {
      cout << "YES" << endl;
      return 0;
    } else {
      // cout << s1 << "," << s2 << endl;
    }
  }
  if (s.find(keyence) == 0 || s.rfind(keyence) == s.size() - keyence.size()) {
    cout << "YES" << endl;
    return 0;
  }
  cout << "NO" << endl;
  return 0;
}


Measured memory_bytes: 256
def main():
    n = int(input())
    s = list(map(int, input().split()))
    q = int(input())
    t = list(map(int, input().split()))
    ans = 0
    for i in range(q):
        for j in range(n):
            if t[i] == s[j]:
                ans += 1
                break
    print(ans)


if __name__ == '__main__':
    main()



Measured memory_bytes: 6552
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())

using namespace std;
using ll = long long;

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> inline void dump(vector<T> v) { for (auto& x : v) cerr << x << " "; cerr << endl; }
template<class T> inline void dump(vector<pair<T, T>> v) { for (auto& p : v) cerr << p.first << " " << p.second << endl; }
template<class T> inline void dump(vector<vector<T>> vv) { for (auto& v : vv) {for (auto& x : v) cerr << x << " "; cerr << endl;} }

constexpr int INF = 1001001001;
constexpr long long INFL = (1LL<<60);
constexpr double eps = (1e-9);

map<int, int> memo;

int pcnt(int x) {
  bitset<32> bs(x);
  return bs.count();
}

int f(int x) {
  if (x == 0) return 0;
  return f(x % pcnt(x)) + 1;
}

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

  int n;
  cin >> n;

  string s;
  cin >> s;

  int pop_base = 0;
  rep(i, n) if (s[i] == '1') pop_base++;

  int r0 = 0;   // X を pop_base で割った余り
  rep(i, n) {
    r0 = (r0 * 2) % pop_base;
    r0 += s[i] == '1' ? 1 : 0;
  }
  int rl = 0;   // X を pop_base - 1 で割った余り
  if (pop_base != 1) {
    rep(i, n) {
      rl = (rl * 2) % (pop_base - 1);
      rl += s[i] == '1' ? 1 : 0;
    }
  }
  int ru = 0;   // X を pop_base + 1 で割った余り
  rep(i, n) {
    ru = (ru * 2) % (pop_base + 1);
    ru += s[i] == '1' ? 1 : 0;
  }

  vector<int> ans(n);

  rep(b, 2) {
    int npc = pop_base;
    if (b == 0) npc++; else npc--;
    if (npc <= 0) continue;
    int r0 = 0;
    rep(i, n) {
      r0 = (r0 * 2) % npc;
      r0 += s[i] - '0';
    }
    int k = 1;
    for (int i = n - 1; i >= 0; --i) {
      if (s[i] - '0' == b) {
        int r = r0;
        if (b == 0) r = (r + k) % npc;
        else r = (r - k + npc) % npc;
        ans[i] = f(r) + 1;
      }
      k = (k * 2) % npc;
    }
  }

  for (auto& x : ans) cout << x << endl;

  return 0;
}


Measured memory_bytes: 4336
fun main(args: Array<String>) {
    abc050b()
}

fun abc050b() {
    val n = readLine()!!.toInt()
    val tList = readLine()!!.split(" ").map { it.toInt() }.toIntArray()
    val m = readLine()!!.toInt()
    val pxList = (1..m).map { readLine()!!.split(" ").map { it.toInt() } }
        .map { Pair(it[0], it[1]) }

    val answer = pxList.map { px ->
        val times = tList.clone()
        times[px.first - 1] = px.second
        times.sum()
    }

    println(answer.joinToString(System.lineSeparator()))
}


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

#define vi vector<int>
#define vl vector<long>
#define vvi vector<vector<int>>
#define vvl vector<vector<long>>
#define pint pair<int, int>
#define plong pair<long, long>

int main() {
    int N, x;
    cin>>N>>x;
    vi A(N);
    REP(i, 0, N) cin >> A[i];
    long count = 0;
    REP(i, 1, N){
        if(A[i-1] + A[i] > x){
            count += A[i-1] + A[i] - x;
            if(A[i-1] + A[i] - x > A[i]){
                A[i] = 0;
                A[i-1] = x;
            }else{
                A[i] = x - A[i-1];
            }
        }
    }
    cout << count << endl;
}

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

using namespace std;

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

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
    sort(a, a + n);
    int x = a[n / 2 - 1], y = a[n / 2];
    printf("%d\n", y - x);
    return 0;
}


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

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;

using namespace std;


int inputValue(){
    int a;
    cin >> a;
    return a;
};

void inputArray(int * p, int a){
    rep(i, a){
        cin >> p[i];
    }
};

void inputVector(vector<int> * p, int a){
    rep(i, a){
        int input;
        cin >> input;
        p -> push_back(input);
    }
}

template <typename T>
void output(T a, int precision) {
    if(precision > 0){
        cout << setprecision(precision)  << a << "\n";
    }
    else{
        cout << a << "\n";
    }
}

int main(int argc, const char * argv[]) {
    
    // source code
  int n;
  cin >> n;
  cout << n*n*n << endl;
}

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

// 計算量は O(NloglogN) らしい
vector <bool> sieve(int n) { // sieve : ふるい
    vector <bool> is_prime(n + 1, true);
    if (n >= 0) is_prime[0] = false;
    if (n >= 1) is_prime[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (!is_prime[i]) continue;
        for (int j = 2 * i; j <= n; j += i) {
            is_prime[j] = false;
        }
    }
    return is_prime;
}


// verified
//   http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_C&lang=jp
void AOJ_ALDS_1_C() {
    int n;
    cin >> n;
    vector <bool> is_prime = sieve(100000005);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int m;
        cin >> m;
        ans += is_prime[m];
    }
    cout << ans << "\n";
}


// verified
//   https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day1/problems/C
void ACPC_C() {
    int n;
    cin >> n;
    vector <bool> is_prime = sieve(n+2);
    int ans = 0;
    for (int i = 3; i <= n; i++) {
        ans += is_prime[i] & is_prime[i + 2];
    }
    cout << ans * 2 << "\n";
}

int main() {
    // AOJ_ALDS_1_C();
    ACPC_C();
    return 0;
}


Measured memory_bytes: 4052
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string s;
const int Kmax=1e7;
int sum[Kmax];
int R[Kmax];
 
int main()
{
    int n;
    cin>>n;
    cin>>s;
    int Max=0;
        for(int j=1;j<n;j++){
         sum[j]=sum[j-1];
         if(s[j-1]=='E'){
            sum[j]++;
			//printf("%d:%d\n",j,sum[j]);
         }
         }
        for(int k=n;k>0;k--){
        R[k-1]=R[k];
        if(s[k]=='W'){
        R[k-1]++;
        }
         sum[k-1]=sum[k-1]+R[k-1];
		// printf("%d:%d\n",k-1,sum[k-1]);
         
         Max=max(Max,sum[k-1]);
        }
        cout<<n-1-Max<<endl;
    return 0;
}

Measured memory_bytes: 3972
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    string ss,tt;
    cin>>ss>>tt;
    for(int i=0;i<(int)ss.length();i++)
        if(ss[i]!=tt[i])
        {
            cout<<"No\n";
            return 0;
        }
    cout<<"Yes\n";
    return 0;
}


Measured memory_bytes: 3652
#include<bits/stdc++.h>
 
using namespace std;
 
//container util
//------------------------------------------
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
 
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define REACH(i,c) for(typeof((c).end()) i=(c).end(); i!=(c).begin(); --i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
 
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).begin(),(c).end(),greater<int>())
 
#define PB(a) push_back(a)
#define PF(a) pop_front(a)

#define MP(a,b) make_pair(a,b)
 
#define FS first
#define SE second
 
#define ALL(x) (x).begin(),(x).end()
#define MAX_EL(c) *max_element((c).begin(),(c).end())
#define MIN_EL(c) *min_element((c).begin(),(c).end())
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<long long> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef string str;
 
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
 
//grobal var
//------------------------------------------
const int MAX = 2*10e5+2;

//---------interval scheduling----------------------
struct interval {
  int s, f;
  interval(int s, int f) : s(s), f(f) { }
};
bool compare_f(const interval &x, const interval &y) {
  return x.f < y.f;
}
vector<interval> interval_scheduling(vector<interval> J) {
  vector<interval> A;
  sort(J.begin(), J.end(), compare_f);
  int f = 0;
  for (int i = 0; i < J.size(); ++i) {
    if (J[i].s >= f) {
      A.push_back(J[i]);
      f = J[i].f;
    }
  }
  return A;
}

int main(){
// magic spell------------------------------
  cin.tie(0);
  ios::sync_with_stdio(false);
//------------------------------------------
  int N,M;
  while(cin >> N >> M){
    int ans = 0;
    PII range = MP(0,N);
    REP(i,M){
      int l,r;
      cin >> l >> r;
      l--;
      r--;
      range = MP(max(range.FS,l),min(r,range.SE));
    }
    REP(i,N){
      if(range.FS<=i&&i<=range.SE) ans++;
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 384
a,b,c,x,y=map(int,input().split())
ans1 = a*x+b*y
if x<y:
  ans2 = x*2*c+b*(y-x)
else:
  ans2 = y*2*c+a*(x-y)
ans3 = max(x,y)*2*c
print(min(ans1,ans2,ans3))

Measured memory_bytes: 9212
#include <iostream>
#include <cstdio>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <complex>
#include <map>
#include <climits>
#include <sstream>
using namespace std;

#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define EPS 1e-8
#define F first
#define S second
#define mkp make_pair

static const double PI=6*asin(0.5);
typedef long long ll;
typedef complex<double> CP;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vint;
static const int INF=1<<24;

template <class T>
void initvv(vector<vector<T> > &v,int a,int b, const T  &t = T()){
	v.assign(a,vector<T>(b,t));
}

//v.erase(unique(v.begin(),v.end()),v.end());


int main(){
	string s;
	vector<string> v;
	cin>>s;
	while(s.size()){
		rep(i,s.size()){
			if(i+6<s.size()&&s.substr(i,6)=="eggegg"){
				v.PB(s.substr(0,i+3));
				s=s.substr(i+3);
				break;
			}
			else if(i+6<s.size()&&s.substr(i,6)=="kenchi"){
				v.PB(s.substr(0,i+3));
				s=s.substr(i+3);
				break;
			}
			else if(i==s.size()-1){
				v.PB(s);
				s="";
			}
		}
	}
	vector<pair<pii,string> > ans;
	rep(i,v.size()){
		int cnt=0;
		string t;
		while(v[i].size()){
			if(v[i].substr(0,3)=="egg"){
				t="egg";
				v[i]=v[i].substr(3);
				// cnt++;
			}
			else{
				t="chicken";
				v[i]=v[i].substr(7);
			}
			cnt++;
		}

		ans.PB(mkp(mkp(-cnt,i),t));
	}
	sort(ALL(ans));
	// rep(i,ans.size()){
		// cout<<ans[i].F.F<<" "<<ans[i].F.S<<" "<<ans[i].S<<endl;
	// }
	cout<<ans[0].S<<endl;
}

Measured memory_bytes: 1244
from collections import defaultdict
import sys


sys.setrecursionlimit(10**6)


def main():
    N = int(input())
    adj = defaultdict(list)
    for _ in range(N - 1):
        a, b = list(map(int, input().split()))
        adj[a - 1].append(b - 1)
        adj[b - 1].append(a - 1)
    C = list(map(int, input().split()))

    # 深さ優先で番号の大きい順に埋めていく
    C.sort(reverse=True)
    ans = [0] * N

    def dfs(node=0, parent=None, c_index=0):
        ans[node] = C[c_index]
        next_c_index = c_index + 1
        for child in adj[node]:
            if child == parent:
                continue
            next_c_index = dfs(child, node, next_c_index)
        return next_c_index

    dfs()
    print(sum(C[1:]))
    print(' '.join(map(str, ans)))


if __name__ == '__main__':
    main()


Measured memory_bytes: 23368
import itertools
import math

N = int(raw_input())

pts = [map(float, raw_input().split()) for _ in xrange(N)]

def dist(p1, p2):
    x1, y1 = p1
    x2, y2 = p2
    return math.sqrt((x1 - x2)**2 + (y1-y2)**2)

def path_len(path):
    return sum(dist(path[i-1], path[i]) for i in xrange(1, len(path)))

total_cnt = 0
total_len = 0.
for path in itertools.permutations(pts):
    total_len += path_len(path)
    total_cnt += 1

print total_len/total_cnt

Measured memory_bytes: 34152
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define INF 1000000010
#define EPS 1e-9
#define fst first
#define scd second

#define debug(x) cout<<x<<endl;
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define lp(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
#define int long long
#define endl "\n"


signed main(){
  cin.tie(0);	
  ios::sync_with_stdio(false);
  int n;
  cin>>n;
  n++;
  int ans=0;
  while(n>=10){
    ans+=9;
    n/=10;
  }
  cout<<ans+n-1<<endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define LL long long
#define LD long double
#define pb push_back
#define mp make_pair
#define ss(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl
#define rep(i, j, n) for (int i = j; i <= n; ++i)
#define per(i, j, n) for (int i = n; j <= i; --i)
#define all(x) x.begin(), x.end()

using namespace std;

const int N = 1e5 + 100;

int n, L;
int a[N];

int main() {		
	scanf ("%d%d", &n, &L);
	rep(i, 1, n) scanf ("%d", a + i);
	rep(i, 1, n - 1) {
		if (a[i] + a[i + 1] >= L) {
			printf ("Possible\n");
			vector <int> v;
			rep(j, 1, i - 1)
				v.pb(j);
			per(j, i + 1, n - 1)
				v.pb(j);
			v.pb(i);
			for (auto it : v) printf ("%d\n", it);
			return 0;
		}
	}
	printf ("Impossible\n");
	
	return 0;
}


Measured memory_bytes: 1784
#D
import numpy as np
n, k = map(int, input().split())
p = list(map(int, input().strip().split()))
p = np.array(p)
def calc_E(p):
    return ((p+1)/2)

q = (p+1)/2

#print(q)
sum = np.cumsum(q)

sum2 = np.zeros((n+1))
sum2[1:] = sum
max = -1
for i in range(k,n+1):
    tmp = sum2[i] - sum2[i-k]
    if max < tmp:
        max = tmp

print(max)

Measured memory_bytes: 33836
// 并查集
#include <bits/stdc++.h>
#define A first
#define B second
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int maxn = 1e5 + 10;
int pre[maxn],N,M;
PII arr[maxn];
LL big[maxn];
LL ans[maxn];
int getPre(int i){
	return i == pre[i] ? i : pre[i] = getPre(pre[i]);
}
void init(){
	for(int i = 1; i <= N ; ++i){
		pre[i] = i;
		big[i] = 1;
	}
}
void readIn(){
	scanf("%d%d",&N,&M);
	init();
	for(int i = 0 ; i < M ; ++i) {
		PII &now = arr[i];
		scanf("%d%d",&now.A,&now.B);
	}
}
int main(){
	readIn();
	LL res = 1ll*N*(N-1)/2;
	for(int i = M -1 ; i >= 0 ; --i){
		ans[i] = res;
		PII &now  = arr[i];
		int fa = getPre(now.A),fb = getPre(now.B);
		if(fa != fb){
			res -= 1ll*big[fa]*big[fb];
			// cout<<"fa = "<<fa<<" fb = "<<fb<<endl;
			// cout<<"n a = "<<big[fa]<<" n b = "<<big[fb]<<endl;
			pre[fb] = fa; // 注意这个地方是反过来的
			big[fa] += big[fb];
		}
	}
	for(int i = 0 ; i < M ; ++i){
		printf("%lld\n",ans[i]);
	}
	return 0;
}

Measured memory_bytes: 4096
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define dl 998244853
lli maxi(lli a,lli b){
    if(a>=b)return a;
    return b;
}

int main() {
    int n,W;
    cin>>n>>W;
    vector<vector<lli>> a(n,vector<lli>(2,0));
    for(int i=0;i<n;i++){
        cin>>a[i][0]>>a[i][1];
    }
    vector<vector<lli>> ans(n+1,vector<lli>(W+1,0));
    
    for(int i=0;i<=n;i++){
        for(int j=0;j<=W;j++){
           if(i==0||j==0){
               ans[i][j]=0;
           }else if(a[i-1][0]>j){
               ans[i][j]=ans[i-1][j];
           }else{
               ans[i][j]=maxi(ans[i-1][j],ans[i-1][j-a[i-1][0]]+a[i-1][1]);
           }
            }
        }
       
    cout<<ans[n][W]<<endl;
}

Measured memory_bytes: 80256
#include <bits/stdc++.h>
using namespace std;
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;
}
typedef long long int ll;

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define endl "\n"
const double EPS = 1e-7;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
const double PI = acos(-1);
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

//-------------------------------------

ll dp[310][310][310];

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    vector<ll> h(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        cin >> h[i];
    }
    for (int i = 0; i < 310; i++)
    {
        for (int j = 0; j < 310; j++)
        {
            for (int l = 0; l < 310; l++)
            {
                dp[i][j][l] = LLINF;
            }
        }
    }
    dp[1][0][0] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= k; j++)
        {
            for (int x = 0; x < i; x++)
            {
                chmin(dp[i + 1][j][i], dp[i][j][x] + max(0LL, h[i] - h[x]));
                chmin(dp[i + 1][j + 1][x], dp[i][j][x]);
            }
        }
    }
    ll ans = LLINF;
    for (int i = 0; i <= k; i++)
    {
        for (int j = 0; j < 310; j++)
        {
            chmin(ans, dp[n + 1][i][j]);
        }
    }
    cout << ans << endl;
}

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

#define int long long
#define fast_io(); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define loop(i,a,b) for(int i=a;i<b;i++)
#define all(x) x.begin(),x.end()
#define us unordered_set
#define um unordered_map
#define ms multiset
#define mm multimap
#define pb push_back
#define pf push_front
#define ins insert
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define _max max_element
#define _min min_element
#define tc(T) int T; cin>>T; while(T--)
#define q(q) int q; cin>>q; while(q--)
#define pi 3.1415926535897932384626433832
const int pinf=((int)2e18);
const int ninf=((int)-2e18);
const int mod=1000000007;

using namespace std;

int power(int x,int n,int M)
{
    if(n==0)
        return 1;
    else if(n%2 == 0)
        return power((x*x)%M,n/2,M);
    else
        return (x*power((x*x)%M,(n-1)/2,M))%M;
}

bool vowel(char c)
{
    return(c=='a' or c=='e' or c=='i' or c=='o' or c=='u' or c=='A' or c=='E' or c=='I' or c=='U' or c=='O');
}

int32_t main()
{
    fast_io();

    //FILE *fptr1=freopen("in.txt","r",stdin);
    //FILE *fptr2=freopen("out.txt","w",stdout);

    int n;
    cin>>n;
    vector <int> a(n),p(n),s(n);
    loop(i,0,n) cin>>a[i];

    p[0]=0;
    loop(i,1,n)
    p[i]=p[i-1]^a[i-1];

    s[n-1]=0;
    for(int i=n-2;i>=0;i--)
        s[i]=s[i+1]^a[i+1];

    loop(i,0,n) cout<<(p[i]^s[i])<< " ";


    return 0;
}


Measured memory_bytes: 7896
from collections import deque, Counter as cnt
from collections import defaultdict as dd
from operator import itemgetter as ig
from bisect import bisect_right as bsr
from math import factorial, ceil, floor
import sys
sys.setrecursionlimit(1000000)

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)


def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]


def nlist(n, v):
    if not n:
        return [] if type(v) is list else v
    return [nlist(n[1:], v) for _ in range(n[0])]


def yesno(v, yes="Yes", no="No", upper=False):
    if upper:
        print([yes.upper(), no.upper()][not v])
    else:
        print([yes, no][not v])


def main():
    """エントリーポイント"""
    K, X = input([int, 2])
    yesno(X <= K * 500)


if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()


Measured memory_bytes: 3316
import sys,math,collections,itertools
input = sys.stdin.readline

N,K=list(map(int,input().split()))
R,S,P=list(map(int,input().split()))
T = input().rstrip()
s =T.replace('r','P') #P
ss=s.replace('s','R') #R
sss=ss.replace('p','S') #S
sl = list(sss)

for i in range(K,N):
    if sl[i]==sl[i-K]:
        sl[i] = '0'

sc = collections.Counter(sl)

print(sc['R']*R + sc['P']*P + sc['S']*S)


Measured memory_bytes: 10252
#!/usr/bin/env python3
import sys


def solve(N: int, S: str):

    ans = []
    n = S[0]
    c = 1
    for i in range(1,N):
        if(S[i] == n):
            c += 1
        else:
            ans.append(n)
            n = S[i]
            c = 1
    ans.append(n)

    print(len(ans))
    # print(ans)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()


Measured memory_bytes: 4060
#include <bits/stdc++.h>
#define int long long
#define ALL(v) (v).begin(),(v).end()
#define Vi vector<int>
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repeq(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=a;i>b;i--)
#define repreq(i,a,b) for(int i=a;i>=b;i++)
#define leng(n) (int)(log10(n)+1)
#define INF 9000000000000000000
#define MOD 1000000007
using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}  //  最大公約数gcd
int lcm(int a,int b){return a/gcd(a,b)*b;}  //  最小公倍数lcm

signed main() {
  string s;
  cin >> s;
  int ct = 0;
  rep(i,0,s.size()-1){
    if(s[i]!=s[i+1]) ct++;
  }
  
  cout << ct << endl;
}


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

bool integer(double x) {
  while (1 <= x) {
    x -= 1;
  }
  if (x == 0) {
    return true;
  } else {
    return false;
  }
}

int main() {
  int N, D;
  cin >> N >> D;
  vector<vector<int>> X(N, vector<int>(D));
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < D; j++) {
      cin >> X.at(i).at(j);
    }
  }
  int count = 0;
  for (int i = 0; i < N-1; i++) {
    for (int j = i + 1; j < N; j++) {
      double dist2 = 0;
      for (int k = 0; k < D; k++) {
        dist2 += pow(X.at(i).at(k) - X.at(j).at(k), 2);
      }
      double dist = sqrt(dist2);
      if (integer(dist)) {
        count++;
      }
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 3732
#include <iostream>
#include <iomanip>
#include <bits/stdc++.h>
#include <vector>
#include <iterator>
#include <string>
#define pan(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define vi vector<int>
#define pb push_back
using namespace std;
 

int main(){
    int n;
    cin>>n;
    string s,t,ans;
    cin>>s>>t;
    pan(i,2*n){
        if(i%2==0) ans+=s[(i)/2];
        else ans+=t[(i-1)/2];
    }
    cout<<ans;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
#include<string.h>
#include<set>
#include<stdio.h>
#include<math.h>
#include<queue>
#include<map>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include <cstdio>
#include <cstdlib>
#include<stack>
#include<vector>
char b[20]={'A','K','I','H','A','B','A','R','A'};
char a[50];
int main()
{
    cin>>a;
    int add1=0;
    int add2=0;
    int len1=strlen(a);

    int len2=9;
    if(len1>len2)
    {
         cout<<"NO"<<endl;
            return 0;
    }
    int sum=0;
    for(int i=0;i<=len1;i++)
    {
        if(a[i]=='A')
            sum++;
        else
        break;
    }

    if(sum>1)
    {
        cout<<"NO"<<endl;
            return 0;
    }
    while(add2<len2&&add1<len1)
    {
        //cout<<add1<<"_"<<add2<<"_"<<a[add1]<<"_"<<b[add2]<<endl;
        if(a[add1]==b[add2])
        {
            add1++;
            add2++;
        }
        else if(b[add2]=='A')
            add2++;
        else
        {
            cout<<"NO"<<endl;
            return 0;
        }
    }
    //cout<<add1<<"_"<<add2<<endl;
    int sum1=0;
    for(int i=add1;i<len1;i++)
    {
        if(a[i]!='A')
        {
            cout<<"NO"<<endl;
            return 0;
        }
        else
        {
            sum1++;
        }
    }
    if(sum1>1)
        {
            cout<<"NO"<<endl;
            return 0;
        }
    for(int i=add2;i<len2;i++)
    {
        if(b[i]!='A')
        {
            cout<<"NO"<<endl;
            return 0;
        }
    }
    cout<<"YES"<<endl;
    return 0;
}


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

#define inf 0x3f3f3f3f
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector <int> vi;
typedef vector <vector <int>> vvi;
typedef pair <int, int> pi;
typedef vector <pair <int, int>> vpi;

int n, m;

bitset <100001> ap;

void read() {
  cin >> n >> m;
  for(int i = 0; i < m; ++i) {
    int x;
    cin >> x;
    ap[x] = 1;
  }
}

const int MOD = 1000000007;

void solve() {
  vector <int> dp(n + 1);
  dp[0] = 1;
  if (!ap[1])
    dp[1] = 1;
  for(int i = 2; i <= n; ++i)
    if (!ap[i])
      dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
  int sol = 1;
  cout << dp[n];
}

int main() {
  ios :: sync_with_stdio(false);
  cin.tie(nullptr);
  read();
  solve();
  return 0;
}


Measured memory_bytes: 640
#include<iostream>
// #include<vector>
// #include<string>
using namespace std;

int main(){
  int n,p=0,w=0,g=0,y=0;cin>>n;
  char c;
  bool flag=false;
  for(int i=0;i<n;i++){
    cin>>c;
    if(c=='Y')flag=true;
  }
  cout<<(flag?"Four":"Three")<<endl;
  return 0;


}


Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#define rep(i,n) for(int i = 0; i < n;i++)
#define ll long long
#include <bits/stdc++.h>
using namespace std;
 
  int main(){
    int n;cin>>n;
    vector<int>p(n);
    for(int i=0;i<n;i++)
      cin>>p.at(i);
    int ans=1;
    int r=p.at(0);
    for(int i=1;i<n;i++)
    {
      if(r>p.at(i))
      {
        ans++;
        r=p.at(i);
      }
    }
    cout<<ans;
  }
      

    
    
      
    


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <random>
#include <ctime>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2")
#define ll long long
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define pll pair<ll,ll>
#define ld double
#define pld pair<ld,ld>
#define pii pair<int,int>
#define sqr(a) ((a)*(a))
#define all(v) v.begin(),v.end()

using namespace std;
//using namespace __gnu_pbds;

ll MOD = 998244353;
const ll INF = 1e18;
const ld E = 1e-18;
const ld PI=acos(-1);
mt19937_64 rnd(time(0));
ll p1 = 31, p2 = 37, p3 = 7, p4 = rnd() % 100 + 1, md1 = MOD, md2 = 998244353, md3 = 998244357, md4 = rnd() % 1000000000;

//using ord_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

ll n, m, k, a[1000001];


ll binpow(ll h, ll r, ll md = MOD)
{
    ll l = 1;
    while (r)
    {
        if (r & 1) l *= h, l%=md;
        h *= h;
        h %= md;
        r /= 2;
    }
    return l;
}

ll gcd(ll x, ll y)
{
    if (x < y) swap(x, y);
    while (x && y)
    {
        x %= y;
        swap(x, y);
    }
    return x + y;
}

int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    //freopen("capitals.in","r",stdin);
    //freopen("capitals.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll k;
    cin >> n >> k;
    ll mx=0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    ll l=1, r=1e18;
    while (l<r)
    {
        ll w=(l+r)/2;
        ll o=0;
        for (int i = 1; i <= n; i++)
            o+=(a[i]+w-1)/w-1;
        if (o<=k) r=w; else l=w+1;
    }
    cout << l << "\n";
    return 0;
}

/*
a-b=k
a+b=m
a=(m+k)/2;
b=(m-k)/2;
*/


Measured memory_bytes: 5212
#include<iostream>
#include<vector>

int main() {
	int n, k,i=1;
	

	std::cin >> n >> k;

	std::vector<int> v(n);

	for (int &x : v) {
		std::cin >> x;
	}

	//入力完了

	n = n - k;
	
	while (n > 0) {
		n = n - k+1;
		i++;
	}

	std::cout << i << std::endl;

	return 0;
}

Measured memory_bytes: 640
package main

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

func main() {
	// 標準入力をソースにしたスキャナの生成
	scanner := bufio.NewScanner(os.Stdin)

	scanner.Scan()
	var N, _ = strconv.Atoi(scanner.Text())

	for N > 0 {
		N = N - 1000
	}

	fmt.Println(math.Abs(float64(N)))
}

Measured memory_bytes: 1776
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

def f(i,d):
    """
    i 桁の n で、r(n)-n = d
    """
    n = i-1
    m = 0
    res = []
    while n>m:
        x = 10**n-10**m
        if m:
            res.append(tuple((x*k,v) for k,v in d2.items()))
        else:
            res.append(tuple((x*k,v) for k,v in d1.items()))
        n -= 1
        m += 1
    
    def sums(lsts):
        dic = {0:1}
        for lst in lsts:
            ndic = {}
            for k1,v1 in dic.items():
                for k2,v2 in lst:
                    k = k1+k2
                    v = v1*v2
                    if k in ndic: ndic[k] += v
                    else: ndic[k] = v
            dic = ndic
        
        return dic.items()
    
    L = len(res)
    #print(res[L//2:])
    s1 = sums(res[:L//2])
    s2 = sorted(sums(res[L//2:]))
    
    #print(s1)
    #print(s2)
    #print(d)

    v = 0
    from bisect import bisect_left
    for k1,v1 in s1:
        idx = bisect_left(s2,(d-k1,0))
        if idx < len(s2) and s2[idx][0] == d-k1:
            #print(k1,v1,idx,s2[idx])
            v += v1*s2[idx][1]
    return v*(1 if i%2==0 else 10)


d, = map(int,read().split())

ans = 0

from collections import Counter

d1 = Counter()
for i in range(10):
    for j in range(1,10):
        d1[i-j] += 1
        
d2 = Counter()
for i in range(10):
    for j in range(10):
        d2[i-j] += 1

for i in range(2,18):
#for i in range(2,19):
    r = f(i,d)    
    #print(r,i)
    ans += r
if d%(10**9-10**8)==0:
    r = d//(10**9-10**8)
    ans += d2[r]*(10**7)*9

print(ans)






Measured memory_bytes: 159572
#include <iostream>
#include <string>
#include <set>

using namespace std;

int main(int argc, char* argv[]) {
  int N;
  cin >> N;

  string s;
  cin >> s;

  int ret = 0;
  set<char> past;
  for (int i = 1; i < N; ++i) {
    past.insert(s[i - 1]);
    int count = 0;
    set<char> used;
    for (int j = i; j < N; ++j) {
      if (past.find(s[j]) != past.end() && used.find(s[j]) == used.end()) {
        used.insert(s[j]);
        ++count;
      }
    }
    ret = max(ret, count);
  }

  cout << ret << endl;

  return 0;
}

Measured memory_bytes: 384
import sys
import heapq
from decimal import Decimal

input = sys.stdin.readline
n = int(input())
alpha_list = [chr(i) for i in range(97, 97+26)]


def dfs(s,used_count):

    if len(s) == n:
        print(s)
        return

    for i in range(used_count+1):
        if i == used_count:
            dfs(s+alpha_list[i],used_count+1)
        else:
            dfs(s+alpha_list[i],used_count)

dfs("a",1)


Measured memory_bytes: 9868
n,m=map(int,input().split())
x_list=list(map(int,input().split()))
x_list.sort()
d_list=[]
for i in range(0,m-1):
    d_list.append(x_list[i+1]-x_list[i])
if m<=n:
    print(0)
else:
    d_list.sort()
    print(sum(d_list[0:m-n]))
    
        


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

int main(){
    int n;
    cin >> n;
    while (n!=0){
        int a , b , c;
        cin >> a >> b >> c;
        if(a*a==b*b+c*c || b*b==a*a+c*c || c*c==a*a+b*b) cout << "YES" << endl;
        else cout << "NO" << endl;
        --n;
    }
}


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

int main() {
  int K, S;
  cin >> K >> S;
  int ans=0;
  for (int X=0; X<=K; X++) {
    for (int Y=0; Y<=K; Y++) {
      int Z=S-X-Y;
      if ((Z>=0 && Z<=K) && X+Y+Z==S) {
        ans++;
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
/**
 *    author:  tourist
 *    created: 26.01.2020 19:09:20       
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> l(n), r(n);
  for (int i = 0; i < n; i++) {
    cin >> l[i] >> r[i];
  }
  multiset<long long> L, R;
  long long sL = 0, sR = 0;
  L.insert(l[0]);
  R.insert(l[0]);
  long long ans = 0;
  for (int i = 1; i < n; i++) {
    sL -= r[i] - l[i];
    sR += r[i - 1] - l[i - 1];
    long long xL = sL + *prev(L.end());
    if (l[i] <= xL) {
      ans += xL - l[i];
      R.insert(xL - sR);
      L.erase(prev(L.end()));
      L.insert(l[i] - sL);
      L.insert(l[i] - sL);
      continue;
    }
    long long xR = sR + *R.begin();
    if (l[i] >= xR) {
      ans += l[i] - xR;
      L.insert(xR - sL);
      R.erase(R.begin());
      R.insert(l[i] - sR);
      R.insert(l[i] - sR);
      continue;
    }
    L.insert(l[i] - sL);
    R.insert(l[i] - sR);
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 10368
#include<iostream>
#include<cstdlib>

#include<cmath>
#include<map>
#include<string>
#include<vector>
#include<algorithm> 

using namespace std;

# define p(s) std::cout << s << endl;
# define printIf(j,s1,s2) std::cout << (j ? s1 : s2) << endl;
# define YES(j) std::cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
# define yes(j) std::cout << (j ? "yes" : "no") << endl;
# define rep(n,i) for(i = 0 ; i < n ; i++)

int main()
{
    string s;cin >> s;
    cout << s.substr(0,1)+to_string(s.size()-2)+s.substr(s.size()-1,1) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>   
using namespace std;
using namespace __gnu_pbds;
typedef long long ll; 
#define int long long
typedef unsigned long long lu;
typedef vector<ll> v;
typedef vector<vector<ll> > vv;
typedef vector<string>  vs;
typedef vector<pair<ll,ll>> vpr;
typedef long double ld;
#define f(i,n) for(ll i = 0; i < n; i++)
#define ff(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define endl "\n"
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define amax(x,y) if(y>x) x=y;
#define amin(x,y) if(y<x)x=y;
#define bg(x) x.begin()
#define sz(x) (ll)x.size()
#define in(x,n) for(ll i=0;i<n;i++)cin>>x[i]
#define out(x,n) for(ll i=0;i<n;i++)cout<<x[i]<<" " 
#define mxt(a) *(max_element(a.begin(),a.end()))
#define mnt(a) *(min_element(a.begin(),a.end())
#define tc ll t;cin>>t;while(t--)
typedef pair<ll,ll> pi;
#define yes cout<<"YES\n";
#define no cout<<"NO\n";
#define yesno(f) if(f) yes else no
const v dx = {1, -1, 0, 0};
const v dy = {0, 0, 1, -1};
const ll mod=1e9+7;
const ld PI = 2 * acos(0.0);
ll m(ll a){ return (a+mod)%mod;}
ll cel(ll x1,ll y1){if((x1%y1)==0)return x1/y1;else return x1/y1+1;}
ll power(ll a,ll b,ll m)
{
	if(b==0)
		return 1;
	ll d=power(a,b/2,m);
	d=(d*d)%m;
	if(b&1)
		d=(d*a)%m;
	return d;
}
// set_name.find_by_order(k) It returns to an iterator to the kth element (counting from zero) in the set in O(logn) time
// set_name.order_of_key(k) It returns to the number of items that are strictly smaller than our item k in O(logn) time.
/*string operations :
str.substr (x,y) : returns a substring str[x],str[x+1],...str[x+y-1]
str.substr (x) : returns a substring str[x],... end of string
str.find(qtr) : returns the first occurenece of qtr in str */
int32_t main()
{
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int x;cin>>x;
	for(int i=1;i*i<=x;i++)
	{
		if(x%i==0)
		{
			for(int a=1;a*a*a*a<=x;a++)
			{
				int b=a-i;
				if(a*a*a*a*a - b*b*b*b*b ==x)
				{
					cout<<a<<" "<<b<<endl;
					return 0;
				}
			}
			int i1=x/i;
			for(int a=1;a*a*a*a<=x;a++)
			{
				int b=a-i1;
				if(a*a*a*a*a - b*b*b*b*b ==x)
				{
					cout<<a<<" "<<b<<endl;
					return 0;
				}
			}

		}
	}	
	return 0;
}

Measured memory_bytes: 3656
A, B, C, K = gets.split.map(&:to_i)

if K == 0
    ans = A - B
elsif K % 2 == 1
    ans = B - A
elsif K % 2 == 0
    ans = A - B
end

if ans.abs > 10**18
    puts 'Unfair'
else
    puts ans
end

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
#define bit(n) (1LL << (n))
#define sz(x) ((ll)(x).size())
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1000000007;

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 main() {
  ll T1, T2;
  cin >> T1 >> T2;
  ll A1, A2;
  cin >> A1 >> A2;
  ll B1, B2;
  cin >> B1 >> B2;

  if (A1 < B1) {
    swap(A1, B1);
    swap(A2, B2);
  }

  ll C1 = (A1 - B1) * T1, C2 = (A2 - B2) * T2;

  if (C1 + C2 == 0) {
    cout << "infinity" << endl;
    return 0;
  }

  if (C1 + C2 > 0) {
    cout << 0 << endl;
    return 0;
  }

  ll D = -(C1 + C2);
  ll ans;
  if (C1 % D == 0) {
    ans = (C1 / D - 1) * 2 + 2;
  } else {
    ans = (C1 / D) * 2 + 1;
  }


  cout << ans << endl;
}

Measured memory_bytes: 384