akhauriyash/Code-Regression huggingface dataset:
object Main extends App {
  val Array(n, k) = io.StdIn.readLine().split(' ').map(_.toInt)
  val k2 = k*2
  val end = k2-1
  // 0 ≦ x,y ≦ 2K に圧縮
  val squares = Array.fill(k2)(Array.fill(k2)(0))
  for (i <- 1 to n) {
    val Array(x, y, color) = io.StdIn.readLine().split(' ')
    // 'W'はY方向にKずらした'B'と同値
    squares(x.toInt % k2)((y.toInt + (if (color == "B") 0 else k)) % k2) += 1
  }
  // 計算量削減のために累積和を事前算出
  for {
    i <- 0 to end
    j <- 1 to end
  } squares(i)(j) += squares(i)(j-1)
  for {
    j <- 0 to end
    i <- 1 to end
  } squares(i)(j) += squares(i-1)(j)
  var max = 0
  for {
    i <- 0 to k-1
    j <- 0 to k-1
  } {
    // ex) k = 2
    //      ■ □ □ ■ 
    //  j+k □ ■ ■ □
    //      □ ■ ■ □
    //    j ■ □ □ ■
    //      i   i+k
    val cnt =
      (squares(i)(j)) +
      (squares(end)(j) - squares(i+k)(j)) +
      (squares(i+k)(j+k) - squares(i+k)(j) - squares(i)(j+k) + squares(i)(j)) +
      (squares(i)(end) - squares(i)(j+k)) +
      (squares(end)(end) - squares(end)(j+k) - squares(i+k)(end) + squares(i+k)(j+k))
    max = Math.max(Math.max(cnt, n - cnt), max)
  }
  print(max)
}


Measured memory_bytes: 87932
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#define MAX_N 1002
using namespace std;

typedef long long ll;
typedef pair<int,int> P1;
typedef pair<P1,ll> P2;
typedef pair<double,int> Pdi;
const ll INF=100000000000000001;
int dp1[MAX_N][MAX_N]={};
int dp2[MAX_N][MAX_N]={};
bool d[MAX_N]={};
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
priority_queue<Pdi,vector<Pdi>,greater<Pdi>> que;
vector<P1> v;
P2 xy[MAX_N]={};

double calc(int xx1,int xx2,int yy1,int yy2){
	double f=pow((double)xx1-(double)xx2,2)+pow((double)yy1-(double)yy2,2);
	return pow(f,0.5);
}
int main() {
//	printf("%f\n",calc(-2,2,-2,2));
	int x1,y1,x2,y2,r1;
	cin>>x1>>y1>>x2>>y2;
	xy[0]=P2(P1(x1,y1),0);
	xy[1]=P2(P1(x2,y2),0);
	int n;
	cin>>n;
	rep(i,n){
		cin>>x2>>y2>>r1;
		xy[i+2]=P2(P1(x2,y2),r1);
	}
	que.push(Pdi(0.0,0));
//	printf("%d,%d,%f\n",xy[0].first.first,xy[0].first.second,xy[0].second);
//	printf("%d,%d,%f\n",xy[1].first.first,xy[1].first.second,xy[1].second);
	while(!que.empty()){
		Pdi pd1=que.top();que.pop();
		double cost=pd1.first;
		int to=pd1.second;
		if(to==1){
			printf("%.9f\n",cost);
			return 0;
		}
		if(d[to])continue;
		d[to]=true;
		rep(i,n+1){
			if(i+1!=to){
				x1=xy[to].first.first;
				y1=xy[to].first.second;
				x2=xy[i+1].first.first;
				y2=xy[i+1].first.second;
				double ncost=cost+max(0.0,calc(x1,x2,y1,y2)-xy[to].second-xy[i+1].second);
//				printf("%f %d %d %d %d %d %d\n",ncost,i+1,to,x1,x2,y1,y2);
				que.push(Pdi(ncost,i+1));
			}
		}
	}
	return 0;
}


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

using namespace std;

bool notP[10000005];

int prime[1000005], tot = 0;

void getPrime() {
    int n = 10000000;
    for (int i = 2; i <= n; ++i) {
        if (!notP[i])
            prime[tot++] = i;
        for (int j = 0; j < tot && i * prime[j] <= n; ++j) {
            notP[i * prime[j]] = true;
            if (i % prime[j] == 0)
                break;
        }
    }
}

vector <int> A[2];

vector <int> G[105];

int mat[105], used[105], tag = 0;

int dfs(int u) {
    for (auto v : G[u]) {
        if (used[v] == tag)
            continue;
        used[v] = tag;
        if (mat[v] == -1 || dfs(mat[v])) {
            mat[v] = u;
            return 1;
        }
    }
    return 0;
}

