akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ll long long
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
// rep(i, 1, 5) --> {1,2,3,4}
// rep(i, 5, 1) --> {4,3,2,1}
// rep(it, end(v), begin(v)) --> *it

using namespace std;

int main()
{
    string s, t;
    cin >> s >> t;
    int i = 0;
    bool ok = true;
    vector<string> v;
    rep(i, 0, s.size() - t.size() + 1)
    {
        ok = true;
        int j = 0;
        int anc = i;
        string s2 = s;
        rep(j, 0, t.size())
        {
            if (s[i] != t[j] && s[i] != '?')
            {
                ok = false;
                break;
            }
            i++;
        }
        if (ok)
        {
            rep(k, 0, t.size())
                s2[anc+k] = t[k];
            rep(i, 0, s2.size())
            if (s2[i] == '?')
                s2[i] = 'a';
            v.push_back(s2);
        }
        i = anc;
    }
    if (v.size() == 0)
        return cout << "UNRESTORABLE", 0;
    else 
        {
            sort(begin(v), end(v));
            cout << v[0];
        }    
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main
{
  private static class Cell
  {
    public int xl, xr, h;
    public int value;
    public Cell l, r;

    public Cell(int xl_, int xr_, int h_)
    {
      xl = xl_;
      xr = xr_;
      h = h_;
    }

    public void part(int x, int h)
    {
      if (isLeaf())
      {
        l = new Cell(xl, x, h);
        r = new Cell(x, xr, h);
      }
      else if (x < l.xr)
      {
        l.part(x, h);
      }
      else if (r.xl < x)
      {
        r.part(x, h);
      }
    }

    public boolean isLeaf() { return l == null && r == null; }

    public int bottomArea() { return (xr - xl) * 30; }

    public boolean isFull() { return value == maxCapacity(); }

    public void fill() { value = maxCapacity(); }

    public int maxCapacity() { return h * bottomArea(); }

    public void clear()
    {
      value = 0;
      if (!isLeaf())
      {
        l.clear();
        r.clear();
      }
    }

    public int water(int x, int v)
    {
      int cap = maxCapacity() - value;
      if (cap <= v)
      {
        if (!isLeaf())
        {
          l.fill();
          r.fill();
        }
        fill();
        return v - cap;
      }

      if (isLeaf() || (l.isFull() && r.isFull()))
      {
        value += v;
      }
      else
      {
        int rem = 0;
        if (x < l.xr)
        {
          rem = l.water(x, v);
          if (l.isFull() && rem != 0)
          {
            rem = r.water(r.xl, rem);
          }
        }
        else if (r.xl < x)
        {
          rem = r.water(x, v);
          if (r.isFull() && rem != 0)
          {
            rem = l.water(l.xr, rem);
          }
        }
        value = l.value + r.value + rem;
      }
      return 0;
    }

    public double getWaterHeight(int x)
    {
      if (isLeaf() || (l.isFull() && r.isFull()))
      {
        return (double)value / bottomArea();
      }
      else if (x < l.xr)
      {
        return l.getWaterHeight(x);
      }
      else if (r.xl < x)
      {
        return r.getWaterHeight(x);
      }
      return -1;
    }
  }

  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int D = sc.nextInt();
    for (;D-->0;)
    {
      int N = sc.nextInt();

      int[] div = new int[50 + 1];
      for (int i = 0; i < N; i++)
      {
        int x = sc.nextInt(), h = sc.nextInt();
        div[h] = x;
      }

      Cell root = new Cell(0, 100, 50);
      for (int h = 50; h > 0; h--)
      {
        if (div[h] > 0) root.part(div[h], h);
      }

      int M = sc.nextInt();
      int[][] flow = new int[M][2];
      for (int i = 0; i < M; i++)
      {
        int x = sc.nextInt();
        int a = sc.nextInt();
        flow[i][0] = x;
        flow[i][1] = a;
      }

      int L = sc.nextInt();
      for (int i = 0; i < L; i++)
      {
        root.clear();
        int x = sc.nextInt();
        int t = sc.nextInt();
        for (int j = 0; j < M; j++)
        {
          root.water(flow[j][0], t * flow[j][1]);
        }
        System.out.printf("%.5f\n", root.getWaterHeight(x));
      }
    }
  }
}

Measured memory_bytes: 12000
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;

set<int> edge[2001];
int cnt[2001] = {};

void digstra(int n){
    queue<int> dig;
    int dist[2001] = {};

    dig.push(n);
    dist[n] = 1;

    while(!dig.empty()){
        int nn = dig.front();
        dig.pop();

        for(auto e:edge[nn]){

            if(dist[e] == 0){
                dist[e] = dist[nn] + 1;
                dig.push(e);
                cnt[dist[e]] ++;
            }

        }
    }
}


int main(){
    int n;
    cin >> n;
    int x, y; cin >> x >> y;
    edge[x].insert(y);
    edge[y].insert(x);

    for(int i = 1; i < n; i++){
        edge[i].insert(i+1);
        edge[i+1].insert(i);
    }

    for(int i = 1; i <= n; i++){
        digstra(i);
    }
    for(int i = 2; i <= n; i++){
        cout << cnt[i]/2 << endl;
    }
    return 0;

}

Measured memory_bytes: 512
// Shift-JIS（シフトジス）

#include <bits/stdc++.h>
using namespace std;

int N;
vector<long long> A(100000);
vector<long long> memoL(100000);
vector<long long> memoR(100000);

int gcd(int m, int n)
{
    if (n == 0)
    {
        return abs(m);
    }

    return gcd(n, m % n);
}

int L(int i)
{
    if (i == 0)
    {
        return 0;
    }

    if (memoL[i] != 0) {
        return memoL[i];
    }

    return memoL[i] = gcd(L(i - 1), A[i - 1]);
}

int R(int i)
{
    if (i == N + 1)
    {
        return 0;
    }

    if (memoR[i] != 0) {
        return memoR[i];
    }

    return memoR[i] = gcd(R(i + 1), A[i]);
}

