akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SignBoard
{
    class Program
    {
        static bool IsOK(int first, int space, string old, string board)
        {
            for (int i = 0; i < board.Length; i++)
            {
                if(old.Length <= first + space * i || old[first + space * i] != board[i]) return false;
            }
            return true;
        }
        static void Main()
        {
            int n = int.Parse(Console.ReadLine());
            string board = Console.ReadLine();
            string[] olds = new string[n];
            for (int i = 0; i < n; i++)
            {
                olds[i] = Console.ReadLine();
            }
            int ans = 0;
            for (int i = 0; i < n; i++)
            {
                bool ok = false;
                for (int j = 0; j < olds[i].Length; j++)//最初の添字
                {
                    for (int k = 0; k < olds[i].Length; k++)//幅
                    {
                        if (ok = IsOK(j, k, olds[i], board))
                        {
                            ans++;
                            break;
                        }
                    }
                    if (ok) break;
                }
            }
            Console.WriteLine(ans);
            Console.ReadKey();
        }
    }
}

Measured memory_bytes: 5604
#include<iostream>
using namespace std;
#include<string>
#include<set>


int main() {
	int n = 0;
	set<string> st;
	cin >> n;
	while (n--) {
		string str;
		cin >> str;
		st.insert(str);
	}
	cout << st.size() << endl;
	return 0;
}

Measured memory_bytes: 19192
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<math.h>

#define rep(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define rrep(i,a,n) for(int (i)=(a);(i)>=(n);(i)--)

#define INF ll 1 << 60
#define MOD 1000000007

typedef  long long ll;

using namespace std;

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 gcd(long long int a,long long int b){
    long long int r;
    if(a < b){
        int tmp;
        tmp = a;
        a = b;
        b = tmp;
    }
    while(r = a % b){
        a = b;
        b = r;
    }
    return a;
}

void Integer_factorization(long long int b,long long int n){
    long long int a = 2;
    long long int count = 0;
    long long int ans = 1;
    long long int ndash = n;
    if(b == 1) cout << n << endl;
    else{
    while(ndash >= a*a){
        if(n % a  == 0){
            count++;
            n/=a;

        if(count % b == 0){
            ans *= a;
        }
        }else{a++;count = 0;}
    }

    cout<<  ans << endl;
    }
}

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

void yb(){
    cout << "YES" << endl;
}

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

void nb(){
    cout << "NO" << endl;
}

int dig(int d){
    int ans = 1;
    if(d == 0) return ans;
    while(d != 0){
        d--;
        ans*=100;
    }
    return ans;
}
int c['z'+1];

void solve(void){
    int n;
    string s;
    cin >> n >> s;
    int ans = 0;
    rep(i,1,n-1){
        int c1['z'+1],c2['z'+1];
        int tmp = 0;

        rep(i,'a','z'+1){
            c1[i] = c2[i] = 0;
        }

        rep(j,0,i){
            c1[s[j]]++;
        }

        rep(j,i,n){
            c2[s[j]]++;
        }

        rep(i,'a','z'+1){
            if(c1[i] != 0 && c2[i] != 0){
                tmp++;
            }
        }
        ans = max(ans,tmp);

    }
    cout << ans << endl;
}

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

Measured memory_bytes: 256
List = list(map(int, input().split()))
A = list(map(int, input().split()))

X = sum(A) / (4 * List[1])

c = 0
for i in range(0,List[0]):
    if A[i] >= X:
        c += 1