int main() {
    getPrime();
    int n, p = -1;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        int x;
        scanf("%d", &x);
        if (p != x - 1) {
            if (p != -1)
                A[(p + 1) & 1].push_back(p + 1);
            A[x & 1].push_back(x);
        }
        p = x;
    }
    A[(p + 1) & 1].push_back(p + 1);
    for (int i = 0; i < (int)A[0].size(); ++i) {
        for (int j = 0; j < (int)A[1].size(); ++j) {
            int d = abs(A[0][i] - A[1][j]);
            if (d >= 3 && !notP[d])
                G[i].push_back(j);
        }
    }
    memset(mat, -1, sizeof(mat));
    int k = 0;
    for (int i = 0; i < (int)A[0].size(); ++i) {
        ++ tag;
        k += dfs(i);
    }
    int ans = k + (A[0].size() - k) / 2 * 2 + (A[1].size() - k) / 2 * 2;
    if ((A[0].size() - k) % 2)
        ans += 3;
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 14080
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    /* ll t;
    cin>>t;
    while(t--) */
    {
        ll i,j,k,l,m,n,a,b,c,d,cnt=0,p=0,q;
        cin>>n;
        ll arr[n+1];
        map <int,int> mp;
        for(i=1;i<=n;i++)
        {
            cin>>arr[i];
            cnt+=mp[i-arr[i]];
            mp[i+arr[i]]++;
        }

        cout<<cnt<<endl;

    }
}


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

    #define all(v) v.begin(),v.end()
    #define rall(v) v.rbegin(),v.rend()
    #define trav(i,a) for(auto i: a)
    #define ff first
    #define ss second
    #define eb emplace_back
    #define tc(t) ll t; cin>>t; while(t--)
    #define prec(n) fixed<<setprecission(n)
    #define mst(arr,value) memset(arr,value,sizeof(arr))
    #define sz(a) a.size()
    #define fio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    
    const long long inf = (long long)1e18;
    const long long M = (long long)1e9+7;
    
    #define fab(i,a,b) for(ll i=a; i<b; i++)
    #define fba(i,b,a) for(ll i=b; i>=a; i--)

    ll mpw(ll a, ll b, ll M = inf) {
        if(b == 0) return 1;
        if(b % 2 == 1) 
            return a * mpw((a * a) % M, b / 2, M) % M;
        return mpw((a * a) % M, b / 2, M);        
    }
    

    int main() {
        fio


        ll n;
        cin >> n;
        vector<ll> v(n);
        vector<ll> dp(n, 0);
        fab(i, 0, n) 
            cin >> v[i];
        
        fab(i, 1, n) {
            dp[i] = dp[i - 1] + abs(v[i] - v[i - 1]);
            if(i > 1)
                dp[i] = min(dp[i], dp[i - 2] + abs(v[i] - v[i - 2]));
        }
        
        cout << dp[n - 1];

        
        return 0;
    }

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

int main() {
  string s;
  cin >> s;
  int result = 0;
  for (int i = 0, j = 0; i < s.size(); i++) {
    if (s[i] == 'g') {
      if (j > 0) {
        j--;
        result++;
      } else {
        j++;
      }
    } else {
      if (j > 0) {
        j--;
      } else {
        j++;
        result--;
      }
    }
  }
  cout << result;
  return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const long long LINF=8101145141919364364;

int main(){
	int n,k; cin>>n>>k;
	int p[26]={};
	rep(i,n){
		string s; cin>>s;
		p[s[0]-'A']++;
	}
	int ans=0;
	while(1){
		sort(p,p+26); reverse(p,p+26);
		for(int i=0;i<k;i++){
			p[i]--;
			if(p[i]<0){
				cout<<ans<<endl;
				return 0;
			}
		}
		ans++;
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b) - 1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)

#define PB push_back
#define INF INT_MAX/3
#define ALL(a) (a).begin(),(a).end()
#define CLR(a) memset(a,0,sizeof(a))

typedef long long int ll;

using namespace std;

int dp[41];


int main(){
    memset(dp,0,sizeof(dp));
    dp[0] = 1;
    for(int j=0;j<30;j++){
	for(int i=1;i<=3;i++){
	    dp[i+j] += dp[j];
	}
    }
    while(true){
	int n;
	cin >> n;
	if(n == 0) break;
	int fact = dp[n]/10 + ((dp[n]%365==0) ? 0 : 1) ;
	cout << fact/365 + ((fact%365==0) ? 0 : 1) << endl;
    }
    return 0;
}

Measured memory_bytes: 1156
#include <stdio.h>
long long n, ans;
int main() {
	scanf("%lld", &n);
	if (n % 2) {
		printf("0\n");
		return 0;
	}
	n /= 2;
	while (n) {
		ans += n / 5;
		n /= 5;
	}
	printf("%lld\n", ans);
}


Measured memory_bytes: 1712
a,b,c = map(int, input().split())
k = int(input())

while not (a<b and b<c):
    if a>=b :
        b*=2
        k-=1
    if b>=c :
        c*=2
        k-=1

if(k<0):
    print("No")
else:
    print("Yes")

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

int main() {
  ll n; cin >> n;
  ll sum = 0;
  REP (i, n) {
    if (i % 3 != 0 && i % 5 != 0) sum += i;
  }
  
  cout << sum << endl;
  
  return 0;
}


Measured memory_bytes: 3636
N = int(input())
D = [int(s) for s in input().split()]

maximum = max(D)
max_distance = [i+1 for i in range(maximum)]
count_list = [0 for i in range(maximum+1)]
for i in D:
  count_list[i] += 1
if D[0] != 0 or count_list[0] != 1:
  print(0)
  exit()

stock = 1
for i in max_distance:
  count_1 = count_list[i-1]
  count_2 = count_list[i]
  if count_1 == 0 or count_2 == 0:
    stock = 0
    break
  stock *= count_1**count_2

print(stock%998244353)

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

using ll = long long;

int main() {
  ll k;
  std::cin >> k;
  ll t = 0;
  ll m = 100;
  while (m < k) {
    m += m / 100;
    t++;
  }
  std::cout << t << std::endl;
  
}


Measured memory_bytes: 3600
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  string str;
  cin >> str;
  vector<int> num;
  sort(str.begin(), str.end());
  // cout << str << endl;
  // cout << (str[0] == str[1]) << endl;
  if (str.size() == 1) {
    cout << "No" << endl;
  } else {
    int j = 1;
    for (int i = 1; i < str.size(); i++) {
      char x = str[i - 1]; 
      if (str[i] == x) {
        j += 1;
      } else {
        char x = str[i];
        num.push_back(j);
        j = 1;
      }   
    }   

    for (int i = 0; i < num.size(); i++) {
      if (num[i] % 2 != 0) {
        // cout << i << num[i] << endl;
        cout << "No" << endl;
        return 0;
      }   
    }   

    cout << "Yes" << endl;
  }
}


Measured memory_bytes: 256
import sys
N, K = [int(x) for x in input().split()]

ans = 0
lower = 0
upper = 0
cnt = 0
p = 1000000007

for i in range(K,N+2):
  lower = i*(i-1)/2
  upper = i*(2*N-i+1)/2
  cnt += (upper - lower + 1) % p
  
ans = cnt % p
print(int(ans))

Measured memory_bytes: 9208
#include <iostream>
#include <vector>
#include <tuple>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <limits>
#include <unordered_map>

using namespace std;
using str = string;

#define rep(a,l,r) for(int a=(l);a<(r);a++)
#define get cin>>
#define put cout<<