int main()
{
    cin >> N;

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

    int ans = 0, M;

    for (int i = 0; i < N; i++)
    {
        M = gcd(L(i), R(i + 1));
        if (ans < M)
        {
            ans = M;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 5760
i=3;main(n,j){scanf("%d",&n);if(n==3)printf("2 3 25\n");else{for(;j=(n-i+((n-i)%2)),!(0<j&&j<5001&&i<15001);i+=3);for(i-=(n-i)%2;i--;)printf("%d ",2*i+2);for(;j;)printf("%d%s",6*j+3,--j?" ":"\n");}return 0;}

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

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<vector<int>> f(n, vector<int>(10)), p(n, vector<int>(11));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 10; j++) {
			cin >> f[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 11; j++) {
			cin >> p[i][j];
		}
	}

	long long mx = -101010101010101010;
	for (int i = 1; i < (1 << 10); i++) {
		int a[10];
		for (int j = 0; j < 10; j++) {
			if (((i >> j) % 1) == 1) {
				a[j] = 1;
			} else {
				a[j] = 0;
			}
		}

		long long t = 0;
		for (int j = 0; j < n; j++) {
			int cnt = 0;
			for (int k = 0; k < 10; k++) {
				if (f[j][k] == 1 && ((i >> k) & 1) == 1) {
					cnt++;
				}
			}
			t += p[j][cnt];
		}
		mx = max(mx, t);
	}
	cout << mx << endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
			while(sc.hasNext()) {
				String str = sc.nextLine();
					if (str.equals("EOF")) {
						break;
					}
				String[] s = str.split(" ");

				System.out.println(Integer.parseInt(s[0]) + Integer.parseInt(s[1]));
			}
		sc.close();

	}

}


Measured memory_bytes: 26264
#include<algorithm>
#include<climits>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<list>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<utility>
#include<vector>

#define lint long long
#define REP(i, x, n) for(int i = x ; i < n ; i++)
#define rep(i, n) REP(i, 0, n)
#define repr(i, n) for(int i = n - 1 ; i >= 0 ; i--)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c).begin(), (c).end(), greater<int>())
#define IINF INT_MAX
#define LLINF LLONG_MAX

using namespace std;

int main(){
    lint a, b, c;
    cin >> a >> b >> c;
    if(a % 2 == 0 || b % 2 == 0 || c % 2 == 0){
        cout << 0 << endl;
    }else{
        vector<lint> x = {a, b, c};
        SORT(x);
        cout << x[0] * x[1] << endl;
    }
    return 0;
}

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

#define ll long long int

int N;
int dias[100005][3];
ll memo[100005][3];

ll solve(int dia, int act){
	if(!dia) return dias[dia][act];
	if(memo[dia][act]) return memo[dia][act];
	return memo[dia][act] = 
		dias[dia][act]+max(solve(dia-1, (act+1)%3), solve(dia-1, (act+2)%3));
}

ll solve(){
	for(int i = 0; i < 3; i++)
		memo[0][i] = dias[0][i];
	for(int i = 1; i<N; i++)
		for(int j = 0; j<3; j++)
			memo[i][j] = dias[i][j]+
							max(memo[i-1][(j+1)%3], 
								memo[i-1][(j+2)%3]);
	ll maxi = 0;
	for(int i = 0; i < 3; i++)
		maxi = max(maxi, memo[N-1][i]);
	return maxi;
}

int main() {
	cin>>N;
	for(int i = 0; i< N; i++)
		cin>>dias[i][0]>>dias[i][1]>>dias[i][2];
	cout<<max(max(solve(N-1,0), solve(N-1,1)), solve(N-1,2))<<"\n";
	return 0;
}

Measured memory_bytes: 11800
using System;
using System.Collections.Generic;

namespace ABLC
{
    class Program
    {
        static void Main(string[] args)
        {
            var NM = Console.ReadLine().Split(' ');
            var N = int.Parse(NM[0]);
            var M = int.Parse(NM[1]);
            var passed = new HashSet<int>();
            var road = new Dictionary<int, List<int>>();
            for (var i = 1; i <= N; i++)
            {
                road[i] = new List<int>();
            }

            for (var i = 0; i < M; i++)
            {
                var AB = Console.ReadLine().Split(' ');
                var A = int.Parse(AB[0]);
                var B = int.Parse(AB[1]);
                road[A].Add(B);
                road[B].Add(A);
            }

            var treeCount = 0;
            for (var i = 1; i <= N; i++)
            {
                var ret = DFS(-1, i, road, passed);
                if (ret > 0)
                {
                    treeCount++;
                }
            }

            Console.WriteLine(treeCount - 1);
        }

        static int DFS(int prev, int current, Dictionary<int, List<int>> road, HashSet<int> passed)
        {
            var ret = 0;
            if (passed.Contains(current))
            {
                return ret;
            }
            passed.Add(current);
            ret++;

            foreach (var next in road[current])
            {
                if (next != prev)
                {
                    ret += DFS(current, next, road, passed);
                }
            }

            return ret;
        }
    }
}


Measured memory_bytes: 53388
///                                                     ببِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم
#include <bits/stdc++.h>
//#define off  exit( 0 )
//#define cn   continue
#define rt   return/*
#define sc   scanf
#define pr   printf
#define pb   push_back
#define pf   push_front
#define p_f  pop_front
#define p_b  pop_back
#define ff   first
#define ss   second
#define vec  vector
#define gcd  __gcd
#define pi   acos( -1 )*/
#define ll   long long
/*#define ld   long double
#define N    2256
#define M    1000000007
#define I    1000000000000000000
#define pdd  pair < ld, ld >
#define pll  pair < ll, ll >
#define pii  pair < int, int >
#define rep( a, b, c, d )  for( int a = b; a <= c; a += d )
#define rvv( a, b, c, d )  for( int a = b; a >= c; a -= d )
#define en                 printf( "\n" )
#define sqr( a )           a * a
#define all( c )           c.begin(), c.end()
#define srt( c )           sort( all( c ) )
#define rev( c )           reverse( all( c ) )
#define srtr( c )          sort( c.rbegin(), c.rend() )
#define numcounts          __builtin_popcount
#define mxn( x, y, z )     max( x, min( y, z ) )
#define mnx( x, y, z )     min( x, max( y, z ) )
const int dx[ ] = { 1, -1, 0, 0 };
const int dy[ ] = { 0, 0, -1, 1 };*/
using namespace std;
ll ttt = 1;
ll T1, T2, A1, A2, B1, B2, h1, h2, q, m, k;
void solve()
{
    cin >> T1 >> T2 >> A1 >> A2 >> B1 >> B2;
    h1 = T1 * (A1 - B1);
    h2 = T2 * (A2 - B2);
    if(signbit(h1) == signbit(h2))
    {
        cout << 0 << endl;
        rt;
    }
    if(h1 >= 0)
    {
        h1 *= -1;
        h2 *= -1;
    }
    if(h1 + h2 == 0)
    {
        cout << "infinity" << endl;
        rt;
    }
    if(h1 + h2 < 0)
    {
        cout << 0 << endl;
        rt;
    }
    q = -h1 / (h1 + h2);
    m = -h1 % (h1 + h2);

    ll k = 2 * q;
    if(m)k ++;
    cout << k << endl;
}
int main()
{
    //sc( "%I64d", &ttt );
    for(int i = 0; i < ttt; i ++ )
        solve();
}


