akhauriyash/Code-Regression huggingface dataset:
from bisect import bisect_left, bisect_right
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))

negative_end = bisect_left(A, 0)
positive_start = bisect_right(A, 0)

positive_cnt = N - positive_start
negative_cnt = negative_end
zero_cnt = N - (positive_cnt + negative_cnt)

negative_pairs_cnt = positive_cnt * negative_cnt
zero_pairs_cnt = zero_cnt * (positive_cnt + negative_cnt) + (zero_cnt * (zero_cnt - 1) // 2)

if K <= negative_pairs_cnt:
    # にぶたん: X以下になるペアがK個以上あるか？
    ok, ng = 0, -10 ** 18
    while abs(ok - ng) > 1:
        X = (ok + ng) // 2
        or_higher_cnt, r = 0, positive_start
        for l in range(negative_end):
            while (r < N) and (A[l] * A[r] > X):
                r += 1
            or_higher_cnt += positive_cnt - (r - positive_start)

        if or_higher_cnt >= K:
            ok = X
        else:
            ng = X

    print(ok)

elif K <= negative_pairs_cnt + zero_pairs_cnt:
    print(0)

else:
    # にぶたん: X以下になるペアがK個以上あるか？
    K -= (negative_pairs_cnt + zero_pairs_cnt)
    ok, ng = 10 ** 18, 0
    while abs(ok - ng) > 1:
        X = (ok + ng) // 2
        or_higher_cnt = 0

        r = N - 1
        for l in range(positive_start, N):
            while (r < N) and (A[l] * A[r] > X) and (l < r):
                r -= 1
            or_higher_cnt += max(0, r - l)

        l = 0
        for r in range(negative_end - 1, -1, -1):
            while (l < N) and (A[l] * A[r] > X) and (l < r):
                l += 1

            or_higher_cnt += max(0, r - l)

        if or_higher_cnt >= K:
            ok = X
        else:
            ng = X

    print(ok)


Measured memory_bytes: 95108
counter = {}
start_sum = 0
n = int(input())
a_list = list(map(int, input().split()))
q = int(input())
b_list, c_list = [], []
for _ in range(q):
    b_in, c_in = map(int, input().split())
    b_list.append(b_in)
    c_list.append(c_in)
    counter[b_in] = 0
    counter[c_in] = 0
    

for a in a_list:
    start_sum += a
    if not (counter.get(a) is None):
        counter[a] += 1

for b, c in zip(b_list, c_list):
    counter[c] += counter[b]
    start_sum += (c-b)*counter[b]
    counter[b] = 0
    print(start_sum)

Measured memory_bytes: 24620
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <iomanip>
using namespace std;
#define all(x) x.begin(), x.end()
typedef vector <int> vi;
typedef pair<int,int> ii;
typedef long long ll;
typedef long double ld;
const int mod = 1e9 + 7;
const ll inf = 3e18 + 5;
int add(int a, int b) { return (a += b) < mod ? a : a - mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }
int sub(int a, int b) { return (a -= b) < 0 ? a + mod : a; }
int ctz(int x) { return __builtin_ctz(x); }
int clz(int x) { return __builtin_clz(x); }

int n;
string s;

const int maxn = 5e5 + 5;
int seg[maxn * 4];

void update(int x, int val, int ind = 1, int l = 0, int r = n - 1){
  if(l > x || r < x) return;
  if(l == x && r == x){
    seg[ind] = (1 << val);
    return;
  }
  int mid = (l + r) / 2;
  update(x, val, ind * 2, l, mid);
  update(x, val, ind * 2 + 1, mid + 1, r);
  seg[ind] = seg[ind * 2] | seg[ind * 2 + 1];
}

int get(int tl, int tr, int ind = 1, int l = 0, int r = n - 1){
  if(l > tr || r < tl) return 0;
  if(l >= tl && r <= tr){
    return seg[ind];
  }
  int mid = (l + r) / 2;
  return get(tl, tr, ind * 2, l, mid) | get(tl, tr, ind * 2 + 1, mid + 1, r);
}

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);
  #ifdef LOCAL
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  #endif

  cin >> n;
  cin >> s;
  for(int i = 0; i < n; i++){
    update(i, s[i] - 'a');
  }
  int q;
  cin >> q;
  while(q--){
    int t;
    cin >> t;
    if(t == 1){
      int pos;
      char c;
      cin >> pos >> c;
      pos--;
      update(pos, c - 'a');
    }
    else{
      int l, r;
      cin >> l >> r;
      l--; r--;
      int m = get(l, r);
      cout << __builtin_popcount(m) << "\n";
    }
  }
}

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

// ----本問について----
// 問題：コイン問題
// 問題文URL：https://onlinejudge.u-aizu.ac.jp/problems/DPL_1_A
// 所要時間：
// 学んだこと：
// ------------------

// ----ここから本問のソースコード----

const int N = 50010;
const int M = 25;

// グローバル変数（入力）
ll dp[M][N], n, m, c[M];

ll solve(ll i, ll j) {                     // メモ化再帰（？）
  if (dp[i][j] != -1) { return dp[i][j]; } // 計算済みならその値を返す

  if (i == 1) { dp[i][j] = j; }
  else {
    ll maxCount = j / c[i]; // c[i]の硬貨を使える最大の枚数
    ll mini = LONG_LONG_MAX;  // c[i]を何枚使うかを変えて行った時の最小枚数
    for (ll k = maxCount; k >= 0; k--) {
      mini = min(mini, solve(i - 1, j - c[i] * k) + k);
      // その時点で最大の硬貨を最大枚数使ったらぴったり払える時break（計算量削減）
      if (j - c[i] * k == 0) { break; }
    }
    dp[i][j] = mini;
  }

  return dp[i][j];
}

int main() {
  // cout << fixed << setprecision(10);
  cin >> n >> m;
  for (ll i = 1; i <= m; i++) {
    cin >> c[i];
  }
  sort(c + 1, c + m + 1); // ソートしておく。
  rep(i, M) {
    rep(j, N) {
      dp[i][j] = -1; // dpを全部未計算(-1)に初期化
    }
  }
  cout << solve(m, n) << endl;

  return 0;
}