int gcd_euclid(int u, int v) {
  int r;
  while (0 != v) {
    r = u % v; u = v; v = r; /* swap */
  }
  return u;
}

void run() {

	int n; get n;
	int x; get x;

	vector<int> city(n);

	rep(i,0,n){
		get city[i];
	}

	vector<int> distance(n);

	rep(i,0,n){
		if(city[i] < x){
			distance[i] = x-city[i];
		} else {
			distance[i] = city[i]-x;
		}
	}

	int gcd = *min_element(distance.begin(), distance.end());
	rep(i,0,n){
		gcd = gcd_euclid(gcd, distance[i]);
	}

	put gcd;



}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);run();return 0;}


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

int main() {
  vector<int> a(5),b(5);
  rep(i,0,5) {cin >> a[i]; b[i] = i;}
  sort(a.begin(), a.end());
  int ans = 1000;
  do {
    int k = 0;
    rep(i,0,5) {
      k += a[b[i]];
      if (i < 4) {
        while(k % 10 != 0) k++;
      }
    }
    ans = min(ans,k);
  } while(next_permutation(b.begin(), b.end()));
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3596
N = int(input())
A = [int(i) for i in input().split()]
ls = []
for i, x in enumerate(A):
    ls.append([i+1, x])
ls.sort(key=lambda x: x[1])
cur = 1
num = 0
ans = 0
s = set()
for x, y in ls:
    if cur == y and y not in s and num < x:
        cur += 1
        num = x
        s.add(y)
    else:
        ans += 1
if ans == N:
    print(-1)
else:
    print(ans)

Measured memory_bytes: 54016
# include "bits/stdc++.h"
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const double PI = acos(-1);
template<class T>constexpr T INF() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T HINF() { return INF<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        sort(ALL((wpwpw)));(wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define REP(i,upupu)         FOR(i,0,upupu)
# define INIT                 std::ios::sync_with_stdio(false);std::cin.tie(0)

int n;
string s;
int wcnt, bcnt;
int main(){
    cin >> n;
    cin >> s;
    REP(i, n)if(s[i] == '#')bcnt++;
    LL ans = n;
    REP(i, n + 1){
        ans = min(ans, (i - wcnt) + (n - i - bcnt));
        if(s[i] == '.')wcnt++;
        if(s[i] == '#')bcnt--;
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0)
//#define MULTI_TEST
//#define GOOGLE
#ifdef LOCAL
#include "debugger.h"
#else
#define db(...)
#endif
#define ll long long
#define v32 vector<int>
#define v64 vector<ll>
#define s32 set<int>
#define s64 set<ll>
#define p32 pair<int, int>
#define p64 pair<ll, ll>
#define sz(v) (ll)(v).size()
#define fi first
#define se second
#define ln '\n'
const ll MOD = 1e9 + 7;
inline ll add(ll a, ll b, ll m) { return (((a % m + b % m) % m + m) % m); }
inline ll mul(ll a, ll b, ll m) { return (((a % m * b % m) % m + m) % m); }

void solve(int tc)
{
	ll a, b;
	cin >> a >> b;
	ll ans = (a * b) / __gcd(a, b);
	cout << ans << ln;
	return;
}

int main()
{
#ifndef LOCAL
	FASTIO;
#endif
	int t = 1;
#ifdef LOCAL
	clock_t start, stop;
	start = clock();
#endif
#ifdef MULTI_TEST
	cin >> t;
#endif
	for (int tc = 1; tc < t + 1; tc++)
	{
#ifdef GOOGLE
		cout << "Case #" << tc << ": ";
#endif
		solve(tc);
	}
#ifdef LOCAL
	stop = clock();
	cerr << "Time :" << fixed << setprecision(5) << double(stop - start) / double(CLOCKS_PER_SEC) << "s" << ln;
#endif
	return 0;
}


Measured memory_bytes: 3660
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define io ios_base::sync_with_stdio(0); cin.tie(NULL);
void solve(){
	int x;
	cin>>x;
	if(x >= 30) cout<<"Yes";
	else cout<<"No";
}
	
int main(){
	solve();
	return 0;
}
	


Measured memory_bytes: 3600
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
  int n,m;
  cin>>n>>m;
  vector<int> a(n);
  for(int i=0;i<n;++i){
    cin>>a[i];
  }
  sort(a.begin(),a.end());
  int ans=0;
  for(int i=0;i<m;++i){
    ans+=a[n-1-i];
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3604
from collections import Counter, deque

N = int(input())
A = list(map(int, input().split())) + [N+1]
B = list(map(int, input().split())) + [N+1]
C = [0]
D = [0]

AB_cn = Counter(A+B)
if AB_cn.most_common()[0][1] > N:
    print("No")
else:
    print("Yes")
    for i in range(N+1):
        if len(C) != A[i]:
            C.extend([i]*(A[i]-len(C)))
        if len(D) != B[i]:
            D.extend([i]*(B[i]-len(D)))
    ans = 0
    for i in range(N):
        curr = C[i+1] - D[i]
        ans= max(curr, ans)
    B = B[:-1]
    ans = [B[(i-ans)%N] for i in range(N)]
 
    print(*ans)


Measured memory_bytes: 52332
a=input()
b=input()
if(len(a)>len(b)):
    print('GREATER')
elif(len(b)>len(a)):
    print('LESS')
else:
    fla,flb=0,0
    for i in range(len(a)):
        if(int(a[i])>int(b[i])):
            fla=1
            break
        if(int(b[i])>int(a[i])):
            flb=1
            break
    if(fla==0 and flb==0):
        print('EQUAL')
    elif(fla==1):
        print('GREATER')
    else:
        print('LESS')
        


Measured memory_bytes: 3064
n=int(input())
b=[int(i) for i in input().split()]
a=[b[0]]
for i in range(n-1):
	a.append(b[i])
	if a[i]>b[i]:
		a[i]=b[i]
	if a[i+1]>b[i]:
		a[i+1]=b[i]
print(sum(a))

Measured memory_bytes: 3060
n=int(input())
edge=[]
node=[]
for i in range(n-1):
    u,v,w=map(int,input().split())
    edge.append([u,v,w])
    node.append([])
node.append([])
dist=[-1]*n
for i in range(n-1):
    [u,v,w]=edge[i]
    node[u-1].append([v-1,w])
    node[v-1].append([u-1,w])
#print(node)

def bfs(node,l):
    stack=[]
    for [v,w] in node[l]:
        stack.append([v,l,w])
    while stack:
        [v,l,w]=stack.pop()
        if(dist[v]==-1):
            dist[v]=(dist[l]+w)%2
            for [v1,w1] in node[v]:
                stack.append([v1,v,w1])
    
dist[0]=1
bfs(node,0)
for i in range(n):
    print(dist[i],end='\n')

Measured memory_bytes: 61676
import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int i;
      
      for(i = 0; a > 0; i++)
        a-=b;

      System.out.println(i);

    }
}

Measured memory_bytes: 22612
S = input()
K = int(input())
s = list(map(int, list(S)))

if K <= 100:
    # 1からK文字目まで連続した1が見つかるかを探す
    for i in range(K):
        if s[i] != 1:
            # 1ではない -> つまりこの数字
            print(S[i])
            break
    else:
        # 1が連続している -> 1
        print(1)
else:
    # 一番最初に発見した1以外の数字
    for c in s:
        if c != 1:
            print(c)
            break


Measured memory_bytes: 3060
import java.util.*;

    class Main{
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            String[] n = sc.next().split("");
            for(int i=0;i<n.length; i++){
                if(n[i].equals("7")){
                    System.out.println("Yes");
                    return;
                }
            }
            System.out.println("No");

        }
    }

Measured memory_bytes: 26952
if __name__ == "__main__":
    n = int(input())
    s = dict()
    for i in range(n):
        tmp = input()
        if tmp not in s:
            s[tmp] = [tmp]
        else:
            s[tmp].append(tmp)

    ls = sorted(s)

    maxvote = 0
    for ss in s:
        if len(s[ss]) > maxvote:
            maxvote = len(s[ss])

    for l in ls:
        if len(s[l]) == maxvote:
            print(l)


Measured memory_bytes: 50448
import java.util.*;

public class Main {
	void solve() {
		Scanner scan = new Scanner(System.in);
		long a = scan.nextInt();
		long b = scan.nextInt();
		System.out.println(lcm(a, b));
		scan.close();
	}
	
	long lcm(long a, long b) {
		return a * b / gcd(a, b);
	}
	
	long gcd(long a, long b) {
		if(a % b == 0) return b;
		return gcd(b, a % b);
	}
	
	public static void main(String[] args) {
		new Main().solve();
	}
}


Measured memory_bytes: 35712
import java.io.IOException;
import java.util.*;

/**
 */
class Main {
	final static int N = 10;

	public static void main(String[] args) throws IOException {
		Scanner in = new Scanner(System.in);
		while(in.hasNext()) {
			String[] strArr = in.nextLine().split(",");
			int[] larr = new int[12];
			int L = 0;
			for (int i = 0; i < 12; i++) {
                larr[i] = Integer.parseInt(strArr[i]);
				if(i < 10) {
					larr[i] *= 1000;
					L += larr[i];
				}
			}

			int l1 = (int)((double) (larr[10] * L) / (larr[11] + larr[10]));
			int sum = 0;
			for(int i=0;i<10;i++) {
				sum += larr[i];
				if(l1 <= sum) {
					System.out.println(i+1);
					break;
				}
			}
		}
	}
}

Measured memory_bytes: 25768
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define ALL(x) (x).begin(), (x).end()
#define REP(i ,n) for(int i = 0; i < (int)(n); i++)
#define pb push_back
typedef vector<int>vint;
typedef vector<ll>vll;
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
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;}

int main()
{
  int N;
  cin >> N;
  vector<int> A(N);
  REP(i,N-1){
    int a;
    cin >> a;
    a--;
    A[a]++;
  }
  REP(i,N){
    cout << A[i] << endl;
  }
}

Measured memory_bytes: 4060
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
#define MOD (1000000007)
#define INF (1e9)
#define INFL (1e18)
 
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
template<class T>using arr=vector<vector<T>>;
template<class T>void pr(T x){cout << x << endl;}
template<class T>void prvec(vector<T>& a){rep(i, a.size()-1){cout << a[i] << " ";} cout << a[a.size()-1] << endl;}
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 main()
{
    char a; cin >> a;
    if(a >= 'a' && a <= 'z') pr('a');
    else pr('A');
    return 0;}

Measured memory_bytes: 3616
#include <iostream>
#include <vector>
#include<algorithm>
#include<math.h>
#include<iomanip>
#define ff(i,m,n) for(int i=m;i<n;i++)
#define i64 int64_t
using namespace std;


int main() {
	int a, b, c;
	cin >> a >> b >> c;
	if (a + b + c != 17) {
		cout << "NO" << endl;
		return 0;
	}
	if (a != 5 && a != 7) {
		cout << "NO" << endl;
		return 0;
	}
	if (c != 5 && c != 7) {
		cout << "NO" << endl;
		return 0;
	}
	if (b != 5 && b != 7) {
		cout << "NO" << endl;
		return 0;
	}
	cout << "YES" << endl;
	return 0;
}

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

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

    static class CSkip {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            long x = in.nextLong();

            long answer = 0;
            for (int i = 0; i < n; i++) {
                long x2 = in.nextLong();
                x2 = Math.abs(x2 - x);
                answer = NumberTheory.gcd(answer, x2);
            }

            out.println(answer);
        }

    }

    static class NumberTheory {
        public static long gcd(long a, long b) {
            long c;
            while (a != 0) {
                c = a;
                a = b % a;
                b = c;
            }
            return b;
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

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

    }
}