Measured memory_bytes: 256
def main():
    n = int(input())
    
    d_s = make_divisors(n)

    ans = n - 1

    for d in d_s:
        ans = min(ans, (d-1) + ((n // d) - 1))
    print(ans)


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors

if __name__ == '__main__':
    main()

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

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int main() {
	cin.sync_with_stdio(false); cin.tie(0);
	cin.exceptions(cin.failbit);

	int n; cin >> n;
	vector<pair<int, int>> v(n);
	vi ans(n);
	rep(i, 0, n) { cin >> v[i].first; v[i].second = i; }
	sort(all(v));
	rep(i, 0, n / 2) ans[v[i].second] = v[n / 2].first;
	rep(i, n / 2, n) ans[v[i].second] = v[n / 2 - 1].first;
	rep(i, 0, n) cout << ans[i] << endl;
}



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

using ll = long long;

ll solve(int N, vector<int> counts)
{
    auto pairs = 0LL;
    auto previous = false;
    for (auto i = 0; i < N; i++)
    {
        pairs += (previous + counts[i]) / 2;
        if (previous) previous = counts[i] > 0 && counts[i] % 2 == 0;
        else previous = counts[i] % 2 == 1;
    }
    return pairs;
}

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

    auto counts = vector<int>(N);
    for (auto& x : counts) cin >> x;

    cout << solve(N, counts) << endl;
}


Measured memory_bytes: 1024
/*
 * Print a Rectangle.c
 *
 *  Created on: 2015/02/13
 *
 */

#include <stdio.h>

int main(void){
	int H,W;
	int i,j;

	while(1){
		scanf("%d %d",&H,&W);

		if(H==0 && W==0)break;

		for(i=0;i<H;i++){
			for(j=0;j<W;j++){
				if((i+j)%2 ==0) printf("#");
				else printf(".");
			}
			printf("\n");
		}
		printf("\n");
	}

	return 0;
}

Measured memory_bytes: 572
#include <iostream>
using namespace std;
int main(){
  int n;cin>>n;
  int r=0,b=0;
  string s;cin>>s;
  for(int i = 0; n > i; i++){
    if(s[i] == 'R')r++;
    else b++;
  }
  if(r > b)cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
N = int(input())
*P, = map(float, input().split())

dp = [[0]*(N+1) for i in range(N+1)]
for i in range(N+1):
    if N <= 2*i:
        dp[N][i] = 1.
for c in range(N-1, -1, -1):
    p = P[c]
    for k in range(N-1, -1, -1):
        dp[c][k] = r = p * dp[c+1][k+1] + (1.-p) * dp[c+1][k]
print("%.10f" % dp[0][0])

Measured memory_bytes: 260872
#include <stdio.h>
#include <string.h>

int main(void)
{
	char dice[6], str[10], dice_c[6];
	int n, i, sum;
	
	while (1){
		scanf("%d", &n);
		
		if (n == 0){
			break;
		}
		
		dice[0] = 1;
		dice[1] = 2;
		dice[2] = 3;
		dice[3] = 4;
		dice[4] = 5;
		dice[5] = 6;
		
		sum = 1;
		
		for (i = 0; i < n; i++){
			
			scanf("%s", str);
			
			if (strcmp(str, "North") == 0){
				dice_c[0] = dice[1];
				dice_c[1] = dice[5];
				dice_c[2] = dice[2];
				dice_c[3] = dice[3];
				dice_c[4] = dice[0];
				dice_c[5] = dice[4];
				strcpy(dice, dice_c);
			}
			else if (strcmp(str, "East") == 0){
				dice_c[0] = dice[3];
				dice_c[1] = dice[1];
				dice_c[2] = dice[0];
				dice_c[3] = dice[5];
				dice_c[4] = dice[4];
				dice_c[5] = dice[2];
				strcpy(dice, dice_c);
			}
			else if (strcmp(str, "West") == 0){
				dice_c[0] = dice[2];
				dice_c[1] = dice[1];
				dice_c[2] = dice[5];
				dice_c[3] = dice[0];
				dice_c[4] = dice[4];
				dice_c[5] = dice[3];
				strcpy(dice, dice_c);
			}
			else if (strcmp(str, "South") == 0){
				dice_c[0] = dice[4];
				dice_c[1] = dice[0];
				dice_c[2] = dice[2];
				dice_c[3] = dice[3];
				dice_c[4] = dice[5];
				dice_c[5] = dice[1];
				strcpy(dice, dice_c);
			}
			else if (strcmp(str, "Right") == 0){
				dice_c[0] = dice[0];
				dice_c[1] = dice[2];
				dice_c[2] = dice[4];
				dice_c[3] = dice[1];
				dice_c[4] = dice[3];
				dice_c[5] = dice[5];
				strcpy(dice, dice_c);
			}
			else if (strcmp(str, "Left") == 0){
				dice_c[0] = dice[0];
				dice_c[1] = dice[3];
				dice_c[2] = dice[1];
				dice_c[3] = dice[4];
				dice_c[4] = dice[2];
				dice_c[5] = dice[5];
				strcpy(dice, dice_c);
			}
		
			sum += dice[0];
		}
		printf("%d\n", sum);
	}
	
	return (0);
}

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

using namespace std;

using ll = long long;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    int ans = 0;
    int cnt = 0;
    for (int i = 0; i < n - 1; i++) {
        if (a[i + 1] <= a[i]) cnt++;
        else {
            ans = max(ans, cnt);
            cnt = 0;
        }
    }
    ans = max(ans, cnt);
    cout << ans << endl;
    return 0;
}

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

map<string, int> dp;
const int cd[] = {-1, 1, 4, -4};
void dfs(){
    dp["01234567"] = 0;
    queue<string> que;
    que.push("01234567");
    while(!que.empty()){
        string str = que.front();
        que.pop();
        int zpos = 0;
        for(int i = 0; str[i]; ++i)
            if(str[i] == '0'){
                zpos = i;
                break;
            }
        for(int i = 0; i < 4; ++i){
            int npos = zpos + cd[i];
            if(npos < 0 || 7 < npos || (zpos == 3 && cd[i] == 1) || (zpos == 4 && cd[i] == -1)) continue;
            string nstr = str;
            swap(nstr[zpos], nstr[npos]);
            if(dp.find(nstr) == dp.end()){
                dp[nstr] = dp[str] + 1;
                que.push(nstr);
            }
        }
    }
}

int main(){
    // ios::sync_with_stdio(false);
    // cin.tie(NULL);
    dfs();
    string str;
    while(getline(cin, str)){
        str.erase(remove(str.begin(), str.end(), ' '), str.end());
        cout << dp[str] << endl;
    }
    return 0;
}

Measured memory_bytes: 5296
n = int(input())
p = list(map(int, input().split()))

l = []
cnt = 0
for i in range(n):
    if p[i] == i + 1:
        cnt += 1
    else:
        if cnt > 0:
            l.append(cnt)
            cnt = 0
if cnt > 0:
    l.append(cnt)
    cnt = 0

res = 0
for v in l:
    res += (v + 1) // 2

print(res)

Measured memory_bytes: 86240
s=input()
import collections
c = collections.Counter(s)

if (c["N"]!=0 and c["S"]==0) or (c["N"]==0 and c["S"]!=0) or (c["W"]!=0 and c["E"]==0) or (c["W"]==0 and c["E"]!=0):
  print("No")
else:
  print("Yes")
  
  

Measured memory_bytes: 38256
#include<stdio.h>
int main(){
  int n,m,t,r,a,b,i,j;
  int q[400001];
  while(scanf("%d %d",&n,&m),n||m){
    t=r=0;
    for(i=0;i<n;i++){
      scanf("%d %d",&a,&b);
      if(a==0){
	q[r++]=b;
	if(r-t>m)t++;
      }
      if(a==1){
	r--;
	for(j=b+t-1;j<r;j++)q[j]=q[j+1];
      }
      if(a==2)printf("%d\n",q[b+t-1]);
      if(a==3){
	for(j=t;q[j]!=b;j++);
	for(r--;j<r;j++)q[j]=q[j+1];
      }
      //for(j=t;j<r;j++)printf("%d",q[j]);printf("\n");
    }
    printf("end\n");
  }
  return 0;
}

Measured memory_bytes: 2172
using System;
using System.IO;
using System.Linq;
using System.Text;
using System.Collections.Generic;
using System.Diagnostics;
using Enu = System.Linq.Enumerable;

public class Program
{
    public void Solve()
    {
        long[] A = { Reader.Int(), Reader.Int(), Reader.Int(), Reader.Int() };
        long N = Reader.Int();
        long ans = N * A[2];
        long minSmall = new[] { A[0] * 4, A[1] * 2, A[2] }.Min();

        foreach (int buy2 in new[] { 0, N / 2 * 2 / 2 })
        {
            long sum = A[3] * buy2;
            long rem = N - buy2 * 2;
            sum += rem * minSmall;
            ans = Math.Min(ans, sum);
        }

        Console.WriteLine(ans);
    }
}


class Entry { static void Main() { new Program().Solve(); } }
class Reader
{
    static TextReader reader = Console.In;
    static readonly char[] separator = { ' ' };
    static readonly StringSplitOptions op = StringSplitOptions.RemoveEmptyEntries;
    static string[] A = new string[0];
    static int i;
    static void Init() { Dispose(); A = new string[0]; }
    public static void Set(TextReader r) { Init(); reader = r; }
    public static void Set(string file) { Init(); reader = new StreamReader(file); }
    public static bool HasNext() { return CheckNext(); }
    public static string String() { return Next(); }
    public static int Int() { return int.Parse(Next()); }
    public static long Long() { return long.Parse(Next()); }
    public static double Double() { return double.Parse(Next()); }
    public static int[] IntLine() { return Array.ConvertAll(Split(Line()), int.Parse); }
    public static int[] IntArray(int N) { return Range(N, Int); }
    public static int[][] IntTable(int H) { return Range(H, IntLine); }
    public static string[] StringArray(int N) { return Range(N, Next); }
    public static string[][] StringTable(int N) { return Range(N, () => Split(Line())); }
    public static string Line() { return reader.ReadLine().Trim(); }
    public static T[] Range<T>(int N, Func<T> f) { var r = new T[N]; for (int i = 0; i < N; r[i++] = f()) ; return r; }
    public static void Dispose() { reader.Dispose(); }
    static string[] Split(string s) { return s.Split(separator, op); }
    static string Next() { CheckNext(); return A[i++]; }
    static bool CheckNext()
    {
        if (i < A.Length) return true;
        string line = reader.ReadLine();
        if (line == null) return false;
        if (line == "") return CheckNext();
        A = Split(line);
        i = 0;
        return true;
    }
}

Measured memory_bytes: 13268
MOD = 998244353


def solve(a, b, c, d):
    dp1 = [[0] * (d + 1) for _ in range(c + 1)]
    dp2 = [[0] * (d + 1) for _ in range(c + 1)]
    dp3 = [[0] * (d + 1) for _ in range(c + 1)]
    dp1[a][b] = 1
    dp2[a][b] = 0
    dp3[a][b] = 0
    for i in range(a + 1, c + 1):
        dp1[i][b] = (pow(b - 1, i - a, MOD) + pow(b - 1, i - a - 1, MOD) * 1 * (i - a)) % MOD
        dp3[i][b] = (pow(b, i - a, MOD) - dp1[i][b]) % MOD
    for j in range(b + 1, d + 1):
        dp1[a][j] = (pow(a - 1, j - b, MOD) + pow(a - 1, j - b - 1, MOD) * 1 * (j - b)) % MOD
        dp2[a][j] = (pow(a, j - b, MOD) - dp1[a][j]) % MOD
    for i in range(a + 1, c + 1):
        for j in range(b + 1, d + 1):
            dp1[i][j] = ((dp1[i - 1][j] + dp2[i - 1][j]) * (j - 1)) % MOD
            dp2[i][j] = (dp2[i][j - 1] * i + dp1[i][j - 1] + dp3[i][j - 1]) % MOD
            dp3[i][j] = (dp3[i - 1][j] * j + dp1[i - 1][j] + dp2[i - 1][j]) % MOD

    # print(dp1, dp2, dp3)
    # print((dp1[c][d] + dp2[c][d] + dp3[c][d]) % MOD)
    return (dp1[c][d] + dp2[c][d] + dp3[c][d]) % MOD


def main():
    a, b, c, d = map(int, input().split())
    res = solve(a, b, c, d)
    print(res)


def test():
    assert solve(1, 1, 2, 2) == 3
    assert solve(1, 1, 3, 3) == 30
    assert solve(2, 1, 3, 4) == 65
    # assert solve(31, 41, 59, 265) == 387222020


if __name__ == "__main__":
    test()
    main()


Measured memory_bytes: 281084
package main

import (
	"fmt"
)

func main() {
	var tmp int
	input := make([]int, 5)
	for i := 0; i < 5; i++ {
		fmt.Scan(&tmp)
		input[i] = tmp
	}

	var subMaxIndex int
	subValue := 0
	for i := 0; i < 5; i++ {
		tmp = 10 - input[i]%10
		if tmp > subValue && tmp != 10 {
			subValue = tmp
			subMaxIndex = i
		}
	}

	output := 0
	for i := 0; i < 5; i++ {
		if subMaxIndex == i || input[i]%10 == 0 {
			output += input[i]
		} else {
			output += (10 - input[i]%10) + input[i]
		}
	}
	fmt.Println(output)
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;

int main() {
	ll n,vsum=0LL,cnt=0,tmp=0,msum=0;
	bool ans = true;
	cin >> n;
	vector<ll>arr(n), brr(n),vdiff(n);
	rep(i, n) cin >> arr[i];
	rep(i, n) {
		cin >> brr[i];
		if (arr[i] < brr[i])ans = false;
		vdiff[i] = arr[i] - brr[i];
	}
	if (ans) { cout << 0 << endl; return 0; }
	vsum = accumulate(all(vdiff), 0LL);
	if (vsum < 0) {
		cout << -1 << endl;
		return 0;
	}
	sort(rall(vdiff));
	for (int i = n - 1; i >= 0;i--) {
		if (0 <= vdiff[i])break;
		msum += vdiff[i];
		cnt++;
	}

	rep(i, n) {
		if (vdiff[i] <= 0) {
			cout << -1 << endl;
			return 0;
		}
		msum += vdiff[i];
		cnt++;
		if (0 <= msum)break;
	}

	cout << cnt << endl;
	return 0;
}



Measured memory_bytes: 5588
#include <iostream>

using namespace std;

int main()
{
    long long int n,i,sum=0,diff=0,a[200001];
    cin>>n;
    for(i=0;i<n;i++){
        cin>>a[i];
    }
    for(i=0;i<n-1;i++){
        if(a[i+1]<a[i]){
                diff=a[i]-a[i+1];
            a[i+1]=a[i+1]+diff;
           sum+=diff;
        }
    }
    cout<<sum;
    return 0;
}


Measured memory_bytes: 5164
//インクルード(アルファベット順)
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<chrono>//実行時間計測
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm,accumulate
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//順序保持しないmap
#include<unordered_set>//順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;
//マクロ
//forループ
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end()
#define SIZE(x) ll(x.size())
//定数
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange
//略記
#define PB push_back //挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素
#define PI 3.14159265358979323846264338327950L

#define YESNO(T) if(T){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define yesno(T) if(T){cout<<"yes"<<endl;}else{cout<<"no"<<endl;}
#define YesNo(T) if(T){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}

#define int long long
#define Graph vector<vector<int> >
#define PII pair<int,int>
#define VI vector<int>
#define VVI vecotor<vector<int> >
#define VPII vector<pair<int,int> >

template<typename A, size_t N, typename T>

void Fill(A (&array)[N], const T &val) {
	std::fill( (T*)array, (T*)(array + N), val );
}


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//ここにグローバル変数宣言
int H, W, sh, sw, gh, gw;
int dh[4] = {1, 0, -1, 0};
int dw[4] = {0, 1, 0, -1};//BFS関連







//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//ここに関数宣言
int ctoi(char c) {
	switch (c) {
	case '0': return 0;
	case '1': return 1;
	case '2': return 2;
	case '3': return 3;
	case '4': return 4;
	case '5': return 5;
	case '6': return 6;
	case '7': return 7;
	case '8': return 8;
	case '9': return 9;
	default: return 0;
	}
}










//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
signed main() {
	//入力の高速化用のコード
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	



int X;
cin>>X;
if (X>=30)
{
	cout<<"Yes"<<endl;
}
else{cout<<"No"<<endl;}



































return 0;

}







Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int a[maxn][3];
int dp[maxn][10];
int main()
{
	#ifdef TEST
		freopen("input.txt","r",stdin);
    #endif
	int n,m,T;
	cin>>n;
	for(int i=1;i<=n;i++)
	for(int j=0;j<3;j++)
	scanf("%d",&a[i][j]);
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<3;j++)
		{
			int temp=7-(1<<j);
			for(int bit=0;bit<3;bit++)
				if((temp>>bit)&1)dp[i][j]=max(dp[i][j],dp[i-1][bit]+a[i][j]);
		}
	}
	cout<<max(dp[n][0],max(dp[n][1],dp[n][2]))<<endl;
}



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

int main() {
    int n = 0, k = 0;
    scanf("%d %d\n", &n, &k);
    int raw[n+1][2];
    int len_raw = 0;
    int count_0 = 0;
    for (int i=0; i<n; i++) {
        raw[i][0] = raw[i][1] = -1;
        char c = getchar();
        if (i == 0) {
            raw[0][0] = c - '0';
            raw[0][1] = 1;
            if (raw[0][0] == 0) count_0++;
        }
        else {
            if ((c - '0') == raw[len_raw][0]) raw[len_raw][1]++;
            else {
                len_raw++;
                raw[len_raw][0] = 1 - raw[len_raw-1][0];
                raw[len_raw][1] = 1;
                if (raw[len_raw][0] == 0) count_0++;
            }
        }
    }
    if (k >= count_0) {
        printf("%d\n", n);
        return 0;
    }
    int max = 0;
    int count = 0;
    int buf = 0;
    for (int i=0; i<=len_raw; i++) {
        count = 0;
        buf = 0;
        if (raw[i][0] == 0) {
            if (i == 0) {
                for (int j=0; j<=len_raw; j++) {
                    if (raw[j][0] == 0) count++;
                    if (count > k) break;
                    buf += raw[j][1];
                }
                if (buf > max) max = buf;
            }
            else {
                for (int j=i-1; j<=len_raw; j++) {
                    if (raw[j][0] == 0) count++;
                    if (count > k) break;
                    buf += raw[j][1];
                }
                if (buf > max) max = buf;
            }
        }
    }
    printf("%d\n", max);
    return 0;
}


Measured memory_bytes: 896
import java.util.*;
import java.io.*;

class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		String s1=br.readLine();
		String s2=br.readLine();
		
		if(s2.length()-s1.length()==1)
		{
			int flag=1;
			for(int i=0;i<s1.length();i++)
			{
				if(s1.charAt(i)==s2.charAt(i))
				{
					continue;
				}
				else
				{
					flag=0;
					break;
				}
			}
			if(flag==1)
			{
				
				System.out.println("Yes");
			}
			else
			{
				System.out.println("No");
			}
		}
		else
		{
			System.out.println("No");
		}

	}

}