if c >= List[1]:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 9176
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define rep2(i,j,n) for(int j=i;j<n;j++)
#define rep3(i,j,n) for(int j=i;j<=n;j++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define sp(n) cout << fixed << setprecision(n)
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 ll;
using namespace std;
int main(void){
    ll n;cin>>n;
    if(n%2==0){
        ll res=0;
        ll tmp=5;
        for(;tmp<=n;tmp*=5) res+=(n/tmp)/2;
        cout<<res<<endl;
    }else{
        cout<<0<<endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair

using namespace std;

int main()
{
   FAST/**/
   
   ll n;
   cin>>n;
   
   ll arr[n];
   for(ll i=0;i<n;i++)
        cin>>arr[i];
   
   ll store[n];
   store[0] = arr[0];
   ll ans = arr[0];
   for(ll i=1;i<n;i++)
   {
       if(arr[i]<arr[i-1])
       {
           store[i] = arr[i];
           continue;
       }
       if(arr[i] == arr[i-1])
       {
           store[i] = arr[i];
           continue;
       }
       
       ans+= arr[i] - store[i-1];
       store[i] = arr[i];
   }
   
   cout<<ans;
   
   return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <numeric>
#include <cmath>
#include <limits>
#include <stdio.h>
#include <iomanip>
#include <cstdlib>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
ll Max(ll(a), ll(b), ll(c)) {
	return max(max(a, b), c);
}
ll Min(ll(a), ll(b), ll(c)) {
	return min(min(a, b), c);
}





int main() {

	ll a=0;
	string S, T;
	cin >> S >> T;
	rep(i, S.size()) {
		if (S.at(i) != T.at(i))a++;
	}
	
	cout << a << endl;

}


Measured memory_bytes: 3920
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int):
    def dig(n):
        ret = 0
        while n > 0:
            ret += 1
            n //= 10
        return ret
    ret = 0
    for i in range(1, N + 1):
        if dig(i) % 2 == 1:
            ret += 1
    print(ret)
    return


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
    solve(N)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define fori(i, a, b) for(int i = (int) a; i <= (int) b; ++i)
#define rofi(i, b, a) for(int i = (int) b; i >= (int) a; --i)
#define foreach(tt, a) for(auto &tt: a)
#define all(a) begin(a), end(a)
#define csz(a) (int) a.size()
#define pb push_back
#define epb emplace_back
#define mp make_pair
#define load(a, v) fill(begin(a), end(a), v)
#define load_mem(a, v) memset(a, v, sizeof(a));
#define iostream_optimize() ios::sync_with_stdio(false); cin.tie(0);
using ll = long long;
const ll MOD = 1e9+7, LINF = 1e16+1;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const ll P1 = 31, P2 = 37, M1 = 1e9+7, M2 = 1e9+9;
/* <<<<<<<<<<<<<<<<<<<<<<<<<<<< END TEMPLATE >>>>>>>>>>>>>>>>>>>>>>>>>>> */
const int N = 2e5+1;

int n, a[N];
ll ans, x[N], s[N];
int main() {
	iostream_optimize();
	cin >> n;
	fori(i, 1, n) {
		cin >> a[i];
		x[i] = x[i-1] ^ a[i];
		s[i] = s[i-1] + a[i];
	}
	fori(i, 1, n) {
		int l = 0, r = i-1;
		while(l < r) {
			int mid = l+r >> 1;
			if((x[i] ^ x[mid]) == s[i] - s[mid]) r = mid;	
			else l = mid+1;
		}
		ans += i - l;
	}
	cout << ans;
}

Measured memory_bytes: 4224
#include<iostream>
#include<string>
#include<cstdio>
#include<cstdlib>
#define MAX 10000
using namespace std;

struct Node{
    int key;
    Node *parent, *left, *right;
};

Node *root, *NIL;

void insert(int k){
    Node* y = NIL; //xの親
    Node* x = root;
    Node* z;

    z = (Node *)malloc(sizeof(Node));
    z->key = k;
    z->left = NIL;
    z->right = NIL;
    while(x != NIL){
        y = x; //親の設定
        if(z->key < x->key) x = x->left;//左の子へ移動
        else x = x->right;
    }
    z->parent = y;

    if( y == NIL) root = z;
    else if(z->key < y->key ) y->left = z; //z を y の左の子にする
    else y->right = z; //z を y の右の子にする
}

void preorder(Node* z){//先行順巡回
    printf(" %d", z->key);
    if(z->left != NIL) preorder(z->left);
    if(z->right != NIL) preorder(z->right);
}

void inorder(Node* z){
    if(z->left != NIL) inorder(z->left);
    printf(" %d", z->key);
    if(z->right != NIL) inorder(z->right);
}

void print(){
    Node* z = root;
    inorder(z);
    printf("\n");
    preorder(z);
    printf("\n");
}

int main(){
    int n, k;
    string com;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> com;
        if(com == "insert"){
            scanf("%d", &k);
            insert(k);
        }else if( com == "print"){
            print();
        }
    }

    return 0;
}


Measured memory_bytes: 26732
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n, k;
	cin>>n>>k;
	int a[n], boz[n];
	for(int i=0; i<n; i++){
		cin>>a[i];
	}
	boz[0]=0;
	boz[1]=abs(a[1]-a[0]);
	for(int i=2; i<n; i++){
		boz[i]=boz[i-1]+abs(a[i]-a[i-1]);
		for(int j=i-1; j>=0 and j>=i-k; j--){
			boz[i]=min(boz[j]+abs(a[i]-a[j]),boz[i]);		
		}
	}
	cout<<boz[n-1]<<endl;
}


Measured memory_bytes: 1024
import itertools

def main():
    N = int(input())
    P = list(map(int, input().split()))
    Q = list(map(int, input().split()))

    p = 0
    q = 0
    count = 0
    for i in itertools.permutations([i+1 for i in range(N)]):
        if P == list(i):
            p = count + 1
        if Q == list(i):
            q = count + 1
        count += 1
    print(abs(p-q))

    return 0
if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <cstring>
#include <utility>
#include <algorithm>
#include <functional>
#include <deque>
#include <cctype>
#include <ctime>
#include <cstdlib>
#include <iomanip>
using namespace std;

int main(){
    int r;
    cin >> r;
    
    if (r<1200) cout << "ABC" << endl;
    else if (r<2800) cout << "ARC" << endl;
    else cout << "AGC" << endl;
}

Measured memory_bytes: 256
def main():
    n = int(input())
    aList = list(map(int,input().split()))
    
    cnt = 0
    for i in range(1,n):
        deff = aList[i-1] - aList[i]
        
        if deff > 0:
            cnt += deff
            aList[i] += deff
        
    print(cnt)

if __name__ == "__main__":
    main() 

Measured memory_bytes: 32320
import math
a,b = list(map(int,input().split()))

f= False

for i in range(1011):
  t1 = math.floor(i*0.08)
  t2 = math.floor(i*0.1)
  if t1 == a and t2 == b:
    ans = i
    f = True
    break

if f:
  print(ans)
else:
  print(-1)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int n;
char book[200];
int anst,anss=0;
int lis[30];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>book[i];
	for(int i=1;i<n;i++)
		{
			memset(lis,0,sizeof(lis));
			anst=0;
			int j;
			for(j=1;j<=i;j++)
				lis[(int)book[j]-96]=1;
			for(;j<=n;j++)
				{
					if(lis[(int)book[j]-96]==1)
					{
						anst++;
						lis[(int)book[j]-96]=0;
					}
				}
			if(anst>anss)
				anss=anst;
		}
	cout<<anss;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h> 