Measured memory_bytes: 34220
#include <stdio.h>
int main (void)
{
    int X,Y,Z,n;
    scanf("%d%d%d",&X,&Y,&Z);
    n=X;
    X=Y;
    Y=n;
    n=X;
    X=Z;
    Z=n;
    printf("%d %d %d\n",X,Y,Z);
return 0 ;
}


Measured memory_bytes: 128
def main():
    S = input()
    S = S[::-1]
    _T = 'dreamer', 'dream', 'eraser', 'erase'
    T = []
    for t in _T:
        T.append(t[::-1])
    i = 0
    while 1:
        temp = []
        bool = True
        for t in T:
            if S[i:len(t) + i] == t:
                i += len(t)
                bool = False
        if bool:
            break
    if len(S) != i:
        print('NO')
    else:
        print('YES')


if __name__ == '__main__':
    main()


Measured memory_bytes: 3188
#include<cstdio>
#include<iostream>
using namespace std;
int mod[2010];
int main()
{
    cout<<"Christmas";
    int d;
    cin>>d;
    if(d==25) cout<<endl;
    if(d==24) cout<<" Eve"<<endl;
    if(d==23) cout<<" Eve Eve"<<endl;
    if(d==22) cout<<" Eve Eve Eve"<<endl;
}


Measured memory_bytes: 256
n = float(input())
i = 0
total = 0
while i < n:
  date = input().split()
  m = float(date[0])
  t = date[1]
  if date[1] == "JPY":
    total += m
  else:
    total += m * 380000
  i += 1
  