Measured memory_bytes: 32672
import Data.List
import Data.Maybe
import Control.Monad
import Control.Applicative
import qualified Data.ByteString.Char8 as B

main :: IO ()
main = do
    [n',h'] <- words <$> getLine :: IO [String]
    let n = read n' :: Int
        h = read h' :: Integer

    (as,bs) <- unzip <$> replicateM n ((\[a,b]->(a,b)) . 
               map (fst . fromJust . B.readInteger) . B.words <$> B.getLine) :: IO ([Integer],[Integer])
    let a = maximum as
    let ls = ((0,0):) . zip [0..] . scanl (+) 0 . sortBy (flip compare) $ filter (> a) bs
    let Just (i, b) = find ((>=h) . snd) ls <|> Just (last ls)
    print (i + ceiling (fromIntegral (max 0 (h - b)) / fromIntegral a :: Double) :: Integer)

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

using namespace std;

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

  vector<int> S(n);
  for (int i = 0; i < n; ++i) {
    cin >> S[i];
  }

  int q;
  cin >> q;

  int C = 0;
  int t;
  for (int i = 0; i < q; ++i) {
    cin >> t;
    for (int j = 0; j < n; ++j) {
      if (t == S[j]) {
        ++C;
        break;
      }
    }
  }
  cout << C << endl;

  return 0;
}