Measured memory_bytes: 12932
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll temp,n,i,count=0;
    cin>>n;
    map<ll,ll> m1;
    ll arr[n+5];
    for(i=1;i<=n;i++){
        cin>>arr[i];
        m1[arr[i]]=i;
    }
    for(i=1;i<=n;i++){
        if(arr[i]!=i){
            count+=1;
            swap(arr[i],arr[m1[i]]);
            if(count>1){
                cout<<"NO"<<endl;
                return 0;
            }
        }
    }
    cout<<"YES"<<endl;
    return 0;
}


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

int main()
{
	int N;
  	cin >> N;
    vector<int> A(N);
    for(int i=0; i<N; i++)
    {
    	cin >> A.at(i);
    }
  	sort(A.begin(),A.end());
    int sum=0;
  	for(int i=0; i<N; i++)
    {
    	if(i!=N-1) sum+=A.at(i);
      	else sum+=A.at(i)/2;
    }
  	cout << sum << endl;
}

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

#define rep(i,n) for(int i = 0; i < n; i++)
#define Rep(i,n) for(int i = 1; i <= n; i++)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
#define fi first
#define se second
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
template<class T> using V = vector<T>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }



int main(){
    
    ll x;
    cin >> x;
    ll cnt = x / 11;
    cnt *= 2;
    x %= 11;
    if(x == 0) cout << cnt << endl;
    else if(x <= 6) cout << cnt+1 << endl;
    else cout << cnt+2 << endl;
}

Measured memory_bytes: 3564
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
	int a[1010];
	int n,i,max;
	while(scanf("%d",&n)!=EOF)
	{
		max=0;
		for(i=0;i<2*n;i++)
		{
			scanf("%d",&a[i]);
		}
		sort(a,a+n+n);
		for(i=0;i<2*n;i=i+2)
		{
			max=max+a[i];
		}
		printf("%d\n",max);
	}
	return 0;
}

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

int main() {
  string S, T;
  cin >> S >> T;
  int A, B;
  cin >> A >> B;
  string U;
  cin >> U;
  if (S==U) {
    A--;
  }
  else {
    B--;
  }
  cout << A << " " << B << endl;
}

Measured memory_bytes: 3604
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
//小数点以下　cout << fixed << setprecision(10) << num << endl;

int main(){
    int s; cin >> s;
    int a = s/1000;
    int b = s/100-a*10;
    int c = s/10-a*100-b*10;
    int d = s%10;
    int j=10;
    rep(i,8){
        int res=a;
        if(i&(1<<0)) res+=b;
        else res-=b;
        if(i&(1<<1)) res+=c;
        else res-=c;
        if(i&(1<<2)) res+=d;
        else res-=d;
        if(res==7){
            j=i;
            break;
        }
    }
    cout << a;
    if(j&(1<<0)) cout << '+';
    else cout << '-';
    cout << b;
    if(j&(1<<1)) cout << '+';
    else cout << '-';
    cout << c;
    if(j&(1<<2)) cout << '+';
    else cout << '-';
    cout << d << "=7";
}



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

int h, w, a, b;

int main()
{
	cin >> h >> w >> a >> b;

	for (int i = 0; i < b; i++) {
		for (int j = 0; j < a; j++)
			cout << 1;
		for (int j = 0; j < w - a; j++)
			cout << 0;
		cout << endl;
	}
	for (int i = 0; i < h - b; i++) {
		for (int j = 0; j < a; j++)
			cout << 0;
		for (int j = 0; j < w - a; j++)
			cout << 1;
		cout << endl;
	}

	return 0;
}

Measured memory_bytes: 1280
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int D = sc.nextInt();
		int X = sc.nextInt();
		int[] A = new int[N];
		for(int i = 0 ; i < N; i++) {
			A[i] = sc.nextInt();
		}
		int eatNum = 0;
		for(int i = 0; i < N; i++) {
			int tmp = A[i];
			int day = 1;
			while(true) {
				if(day <= D) {
					eatNum++;
					day += A[i];
				} else {
					break;
				}
			}
		}
		System.out.println(X+eatNum);
	}
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for(int i=0;i<(n);i++)
#define all(t) (t).begin(),(t).end()
#define MOD 1000000007
typedef long long ll;
template <class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}else{return 0;}}
template <class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}else{return 0;}}
template <class T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template <class T> inline T LCM(T a,T b){return a*b/GCD(a,b);}

int main(){
	int n;
	cin >> n;
	int p[20010];
	FOR(i,n)cin >> p[i];
	for(int i=1;i<=n;i++){
		cout << i*(n+1);
		if(i!=n)cout << " ";
	}
	cout << endl;
	int ans[20010];

	for(int i=n;i>0;i--){
		ans[n-i]=i*(n+1);
	}
	FOR(i,n){
		ans[p[i]-1]+=i;
	}
	FOR(i,n){
		cout << ans[i];
		if(i!=n-1)cout << " ";
	}
	cout << endl;
}

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

ll mod = 1e9 + 7;
ll dp[100005][13];
int main() {
    string s;
    cin >> s;
    int n = s.length();
    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        int c;
        if (s[i] == '?')
            c = -1;
        else
            c = s[i] - '0';
        for (int j = 0; j < 10; j++) {
            if (c != -1 && c != j) continue;
            for (int ki = 0; ki < 13; ki++) {
                dp[i + 1][(ki * 10 + j) % 13] += dp[i][ki];
                dp[i + 1][(ki * 10 + j) % 13] %= mod;
            }
        }
    }
    cout << dp[n][5] << endl;
    return 0;
}

Measured memory_bytes: 10624
// Aizu Vol0 0093: Leap Year
// 2017.7.29

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

#define MAX 11