using namespace std;
 
#define ll long long int
#define absdiff(a,b) (a>b)?a-b:b-a
#define debug cout<<"debug";
#define mp make_pair 
#define pb push_back
#define fast  ios_base::sync_with_stdio(false);cin.tie(0);
#define MOD 1000000007
#define ll_MAX 19223372036859
#define endl "\n"
ll fast_expo(ll x,ll p){if(p==0) return 1;
else if(p%2==0){ ll t=fast_expo(x,p/2)%MOD;return (t*t)%MOD;} else return (x*(fast_expo(x,p-1))%MOD)%MOD;}
ll gcd(ll a,ll b){if(a==0||b==0) return a+b;  else return gcd(b%a,a); }

ll ord[100001],dp[100001];
ll curr;

void dfs(vector<ll> AdjL[],ll src,ll vis[]){
    vis[src] = 1;

    for(auto i:AdjL[src]){
        if(!vis[i]){
            dfs(AdjL,i,vis);
        }
    }
    ord[curr--] = src;
}

void top_sort(vector<ll> AdjL[],ll n){
    curr = n;
    ll vis[n+1]{};
    for(ll i=1; i<=n; ++i){
        if(!vis[i]){
            dfs(AdjL,i,vis);
        }
    }
}

int main()
{
    ll t_c; t_c = 1;
    // cin >> t_c;
    for(ll t_i=0; t_i<t_c; ++t_i){
        ll n,m; cin >> n >> m;
        vector<ll> AdjL[n+1];
        for(ll i=0; i<m; ++i){
            ll x,y; cin >> x >> y;
            AdjL[x].pb(y);
        }        

        top_sort(AdjL,n);
        for(ll i=1; i<=n; ++i){
            for(auto j:AdjL[ord[i]]){
                dp[j] = max(dp[ord[i]]+1,dp[j]);
            }
        }

        ll ans = INT_MIN;
        for(ll i=1; i<=n; ++i){
            ans = max(ans,dp[i]);
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 10112
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <algorithm>
#include <tuple>

//#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

int main() {
  float x, t;
  cin >> t >> x;

  printf("%.5f\n", t/x);
  
}


Measured memory_bytes: 256
#include <iostream> // cin, cout, cerr
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota
#include <cstdio> // printf, scanf
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <iomanip> // cout<<setprecision(n)
#include <functional> // function<void(int)>
#include <cmath>

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif

#define int long long // at least int64 > 9*10^18
#define ENDL '\n'
#define rep(i,n) for(int i = 0; i < (n); i++)
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
/* libraries */

struct UnionFind
{
  int n;
  std::vector<int> par,size;
  UnionFind(int sz) : n(sz), par(sz,0), size(sz,1) {
    std::iota(par.begin(),par.end(),0);
  }
  int find(int x) {
    if(par[x]==x) return x;
    return par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    x=find(x);y=find(y);
    if(x==y) return;
    if(size[x]<size[y]) std::swap(x,y);
    size[x]+=size[y];
    par[y]=x;
  }
};


signed main() {
	int n,m;
	std::cin >> n >> m;
	std::vector<int> ans(m);
	std::vector<std::pair<int,int> > inp;
	UnionFind uf(n);
	int inconv = n*(n-1)/2;
	rep(i,m) {
		int a,b;
		std::cin >> a >> b;
		a--;b--;
		inp.emplace_back(a,b);
	}
	std::reverse(all(inp));
	rep(i,m) {
		ans[m-i-1] = inconv;
		int a=inp[i].first;
		int b=inp[i].second;
		if(uf.find(a)!=uf.find(b)) inconv -= uf.size[uf.find(a)]*uf.size[uf.find(b)];
		debug(a,b,uf.size[uf.find(a)]*uf.size[uf.find(b)]);
		debug(inconv,uf.size[uf.find(a)]);
		uf.unite(a,b);
	}
	for(int x:ans) print(x);

	return 0;
}


Measured memory_bytes: 5360
def init():
  global top
  top = 0

def isEmpty():
  global top
  return top == 0

def isFull():
  global top, MAX
  return top >= MAX

def push(x):
  global top, s
  if isFull():
    return False
  s[top] = x
  top += 1


def pop():
  global top, s
  if isEmpty():
    return False
  top -= 1
  return s[top]


def calc(i_1, i_2, op):
  if op == '+':
    return i_1 + i_2
  elif op == '-':
    return i_1 - i_2
  else:
    return i_1 * i_2

data = list(map(str, input().split()))
top = 0
MAX = 100
s = [0 for i in range(MAX)]
for i in data:
  if i == '+' or i == '*' or i == '-':
    a = pop()
    b = pop()
    push(calc(int(b), int(a), i))
  else:
    push(i)
print(s[0])



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

using namespace std;

int main() {
	int a, b, c, d;
	scanf("%d%d%d%d", &a, &b, &c, &d);
	
	while (true) {
		c -= b;
		if (c <= 0) return 0 * printf("Yes\n");
		a -= d;
		if (a <= 0) return 0 * printf("No\n");
	}
}


Measured memory_bytes: 3740
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let t: String = read();
    let p: String = read();
    if t.len() < p.len() {
        return;
    }
    for index in 0..(t.len() - p.len() + 1) {
        if &t[index..index + p.len()] == p {
            println!("{}", index);
        }
    }
}



Measured memory_bytes: 5024
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 6)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")
al = "abcdefghijklmnopqrstuvwxyz"
AL = al.upper()

s = v()
for i in range(len(s)-1):
    if s[i] == s[i+1]:
        print("Bad")
        sys.exit()

print("Good")

Measured memory_bytes: 10412
#include <vector>
#include <cassert>
#include <iostream>
using namespace std;
const int mod = 1000000007;

int main(void) {
    int H, W, K;

    cin >> H >> W >> K;

    vector< vector<int> > dp(H+1, vector<int>(W, 0)); // make 2 dim list

    dp[0][0] = 1;

    for(int i=0; i<H; ++i) {
        for (int j=0; j<W; ++j) {
            for(int k=0; k < (1 << (W-1)); ++k) { // set bar using bits
                bool flag = true;

                for(int l=0; l < W-2; ++l) { 
                    if  (((k >> l) & 1) && ((k >> (l+1)) & 1))  { // slide bits for number l

                        flag = false; // invalid case
                    }
                }

                if (flag) {
                    if (j>=1 && ((k >> (j-1)) & 1)) {
                        dp[i+1][j-1] += dp[i][j];
                        dp[i+1][j-1] %= mod;

                    } else if (j <= W-2 && ((k >> j) & 1)) {
                        dp[i+1][j+1] += dp[i][j];
                        dp[i+1][j+1] %= mod;
                    } else {
                        dp[i+1][j] += dp[i][j];
                        dp[i+1][j] %= mod;
                    }

                }
            }
        }
    }

    cout << dp[H][K-1] << endl;
}




Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
ll t,a,b,c,i,j,k,n,m,arr[100005],flag[100005];
int main(){
	string s;
	scanf("%lld",&n);
	cin>>s;
	for(i=0;i<s.length();i++){
        a=s[i]-'A';
        a=(a+n)%26;
        s[i]='A'+a;
	}
	cout<<s;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    long long int x;
    cin>>x;
    long long int sum=0;
    long long int tmp500=x/500;
    sum+=tmp500*1000;
    x-=tmp500*500;
    long long int tmp5=x/5;
    sum+=tmp5*5;
    cout<<sum<<endl;
}

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

#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

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

    constexpr auto M = 1000000007L;

    vector<int64_t> dp(4);
    dp[0] = 1;
    for (auto c : s) {
        if (c == '?') {
            dp[3] = 3 * dp[3] + dp[2];
            dp[3] %= M;
            dp[2] = 3 * dp[2] + dp[1];
            dp[2] %= M;
            dp[1] = 3 * dp[1] + dp[0];
            dp[1] %= M;
            dp[0] = 3 * dp[0];
            dp[0] %= M;
        }
        if (c == 'C') {
            dp[3] += dp[2];
            dp[3] %= M;
        }
        if (c == 'B') {
            dp[2] += dp[1];
            dp[2] %= M;
        }
        if (c == 'A') {
            dp[1] += dp[0];
            dp[1] %= M;
        }
        cerr << dp[0] << "," << dp[1] << "," << dp[2] << "," << dp[3] << endl;
    }

    cout << dp[3] << endl;
}

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

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define fr(i,k) for(i=0;i<k;i++)
#define ALL(c) (c).begin(),(c).end()
#define deb(x) cerr<<#x<<"  = "<<x<<endl;
#define SZ(x) (x).size();
#define ll long long
#define MOD 1000000007
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define em emplace_back
#define ulli unsigned long long int
#define INF 1e18
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<int, int> ii;
void solve();

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}