Measured memory_bytes: 1232
<?php
fscanf(STDIN, '%d %d', $n, $m);
for ($i  = 0; $i < $m; $i++) {
    fscanf(STDIN, '%d %d', $a[], $b[]);
    $a[$i]--;
    $b[$i]--;
}
$u = new UnionFind($n);
$ans[$m - 1] = $n * ($n - 1) / 2;
for ($i = $m - 1; $i >= 1; $i--) {
    if ($u->isSame($a[$i], $b[$i])) {
        $ans[$i - 1] = $ans[$i];
    } else {
        $ans[$i - 1] = $ans[$i] - $u->size($a[$i]) * $u->size($b[$i]);
        $u->unite($a[$i], $b[$i]);
    }
}
for ($i = 0; $i < $m; $i++) {
    echo $ans[$i] . PHP_EOL;
}

// Union-Find：同じグループに属するかどうかを判定する
class UnionFind {
    private $par; // par[$i]:$iの親 自分が根の場合は自身のindexとなる
    private $size;

    function __construct($n) {
        for ($i = 0; $i < $n; $i++) {
            $this->par[$i] = $i; // 最初は全てが根
            $this->size[$i] = 1;
        }
    }

    function root($x) { // 根を返す
        if ($this->par[$x] === $x) return $x; // 根の場合
        return $this->par[$x] = $this->root($this->par[$x]); // 全ての枝の親を根にしながら再帰処理
    }