int main()
{
	int a, b;
	int i, first_dataset, printed;

	first_dataset = 1;
	while (1) {
		scanf("%d%d", &a, &b);
		if (a == 0 && b == 0) break;

		if (first_dataset) first_dataset = 0;
		else putchar('\n');

		printed = 0;
		for (i = a; i <= b; i++) {
			if (i % 4 == 0 && i % 100 != 0 || i % 400 == 0) {
				printf("%d\n", i);
				printed = 1;
			}
		}
		if (!printed) puts("NA");
	}
	return 0;
}

Measured memory_bytes: 616
d = int(input())
c = list(map(int, input().split()))
s = []


for i in range(d):
    si = list(map(int, input().split()))
    s.append(si)

num = []
ans = 0

for i in range(d):
    day = list(zip(s[i], list(range(1,27))))
    day.sort(reverse=True)
    ans += day[0][0]
    num.append(day[0][1])

for i in range(d):
    print(num[i])

Measured memory_bytes: 9268
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define rep3(i, s, n) for (int i = (s); i <= (int)(n); i++)

int main() {
	long long N;
	long long K;
	int gaid;
	long long ans;
 	long long kai_count;
 	long long kai_max;
 	long long kai_max2;
 	long long kai_max3;
  
	cin >> N >> K;
 	vector<long long> P(N+1);
 	vector<long long> C(N+1);
 	vector<long long> kai_1(N+1);
	ans=-1e10;
	rep3(i,1, N) cin >> P.at(i);
	rep3(i,1, N) cin >> C.at(i);
	rep3(i,1, N) {
 		kai_count=0;
 		kai_1.at(0)=0;
 		kai_max=-1e10;
 		gaid=P.at(i);

		rep3(j,1, min(N,K)) {
			kai_count++;
			kai_1.at(j)=kai_1.at(j-1)+C.at(gaid);
			if(kai_max<kai_1.at(j)) {
				kai_max=kai_1.at(j);
			}
			if (gaid==i) {
				if (kai_1.at(j)<=0) break;
				kai_max2=0;
				if(K%kai_count==0){
					kai_max=kai_max+kai_1.at(j)*(K/kai_count-1);
					break;
				}
				rep3(jj,1,K%kai_count){
					if(kai_max2<kai_1.at(jj)) kai_max2=kai_1.at(jj);
				}
				kai_max3=kai_max2+kai_1.at(j)*(K/kai_count);
				if(kai_max2+kai_1.at(j)<kai_max) {
					kai_max3=kai_max+kai_1.at(j)*(K/kai_count-1);
				}
              	kai_max=kai_max3;
				break;
            }
          gaid=P.at(gaid);
		}
		if(ans<kai_max) ans=kai_max;
	}

	cout << ans << endl;
	return 0;
}


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

using ll=long long;
int main(){
    ll n,p,q;
    cin>>n>>p>>q;
    vector<ll> c(n);
    for(int i=0;i<n;i++) cin>>c[i];

    vector<ll> dem(n);
    for(ll i=0;i<n;i++){
        dem[i]=p*i+c[i];
    }
    sort(dem.begin(),dem.end());
    ll sum=accumulate(c.begin(),c.end(),0LL);
    ll res=sum;
    ll dsum=0;
    for(ll i=0;i<n;i++){
        dsum+=dem[i];
        ll m=i+1;
        ll sc=sum+m*p*q+p*m*(m-1)-dsum;
        res=max(res,sc);
    }
    cout<<res<<endl;
    return 0;
}


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

import io
import sys
import math

def solve():
    # implement process
    pass

def main():
    # input
    n = int(input())
    s_list = []
    for s in range(n):
      s_list.append(input())
    
    # process
    s_set = set(s_list)
    ans = str( len( s_set) )
    
    # output
    print(ans)
    return ans
        
### DEBUG I/O ###
_DEB = 0   # 1:ON / 0:OFF

_INPUT = """\
5
grape
grape
grape
grape
grape
"""
_EXPECTED = """\
1
"""

def logd(str):
    """usage:
    if _DEB: logd(f"{str}")
    """
    if _DEB: print(f"[deb] {str}")

### MAIN ###
if __name__ == "__main__":
    if _DEB:
        sys.stdin = io.StringIO(_INPUT)
        print("!! Debug Mode !!")

    ans = main()

    if _DEB:
        print()
        if _EXPECTED.strip() == ans.strip(): print("!! Success !!")
        else: print(f"!! Failed... !!\nANSWER:   {ans}\nExpected: {_EXPECTED}")

Measured memory_bytes: 35532
#include<bits/stdc++.h>
using namespace std;
const int N=1<<20;
int a[N];

int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",a+i);
		if(i && a[i]>a[i-1]+1)
		{
			puts("-1");
			return 0;
		}
	}
	if(a[0])
	{
		puts("-1");
		return 0;
	}
	long long ans=0;
	for(int i=0;i<n;i++)
	{
		if(i==n-1 || a[i+1]<=a[i])ans+=(long long)a[i];
	}
	cout<<ans<<endl;
	return 0;
}

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