int main() {
	fastio;
/*#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif*/

	int t;
	t=1;

    //cin>>t;
	while (t--)
	{
		solve();
	}
	return 0;
}

ll calc(ll a[],ll i,ll j,vector<vector<ll>> &sum,vector<vector<ll>> &dp)
{
    if(i==j)
        return 0;

    if(dp[i][j]!=-1)
        return dp[i][j];

    ll ans=INF;

    for(int k=i;k<j;k++)
    {
        ans=min(ans,sum[i][j]+calc(a,i,k,sum,dp)+calc(a,k+1,j,sum,dp));
    }

    return dp[i][j]=ans;
}

void solve()
{
	ll n,i,j,k,c;
	cin>>n;

	ll a[n+1];

	for(i=1;i<=n;i++)
        cin>>a[i];

    vector<vector<ll>> dp(n+1,vector<ll>(n+1,-1));
    vector<vector<ll>> sum(n+1,vector<ll>(n+1));

    for(i=1;i<=n;i++)
    {
        for(j=i;j<=n;j++)
        {
            if(i==j)
                sum[i][j]=a[j];
            else
                sum[i][j]=sum[i][j-1]+a[j];
        }
    }

    cout<<calc(a,1,n,sum,dp)<<endl;
}


Measured memory_bytes: 5816
/**
 *      purpose : 
 *      author  : kyomukyomupurin
 *      created : 
**/

// input/output
#include <iostream>
#include <fstream>
#include <sstream>
// container class
#include <array>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// math, algorithm
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
// etc
#include <bitset>
#include <cassert>
#include <cctype>
#include <cstring>
#include <chrono>
#include <iomanip>
#include <random>
#include <utility>
// using-directive
using namespace std;
// alias template
using int64 = int64_t;
using pii = pair<int, int>;
using pll = pair<int64_t, int64_t>;
// text macro replacement
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define print(x) cout << (x) << '\n'
#define debug(x) cout << #x << ": " << (x) << '\n'
// variadic template
template<typename T> inline void chmax(T &a, T b) { if (a < b) a = b; return; }
template<typename T> inline void chmin(T &a, T b) { if (a > b) a = b; return; }

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m; cin >> n >> m;
  vector<int> l(m), r(m);
  for (int i = 0; i < m; ++i) {
    cin >> l[i] >> r[i];
    --l[i]; --r[i];
  }

  int sum[n] = {};
  for (int i = 0; i < m; ++i) {
    ++sum[l[i]]; --sum[r[i] + 1];
  }
  for (int i = 0; i < n - 1; ++i) {
    sum[i + 1] += sum[i];
  }
  int ans = 0;
  //int mx = *max_element(sum, sum + n + 1);
  for (int i = 0; i < n; ++i) {
    ans += sum[i] == m;
  }
  print(ans);

  return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define int long long