    function unite($x, $y) { // $xと$yの木を併合
        $ix = $this->root($x);
        $iy = $this->root($y);
        if ($ix === $iy) return;
        if ($this->size[$ix] < $this->size[$iy]) list($ix, $iy) = [$iy, $ix];
        $this->size[$ix] += $this->size[$iy];
        $this->par[$iy] = $ix; // $yの根を$xの根に付ける
    }

    function isSame($x, $y) { // $xと$yの根が同じか
        return $this->root($x) === $this->root($y);
    }

    function size($x) {
        return $this->size[$this->root($x)];
    }
}

Measured memory_bytes: 29552
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<numeric>
#include<algorithm>
#include<complex>
#include<queue>
#include<stdlib.h>
#include<map>
#include<cmath>

#include<stdio.h>
#include<stdlib.h>

#define ll long long

using namespace std;

int main(){
    int M,K;
    cin >> M >> K;
    if(M==0){
        if(K!=0){
            cout << -1 << endl;
            return 0;
        }
        else{
            cout << "0 0" << endl;
            return 0;
        }
    }
    if(M==1){
        if(K==0){
            cout << "0 0 1 1" << endl;
            return 0;
        }
        else{
            cout << -1 << endl;
            return 0;
        }
    }
    if(K>=pow(2,M)){
        cout << -1 << endl;
        return 0;
    }
    else{
        for(int i=0;i<pow(2,M);i++){
            if(i!=K){
                cout << i << " ";
            }
        }
        cout << K << " ";
        for(int i=pow(2,M)-1;i>=0;i--){
            if(i!=K){
                cout << i << " ";
            }
        }
        cout << K << endl;
    }
    return 0;
}


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