int main() {
  cout << fixed << setprecision(15);
  int n, k;
  cin >> n >> k;

  int max_sum = 0;
  vector<int> arr(n);
  for (int i = 0; i < n; ++i) {
    cin >> arr[i];
    if (i < k) {
      max_sum += arr[i];
    }
  }
  int curr_sum = max_sum;

  for (int i = k; i < n; ++i) {
    curr_sum += arr[i] - arr[i - k];
    max_sum = max(curr_sum, max_sum);
  }

  cout << (k + max_sum) / 2.0 << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define llu unsigned long long int
#define sa(a,n,t) for(int ii=0;ii<n;ii++) scanf("%"#t"",&(a)[ii])
#define rep(i,n) for(int i=0;i<n;i++) 
#define reps(i,a,n) for(int i=a;i<n;i++) 
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define rreps(i,a,n) for(int i=n-1;i>=a;i--)
#define validl(i,a,b) ((i>=a)&&(i<=b))?1:0
#define validmat(x,y,a,b,c,d) (validl(x,a,b) && validl(y,a,b))?1:0
#define validmn(x,y,m,n) validmat(x,y,0,m,0,n)
#define valid(i,n) validl(i,0,n)
#define v(t) vector<t>
#define vv(t) vector<vector<t> >
#define mk make_pair
#define pb push_back
#define pa(a,n,t)  for(int i=0;i<n;i++) printf("%"#t"",a[i])
#define p2 pair<int,int>
#define p3 pair<p2,int>
#define fi first
#define se second
#define sd(a) scanf("%d",&a)
#define sl(a) scanf("%lld",&a)
#define pl(a) printf("%lld",a)
#define pd(a) printf("%d",a)
#define sf(a) scanf("%lf",&a)
#define pf(a) printf("%lf",a)
#define nline printf("\n")
#define ss(a) scanf("%s",a)
#define ps(a) printf("%s",a)
#define sc(a) scanf("%c",&a)
#define pc(a) printf("%c",&a)
#define mf(m,f) m.find(f)!=m.end()
#define pp3(m) cout<<m.fi.fi<<" "<<m.fi.se<<" "<<m.se<<" "
#define pp2(m) cout<<m.fi<<" "<<m.se<<" "
#define debug 0
/*v(int) adj[200001];
void dfs(int i,int p){
    rep(j,adj[i].size()){
        if(p!=adj[i][j])
            dfs(adj[i][j],i);
    }
}*/
int main()
{
  int n;
  cin>>n;
  if(n<600) cout<<8;
  else if(n<800) cout<<7;
  else if(n<1000) cout<<6;
  else if(n<1200) cout<<5;
  else if(n<1400) cout<<4;
  else if(n<1600) cout<<3;
  else if(n<1800) cout<<2;
  else if(n<2000) cout<<1;
  //cout<<"-kyu\n";
  return 0;
}


Measured memory_bytes: 3660
#コストをマイナスにして最小化する
import sys
inf=10**15
fastinput=sys.stdin.readline
N,M=map(int,fastinput().split())
cost=[inf]*N
cost[0]=0
abc=[[int(o) for o in fastinput().split()] for _ in range(M)]#[a,b,c];点a-1とb-1を結ぶ辺のコストが-c
for t in range(N):
    changed=0
    for a,b,c in abc:
        if cost[b-1]>cost[a-1]-c:
            changed=1#コストの更新あり
            cost[b-1]=cost[a-1]-c
gendankainokosuto=cost[N-1]
for t in range(100):
    changed=0
    for a,b,c in abc:
        if cost[b-1]>cost[a-1]-c:
            changed=1#コストの更新あり
            cost[b-1]=cost[a-1]-c
if cost[N-1]!=gendankainokosuto:
    print("inf")
else:
    print(-cost[N-1])

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

int main(){
    string s;
    cin>>s;
    bool f=true;
    rep(i,s.size()){
        char x=s[i];
        if(i%2==0){
            if(x=='L') f=false;
        }
        else{
            if(x=='R') f=false;
        }
    }
    cout<<(f?"Yes":"No")<<endl;
    return 0;
}


Measured memory_bytes: 256
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;


long P = 10^^9+7;
long[10^^5*2+50] F, RF;

long pow(long x, long n) {
    long y = 1;
    while (n) {
        if (n%2 == 1) y = (y * x) % P;
        x = x^^2 % P;
        n /= 2;
    }
    return y;
}

long inv(long x)
{
    return pow(x, P-2);
}

void init()
{
    F[0] = F[1] = 1;
    foreach (i, ref x; F[2..$]) x = (F[i+1] * (i+2)) % P;

    {
        RF[$-1] = 1;
        auto x = F[$-1];
        auto k = P-2;
        while (k) {
            if (k%2 == 1) RF[$-1] = (RF[$-1] * x) % P;
            x = x^^2 % P;
            k /= 2;
        }
    }
    foreach_reverse(i, ref x; RF[0..$-1]) x = (RF[i+1] * (i+1)) % P;
}

long comb(N)(N n, N k)
{
    if (k > n) return 0;
    auto n_b = F[n];    // n!
    auto nk_b = RF[n-k]; // 1 / (n-k)!
    auto k_b = RF[k];    // 1 / k!

    auto nk_b_k_b = (nk_b * k_b) % P; // 1 / (n-k)!k!

    return (n_b * nk_b_k_b) % P;  // n! / (n-k)!k!
}

alias E = Tuple!(int, "i", long, "k", long, "p");

void main()
{
    init();
    auto N = readln.chomp.to!int;
    int[][] T;
    T.length = N;
    foreach (_; 0..N-1) {
        auto ab = readln.split.to!(int[]);
        auto a = ab[0]-1;
        auto b = ab[1]-1;
        T[a] ~= b;
        T[b] ~= a;
    }

    E[][] es;
    es.length = N;
    E run1(int i, int p) {
        long pp = 1, k;
        foreach (j; T[i]) if (j != p) {
            auto e = run1(j, i);
            es[i] ~= e;
            pp = pp * inv(F[e.k]) % P * e.p % P;
            k += e.k;
        }
        return E(i, k + 1, pp * F[k] % P);
    }
    run1(0, -1);
    void run2(int i, int p, E e) {
        long pp = 1;
        if (p != -1) {
            pp = pp * inv(F[e.k]) % P * e.p % P;
        }
        foreach (ee; es[i]) {
            pp = pp * inv(F[ee.k]) % P * ee.p % P;
        }
        foreach (ee; es[i]) {
            run2(ee.i, i, E(i, N - ee.k, pp * F[N-ee.k-1] % P * F[ee.k] % P * inv(ee.p) % P));
        }
        if (p != -1) es[i] ~= e;
    }
    run2(0, -1, E(0, 0, 1));

    foreach (i; 0..N) {
        long r = F[N-1];
        foreach (e; es[i]) if (e.i != i) {
            r = r * inv(F[e.k]) % P * e.p % P;
        }
        writeln(r);
    }
}

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

std::string getPoundLine(int stringLength) {
    std::string poundLine = "";
    int i;
    
    for (i = 0; i < stringLength; ++i) {
        poundLine += "#";
    }
    
    return poundLine;
}

std::string getDottedLine(int stringLength) {
    std::string dottedLine = "";
    int i;
    
    for (i = 0; i < stringLength; ++i) {
        if (i == 0 || i == stringLength - 1) {
            dottedLine += "#";
        } else {
            dottedLine += ".";
        }
    }
    
    return dottedLine;
}


int main() {
    
    while (true) {
        int h, w = 0;
        std::cin >> h >> w;
        
        if (h == 0 && w == 0) {
            break;
        }
        
        int i;
        
        for (i = 0; i < h; ++i) {
            if (i == 0 || i == h - 1) {
                std::cout << getPoundLine(w) << std::endl;
            } else {
                std::cout << getDottedLine(w) << std::endl;
            }
        }
        
        
        std::cout << std::endl;
    }

    return 0;
   
}


Measured memory_bytes: 3184
##########################
#  
##########################
from functools import reduce
from fractions import gcd

MOD = 10**9+7

def lcm_base(x, y):
    return x * (y // gcd(x, y))

def main():
    N = int(input())
    a = [int(i) for i in input().split()]

    lcm = reduce(lcm_base, a, 1)
    lcm %= MOD
    
    b = sum(pow(i, MOD - 2, MOD) for i in a)
    b %= MOD
    ans = lcm * b

    print(ans % MOD)


if __name__ == "__main__":
    main()


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

int main() {
    int a,b,c;
    cin >> a >> b >> c;
    
    if(c%gcd(a,b) != 0) {
        cout << "NO";
    }    
    else {
     cout << "YES";
    }
    }


Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define reg register

using namespace std;

typedef long long ll;
const int maxn = 100005;

inline ll read() {
    reg ll s = 0, t = 0; reg char ch = getchar();
    while (!isdigit(ch)) t |= ch == '-', ch = getchar();
    while (isdigit(ch)) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return t ? -s : s;
}

int main() {
    reg int n = read(), cnt = 0, k = read();
    for (reg int i = 1; i <= n; i++) {
        reg int x = read();
        if (x >= k) cnt++;
    }
    cout << cnt << endl;
    return 0;
}


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

#define FOR(i,a,b) for(int i = a; i < b; i++)
#define pb push_back

typedef long long ll;
typedef pair<int, int> ii;

const int N = 1e6 + 5;

int main(){

    int n;
    cin >> n;
    if(n < 1200)
        cout << "ABC";
    else if(n < 2800)
        cout << "ARC";
    else
        cout << "AGC";

    return 0;
}


Measured memory_bytes: 384
import itertools
import sys

s=input()
a,b,c,d=s

op=("+","-")
for op1,op2,op3 in itertools.product(op,repeat=3):
    if eval(a + op1 + b + op2 + c + op3 + d)==7:
        print(a + op1 + b + op2 + c + op3 + d+"=7")
        sys.exit()

Measured memory_bytes: 3064
s = input()
record = list(s)
n = 0
high_score = 0
yesterday = ' '
for today in record :
    if today == 'R':
        if yesterday == 'R' :
            n += 1
        else :
            n = 1
    if high_score < n :
        high_score = n
    yesterday = today
print(high_score)


Measured memory_bytes: 9040
//master
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] a = new int[n];
        for(int i = 0; i<k; i++) {
            int b = sc.nextInt();
            for(int j = 0; j<b; j++) { 
                a[sc.nextInt()-1]++;
            }
        }
        int count = 0;
        for(int i = 0; i<n; i++) { 
            if(a[i]==0) count++;
         }
         p(count);
    }

    public static <T> void p(T message) {
        System.out.println(message);
    }

    public static <T> void pe(T message) {
        System.err.println(message);
    }

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