#define ll long long
using ull = unsigned long long;
using namespace std;
#define dump(x)                             \
    if (dbg) {                              \
        cerr << #x << " = " << (x) << endl; \
    }
#define overload4(_1, _2, _3, _4, name, ...) name
#define FOR1(n) for (ll i = 0; i < (n); ++i)
#define FOR2(i, n) for (ll i = 0; i < (n); ++i)
#define FOR3(i, a, b) for (ll i = (a); i < (b); ++i)
#define FOR4(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FORR(i, a, b) for (int i = (a); i <= (b); ++i)
#define bit(n, k) ((n >> k) & 1) /*nのk bit目*/
namespace mydef {
const int INF = 1ll << 60;
const int MOD = 1e9 + 7;
template <class T>
bool chmin(T& a, const T& b) {
    if (a > b) {
        a = b;
        return 1;
    } else
        return 0;
}
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    } else
        return 0;
}
void Yes(bool flag = true) {
    if (flag)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}
void No(bool flag = true) {
    Yes(!flag);
}
void YES(bool flag = true) {
    if (flag)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}
void NO(bool flag = true) {
    YES(!flag);
}
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T& val) {
    std::fill((T*)array, (T*)(array + N), val);
}
bool dbg = false;
}  // namespace mydef
using namespace mydef;
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(), (v).end()
#define SZ(x) ((int)(x).size())
#define vi vector<int>
#define vvi vector<vector<int>>
#define vp vector<pair<int, int>>
#define vvp vector<vector<pair<int, int>>>
#define pi pair<int, int>
//#define P pair<int, int>
//#define V vector<int>
//#define S set<int>
#define asn ans

int N, a[202020];

void solve() {
    vp V;
    for (int i = 0; i < N; i++) {
        V.emplace_back(a[i], i);
    }
    sort(all(V));
    set<int> seen;
    seen.insert(-1);
    seen.insert(N);
    int ans = 0;
    for (auto& p : V) {
        int b = p.first;
        int x = p.second;
        auto it = seen.lower_bound(x);
        int r = *it;
        it--;
        int l = *it;
        ans += b * (x - l) * (r - x);
        seen.insert(x);
    }
    cout << ans << endl;
}

signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

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

    solve();
    return 0;
}


Measured memory_bytes: 17388
s = input()
n = len(s)
if s == "keyence":
    print("YES")
    exit(0)
for i in range(n-2):
    for j in range(i+1,n-1):
        if s[0:i+1]+s[j+1:n] == "keyence":
            print("YES")
            exit(0)
print("NO")

Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,s,n) for(int i=s;i<n;i++)
typedef long long ll;
using namespace std;
ll dp[110][110],a[110],b[110];
int main(){
  int n;cin>>n;
  lol(i,0,n){
    cin>>a[i]>>b[i];
    lol(j,0,n)dp[i][j]=(1<<30);
  }
  lol(i,0,n)dp[i][i]=0;
  lol(k,1,n){
    lol(i,0,n-k){
      int to=i+k;
      lol(j,i,to){
	dp[i][to]=min(dp[i][to],dp[i][j]+dp[j+1][to]+a[i]*b[j]*a[j+1]*b[to]);
      }
    }
  }
  cout<<dp[0][n-1]<<endl;
  return 0;
}

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

int main() {
  int a, b;
  cin >> a >> b;
  int c = a * b;
  if (c % 2 == 0) {
      cout << "Even" << endl;
  } 
  else {
      cout << "Odd" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int  
ll a[100];
int main() {
	// your code goes here
	ll i,j,k,n,m;
	
	cin>>n;
	double re=0.0,s;
for(i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
ll sum=a[1]+a[2];
ll po=2;
for(i=3;i<=n;i++){
    sum+=po*a[i];
    po*=2;
}
re=(double)sum/(double)(po);
printf("%0.6f",re);
	return 0;
}


Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {
	public static void main(String[] args){
		FastScanner sc = new FastScanner();
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		String result = "NO";
		for(int i=1; i< 1000;i++){
			if((a*i)%b == c){
				result = "YES";
				break;
			}
		}
		System.out.println(result);
	}
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
}

Measured memory_bytes: 21204
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
  string s,t;
  cin >> s >> t;
  int len = s.length();
  int flag = 0;
  if(s == t){
    printf("Yes");
  } else {
    for(int i=0;i<len;i++){
      s = s[len-1]+s;
      s.erase(s.begin()+len);
      if(s == t){
        printf("Yes");
        flag = 1;
        break;
      }
    }
    if(flag == 0){
      printf("No");
    }

  }
  return 0;
}

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

typedef long long int ll;
#define INF 1999999999
#define MODA 1000000007

int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    if(s[2] == s[3] && s[4] == s[5])
    {
        cout << "Yes" << endl;
    }
    else
    {
         cout << "No" << endl;
    }
    return 0;
}


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

int main () {
  int n, m;
  long long s, ss;
  cin >> n >> m;
  map<long long, int> a;
  map<long long, int> b;
  for (int i = 0; i < m; i++) {
    cin >> s >> ss;
    if (s == 1) {
      a[ss] = 1;  
    }  
    if (ss == n) {
      b[s] = 1;  
    }
  }
  for (auto itr = a.begin(); itr != a.end(); ++itr) {
    if (b[itr->first] >= 1) {
      cout << "POSSIBLE" << endl;
      return 0;  
    }  
  }
  cout << "IMPOSSIBLE" << endl;
    
}

Measured memory_bytes: 20736
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		String words = sc.next();
		sc.close();

		ArrayList<Integer> AList = new ArrayList<>();
		ArrayList<Integer> ZList = new ArrayList<>();

		for(int i = 0; i < words.length(); i++) {
			char character = words.charAt(i);

			if(character == 'A') {
				AList.add(i);
			}else if(character == 'Z') {
				ZList.add(i);
			}
		}

		int aa = AList.get(0);
		int zz = ZList.get(ZList.size()-1);

		System.out.println(zz-aa+1);

	}

}