int main() {
  for (int j = 0;j < 20; j++ ){
    int n; cin >> n;
    if (n == 0) {
      break;
    }
    int s[n]; for (int i = 0; i < n; i++) cin >> s[i];

    sort(s, s+n);int t = 0;
    for (int i = 1; i < n - 1; i++) {
      t += s[i]; 
    }
    cout << t / (n - 2) << endl;
  }
   return 0;
}


Measured memory_bytes: 3068
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
using ll = long long;

const long double PI = acos(-1.0);
const int MOD = 1e9 + 7;

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

    int n = s.size();

    int tmp = 0;
    for(int i = 0; i < n; i++) {
        tmp += (s[i] - '0');
    }

    if (tmp % 9 == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

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

int n;

bool ok(int x, int y, int z) {
	if(z > x + 1) return false;
	if(y && z > x) return false;
	return true;
}

int main() {
	scanf("%d", &n);

	int four = 0, two = 0, none = 0;
	for(int i = 1; i <= n; ++i) {
		int a;
		scanf("%d", &a);
		if(a % 4 == 0) ++four;
		else if(a % 2 == 0) ++two;
		else ++none;
	}

	if(ok(four, two, none)) printf("Yes\n");
	else printf("No\n");

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <math.h>
#include <utility>
#include <tuple>
#include <map>
#include <ctype.h>
#include <set>
using namespace std;
using ll = long long;
int main() {
    int N,L; cin >> N >> L;
    int S=0;
    for (int i=0;i<N;i++){
        S += (L+i);
    }
    int ans = 0;
    int abs_apple = 400;
    for (int i=0;i<N;i++){
        int tmp = abs(L+i);
        if (tmp<abs_apple) {
            ans = S-(L+i);
            abs_apple = tmp;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main()
{
  int a,b,i;
  char op,box[5]={'+','-','*','/','?'};
  while(op!=box[4])
  {
    scanf("%d %s %d",&a,&op,&b);
    if(op == box[0])printf("%d\n",a+b);
    else if(op == box[1])printf("%d\n",a-b);
    else if(op == box[2])printf("%d\n",a*b);
    else if(op == box[3])printf("%d\n",a/b);
  }
return 0;
}

Measured memory_bytes: 600
using System;
using System.Text;

namespace AtCoder
{
	public class ProblemA
	{
		public static void Main(string[] args)
		{
			string[] line = Console.ReadLine().Split(' ');
			int h = int.Parse(line[0]);
			int w = int.Parse(line[1]);

			char[,] tiles = new char[h, w];

			int empty = 0;

			for (int i = 0; i < h; i++)
			{
				string s = Console.ReadLine();
				for (int j = 0; j < w; j++)
				{
					char c = s[j];
					tiles[i, j] = c;
					if (c == '.')
						empty++;
				}
			}

			StringBuilder sb = new StringBuilder();

			for (int i = 0; i < h; i++)
			{
				bool isTop = i == 0;
				bool isBottom = i == h - 1;


				for (int j = 0; j < w; j++)
				{
					bool isLeft = j == 0;
					bool isRight = j == w - 1;

					char c = tiles[i, j];
					if (empty == 0 || c == '#')
					{
						sb.Append(c);
						continue;
					}

					int bombs = 0;

					if (!isTop && tiles[i - 1, j] == '#')
						bombs++;
					if (!isTop && !isRight && tiles[i - 1, j + 1] == '#')
						bombs++;
					if (!isRight && tiles[i, j + 1] == '#')
						bombs++;
					if (!isBottom && !isRight && tiles[i + 1, j + 1] == '#')
						bombs++;
					if (!isBottom && tiles[i + 1, j] == '#')
						bombs++;
					if (!isBottom && !isLeft && tiles[i + 1, j - 1] == '#')
						bombs++;
					if (!isLeft && tiles[i, j - 1] == '#')
						bombs++;
					if (!isTop && !isLeft && tiles[i - 1, j - 1] == '#')
						bombs++;

					c = (char)(bombs + '0');
					tiles[i, j] = c;
					sb.Append(c);

					empty--;
				}

				sb.AppendLine();
			}

			Console.Write(sb.ToString());
		}
	}
}


Measured memory_bytes: 27456
#include "stdio.h"

int main()
{
  int a, b;
  scanf("%d %d", &a, &b);
  if(a <= 9 && 1 <= a && 1 <= b && b <= 9)
  {
    printf("%d", a * b);
    return 0;
  }
  else
  {
    printf("-1");
    return 0;
  }
}


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

const int INF = 1e9;

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

  sort(a, a+n);
  int min_a = a[0];
  int max_a = a[n-1];

  int cost = 1e9;
  for (int v = min_a; v<=max_a; v++) {
    int tmp_cost = 0;
    for (int i=0; i<n; i++) {
      tmp_cost += (a[i] - v) * (a[i] - v);
    }
    if (tmp_cost < cost) {
      cost = tmp_cost;
    }
  }
  cout<<cost<<endl;
}

Measured memory_bytes: 256
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        HashSet<Integer> nums = new HashSet<>(36);
        for (int i = 1; i < 10; i++){
            for (int j = i; j < 10; j++){
                nums.add(i*j);
            }
        }
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            if (nums.contains(in.nextInt())){
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }

    }
}


Measured memory_bytes: 21844
#include <algorithm>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef unsigned long ul;
typedef long long ll;
typedef pair<ul, ul> P;
#define REP(i, n) for (int i = 0; i < n; i++)
const int INF = 1 << 29;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string S;
  cin >> S;
  int Ssize = S.size();
  int ans1 = 0;
  int ans2 = 0;
  REP(ii, Ssize) {
    if (ii % 2 == 0) {
      if ((S[ii] - '0') ^ 0) ++ans1;
      if ((S[ii] - '0') ^ 1) ++ans2;
    } else {
      if ((S[ii] - '0') ^ 1) ++ans1;
      if ((S[ii] - '0') ^ 0) ++ans2;
    }
  }
  cout << min(ans1, ans2) << endl;

  return 0;
}


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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

int n, a[200000];

bool f(int v) {
	if(v == 1) {
		int ma = -1;
		inc(i, n) { if(! setmax(ma, a[i])) { return false; } }
		return true;
	}
	
	map<int, int> mp;
	inc(i, n) {
		int p = (i == 0 ? 0 : a[i - 1]);
		if(p >= a[i]) {
			if(p > a[i]) {
				while(! mp.empty() && mp.rbegin() -> FI >= a[i]) { mp.erase(mp.rbegin() -> FI); }
			}
			decID(j, -1, a[i]) {
				if(j < 0) { return false; }
				mp[j]++;
				if(mp[j] == v) { mp[j] = 0; } else { break; }
			}
		}
	}
	
	return true;
}

int main() {
	cin >> n;
	inc(i, n) { cin >> a[i]; }
	
	int L = 0, H = n;
	while(H - L > 1) {
		int M = (L + H) / 2;
		(f(M) ? H : L) = M;
	}
	
	cout << H << endl;
	
	return 0;
}


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

int main() {
  int n;
  while(cin>>n) {
    if(n > 2) {
      if(n%2) n = 1 + 2*(pow(3,(n-1)/2)-1);
      else n  = 2 + 3*(pow(3,(n-2)/2)-1);
    }
    cout<<n<<endl;
  }
}

Measured memory_bytes: 0
import std.algorithm, std.array, std.container, std.range, std.bitmanip;
import std.numeric, std.math, std.bigint, std.random, core.bitop;
import std.string, std.ascii, std.regex, std.conv, std.stdio, std.typecons;

void main()
{
  auto s = readln.chomp;
  auto p = readln.chomp;

  foreach (i; 0..s.length)
    if ((s[i..$] ~ s[0..i]).indexOf(p) != -1) {
      writeln("Yes");
      return;
    }

  writeln("No");
}

Measured memory_bytes: 2524
a = gets.to_i
b = gets.to_i
c = gets.to_i
d = gets.to_i
e = gets.to_i
x=[]
x << a
x << b
x << c
x << d
x << e

ans_ = 100000
x.permutation(5){|a,b,c,d,e|
    ans = a + (10 - a%10)%10
    ans += b + (10 - b%10)%10
    ans += c + (10 - c%10)%10
    ans += d + (10 - d%10)%10
    ans += e
    ans_ = ans if ans < ans_
}
puts ans_


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

struct UnionFind {
	vector<int> par;

	UnionFind(int N) : par(N) {
		for (int i = 0; i < N; i++) par[i] = i;
	}

	int root(int x) {
		if (par[x] == x) return x;
		return par[x] = root(par[x]);
	}

	bool issame(int x, int y) {
		return root(x) == root(y);
	}

	void merge(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		if (rx == ry) return;
		par[rx] = ry;
	}
};

int main() {
	int N;
	cin >> N;
	vector<long long> x(N), y(N);
	for (int i = 0; i < N; i++) cin >> x[i] >> y[i];

	using pint = pair<int, int>;
	using Edge = pair<long long, pint>;
	vector<Edge> edges;

	vector<int> ids(N);
	for (int i = 0; i < N; i++) ids[i] = i;
	sort(ids.begin(), ids.end(), [&](int i, int j) { return x[i] < x[j]; });
	for (int i = 0; i < N-1; i++) {
		int u = ids[i], v = ids[i+1];
		edges.push_back(Edge(x[v] - x[u], pint(u, v)));
	}
	sort(ids.begin(), ids.end(), [&](int i, int j) { return y[i] < y[j]; });
	for (int i = 0; i < N-1; i++) {
		int u = ids[i], v = ids[i+1];
		edges.push_back(Edge(y[v] - y[u], pint(u, v)));
	}

	sort(edges.begin(), edges.end());
	UnionFind uf(N);
	long long ans = 0;
	for (auto e : edges) {
		int u = e.second.first, v = e.second.second;
		long long cost = e.first;
		if (uf.issame(u, v)) continue;
		uf.merge(u, v);
		ans += cost;
	}
	cout << ans << endl;
}

Measured memory_bytes: 8304
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
def Yes(x):print("Yes")if x==True else print("No")

D=N()
c=[0]+L()
s=[[0]*27]+[[0]+L() for i in range(D)]

dp=[]
T=[0]+LN(D)
sc=sum(c)
def point():
    ld=[0]*(27)
    score=-sc*((D+1)*D//2)
    for i in range(1,D+1):
        t=T[i]
        score+=s[i][t]+(i-ld[t])*(D-i+1)*c[t]
        ld[t]=i
    return score


m=N()
now=point()
for i in range(m):
    d,q=NM()
    old=T[d]
    T[d]=q
    new=point()
    print(new)

Measured memory_bytes: 70192
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) begin(v),end(v)
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
using ll = long long;
using pii = pair<int, int>;
constexpr ll INF = 1ll<<30;
constexpr ll longINF = 1ll<<60;
constexpr ll MOD = 1000000007;
constexpr bool debug = 0;
//---------------------------------//

void dfs(int u, const vector<vector<pii>> & g, vector<int> & done) {
	if (done[u]) return;
	done[u] = true;
	
	for (pii e : g[u]) {
		int v = e.fi;
		if (!done[v]) dfs(v, g, done);
	}
}

int main() {
	int N, M, P;
	cin >> N >> M >> P;
	
	vector<vector<pii>> g(N), rg(N);
	REP(i, M) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		--a; --b;
		g[a].emplace_back(b, c - P);
		rg[b].emplace_back(a, c - P);
	}
	
	vector<ll> d(N, -longINF);
	d[0] = 0;
	vector<int> loop(N);
	REP(i, 3 * M) {
		REP(j, N) {
			if (d[j] == -longINF) continue;
			for (pii e : g[j]) {
				int v = e.fi;
				int c = e.se;
				if (chmax(d[v], d[j] + c)) {
					if (i >= M) loop[v] = true;
				}
			}
		}
	}
	
	vector<int> done[2];
	REP(i, 2) done[i].resize(N);
	dfs(0, g, done[0]);
	dfs(N - 1, rg, done[1]);
	
	bool upl = false;
	REP(i, N) upl |= done[0][i] && done[1][i] && loop[i];
	
	if (upl) puts("-1");
	else cout << max(d[N - 1], 0ll) << endl;
	
	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define dbg(x) cerr << #x << " = " << x << endl
#define _ << ' ' <<
using namespace std;
using ll = long long;
using vi = vector<int>;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a, b, c;
    cin >> a >> b >> c;
    if (c % __gcd(a, b) == 0)
        cout << "YES";
    else
        cout << "NO";
}


Measured memory_bytes: 256