Measured memory_bytes: 26384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF = 1LL << 60;
const int MAX = 1000000010;
const ll MOD = 1000000007;
const double PI = acos(-1);

int main () {
    int N; cin >> N;
    vector<int> cnt(100010);
    ll sum = 0;
    for (int i = 0; i < N; i++) {
        int a; scanf("%d", &a);
        cnt[a]++;
        sum += a;
    }
    int Q; cin >> Q;
    for (int i = 0; i < Q; i++) {
        int b, c; scanf("%d %d", &b, &c);
        sum += (ll)(c - b) * cnt[b];
        cnt[c] += cnt[b];
        cnt[b] = 0;
        
        printf("%lld\n", sum);
    }

    return 0;
}

Measured memory_bytes: 3764
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;
const int maxn=500000+10;
int n;
int a[maxn];

void max_heapify(int i)
{
    int left=2*i+1;
    int right=2*i+2;
    int largest;
    if(left<=n&&a[left]>a[i])  largest=left;
    else largest=i;
    if(right<=n&&a[right]>a[largest]) largest=right;
    if(i!=largest)
    {
        swap(a[i],a[largest]);
        max_heapify(largest);
    }
}
void build_heap()
{
    for(int i=n/2;i>=0;i-- ) max_heapify(i);
}
int main()
{
//    freopen("in.txt","r",stdin);
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    build_heap();
    for(int i=0;i<n;i++) printf(" %d",a[i]);
    printf("\n");

    return 0;
}

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

int main() {
   int n,m;
   cin >> n >> m;
   int x[m];
   int d[m-1];
   for(int i=0;i<m;i++){
      cin>>x[i];
   }
   sort(x,x+m);
   for(int i=0;i<m-1;i++){
      d[i] = x[i+1] - x[i];
      if(d[i]<0)d[i]=-d[i];
   }
   sort(d,d+m-1);
   int sum=0;
   for(int i=0;i<m-1-(n-1);i++){
      sum += d[i];
   }
   cout<<sum<<endl;

   return 0;
}


Measured memory_bytes: 1024
#define FNAME ""

#include <bits/stdc++.h>

#define hash padjf9srpi
#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define pb push_back
#define mp make_pair
#define forn(i, n) for (int i = 0; i < (n); i++)
#define fornr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define forab(i, a, b) for (int i = (a); i < (b); i++)
#define gcd __gcd
#define all(a) (a).begin(), (a).end()
 
#ifdef _WIN32
    #define I64 "%I64d"
#else
    #define I64 "%lld"
#endif

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair <int, int> pii;                                                                                                                                                                                      
typedef vector <int> vi;