Measured memory_bytes: 32024
#include <stdio.h>

int main(){
	char s[10];
	int t;
	int ac = 0,wa = 0,tle = 0,re = 0;
	scanf("%d",&t);
		for(int i=0;i<t;i++){
			scanf("%s",s);
			if(s[0]=='A') ac++;
			else if(s[0]=='W') wa++;
			else if(s[0]=='T') tle++;
			else if(s[0]=='R') re++;
		}
	printf("AC x %d\n",ac);
	printf("WA x %d\n",wa);
	printf("TLE x %d\n",tle);
	printf("RE x %d\n",re);
	return 0;
}

Measured memory_bytes: 2140
a,b = map(int,input().split())

def func(x):
    if x % 4 == 0:
        return x
    elif x % 4 == 1:
        return 1
    elif x % 4 == 2:
        return x+1
    else:
        return 0
        
print(func(b) ^ func(a) ^ a)

Measured memory_bytes: 2940
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    int N,K,l[100],sum=0;
    cin >> N >> K;
    for (int i=0;i<N;i++){
        cin >> l[i];
    }
    sort(l,l+N);
    for (int i=N-1;i>=N-K;i--){
        sum+=l[i];
    }
    cout << sum;
}

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

using namespace std;

int main() {
    long long  w,h,x,y;
    cin>>w>>h>>x>>y;
    double area =double(w)*double(h)/2;
    printf("%.12f ",area);
    if(x*2==w&&y*2==h)
    cout<<1<<" ";
    else
    cout<<0<<" ";
    
    
    return 0;
}

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

typedef long long ll;

ll gcd(ll a, ll b) {
	return b == 0 ? a : gcd(b, a % b);
}

int main() {
	ll a, b; cin >> a >> b;
	ll maxN = gcd(a, b);

	int ans = 1;
	for (ll i = 2; i * i <= maxN; i++) {
		if (maxN % i == 0) {
			ans++;
			while (maxN % i == 0)maxN /= i;
		}
	}
	cout << (maxN != 1 ? ans + 1 : ans) << endl;

	return 0;
}

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

using namespace std;
typedef unsigned long long ull;
typedef long long ll;

int main() {
    //ios::sync_with_stdio(0);
    //cin.tie(0);
    int n;
    cin >> n;
    int res = 0;
    res += (n/500)*1000;
    n %= 500;
    res += (n/5)*5;
    cout << res << endl;
}

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

int main() {
    long long N, A, B, C, D, E;
    cin >> N >> A >> B >> C >> D >> E;
    cout << max({ (N - 1) / A, (N - 1) / B, (N - 1) / C, (N - 1) / D, (N - 1) / E }) + 5 << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; 
#define INF 1000000000
#define mod 1000000007
typedef long long ll;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
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; }


int n;
vector<vector<int>> g;
string s[200];
vector<int> dis;
vector<bool> checked;


int solve(int st){
    dis=vector<int>(n,INF);
    dis[st]=0;
    checked=vector<bool>(n,false);
    queue<pair<int,int>> q;
    q.push(make_pair(st,0));
    checked[st] = true;
    while(!q.empty()){
        auto now=q.front();
        q.pop();
        for(auto x:g[now.first]){
            if(checked[x]){
                continue;
            }
            else{
                dis[x]=now.second+1;
                q.push(make_pair(x,now.second+1));
                checked[x]=true;
            }
        }
    }

    rep(i,n){
        for(int j=i+1;j<n;j++){
            if(s[i][j]=='1'){
                if(abs(dis[i]-dis[j])!=1)return -1;
            }
        }
    }

    int ret=0;
    rep(i,n){
        ret=max(ret,dis[i]);
    }
    return ret+1;
}


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

    cin>>n;
    g.resize(n);

    rep(i,n){
        cin>>s[i];
    }
    rep(i,n){
        for(int j=i+1;j<n;j++){
            if(s[i][j]=='1'){
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }

    int ans=-1;
    rep(i,n){
        ans=max(ans,solve(i));
    }
    cout<<ans<<endl;
    return 0;
}


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

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if ((a <= b) && (b <= c)) {
        cout << a << " " << b << " " << c << endl;
    }
    else if ((a <= c) && (c <= b)) {
        cout << a << " " << c << " " << b << endl;
    }
    else if ((b <= a) && (a <= c)) {
        cout << b << " " << a << " " << c << endl;
    }
    else if ((b <= c) && (c <= a)) {
        cout << b << " " << c << " " << a << endl;
    }
    else if ((c <= a) && (a <= b)) {
        cout << c << " " << a << " " << b << endl;
    }
    else {
        cout << c << " " << b << " " << a << endl;
    }
    return 0;
}