print(total)
    

    



Measured memory_bytes: 2940
import itertools
 
H,W=map(int, input().split())
garden=[]
 
for i in range(H):
    garden.append(list(input().replace(".","1").replace("#","0")))
 
dct=[(1,0),(0,1)]
d=[ [i+j for i in range(W)] for j in range(H)]

for i, j in itertools.product(range(H),range(W)):
    color=garden[i][j]
    for each in dct:
        di,dj=each[0],each[1]
        if i+di<H and j+dj< W and  garden[i+di][j+dj]==color:
            d[i+di][j+dj]=min(d[i+di][j+dj],d[i][j])

        elif i+di<H and j+dj< W:
            d[i+di][j+dj]=min(d[i+di][j+dj],d[i][j]+1)

if int(garden[0][0])+int(garden[H-1][W-1])==0:
  print(int((d[H-1][W-1]+1)/2)+1)
else:
  print(int((d[H-1][W-1]+1)/2))

Measured memory_bytes: 3316
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();

        HashMap<Character, ArrayList<String>> hashMap = new HashMap<>();

        char[] prefixs = new char[5];
        prefixs[0] = 'M';
        prefixs[1] = 'A';
        prefixs[2] = 'R';
        prefixs[3] = 'C';
        prefixs[4] = 'H';

        long[] cnts = new long[5];

        for(int i=0; i<N; i++){
            char c = scanner.next().charAt(0);

            if(c == 'M'){
                cnts[0]++;
            }else if(c == 'A'){
                cnts[1]++;
            }else if(c == 'R'){
                cnts[2]++;
            }else if(c == 'C'){
                cnts[3]++;
            }else if(c == 'H'){
                cnts[4]++;
            }
        }

        long ans = 0;
        for(int i=0; i<3; i++){
            for(int j=i+1; j<4; j++){
                for(int k=j+1; k<5; k++){
                    ans += (cnts[i] * cnts[j] * cnts[k]);
                }
            }
        }

        System.out.println(ans);
    }
}


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

#define int long long
typedef pair<int, int> P;
#define mod 1000000007
#define INF (1LL<<60)
 
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)
#define YES puts("YES")
#define Yes puts("Yes")
#define NO  puts("NO")
#define No  puts("No")
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
 
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
 
 
#if 1
//-------------
// DUMPマクロ
// https://www.creativ.xyz/dump-cpp-652/
 