template <class T> T sqr(const T &a) {return a * a;}

int n, x, a[30000];


int main()
{
#ifdef LOCAL
    freopen(FNAME".in", "r", stdin);
    freopen(FNAME".out", "w", stdout);
#endif

    scanf("%d%d", &n, &x);
    forn(i, n)
        scanf("%d", &a[i]);
    LL ans = 1e18;
//    sort(a, a + n);
    forn(cnt, n + 1) {
        LL cur = 1ll * cnt * x;
        multiset<int> Set;
        forab(i, n - cnt, n)
            Set.insert(a[i]);
        forn(i, n){
            Set.insert(a[i]);
            cur += *Set.begin();
            Set.erase(Set.find(a[(i - cnt + n) % n]));
        }    
        ans = min(ans, cur);
    }
    printf("%lld\n", ans);
}



Measured memory_bytes: 384
#include<bits/stdc++.h>
#define rp(i,n) for(int i=0; i<n; i++)
using namespace std;
using ll=long long;
#define INF 1000000000
vector<int> dp(20005,INF);
int main(){
    int h,n;
    cin  >> h >> n;
    vector<int> a(n),b(n);
    int amax=0;
    rp(i,n){
        cin >> a.at(i) >> b.at(i);
        amax=max(amax,a.at(i));
    }
    dp.at(0)=0;
    rp(c,n){
        rp(i,h+amax){
            if(a.at(c)>i) continue;
            else{
                dp[i]=min(dp[i],dp[i-a[c]]+b[c]);
            }
        }
    }
    int ans=INF;
    for(int i=h; i<h+amax; i++){
        ans=min(ans,dp[i]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <algorithm>
#include <utility>
#include <iomanip>
#include <functional>
#include <queue>
#include <stack>
#include <cmath>
#include <numeric>
#define INF 100000000
#define MOD 1000000007
using namespace std;



int main(){
    long long N,M;
    cin >> N >> M;
    
    if(N==1 && M==1){
        cout<<1<<endl;
        return 0;
    }
    
    if(N==1){
        cout<<M-2<<endl;
        return 0;
    }
    
    if(M==1){
        cout<<N-2<<endl;
        return 0;
    }
    
    cout<<(N-2)*(M-2)<<endl;
    return 0;
}


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

int main(){
    
    for(int n; cin >> n, n;){
        vector<int>w(n);
        vector<vector<int> >dp(n, vector<int>(n, 0));
        for(int i = 0; i < n; i++)cin >> w[i];
        for(int l = 0; l + 1 < n; l++){
            if(abs(w[l] - w[l + 1]) <= 1){
                dp[l][l + 1] = 2;
            }
        }
        for(int i = 2; i <= n; i++){
            for(int l = 0; l + i < n; l++){
                int r = l + i;
                if(abs(w[l] - w[r]) <= 1 && dp[l + 1][r - 1] == r - l - 1){
                    dp[l][r] = r - l + 1;
                }
                for(int p = l; p < r; p++){
                    dp[l][r] = max(dp[l][r], dp[l][p] + dp[p + 1][r]);
                }
            }
        }
        cout << dp[0][n - 1] << endl;
    }

    return 0;
}


Measured memory_bytes: 3280
#include <cstdio>
inline int min(int a,int b){return (a<b)?a:b;}
int main(){
    int a=1,n,k;
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;++i) a+=min(a,k);
    printf("%d\n",a);
}

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

int main(void) {
    long long x;
    cin >> x;
    long long sum = 0;
    long long tmp = x;
    while (tmp > 0) {
        sum += tmp % 10;
        tmp /= 10;
    }

    if (x % sum == 0) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

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

int main(int argc, const char * argv[]) {
    int i1, i2;
    cin >> i1 >> i2;
    
    int cnt = 0;
    for(int i = i1; i <= i2; i++) {
        string sti = to_string(i);
        if(sti[0] == sti[4] && sti[1] == sti[3]) {
            cnt++;
        }
        
    }
    
    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
bool mp(const int &x,const int &y){
	return x>y;
}
int main(){
	int x[10],y[10];
	for(int i=0;i<10;i++)
	cin>>x[i];
	for(int i=0;i<10;i++)
	cin>>y[i];
	sort(x,x+10,mp);
	sort(y,y+10,mp);
	cout<<x[0]+x[1]+x[2]<<' '<<y[0]+y[1]+y[2]<<endl;
	return 0;
}

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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;

#define INF INT_MAX/3

#define MAX_N 1000

struct dice{
	int d[6];
	void rotation(int& w,int& x,int& y,int& z){
		int tmp=w; w=x; x=y; y=z; z=tmp;
	}
	void n(){rotation(d[4],d[0],d[1],d[5]);}
	void e(){rotation(d[2],d[0],d[3],d[5]);}
	void w(){rotation(d[3],d[0],d[2],d[5]);}
	void s(){rotation(d[1],d[0],d[4],d[5]);}
	void spin(){rotation(d[1],d[2],d[4],d[3]);}
	int query(int a,int b){
		string ss="WWWWSWW";
		rep(i,ss.length()){
			if(ss[i]=='W')w();
			if(ss[i]=='S')s();
			if(d[0]==a)break;
		}
		if(d[0]!=a)return -1;
		rep(i,4){
			if(d[1]==b)break;
			spin();
		}
		if(d[1]!=b)return -1;
		return d[2];
	}
	bool equal(dice a){
		return a.d[2]==query(a.d[0],a.d[1])&&a.d[3]==d[3]&&a.d[4]==d[4]&&a.d[5]==d[5];
	}
};

int n;
dice dic[111];

int main(){
	cin.sync_with_stdio(false);
	cin>>n;
	rep(i,n){
		rep(j,6)cin>>dic[i].d[j];
	}
	rep(i,n)rep(j,i){
		if(dic[i].equal(dic[j])){
			//dbg(i); dbg(j);
			cout<<"No"<<endl;
			return 0;
		}
	}
	cout<<"Yes"<<endl;
	return 0;
}



Measured memory_bytes: 3240
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
     
int main() 
{
   int N, m, r, sum;
   cin >> N;

   rep(i, N) 
    {
      cin >> m >> r;
      sum += r-m+1;
    }
  
    cout << sum << endl;
}

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

int main() {
	int a, b, c;

	cin >> a >> b >> c;

	if (a < b) {
		if (b < c) 
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
		}
		else
			cout << "No" << endl;
	}

Measured memory_bytes: 3080
#include <cstdio>
#include <utility>

#define MAX 200000

class card
{
public:
	int id;
	int value;
};

int partition(card A[], int bigP, int endP){
	int x = A[endP].value;
	int i = bigP-1;
	for(int j=bigP; j< endP; j++){
		if(A[j].value <= x){
			i = i+1;
			std::swap(A[i], A[j]);
		}
	}
	std::swap(A[i+1], A[endP]);
	return i+1;
}


void quickSort(card A[], int bigP, int endP, int q)
{
	if(bigP<endP){
		q = partition(A, bigP, endP);
		quickSort(A, bigP, q-1, q);
		quickSort(A, q, endP, q);
	}
}

int main()
{
	card A[MAX];
	int N;
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		A[i].id = i+1;
		scanf("%d", &A[i].value);
	}
	quickSort(A, 0, N-1, 0);
	for(int i=0; i<N; i++){
		if(i) printf(" ");
		printf("%d", A[i].id);
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 1536
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <numeric>
#include <algorithm>
#include <stack>
#include <map>
using namespace std;
string S;
int n;
int main() {
    int a, b; cin >> a >> b;
    if(a<=8&&b<=8) cout << "Yay!" << endl;
    else cout << ":(" << endl;
    return 0;
}

Measured memory_bytes: 764
while True:
    n = int(input())

    if n == 0:
        break

    score = list(map(float, input().split()))
    ave = sum(score)/float(n)

    score_sum = 0.0

    for i in range(n):
        score_sum += (score[i]-ave)**2

    sigma = (score_sum/float(n))**0.5

    print('{:.08f}'.format(sigma))


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

using ll = long long;
using namespace std;
const int INFint = 1e9+1;
const ll INFll = (ll)1e18+1;
ll MOD=1e9+7;

int main(){
  string s;
  cin>>s;
  ll N = int(s.size());
  ll cnt[30] = {0};
  for(int i(0);i<N;i++){
    cnt[s[i]-'a']++;
  }
  ll ans(N*(N-1)/2+1);
  //cout << ans << endl;
  for(int i(0);i<30;i++){
    ans -= (cnt[i]*(cnt[i]-1)/2);
  }
  cout << ans << endl;
  return 0;
}


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

#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define ACC(c) (accumulate(ALL(c), 0LL))
#define PRINT(x) cout << (x) << "\n"

using namespace std;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;

inline int in(int& a) {return scanf("%d", &a);}
auto pint_compare = [](pint x, pint y) -> bool{return (x.first < y.first);};


signed main(){
    int A, B;
    cin >> A >> B;
    int x = 1, cnt = 0;
    while(x < B){
        x += A - 1;
        cnt++;
    }
    PRINT(cnt);
    return 0;
}

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

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

	int dp[n];
		for(int i=0;i<n;i++){
			dp[i]=9999999999999;
		}
		dp[0]=0;
		dp[1]=abs(a[1]-a[0]);
		for(int i=2;i<n;i++){
			for(int j=i-1, jj=0 ; (j>=0 && jj<k) ; j--,jj++){

					dp[i]=min(dp[i], dp[j]+abs(a[i]-a[j]));
				}
		}
		cout<<dp[n-1]<<endl;
		return 0;
	}


Measured memory_bytes: 1024
#include <stdio.h>
const int N=14e2+10;
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a>b?b:a;}
int main(){
    int n,m,dp[N][N],ans=0;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)for(int j=0;j<m;j++){
        scanf("%d",&dp[i][j]);
        dp[i][j]=1-dp[i][j];
        if(dp[i][j]==1)ans=1;
    }
    for(int i=1;i<n;i++)for(int j=1;j<m;j++)if(dp[i][j]==1)ans=max(ans,dp[i][j]+=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]));
    printf("%d\n",ans*ans);
}


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