Measured memory_bytes: 3096
/*
　　こんにちは。あたしはｶｳｶﾞｰﾙ。
　　redcoderになるためAtCoderを巡る旅をしてます。

　　　 　 ＿_
　　　 ヽ|＿_|ノ　　　　ﾓｫ
　　　　||‘‐‘||ﾚ　　_)_, ―‐ 、
　　　　/(Ｙ (ヽ＿ /・ ヽ　　 ￣ヽ
　　　　∠ ＿ ゝ　 ｀^ヽ ﾉ.::::_(ノヽ
　　　　 _/ヽ　 　　  /ヽ￣￣/ヽ
*/




#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define dump(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) << endl

#define rep(i, n) REP(i, 0, n)                              // 0, 1, ..., n-1
#define REP(i, x, n) for(int i = x; i < n; i++)             // x, x + 1, ..., n-1
#define FOREACH(x,a) for(auto& (x) : (a) )

#define ALL(v) (v).begin() , (v).end()
#define RALL(v) (v).rbegin(), (v).rend()

#define COUT(x) cout << (x) << endl

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; }

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

    int n; cin >> n;
    vector<int> a(n);
    int max1 = 0;
    int max2 = 0;
    rep(i, n) {
        cin >> a[i];
    }
    vector<int> b = a;
    sort(RALL(b));
    max1 = b[0];
    max2 = b[1];
    rep(i, n) {
        if(a[i] == b[0]) {
            cout << max2 << endl;
        } else {
            cout << max1 << endl;
        }
    }

}


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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second

using vint=vector<int>;
using pint=pair<int,int>;
using vpint=vector<pint>;

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

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
    ost<<"{"<<p.first<<","<<p.second<<"}";
    return ost;
}

template<class T>
ostream& operator<<(ostream& ost,const vector<T>&v){
    ost<<"{";
    for(int i=0;i<v.size();i++){
        if(i)ost<<",";
        ost<<v[i];
    }
    ost<<"}";
    return ost;
}

inline int topbit(unsigned long long x){
    return x?63-__builtin_clzll(x):-1;
}

inline int popcount(unsigned long long x){
    return __builtin_popcountll(x);
}

inline int parity(unsigned long long x){
    return __builtin_parity(x);
}

signed main(){
	string s,t;
	cin>>s>>t;
	int cnt=0;
	rep(i,s.size())cnt+=s[i]!=t[i];
	cout<<cnt<<endl;
    return 0;
}


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

int main()
{
    int Q;
    cin >> Q;
    for (int i = 0; i < Q; i++) {
        string X, Y;
        cin >> X >> Y;
        int x, y;
        x = X.size();
        y = Y.size();
        // dp[i][j] := X[i], Y[j] まで見た時のLCS
        int dp[x + 5][y + 5];
        for (int i = 0; i < x + 5; i++) {
            for (int j = 0; j < y + 5; j++) {
                dp[i][j] = 0;
            }
        }
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                if (X[i] == Y[j]) {
                    dp[i + 1][j + 1] = max({ dp[i][j] + 1, dp[i + 1][j], dp[i][j + 1] });
                } else {
                    dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
                }
            }
        }
        printf("%d\n", dp[x][y]);
    }
}



Measured memory_bytes: 7224
import java.util.Scanner;

public class Main{
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n;
		char train[];
		
		n = sc.nextInt();
		for (int i = 0; i < n; i++) {
			String str = sc.next();
			train = new char[2049];
			int strIndex = 0;
			int trainIndex = 1024;
			int maxIndex = 1024;
			int minIndex = 1024;
			while (true) {
				train[trainIndex] = str.charAt(strIndex);
				strIndex += 2;
				if (str.length() < strIndex) {
					break;
				}
				if (str.charAt(strIndex) == '>') {
					trainIndex++;
				} else if (str.charAt(strIndex) == '-') {
					trainIndex--;
				}
				strIndex++;
				if (maxIndex < trainIndex) {
					maxIndex = trainIndex;
				} else if (trainIndex < minIndex) {
					minIndex = trainIndex;
				}
			}
			
			for (int j = minIndex; j <= maxIndex; j++) {
				System.out.print(train[j]);
			}
			System.out.println();
		}
	}
}

Measured memory_bytes: 12000
#include <bits/stdc++.h>
#define INF 1000000000
using namespace std;

int main()
{
  int N;
  cin >> N;
  vector<int> p(N);
  vector<int> q(N);
  for (int i = 0; i < N; ++i)
  {
    cin >> p.at(i);
  }
  for (int i = 0; i < N; ++i)
  {
    cin >> q.at(i);
  }
  for (int i = 0; i < N; ++i)
  {
    if (p.at(i) > q.at(i))
    {
      p.swap(q);
      break;
    }
    else if (p.at(i) < q.at(i))
    {
      break;
    }
  }
  int ans = 0;
  if (p == q)
  {
    cout << 0 << endl;
    return 0;
  }
  while (next_permutation(p.begin(), p.end()))
  {
    if (p == q)
    {
      break;
    }
    ans += 1;
  }
  // for (int i = 0; i < N; ++i)
  // {
  //   cout << p.at(i);
  // }
  cout << ans + 1 << endl;
}


Measured memory_bytes: 256
import heapq