// vector
template <typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    for (T& x : vec) is >> x;
    return is;
}
// pair
template <typename T, typename U>
ostream& operator<<(ostream& os, pair<T, U>& pair_var) {
    os << "(" << pair_var.first << ", " << pair_var.second << ")";
    return os;
}
// vector
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    os << "{";
    for (int i = 0; i < vec.size(); i++) {
        os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
    }
    os << "}";
    return os;
}
// map
template <typename T, typename U>
ostream& operator<<(ostream& os, map<T, U>& map_var) {
    os << "{";
    repi(itr, map_var) {
        os << *itr;
        itr++;
        if (itr != map_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
// set
template <typename T>
ostream& operator<<(ostream& os, set<T>& set_var) {
    os << "{";
    repi(itr, set_var) {
        os << *itr;
        itr++;
        if (itr != set_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
 
#define DUMPOUT cerr
 
void dump_func() {
    DUMPOUT << endl;
}
template <class Head, class... Tail>
void dump_func(Head&& head, Tail&& ... tail) {
    DUMPOUT << head;
    if (sizeof...(Tail) > 0) {
        DUMPOUT << ", ";
    }
    dump_func(std::move(tail)...);
}
#ifdef DEBUG
#define DEB
#define dump(...)                                                              \
    DUMPOUT << "  " << string(#__VA_ARGS__) << ": "                            \
            << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]"        \
            << endl                                                            \
            << "    ",                                                         \
        dump_func(__VA_ARGS__)
#else
#define DEB if (false)
#define dump(...)
#endif
#endif

int func(int a, int b, int c, int d){
    return abs(a-c) + abs(b-d);
}

signed main() {

    int ans = 1;
    int N; cin>>N;
    for(int i=1; i<=N; i++)
        (ans*=i)%=mod;
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <algorithm>
#include <ctime>
#include <vector>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;

#define PI 3.14159265358979323846264338327950L

string res;

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

    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }
    res = "YES";
    sort(A.begin(), A.end());
    for (int i = 0; i < N - 1; i++)
    {
        if (A[i] == A[i + 1])
        {
            res = "NO";
        }
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3968
#include <bits/stdc++.h>
using namespace std;
void rec(vector<vector<int>> &dp, string &s, string &t)
{
  int i, j, len1, len2;
  len1=s.length();
  len2=t.length();
  
  for(i=0;i<=len1;i++)
  {
    for(j=0;j<=len2;j++)
    {
       if(i==0 || j==0)
        dp[i][j]=0;
      else if(i>0 && j>0 && s[i-1]==t[j-1])
        dp[i][j]=dp[i-1][j-1]+1;
      else 
        dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
    }
  }
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  string s, t;
  cin>>s>>t;
  int i, j;
  i=s.length();
  j=t.length();
  vector<vector<int>> dp(i+1, vector<int> (j+1));
  rec(dp, s, t);
  string ans="";
  while(dp[i][j]!=0)
  {
    if(s[i-1]==t[j-1])
    {
      ans=s[i-1]+ans;
      i--;
      j--;
    }
    else if(dp[i-1][j]>=dp[i][j-1])
      i--;
    else
      j--;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 35584
package main

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

type node struct {
	id       int
	parent   int
	depth    int
	nodeType string
	children []int
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	buf := make([]byte, 1000)
	sc.Buffer(buf, 10000000)

	sc.Scan()
	num, _ := strconv.Atoi(sc.Text())
	tree := make([]node, num)

	for sc.Scan() {
		rawInputs := strings.Split(sc.Text(), " ")
		inputs := make([]int, len(rawInputs))
		for j, v := range rawInputs {
			inputs[j], _ = strconv.Atoi(v)
		}

		id := inputs[0]
		if inputs[1] != 0 {
			tree[id].children = inputs[2:]
			tree[id].nodeType = "internal node"
		} else {
			tree[id].nodeType = "leaf"
		}
	}

	for i, v := range tree {
		if v.nodeType == "internal node" {
			registerParent(tree, i, v.children, 0)
		}
	}

	for i, v := range tree {
		children := strings.Join(strings.Split(strings.Trim(fmt.Sprint(v.children), "[]"), " "), ", ")
		if v.nodeType == "internal node" && v.depth == 0 || v.depth == 0 && len(v.children) == 0 {
			v.nodeType = "root"
			v.parent = -1
		}
		fmt.Printf("node %d: parent = %d, depth = %d, %s, [%s]\n", i, v.parent, v.depth, v.nodeType, children)
	}
}

func registerParent(tree []node, id int, children []int, depth int) {
	for _, v := range children {
		if tree[v].depth != 0 && tree[v].depth > depth+1 {
			continue
		}
		tree[v].parent = id
		tree[v].depth = depth + 1
		if len(tree[v].children) > 0 {
			registerParent(tree, v, tree[v].children, depth+1)
		}
	}
}



Measured memory_bytes: 18496
// written by newbiechd
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>

// DELETE the debugging information!
#define debug(x) std::cerr << #x << " = " << (x) << std::endl

int read() {
  int f = 0;
  char ch;
  while (!isdigit(ch = getchar()));
  do f = 10 * f + (ch ^ '0');
  while (isdigit(ch = getchar()));
  return f;
}

const int N_MAX = 200003;
int p[N_MAX], f[N_MAX], c[N_MAX][2];
int find(int x) {
  return x == f[x] ? x : f[x] = find(f[x]);
}

struct Node {
  int c0, c1, id;
  Node() {}
  Node(const int &c0, const int &c1, const int &id) : c0(c0), c1(c1), id(id) {}
  friend bool operator<(const Node &lhs, const Node &rhs) {
    return 1ll * lhs.c0 * rhs.c1 < 1ll * lhs.c1 * rhs.c0;
  }
};
std::priority_queue<Node> que;

int main() {
  int n = read();
  for (int i = 2; i <= n; ++i)
    p[i] = read();
  for (int i = 1; i <= n; ++i)
    f[i] = i, c[i][read()] = 1;
  for (int i = 2; i <= n; ++i)
    que.push(Node(c[i][0], c[i][1], i));
  
  long long ans = 0;
  // int cnt = 0;
  while (!que.empty()) {
    Node now = que.top();
    que.pop();
    // int x = find(now.id);
    int x = now.id;
    if (now.c0 == c[x][0] && now.c1 == c[x][1]) {
      // ++cnt;
      int u = find(p[x]);
      ans += 1ll * c[u][1] * now.c0;
      c[u][0] += now.c0, c[u][1] += now.c1;
      f[now.id] = u;
      if (u > 1)
        que.push(Node(c[u][0], c[u][1], u));
    }
  }
  
  printf("%lld\n", ans);
  // debug(cnt);
  return 0;
}


Measured memory_bytes: 8052
//ProblemD

//#define USE_STDIO
//#define USE_LOG
//#define FILE_ERR

#ifdef _MYPC
#include "mypc.h"
#endif // _MYPC

#ifndef debug
#define debug(...)
#endif // !LOG

#ifndef REDIRECT_STDIO
#define REDIRECT_STDIO {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);}
#endif // REDIRECT_STDIO

//include
#include <iostream>
#include <string>
#include <vector>
#include <bitset>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <algorithm>
#include <numeric>
#include <functional>
#include <memory>
#include <complex>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iomanip>

using namespace std;

//int
using ll = long long;
using ull = unsigned long long;
using uint = unsigned;

//pair
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

//vector
template<typename T> using vt = std::vector<T>;
template<typename T> using vvt = vt<vt<T>>;
template<typename T> using vvvt = vt<vvt<T>>;
using vi = vt<int>;
using vvi = vvt<int>;
using vvvi = vvvt<int>;
using vl = vt<ll>;
using vvl = vvt<ll>;
using vvvl = vvvt<ll>;
using vb = vt<bool>;
using vpii = vt<pii>;

static inline void Solve();

int main(int argc, char* argv[]) {
	REDIRECT_STDIO;

	Solve();
	return 0;
}

//ProblemD
void Solve() {
	int l; cin >> l;

	vi ds;
	for(int x = l; x; x -= x & -x) ds.push_back(x);
	unordered_map<int, int> log2;
	for(int i = 0, m = 1; i <= 20; i++, m <<= 1) log2[m] = i;

	vvi ans;
	for(int i = 1, x = 1; x * 2 <= ds.back(); i++, x <<= 1) {
		ans.push_back({i, i+1, 0});
		ans.push_back({i, i+1, x});
	}
	int n = ans.back()[1];

	for(int i = ds.size() - 1; i > 0; i--) {
		int x = ds[i];
		int j = log2[ds[i-1] - ds[i]];
		ans.push_back({j + 1, n, x});
	}

	cout << n << ' ' << ans.size() << '\n';
	for(auto& a : ans) {
		cout << a[0] << ' ' << a[1]  << ' ' << a[2] << '\n';
	}
	cout << flush;
}


Measured memory_bytes: 256
#include <iostream>
 
#define B (1000000007ULL)
using namespace std;
typedef unsigned long long ull;
 
int h, w, r, c;
char t[1000][1001], p[1000][1001];
ull th[1000][1000], ph[1000];
int st[1001];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>h>>w;
    cin.ignore();
    for(int i=0; i<h; i++) 
        cin.getline(t[i], 1001);
    cin>>r>>c;
    cin.ignore();
    for(int i=0; i<r; i++) 
        cin.getline(p[i], 1001);
 
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            ph[i]=ph[i]*B+p[i][j];
        }
    }
    ull bn=B;
    for(int i=1; i<c; i++) bn*=B;
    for(int i=0; i<h; i++){
        for(int j=0; j<c; j++) th[i][0]=th[i][0]*B+t[i][j];
        for(int j=0; j<w-c; j++) th[i][j+1]=th[i][j]*B-t[i][j]*bn+t[i][j+c];
    }
    for(int y=0; y<=h-r; y++){
        for(int x=0; x<=w-c; x++){
            int i;
            for(i=0; i<r&&th[y+i][x]==ph[i]; i++);
            if(i==r) cout<<y<<' '<<x<<'\n';
        }
    }
    return 0;
}


Measured memory_bytes: 12440
import sys
input = sys.stdin.readline


N, K = map(int,input().split())
A = list(map(int, input().split()))
K=format(K,"040b")
K=list(K)

length = 40
keta = [[0,0] for _ in range(length)]

for i in range(N):
    A[i]=format(A[i], "040b")
    A[i]=list(A[i])


for i in range(length):
    cnt=0
    for j in range(N):
        if A[j][i] == "1": cnt+=1
    keta[i][0] = N-cnt
    keta[i][1] = cnt

max_sum = [0]*length
for i in range(length):
    max_sum[i] = max(keta[i][0],keta[i][1]) * 2**(length-1-i)

dp = [[0,0] for _ in range(length)]
if K[0] == "1":
    dp[0][1] = keta[0][1-int(K[0])]*2**(length-1)
    dp[0][0] = keta[0][1]*2**(length-1)+ sum(max_sum[1:])
else:
    dp[0][1] = keta[0][1]*2**(length-1)

for i in range(1,length):
    if K[i] == "1":
        dp[i][0] = dp[i-1][1] + keta[i][1]*2**(length-1-i)+ sum(max_sum[i+1:]) #all ok
        dp[i][1] = dp[i-1][1] + keta[i][0]*2**(length-1-i)
    if K[i] == "0":
        dp[i][1] = dp[i-1][1] + keta[i][1]*2**(length-1-i)
    
ans = 0
for i in range(length):
    ans=max(ans,dp[i][0])
print(max(ans,dp[length-1][1]))
        

Measured memory_bytes: 50816
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N;
    cin >> N;
    vector<int> v(N);

    int max = 0;

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



    for(int i = 0; i<N;i++){
        int count = 0;
        int memo = 0;
        for(int j = i; j<N-1;j++){
            if(v[j] >= v[j+1]){
                count++;
                memo = j;
            }else{
                break;
            }
        }
        if(count > max) max = count;
        if(memo !=0) i = memo+1;
    }

    cout << max << endl;
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
	string s;
	cin >> s;
	for (int i = 0; i < s.size(); i++) {
		if (i % 2 == 0)cout << s[i];
	}
	cout << endl;
	int x;
	cin >> x;
	return 0;
}

Measured memory_bytes: 512
n,w = [int(x) for x in input().split()]
wts = []
vals = []
for i in range(n):
    wi,vi = [int(x) for x in input().split()]
    wts.append(wi)
    vals.append(vi)

valsum = sum(vals)
dp = []
maxval = 0
for i  in range(n):
    dp.append([float('inf')]*(valsum+1))

for j in range(valsum+1):
    if j==vals[0]:
        dp[0][j] = wts[0]
        if wts[0]<=w:
            maxval = max(maxval,j)

for i in range(n):
    dp[i][0] = 0

for i in range(1,n):
    for j in range(1,valsum+1):
        if j>=vals[i]:
            dp[i][j] = min(dp[i-1][j-vals[i]]+wts[i],dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
        if dp[i][j]<=w:
            maxval = max(maxval,j)
print(maxval)
            


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

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

class Card{
public:
	int num,index;
	char mark;
};

int Partition(vector<Card>& A,int p,int r){
	int x = A[r].num;
	int index = p-1;
	for(int i=p;i<r;i++){
		if(A[i].num<=x){
			index++;
			swap(A[i],A[index]);
		}
	}
	swap(A[index+1],A[r]);
	return index+1;
}

void QuickSort(vector<Card>& A,int p,int r){
	if(p<r){
		int q = Partition(A,p,r);
		QuickSort(A,p,q-1);
		QuickSort(A,q+1,r);
	}
}

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

	int N=in();
	vector<Card> C(N);
	REP(i,N){
		C[i].mark=in<char>();
		C[i].num=in();
		C[i].index=i;
	}
	
	QuickSort(C,0,N-1);
	map<int,int> check;
	bool is_stable=true;
	REP(i,N){
		if(check.find(C[i].num)==check.end()){
			check[C[i].num] = C[i].index;
		}
		else{
			if(check[C[i].num]>C[i].index){
				is_stable = false;
				break;
			}
		}
	}

	out(is_stable ? "Stable" : "Not stable");
	REP(i,N){
		out(C[i].mark,C[i].num);
	}
	return 0;
}



Measured memory_bytes: 4032
#!/usr/bin/env python3
N = int(input())
a = list(map(int, input().split()))

cnt = 0
op = []
mx = {'i':a.index(max(a)), 'v':max(a)}
mn = {'i':a.index(min(a)), 'v':min(a)}
for i in range(N):
    if mx['v'] > 0 and mn['v'] < 0:
        if abs(mx['v']) > abs(mn['v']):
            if a[i] < 0:
                cnt += 1
                op.append([mx['i'] + 1, i + 1])
                a[i] += mx['v']
        else:
            if a[i] > 0:
                cnt += 1
                op.append([mn['i'] + 1, i + 1])
                a[i] += mn['v']

if abs(mx['v']) > abs(mn['v']):
    for i in range(N - 1):
        if a[i] > a[i + 1]:
            cnt += 1
            op.append([i + 1, i + 2])
            a[i + 1] += a[i]
else:
    for i in range(N - 1)[::-1]:
        if a[i] > a[i + 1]:
            cnt += 1
            op.append([i + 2, i + 1])
            a[i] += a[i + 1]

print(cnt)
for i in range(cnt):
    print(op[i][0], op[i][1])


Measured memory_bytes: 3192
#include <iostream>
#include <stdio.h>
using namespace std;

int main() {
    int x;
    int i = 1;

    while(true) {
        cin >> x;
        if (x == 0) {
            break;
        }
        printf("Case %d: %d\n", i, x);
        i++;
    };

    return 0;
}


Measured memory_bytes: 3044
n, y = map(int, input().split())

man = y//10000

ans = 0
for i in range(man+1):
  mansatsu = i*10000
  for j in range(n-i+1):
    temp = mansatsu + j*5000
    if y - temp == 1000*(n-(i+j)):
      print(i,j,n-(i+j))
      ans = 1
      break
  else:
    continue
  break
if ans == 0:
  print("-1 -1 -1")

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <cassert>
#include <stack>
#include <queue>
#include <deque>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
//using namespace __gnu_pbds;

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

// template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//  order_of_key (k) : Number of items strictly smaller than k .
//  find_by_order(k) : K-th element in a set (counting from zero).
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define show(a) cerr << #a <<" -> "<< a <<"\n"
#define fo(a, b, c, d) for(int (a) = (b); (a) <= (c); (a) += (d))
#define foo(a, b, c ,d) for(int (a) = (b); (a) >= (c); (a) -= (d))
//#define int ll

const int N = 2e5 + 5;
const int oo = 1e9 + 5;

string ans[N];

void solve() {
    ans[2] = "hon";
    ans[4] = "hon";
    ans[5] = "hon";
    ans[7] = "hon";
    ans[9] = "hon";
    ans[0] = "pon";
    ans[1] = "pon";
    ans[6] = "pon";
    ans[8] = "pon";
    ans[3] = "bon";
    int n;
    cin >> n;
    cout << ans[(n % 10)];
}

 main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tt = 1;
	while (tt --) {
		solve();
	}
	return 0;
}
/*
	“I’m not gonna run away, I never go back on my word! That’s my nindo: my ninja way.” Naruto
*/


Measured memory_bytes: 9900
d = int(input())
c = list(map(int,input().split()))
cmax = max(c)
for al in range(26):
  if c[al] == cmax:
    maxc = al
up = []
for _ in range(d):
  up.append(list(map(int,input().split())))
ans = [[-1] for _ in range(26)]
for i in range(d):
  ans[maxc].append(i)
task = [maxc for i in range(d)]
#print(task)
#ans[0].append(0)
#ans[16].append(1)
#ans[12].append(2)
#ans[13].append(3)
#ans[12].append(4)

for al in range(26):
  ans[al].append(d)
#print(ans)
import bisect
from random import random
from random import randrange
import math
scr = 0
for al in range(26):
  now = ans[al]
  l = len(now)
  for j in range(1,l):
    scr -= c[al] * (now[j]-now[j-1]-1) * (now[j]-now[j-1]) // 2
    #print(c[al] * (now[j]-now[j-1]-1) * (now[j]-now[j-1]) // 2)
  for j in range(1,l-1):
    scr += up[now[j]][al]
    #print(up[now[j]][al])
  #print('$')
#print(scr)
est = 20000
for _ in range(200):
  for _ in range(1000):
    day = randrange(d)
    pre = task[day]
    pst = randrange(26)
    if pre == pst:
      continue
    bpre = bisect.bisect_left(ans[pre],day)
    bpst = bisect.bisect_left(ans[pst],day)
    bpre1 = ans[pre][bpre-1]
    bpre2 = ans[pre][bpre+1]
    bpst1 = ans[pst][bpst-1]
    bpst2 = ans[pst][bpst]
    #print(day,ans[pre][bpre],ans[pst][bpst])
    #print(day)
    #print(bpre1,day,bpre2,'#',pre)
    #print(bpst1,day,bpst2,'#',pst)
    tmp = 0
    tmp -= c[pre] * (day-bpre1) * (bpre2-day)
    #print(c[pre] * (day-bpre1) * (bpre2-day))
    tmp += c[pst] * (day-bpst1) * (bpst2-day)
    #print(c[pst] * (day-bpst1) * (bpst2-day))
    tmp -= up[day][pre]
    #print(up[day][pre])
    tmp += up[day][pst]
    #print(up[day][pst])
    #print(tmp)
    r = random()
    exp = math.exp(tmp/est)
    if exp > r:
      #print(ans[pre])
      #print(ans[pst])
      ans[pre].remove(day)
      bisect.insort(ans[pst],day)
      #print(ans[pre])
      #print(ans[pst])
      task[day] = pst
      scr += tmp
      #print(scr)
    #print('%')
  est -= 100
#for x in ans:
  #print(x)
for x in task:
  print(x+1)

Measured memory_bytes: 87188
import sys
input = lambda: sys.stdin.readline().rstrip()
inp = sys.stdin.buffer.readline                               
def I(): return list(map(int,inp().split()))
from collections import Counter

n=I()[0]
s=input() 
cut=0
for i in range(len(s)):
    for j in range(i+1,len(s)):
        if 2*j-i>=len(s): break
        if not(s[i]==s[j] or s[i]==s[2*j-i] or s[j]==s[2*j-i]): 
            cut+=1
d=Counter(s) ; mul=1
for i in d.values():
    mul*=i
if len(d)<3: print(0)
else: print(mul-cut)


            


Measured memory_bytes: 68684