using namespace std;
typedef long long nagai;

int main()
{
	int q;
	cin >> q;
	while (q--)
	{
		nagai a, b;
		cin >> a >> b;
		auto mxpref = [&](nagai a, nagai b)
		{
			nagai L = 0, R = a;
			while (R - L > 1)
			{
				nagai M = (L + R) / 2;
				nagai L1 = 1, R1 = M;
				while (R1 - L1 > 2)
				{
					nagai M1 = (2 * L1 + R1) / 3;
					nagai M2 = (L1 + 2 * R1) / 3;
					if (M1 * (b + M + 1 - M1) > M2 * (b + M + 1 - M2))
						R1 = M2;
					else
						L1 = M1;
				}
				nagai mx = 0;
				for (int i = max(1LL, L1 - 2); i <= min(M, R1 + 2); ++i)
				{
					mx = max(mx, i * (b + M + 1 - i));
				}
				if (mx < a * b)
					L = M;
				else
					R = M;
			}
			return L;
		};
		nagai pref1 = mxpref(a, b);
		nagai pref2 = mxpref(b, a);
		cout << pref1 + pref2 + min(a - pref1 - 1, b - pref2 - 1) << '\n';
	}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define range(a) a.begin(), a.end()

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int A, B, M; cin >> A >> B >> M;
  vector<int> a(A);
  vector<int> b(B);
  rep(i, A) cin >> a[i];
  rep(i, B) cin >> b[i];
  int ans = INT_MAX;
  ans = min(ans, *min_element(range(a)) + *min_element(range(b)));
  rep(i, M) {
    int x, y, c; cin >> x >> y >> c;
    x--; y--;
    ans = min(ans, a[x] + b[y] - c);
  }
  cout << ans << endl;
}

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