q = int(input())

# 中央値との大小で集団を２つに分けて管理したいぞ
_,a,b = map(int, input().split())
a_large = []
a_small = [-a]
cnt_large = 0
cnt_small = 1
mean = 0
cons = b
total = 0

for i in range(q-1):
    query = input()
    if query[0] == '1':
        _,a,b = map(int, query.split())
        cons = cons + b
        if a < -a_small[0]:
            # 最大ヒープ
            heapq.heappush(a_small, -a)
            total += -(a - -a_small[0])
            cnt_small += 1
            if cnt_small > cnt_large + 1:
                old_mean = -a_small[0]
                heapq.heappush(a_large, -heapq.heappop(a_small))
                cnt_small -= 1
                cnt_large += 1
                new_mean = -a_small[0]
                total += (new_mean- old_mean) * (cnt_large - cnt_small)
        else:
            # 最小ヒープ
            heapq.heappush(a_large, a)
            total += (a - -a_small[0])
            cnt_large += 1
            if cnt_large > cnt_small:
                old_mean = -a_small[0]
                heapq.heappush(a_small, -heapq.heappop(a_large))
                cnt_small += 1
                cnt_large -= 1
                new_mean = -a_small[0]
                total += (new_mean-old_mean) * (cnt_large - cnt_small)
    else:
        x = -a_small[0]
        print(x, total+cons)


        

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

int main()
{
    int n, m;
    int A[100][100] = {};
    int b[100] = {};
    cin >> n >> m;
    // read A
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            cin >> A[i][j];
        }
    }
    // read b
    for (int i = 0; i < m; i++)
    {
        cin >> b[i];
    }

    // product Ab
    int product;
    for (int i = 0; i < n; ++i)
    {
        product = 0;
        for (int j = 0; j < m; ++j)
        {
            product += A[i][j] * b[j];
        }
        cout << product << endl;
    }
}


Measured memory_bytes: 3144
"use strict"

const Main= (inpuut)=>{
  const number =inpuut.trim().split(" ").join("")-0
  const heihoukon=Math.pow(number,1/2)
  Number.isInteger(heihoukon)? console.log("Yes"):console.log("No")
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 22208
def ascan; gets.split.map(&:to_i);end

N = gets.to_i

dp = [N]*(N+1)
dp[0] = 0

N.times do |ptr|
    0.upto(9) do |i|
        hop = 6**i
        break if ptr+hop > N
        dp[ptr+hop] = [dp[ptr+hop], dp[ptr]+1].min
    end
    1.upto(9) do |i|
        hop = 9**i
        break if ptr+hop > N
        dp[ptr+hop] = [dp[ptr+hop], dp[ptr]+1].min
    end
end

p dp[N]

## 備忘録として他の方のコードを提出させていただきます

Measured memory_bytes: 2556
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>
#include <string>
#include <stack>
#define FI first
#define SE second
#define PF push_front
#define PB push_back
#define PPF pop_front
#define PPB pop_back
#define MA make_pair
#define ll long long
#define PA pair<int,int>
#define VE vector<int>
#define VP vector<PA>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
using namespace std;
//
const int INF=1e9+7;
const int mod=1e9+7;
//
//
struct poi{
  int X;int Y;int Z;
  bool operator<(const poi&R)const{
    return X==R.X ? Y==R.Y ? Z<R.Z : Y<R.Y : X<R.X;
  }
};
//
//
int main(){
	int N;
	string S;
	cin>>N;
	cin>>S;
	deque<char> que;
	stack<char> st;
	int now=0;
	if(S[now]==')'){
		while(S[now]==')'){
			now++;
		}
		FOR(i,0,now){
			que.PF('(');
			que.PB(')');
		}
	}
	while(now<N){
		if(S[now]=='('){
			while(S[now]=='('){
				st.push('(');
				que.PB('(');
				now++;
			}
		}else{
			int cnt=0;
			while(now<N&&S[now]==')'&&!st.empty()){
				now++;
				cnt++;
				st.pop();
			}
			if(now<N&&S[now]==')'){
				while(now<N&&S[now]==')'){
					now++;
					cnt++;
					que.PF('(');
				}
			}
			FOR(i,0,cnt){
				que.PB(')');
			}
		}
	}
	int cnt=st.size();
	while(!st.empty()){
		st.pop();
		que.PB(')');
	}
	while(!que.empty()){
		cout<<que.front();
		que.PPF();
	}
	cout<<endl;
	return 0;
}


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

tmp = input().split(" ")
nums = []
for i in tmp:
    nums.append(int(i))

flag = 1
count = 0
while flag:
    flag = 0
    for i in range(time-1,0,-1):
        #ここにはいってない
        if nums[i] < nums[i-1]:
            count += 1
            a = nums[i-1]
            nums[i-1] = nums[i]
            nums[i] = a
            flag = 1

print(' '.join(map(str,nums)))
print(count)



Measured memory_bytes: 5600
n, m = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  g[a].append(b)
  g[b].append(a)

visit = [-1]*n
from collections import deque
s = deque()
s.append(0)
visit[0] = 0
flag = 0
while s:
  x = s.pop()
  for new_x in g[x]:
    if visit[new_x] == -1:
      visit[new_x] = (visit[x]+1)% 2
      s.append(new_x)
    elif visit[new_x] == visit[x]:
      flag = 1
      break
    else:
      continue
if flag == 0:
  print(sum(visit)*(n-sum(visit))-m)
else:
  print(n*(n-1)//2-m)
      

Measured memory_bytes: 60908