int main() {
  int N;
  cin >> N; 
  
  int X,Y;
  X=(N-N%10)%111;
  Y=(N%1000)%111;
  
  if ( X==0 || Y==0 )
    cout << "Yes" << endl;

  else 
    cout << "No" << endl;
}


Measured memory_bytes: 256
// ABC052B - 

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

typedef unsigned long long int ull;
typedef long long int ll;

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

	int maxT = 0;

	int x = 0;
	for (int i = 0; i < N; i++) {
		if (S[i] == 'I') {
			++x;
		} else if (S[i] == 'D') {
			--x;
		}
		maxT = max(maxT, x);
	}

	cout << maxT << endl;

	return 0;
}


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

static const int MAX = 2000000;

int n;
int C[MAX];

void CountingSort(int A[], int B[], int k) {
	for (int i = 0; i <= k; i++) {
		C[i] = 0;
	}

	for (int j = 1; j < n + 1; j++) {
		C[A[j]] += 1;
	}

	for (int i = 1; i <= k; i++) {
		C[i] = C[i - 1] + C[i];
	}
	
	for (int j = n; j > 0; j--) {
		B[C[A[j]]] = A[j];
		C[A[j]]--;

	}
}

int main() {
	cin >> n;
	int A[MAX+1], B[MAX+1];
	int k = 0;
	for (int i = 1; i < n+1; i++) {
		cin >> A[i];
		if (A[i] > k) {
			k = A[i];
		}
	}
	CountingSort(A, B, k);

	for (int i = 1; i <= n; i++) {
		if (i > 1) {
			cout << " ";
		}
		cout << B[i];
	}
	cout << endl;

}


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

int main() {
    int N, W;
    std::cin >> N >> W;

    std::vector<int> dp(W + 1, 0);
    for (int i = 0; i < N; ++i) {
        int v, w;
        std::cin >> v >> w;
        for (int j = 0; j + w <= W; ++j) {
            dp[j + w] = std::max(dp[j + w], dp[j] + v);
        }
    }

    std::cout << *std::max_element(dp.begin(), dp.end()) << std::endl;
    return 0;
}



Measured memory_bytes: 3128
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define se second
#define fi first
#define ll long long int
#define INF INT_MAX
#define mod
#define chutiyaap ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
int main()
{
    chutiyaap;
    int n;cin>>n;
    int b[n+1];for(int i=0;i<n-1;i++)cin>>b[i];
    int res=b[0]+b[n-2];
    for(int i=1;i<n-1;i++)res+=min(b[i],b[i-1]);
    cout<<res;
    return 0;
}

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


int main(){
  string s; cin>>s;
  
  int ct=0, ans=0;
  for(int i=0; i<s.size(); i++){
    if(s[i]=='A' || s[i]=='C' || s[i]=='G' ||s[i]=='T'){
      ct++;
    }else{
      ct=0;
    }
    ans = max(ans,ct);
  }
  cout << ans << endl;
}


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


ll powmod(ll n,ll k){
    k%=mod-1;
    if(k<0)k+=mod-1;
    ll ret=1;
    while(k){
        if(k&1)ret=ret*n%mod;
        n=n*n%mod;
        k>>=1;
    }
    return ret;
}
int main(){
    int n;
    cin>>n;
    ll x[n];
    ll ans = 0;
    rep(i,n){
        cin>>x[i];
        ans += x[i]*powmod(x[i]+1,i)%mod*powmod(2,n-i-1)%mod;
    }
    cout<<ans%mod<<endl;
    return 0;
}


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

int32_t main()
{
    int n;
    cin >> n;
    map<int, int> mapa;
    for(int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        if(mapa.count(x)) return puts("NO"), 0;
        mapa[x] = 1;
    }
    puts("YES");
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef long double ld;

const int INF = (int) 1e9 + 123;
const ll LINF = (ll) 1e18 + 123;
const ld EPS = (ld) 1e-12;
const ll MOD = (ll) 1e9 + 7;

#define sz(x) (int) (x).size()
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb(s, t, x) (int) (lower_bound(s, t, x) - s)
#define ub(s, t, x) (int) (upper_bound(s, t, x) - s)
#define rep(i, f, t) for (auto i = f; i < t; i++)
#define per(i, f, t) for (auto i = f; i >= t; i--)

ll power(ll x, ll y, ll mod = MOD) {
    if (y == 0) {
        return 1;
    }
    if (y & 1) {
        return power(x, y - 1, mod) * x % mod;
    } else {
        ll tmp = power(x, y / 2, mod);
        return tmp * tmp % mod;
    }
}

void add(ll &x, ll y, ll mod = MOD) {
    x += y;
    if (x >= mod) x -= mod;
    if (x < 0) x += mod;
}

ll sum(ll x, ll y, ll mod = MOD) {
    add(x, y, mod);
    return x;
}

ll mult(ll x, ll y, ll mod = MOD) {
    return (x * y) % mod;
}

ll div(ll x, ll y, ll mod) {
    return x * power(y, mod - 2, mod);
}

template<typename A, typename B> bool mini(A &x, const B &y) {
    if (y < x) {
        x = y;
        return true;
    }
    return false;
}

template<typename A, typename B> bool maxi(A &x, const B &y) {
    if (y > x) {
        x = y;
        return true;
    }
    return false;
}

template<typename T> void read(T first, T last) {
    while (first != last) {
        cin >> *(first++);
    }
}

template<typename T> void print(T first, T last) {
    while (first != last) {
        cout << *(first++) << " ";
    }
    cout << "\n";
}

void run();

#define TASK ""

int main() {
#ifdef LOCAL
    if (strlen(TASK) > 0) {
        cerr << "Reminder: you are using file i/o, filename: " TASK "!" << endl << endl;
    }
#endif
#ifndef LOCAL
    if (strlen(TASK)) {
        freopen(TASK ".in", "r", stdin);
        freopen(TASK ".out", "w", stdout);
    }
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif
    cout << fixed << setprecision(12);
    run();
    return 0;
}

// == SOLUTION == //

void run() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int l = max(a, c);
    int r = min(b, d);
    cout << max(0, r - l) << "\n";
}


Measured memory_bytes: 256