akhauriyash/Code-Regression huggingface dataset:
//ABC078C
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <climits>
#include <cfloat>
#include <string>
using namespace std;

int main(){
	int n, m;
	cin >> n >> m;
	long long int t;
	t = 1800*m + 100*n;
	for(int i=0;i<m;i++){
		t *= 2;
	}
	cout << t << endl;
	return 0;
}

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

int main(){

    int n, a[100];
    std::cin >> n;

    int i = 0;

    for ( ;  i < n; i++ ) std::cin  >> a[i];
    for ( ; i--; )        std::cout << a[i] << ( i ? " " : "" );

    std::cout << std::endl;

    return 0;
}



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

using namespace std;

#define DUMP(x) std::cout << (#x) << " = " << (x) << "\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP(i, k, n) for (int i = (k); i < (int)(n); ++ i)
#define ALL(r) r.begin(), r.end()
#define DUP(x, y) (((x) + (y) - 1) / (y))

using ll = std::int64_t;
using vint = std::vector<int>;
using vll = std::vector<ll>;
using pint = std::pair<int, int>;

constexpr std::int32_t INF = 1001001001;

int f(int n) {
    if (n % 2 == 0) return n / 2;
    else return 3 * n + 1;
}

void Main() {
    int s;
    cin >> s;

    unordered_set<int> a;
    a.insert(s);
    int pre = s;
    int ans = 1;
    while(true){
        ++ans;
        int cur = f(pre);
        pre = cur;
        if (a.count(cur) == 0) {
            a.insert(cur);
        }
        else {
            break;
        }
    }
    cout << ans << endl;
}

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}



Measured memory_bytes: 384
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<map>

using namespace std;
#define REP(i,e,s) for(register int i=e; i<=s; i++)
#define DREP(i,e,s) for(register int i=e; i>=s; i--)
#define DE(...) fprintf(stderr,__VA_ARGS__);
#define DEBUG(a) DE("DEBUG: %d\n",a)
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
#define ll long long

int read() {
	int x=0,f=1,ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int INF=0x3f3f3f,MAXN=6e5,MAXM=3e5;

int head[MAXN],to[MAXM<<2],_next[MAXM<<2],weigh[MAXM<<2],cnt;

void addedge(int u,int v,int w) {
	cnt++;
	_next[cnt]=head[u];
	head[u]=cnt;
	to[cnt]=v;
	weigh[cnt]=w;
}

int dist[MAXN],inq[MAXN];
queue<int> q;
void SPFA() {
	q.push(1);
	inq[1]=1;
	memset(dist,127,sizeof(dist));
	dist[1]=0;
	while(!q.empty()) {
		int u=q.front();q.pop();
		inq[u]=0;
		for(int i=head[u]; i; i=_next[i]) {
			int v=to[i];
			if(dist[v]>dist[u]+weigh[i]) {
				dist[v]=dist[u]+weigh[i];
				if(!inq[v]) {
					inq[v]=1;
					q.push(v);
				}
			}
		}
	}
}

map<int,int> mp[MAXN];
int tot;
int get(int x,int w) {
	if(!mp[x][w]) mp[x][w]=++tot;
	return mp[x][w];
}

int main() {
	int n=read(),m=read();
	tot=n;
	REP(i,1,m) {
		int u=read(),v=read(),w=read();
		int du=get(u,w),dv=get(v,w);
		addedge(u,du,1);addedge(du,u,1);
		addedge(du,dv,0);addedge(dv,du,0);
		addedge(v,dv,1);addedge(dv,v,1);
	}

	SPFA();

	printf("%d\n",dist[n]>=dist[0]?-1:dist[n]/2);
	return 0;
}



Measured memory_bytes: 68608
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;

#define rep(i,n) for (int i = 0; i < (n); ++i)

const ll MAX = 1e18;

void solve(long long N, std::vector<long long> A){
    ll ans = 1;
    rep(i,N){
        if(A[i] == 0){
            cout << 0 << endl;
            return;
        }
    }

    rep(i,N){
        if(A[i] <= MAX/ans){
            ans *= A[i];
        }else{
            cout << -1 << endl;
            return;
        }
    }

    cout << ans << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    solve(N, std::move(A));
    return 0;
}


Measured memory_bytes: 4016
package main

import (
    "fmt"
)

func dream(s string) string {
    dp := make([]int, len(s)+1)
    dp[0] = 1
    for i := range s {
        if dp[i] == 0 {
            continue
        }
        if i+5 <= len(s) && s[i:i+5] == "dream" {
            dp[i+5] = 1
        }
        if i+7 <= len(s) && s[i:i+7] == "dreamer" {
            dp[i+7] = 1
        }
        if i+5 <= len(s) && s[i:i+5] == "erase" {
            dp[i+5] = 1
        }
        if i+6 <= len(s) && s[i:i+6] == "eraser" {
            dp[i+6] = 1
        }
    }
    if dp[len(s)] == 1 {
        return "YES"
    }
    return "NO"
}

func main() {
    var s string
    fmt.Scan(&s)
    fmt.Println(dream(s))
}

Measured memory_bytes: 2048
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
## dp ##
def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]
## math ##
def to_bin(x: int) -> str: return format(x, 'b') # rev => int(res, 2)
def to_oct(x: int) -> str: return format(x, 'o') # rev => int(res, 8)
def to_hex(x: int) -> str: return format(x, 'x') # rev => int(res, 16)
MOD=10**9+7
def divc(x,y) -> int: return -(-x//y)
def divf(x,y) -> int: return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def enumerate_divs(n):
    """Return a tuple list of divisor of n"""
    return [(i,n//i) for i in range(1,int(n**0.5)+1) if n%i==0]
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(MAX_NUM+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(MAX_NUM**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, MAX_NUM+1, i):
            is_prime[j] = False
    return [i for i in range(MAX_NUM+1) if is_prime[i]]
## libs ##
from itertools import accumulate as acc
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left

#======================================================#

def main():
    a, *bcd = list(map(int, IS()))
    for bit in range(1<<3):
        sumv = a
        pm = []
        for i in range(3):
            if bit & (1<<i):
                sumv += bcd[i]
                pm.append('+')
            else:
                sumv -= bcd[i]
                pm.append('-')
        if sumv == 7:
            a = str(a)
            b = str(bcd[0])
            c = str(bcd[1])
            d = str(bcd[2])
            print(a+pm[0]+b+pm[1]+c+pm[2]+d+'=7')
            return None

if __name__ == '__main__':
    main()

Measured memory_bytes: 3316
import Control.Applicative

bothDir :: Int -> Int -> Bool
bothDir 0 0 = True
bothDir _ 0 = False
bothDir 0 _ = False
bothDir _ _ = True

main :: IO ()
main = do
    path <- getLine
    let n = length . filter (=='N') $ path
        s = length . filter (=='S') $ path
        e = length . filter (=='E') $ path
        w = length . filter (=='W') $ path
        res = case (bothDir n s) && (bothDir e w) of
                True -> "Yes"
                False -> "No"
    putStrLn res


Measured memory_bytes: 508
a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())
k=int(input())
long=0

towers=[a,b,c,d,e]
for n in towers:
    for m in towers:
        if m-n > k:
            long=1
            
if long==1:
    print(":(")
else:
    print("Yay!")

Measured memory_bytes: 3064
package main

import (
	"fmt"
)

func main() {
	var n, y int

	fmt.Scan(&n)
	fmt.Scan(&y)

	for i := 0; i <= n; i++ {
		for j := 0; j <= n; j++ {
			if i+j > n {
				break
			}
			k := n - (i + j)
			if y == 10000*i+5000*j+1000*k {
				fmt.Printf("%v %v %v\n", i, j, k)
				return
			}
		}
	}
	fmt.Println("-1 -1 -1")
}

Measured memory_bytes: 512
n = int(input())
a = list(map(int, input().split()))
def f(a):
    l, r = a[:2]
    m = 1
    b = [(l,r)]
    for i in range(2, n-2):
        r += a[i]
        while m<i and abs(l-r)>abs(l-r+a[m]*2): 
            l, r = l+a[m], r-a[m]
            m += 1
        b.append((l,r))
    return b
print(min(max(p,q,r,s)-min(p,q,r,s)
        for ((p,q),(r,s)) in zip(f(a), f(a[::-1])[::-1])))

Measured memory_bytes: 57964
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = (0); i < (n); ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define DEBUG(val) cout << #val << " : " << val << endl
#define MOD 1000000007

int main() {
  int n;
  vector<ll> cum_sum;
  map<ll, ll> mp;
  ll sum = 0;
  mp[0] += 1;
  cin >> n;
  REP(i, n) {
    int x;
    cin >> x;
    sum += x;
    mp[sum] += 1;
  }
  ll ans = 0;
  for (auto itr = mp.begin(); itr != mp.end(); ++itr) {
    ll cnt = itr->second;
    if (2 <= cnt) {
      ans += cnt * (cnt - 1) / 2;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 16056
N, C = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(N)]
SV = [0]
for x, v in S:
    SV.append(v+SV[-1])
left = [0]
leftturn = [0]
for i in range(N):
    left.append(SV[i+1]-S[i][0])
    leftturn.append(SV[i+1]-S[i][0]*2)
S.reverse()
SV = [0]
for x, v in S:
    SV.append(v+SV[-1])
right = [0]
rightturn = [0]
for i in range(N):
    right.append(SV[i+1]-(C-S[i][0]))
    rightturn.append(SV[i+1]-(C-S[i][0])*2)
ml = [0]
mr = [0]
mlt = [0]
mrt = [0]
for i in range(N):
    ml.append(max(left[i+1], ml[-1]))
    mr.append(max(right[i+1], mr[-1]))
    mlt.append(max(leftturn[i+1], mlt[-1]))
    mrt.append(max(rightturn[i+1], mrt[-1]))
res = 0
for i in range(N+1):
    res = max(res, ml[i]+mrt[N-i], mr[i]+mlt[N-i])
print(res)


Measured memory_bytes: 96728
/*
このコード、と～おれ!
Be accepted!
∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
 　　　　　　　　　.· ´¸.·*´¨) ¸.·*¨)
		  　　　　　　　　　　(¸.·´ (¸.·'* ☆
					*/

#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>
#include <numeric>
#include <iostream>
#include <random>
#include <map>
#include <unordered_map>
#include <queue>
#include <regex>
#include <functional>
#include <complex>
#include <list>
#include <cassert>
/*多倍長整数/cpp_intで宣言
#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
*/

//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define rep1(i, n) for(int i = 1; i <= (n); ++i)
#define rep2(i, n) for(int i = 2; i < (n); ++i)
#define repr(i, n) for(int i = n; i >= 0; --i)
#define reprm(i, n) for(int i = n - 1; i >= 0; --i)
#define printynl(a) printf(a ? "yes\n" : "no\n")
#define printyn(a) printf(a ? "Yes\n" : "No\n")
#define printYN(a) printf(a ? "YES\n" : "NO\n")
#define printin(a) printf(a ? "possible\n" : "imposible\n")
#define printdb(a) printf("%.50lf\n", a)//少数出力
#define printdbd(a) printf("%.16lf\n", a)//少数出力(桁少なめ)
#define prints(s) printf("%s\n", s.c_str())//string出力
#define all(x) (x).begin(), (x).end()
#define allsum(a, b, c) ((a + b) * c / 2)//等差数列の和、初項,末項,項数
#define pb push_back
#define priq priority_queue
#define rpriq priq<int, vector<int>, greater<int>>
#define deg_to_rad(deg) (((deg)/360.0)*2.0*PI)
#define rad_to_deg(rad) (((rad)/2.0/PI)*360.0)
#define Please return
#define AC 0
#define addf(T) [](T a, T b){return (a + b);}
#define minf(T) [](T a, T b){return min(a, b);}
#define maxf(T) [](T a, T b){return max(a, b);}


using ll = long long;

constexpr int INF = 1073741823;
constexpr int MINF = -1073741823;
constexpr ll LINF = ll(4661686018427387903);
constexpr ll MOD = 1000000007;
const long double PI = acos(-1.0L);

using namespace std;

void scans(string& str) {
	char c;
	str = "";
	scanf("%c", &c);
	if (c == '\n')scanf("%c", &c);//最初の改行対策
	while (c != '\n' && c != -1) {
		str += c;
		scanf("%c", &c);
	}
}

void scanc(char& str) {
	char c;
	scanf("%c", &c);
	if (c == -1)return;
	while (c == '\n') {
		scanf("%c", &c);
	}
	str = c;
}

double acot(double x) {
	return PI / 2 - atan(x);
}

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

ll lcm(ll number1, ll number2) {//lcmを求める
	return number1 / gcd(number1, number2) * number2;
}

ll LSB(ll n) { return (n & (-n)); }

/*-----------------------------------------ここからコード-----------------------------------------*/



int main() {

	vector<int> a(5);
	rep(i, 5)scanf("%d", &a[i]);
	sort(all(a));
	int ans = INF, tmp = 0;
	do {
		tmp = 0;
		rep(i, 5) {
			if (i == 4) {
				tmp += a[i];
			}
			else {
				int b = a[i];
				while (b % 10)++b;
				tmp += b;
			}
		}
		ans = min(ans, tmp);
	} while (next_permutation(all(a)));
	printf("%d\n", ans);

	Please AC;
}


Measured memory_bytes: 256
N=int(input())
B=list(map(int,input().split()))

mx = 0

for i in range(len(B)):

    if i==0 :

        if len(B)==1 :

            mx += B[0]*2

        else:

            if B[i] > B[i+1]:

                mx += B[i]+B[i+1]

            else:

                mx += B[i]*2

    elif i>0 :

        if i != len(B)-1:

            if B[i] < B[i+1]:

                mx += B[i]

            elif B[i] >= B[i+1]:

                mx += B[i+1]

        elif i == len(B)-1:

            mx += B[i]

print(mx)

Measured memory_bytes: 3064
/*痛みを受け取れ，痛みを知れ*/
#include<bits/stdc++.h>
#define f(i,a,b) for(register int i=a;i<=b;++i)
#define ff(i,a,b) for(register int i=a;i>=b;--i)
#define debug(x) cerr << #x << " : " << x << " " << endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<string, string> pss;
const ll mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const double tiaohe = 0.57721566490153286060651209;
ll oula(ll x) { ll res = x;f(i, 2, x / i) { if (x % i == 0) { res = res / i * (i - 1);while (x % i == 0) x /= i; } }if (x > 1) res = res / x * (x - 1);return res; }
ll quickmod(ll a, ll n, ll m) { ll s = 1;while (n) { if (n & 1) { s = s * a % m; }a = (a*a) % m;n = n / 2; }return s; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
void ex_gcd(ll a, ll b, ll &x, ll &y, ll &d) { if (!b) { d = a, x = 1, y = 0; } else { ex_gcd(b, a % b, y, x, d);y -= x * (a / b); } }
ll inv(ll t, ll p) { ll d, x, y;ex_gcd(t, p, x, y, d);return d == 1 ? (x % p + p) % p : -1; }
bool isPrime(ll x) { if (x == 2)return true;if (x % 2 == 0)return false;for (ll i = 2;i*i <= x;i++) if (x % i == 0)return false; return true; }
//double a = log(n) +tiaohe + 1.0 / (2 * n);
double eqa = (1 + sqrt(5.0)) / 2.0;
const int N = 5e5 + 5;

int main()
{
	//freopen("in.txt", "r", stdin);
	ll x, k, d;
	while (cin >> x >> k >> d)
	{
		ll pos = abs(x) / d;
		ll neg = abs(x) / d + 1;
		if (k <= pos)
		{
			if (x < 0)
			{
				x +=k * d;
			}
			else x -= k * d;
			cout << abs(x) << endl;
			continue;
		}
		ll re = k - pos;
		if (re&1)
		{
			if (x < 0)
			{
				x += neg * d;
			}
			else x -= neg * d;
			cout << abs(x) << endl;
		}
		else
		{
			if (x < 0)
			{
				x += pos * d;
			}
			else x -= pos * d;
			cout << abs(x) << endl;
		}
		
	}
	return 0;
};

Measured memory_bytes: 3636
import sys
def f(a,b,c,d):z=(c-a)*(y-d)-(d-b)*(x-c);return[-1*(z==0),1][z>0]
for e in sys.stdin:
 p,q,r,s,t,u,x,y=map(float,e.split())
 print(['NO','YES'][f(p,q,r,s)==f(r,s,t,u)==f(t,u,p,q)])



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

struct data
{
  int input;
  int ind;
};

int main()
{
  int n;
  std::cin >> n;
  std::vector<int> a(n);
  std::vector<int> b(n);
  for(size_t i = 0; i < n; i++) std::cin >> a[i], --a[i];
  for(size_t i = 0; i < n; i++) b[a[i]] = i;
  for(size_t i = 0; i < n; i++) std::cout << ++b[i] << " " << std::endl;;
  
  
  // int N;
  // std::cin >> N;
  // std::vector<data> A(N);
  // for(int i= 0; i < N; i++)
  // {
  //   std::cin >> A[i].input;
  //   A[i].ind = i;
  // }
  
  // std::sort(A.begin(), A.end(), 
  //     [](const data &a, const data &b){return a.input < b.input;});
  // for(auto it: A)
  // {
  //   std::cout << it.ind + 1 << std::endl;
  // }
  // return 0;
}

Measured memory_bytes: 1664
n=int(input())
s=input()
numbers=[str(i).zfill(3) for i in range(1000)]

count=0
for num in numbers:
	j=0
	for i in range(n):
		if num[j]==s[i]:
			j+=1
		if j==3:
			break
	if j==3:
		count+=1
print(count)

Measured memory_bytes: 41052
#include <stdio.h>
int main (void){
    int n;
    int i;
    int a[100] = {};
    scanf("%d" ,&n);
    for(i = 0;i < n;i++)
        scanf("%d",&a[i]);
    for(i = n;i > 0;i--){
        if(i == 1){
           printf("%d\n",a[i-1]);
           break;
        }
        printf("%d ",a[i-1]);
    }
    return 0;
}



Measured memory_bytes: 2056
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
		ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
		string a;
		cin>>a;
		int tot=0;
		string prec="";
		for(int i=0;i<a.size();i++){
			for(int j=1;i+j<=a.size();j++){
				string k=a.substr(i,j);
				if(k!=prec){
					tot++;
					prec=k;
					i+=j-1;
					break;
				}
			}
		}
		cout<<tot;
		return 0;
}


Measured memory_bytes: 1228
#include <cstdio>
#include <iostream>
 
using namespace std;
 
struct dice{
    int q1,q2,q3,q4,q5,q6;
};
 
void mN(dice &d){
    int tmp=d.q1;
    d.q1=d.q2;
    d.q2=d.q6;
    d.q6=d.q5;
    d.q5=tmp;
}
 
void mE(dice &d){
    int tmp=d.q1;
    d.q1=d.q4;
    d.q4=d.q6;
    d.q6=d.q3;
    d.q3=tmp;
}
void mW(dice &d){
    int tmp=d.q1;
    d.q1=d.q3;
    d.q3=d.q6;
    d.q6=d.q4;
    d.q4=tmp;
}
void mS(dice &d){
    int tmp=d.q1;
    d.q1=d.q5;
    d.q5=d.q6;
    d.q6=d.q2;
    d.q2=tmp;
}
 
void spin(dice &d){
    int tmp=d.q2;
    d.q2=d.q3;
    d.q3=d.q5;
    d.q5=d.q4;
    d.q4=tmp;
}
 
int main(){
    dice z;
    int q;
     
    scanf(" %d %d %d %d %d %d", &z.q1, &z.q2, &z.q3, &z.q4, &z.q5, &z.q6);
    scanf(" %d", &q);
     
    for(int i=0; i<q; ++i){
        int a, b;
        dice x=z;
         
        scanf(" %d %d", &a, &b);
         
        if(a==x.q3 || a==x.q4) mE(x);
        while(a != x.q1) 
            mN(x);
        while(b != x.q2)
            spin(x);
         
        printf("%d\n", x.q3);   
    }
     
    return 0;
}


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

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

const int Maxn = 200005;
const ll Inf = 9000000000000000000ll;

int n;
int a[Maxn];
ii p[Maxn];
ll L[Maxn], R[Maxn];
ll res = Inf;

int Add(const ii &a, const ii &b)
{
    if (a.second < b.second) return 0;
    int res = a.second - b.second;
    if (a.first > b.first) res++;
    return res;
}

void Solve(ll R[])
{
    vector <ii> seq;
    for (int i = n - 1; i >= 0; i--) {
        int num = a[i];
        int digs = 0;
        while (num) {
            digs++;
            num /= 4;
        }
        num = a[i];
        while (4ll * ll(num) < 1ll << 30ll)
            num *= 4ll;
        p[i] = ii(num, digs);
        seq.push_back(ii(i, 0));
        while (seq.size() >= 2) {
            int ind = seq.back().first;
            int delt = seq.back().second;
            int ind2 = ind + 1;
            int delt2 = seq[int(seq.size()) - 2].second;
            int got = Add(ii(p[ind].first, p[ind].second + delt), ii(p[ind2].first, p[ind2].second + delt2));
            if (got > 0) {
                seq.pop_back();
                R[i] += 2ll * ll(got) * (seq.back().first - ind);
                seq.back().second += got;
            } else break;
        }
        p[i].second -= seq.back().second;
        R[i] += R[i + 1];
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    Solve(R);
    reverse(a, a + n);
    Solve(L);
    res = min(R[0], L[0] + ll(n));
    for (int i = 0; i + 1 < n; i++)
        res = min(res, R[i + 1] + L[n - 1 - i] + ll(i + 1));
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 7412
#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;
using ll = long long;
using pll = pair<ll, ll>;
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FI first
#define SE second
#define endl "\n"
#define ciosup cin.tie(0);ios::sync_with_stdio(false);
#define eb emplace_back
constexpr ll INF = 1e9 + 7;
constexpr ll MOD = 1e9 + 7;

int main()
{
    ciosup;
    int s[3];
    cin >> s[0] >> s[1] >> s[2];
    sort(s, s + 3);
    cout << s[0] + s[1] << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#ifdef ENABLE_DEBUG
#define dump(a) cerr<<#a<<"="<<a<<endl
#define dumparr(a,n) cerr<<#a<<"["<<n<<"]="<<a[n]<<endl
#else
#define dump(a) 
#define dumparr(a,n) 
#endif
#define FOR(i, a, b) for(ll i = a;i < b;i++)
#define For(i, a) FOR(i, 0, a)
#define REV(i, a, b) for(ll i = b-1;i >= a;i--)
#define Rev(i, a) REV(i, 0, a)
#define REP(a) For(i, a)
#define SIGN(a) (a==0?0:(a>0?1:-1))

typedef long long int ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;

const ll INF=(1LL<<50);
#if __cplusplus<201700L
ll gcd(ll a, ll b) {
  if(a < b) return gcd(b, a);
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
#endif

template<class S,class T>
std::ostream& operator<<(std::ostream& os,pair<S,T> a){
  os << "(" << a.first << "," << a.second << ")";
  return os;
}
template<class T>
std::ostream& operator<<(std::ostream& os,vector<T> a){
  os << "[ ";
  REP(a.size()){
    os<< a[i] << " ";
  }
  os<< " ]";
  return os;
}



int main(){
  ll H,W;
  cin>>H>>W;
  vector<string> S(H);
  REP(H){
    cin>>S[i];
  }
  ll ans=0;
  For(i,H){
    For(j,W){
      dump(i);
      dump(j);
      if(S[i][j]=='#'){
        continue;
      }
      deque<pair<pll,ll>> q;
      set<pll> s;
      q.push_back(make_pair(pll(i,j),0));
      s.insert(pll(i,j));
      while(!q.empty()){
        auto tmp = q.back();q.pop_back();
        dump(tmp);
        ans=max(ans,tmp.second);
        ll curx=tmp.first.first,cury=tmp.first.second;
        for (int y = -1; y < 2; y+=2)
        {
          int x=0;
          if(curx+x<0 || curx+x>=H || cury+y<0 || cury+y >= W 
            || S[curx+x][cury+y]=='#' ||s.count(pll(curx+x,cury+y))){
            continue;
          }
          s.insert(pll(curx+x,cury+y));
          q.push_front(make_pair(pll(curx+x,cury+y),tmp.second+1));
        }
        for (int x=-1;x<2;x+=2)
        {
          int y=0;
          if(curx+x<0 || curx+x>=H || cury+y<0 || cury+y >= W 
            || S[curx+x][cury+y]=='#' ||s.count(pll(curx+x,cury+y))){
            continue;
          }
          s.insert(pll(curx+x,cury+y));
          q.push_front(make_pair(pll(curx+x,cury+y),tmp.second+1));
        }
      }
    }
  }
  cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
typedef long long int ll;
#define rep(i, n) for (int i = 0; i < n; i++)
#define cinf(n,x,y,a) for(int i=0;i<(n);i++) cin >> x[i] >> y[i] >> a[i] ;

int main(){
  int W,H,N;
  cin >> W >> H >> N ;
  int x[110],y[110],a[110] ;
  cinf(N,x,y,a) ;
  int cmin =0;
  int cmax = W;
  int rmin =0;
  int rmax = H ;
  rep(i,N){
    if(a[i] == 1 && x[i] > cmin)
      cmin = x[i] ;
    else if(a[i] == 2 && x[i] < cmax)
      cmax = x[i] ;
    else if(a[i] == 3 && y[i] > rmin)
      rmin = y[i] ;
    else if (a[i] == 4 && y[i] < rmax)
      rmax = y[i] ;
  }
  if(rmax >= rmin && cmax >= cmin)
    cout << (rmax-rmin)*(cmax-cmin) << endl;
  else
    cout << 0 << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int a,b,n;
    scanf("%d",&n);
    if(n==1)
        printf("Hello World\n");
    else
    {
        scanf("%d %d",&a,&b);
        printf("%d\n",a+b);
    }

    return 0;
}


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

int main()
{
  ll N, M;
  cin >> N >> M;
  ll ans = N * (N - 1) / 2 + M * (M - 1) / 2;
  cout << ans << endl;
}


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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    map<pair<char, char>, int> mp;
    int ans = 0;

    for(int i=1; i<n+1; i++){
        string S = to_string(i);
        if(S.back() != '0') mp[{S.at(0), S.back()}]++;
    }

    for(int i=1; i<10; i++){
        for(int j=i; j<10; j++){
            string I = to_string(i);
            string J = to_string(j);
            if(i == j) ans += mp[{I.at(0), J.at(0)}]*mp[{I.at(0), J.at(0)}];
            else ans += 2*mp[{I.at(0), J.at(0)}]*mp[{J.at(0), I.at(0)}];
        }
    }
    cout << ans << endl;
    return 0;
}

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


int main() {
    int n;
    cin >> n;
    vector<int> d(n,0);
    rep(i,n){
        cin >> d.at(i);
    }
    sort(d.begin(),d.end(),greater<int>());
    int res = 1;
    rep(i,n-1){
        if(d.at(i) > d.at(i+1))res++;
        else continue;
    }
    cout << res << endl;
    return 0;
}

/*
やっほい！
　　　　　　　やほほい！
　　　　+　　 　*
　　　 ∧∧　　. ∧∞∧　*
*　ヽ(=´ω｀)人(´ω｀*)ﾉ
　.～（ O x.） （ 　 O)～　+
。*　 　∪　　　　∪
*/

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

int main(){
  int n;
  string s;
  cin >> n >> s;
  int sum = 0, min;
  for(int i=1; i<n; ++i){
    if(s[i]=='E'){sum++;}
  }
  min = sum;
  for(int i=1; i<n; ++i){
    if(s[i]=='E'){sum--;}
    if(s[i-1]=='W'){sum++;}
    if(sum < min){min = sum;}
  }
  cout << min << endl;
}

Measured memory_bytes: 900
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const ll MOD = 1e9 + 7;
const int N = (21);
int memo[N][1 << N];
int n, a[N][N];

int DP(int pos, int mask) {
	if (pos == n) {
		return __builtin_popcount(mask) == n;
	}
	int &ret = memo[pos][mask];
	if (ret != -1) return ret;
	ret = 0;
	for (int i = 0; i < n; ++i) {//
		if (a[pos][i] == 1 and ((mask >> i) & 1) == 0) {
			ret = (ret + DP(pos + 1, mask | (1 << i))) % MOD;
		}
	}
	return ret;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			scanf("%d", &a[i][j]);
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < (1 << n); ++j) {
			memo[i][j] = -1;
		}
	}
	int ans = DP(0, 0);
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 172288
#include <iostream>
#include <bits/stdc++.h>
     
using namespace std;
     
bool checkPalindrum(int x){
  vector<int> n(100);
  int counter = 0;
  while(x > 0){
    n[counter] = x % 10;
    x /= 10;
    counter++;
  }
  
  for(int i =0; i < counter; i++){
    if(n[i] != n[counter - i - 1]) return false;
  }
  return true;
}
     
int main(){
  int A,B;
  cin >> A >> B;
  int ans = 0;
  for (int i = A; i <= B; i++){
    if(checkPalindrum(i)) ans++;
  }
  cout << ans;
}

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

int main(){
    vector<int> vec(4);

    for(auto &x:vec){
        cin>>x;

    }


    bool test=true;
    sort(vec.begin(),vec.end());

    if(vec[0]!=1){
        test=false;
    }
    if(vec[1]!=4){
        test=false;
    }

    if(vec[2]!=7){
        test=false;
    }

    if(vec[3]!=9){
        test=false;
    }

    if(test){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }


}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define E "\n"

using namespace std;
const long long MOD = (long long)1e9 + 7;


int n, k;
string S;
set<string> st;



int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> S >> k;
	n = S.length();
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j + i - 1 < n; j++) {
			string tmp = S.substr(j, i);
			if ((int)st.size() < k)
				st.insert(tmp);
			else {
				auto x = st.end();
				x--;
				if (tmp < *x) {
					st.erase(x);
					st.insert(tmp);
				}
			}
		}
	}
	auto p = st.end();
	p--;
	cout << *p << E;
	//system("pause");
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
	int countTable[256] = {0};
	char ch;

	while((ch = getchar()) != EOF){
				countTable[ch]++;
	}
	for(int i = 97; i <=122;i++)printf("%c : %d\n",i,countTable[i]+countTable[i-32]);
}



Measured memory_bytes: 2700
N = int(input())
a = list(map(int, input().split()))

b = [0 for _ in range(N + 1)]
M = 0
for i in range(N, 0, -1):
    x = a[i - 1]
    for j in range(i, N + 1, i):
        x += b[j]
    x = x % 2
    b[i] = x
    M += x
print(M)
for i in range(1, N + 1):
    if b[i] == 1:
        print(i)


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

#define PI 3.14159265358979323846264338327950288419

using namespace std;

int n;
char board[303][303];
int ans;

bool symmetric(){
	for(int i = 1; i <= n; i++){
		for(int j = i + 1; j <= n; j++){
			if(board[i][j] != board[j][i]){
				return false;
			}
		}
	}
	return true;
}

void shift(){
	for(int i = 1; i <= n; i++){
		for(int j = 2; j <= n; j++){
			swap(board[i][j - 1], board[i][j]);
		}
	}
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			scanf(" %c", &board[i][j]);
		}
	}
	for(int i = 1; i <= n; i++){
		if(symmetric()){
			ans += n;
		}
		shift();
	}
	printf("%d\n", ans);
	return 0;
}

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

int main(){
    ll N;
    cin >> N;
    ll Y;
    cin >> Y;
    ll yukichi = -1;
    ll higuchi = -1;
    ll noguchi = -1;
    for(ll i = 0; i <= N; i++){
        for(ll j = 0; j <= N - i; j++){
            if (i * 10000 + j * 5000 + (N - i - j) * 1000 == Y){
                yukichi = i;
                higuchi = j;
                noguchi = N - i - j;
                break;
            }
        }
    }
    cout << yukichi << " " << higuchi << " " << noguchi << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#include <climits>
using namespace std; 

const int INF = 1 << 29;

int main(){

    int n,k;
    cin >> n >> k;
    vector<int> h(n);
    for(int& i : h){
        cin >> i;
    }

    vector<int> cache(n,INT_MAX);

    cache[0] = 0;
    cache[1] = abs(h[1] - h[0]);

    for(int i = 1; i < n; ++i){
        for(int j = 1; j <= k; j++){
            if(i - j >= 0){
                cache[i] = min(cache[i],cache[i - j] + abs(h[i] - h[i - j]));
            }
        }
    }

    cout << cache[n - 1];

    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>

using namespace std;

int gcd( int, int );

int main()
{
	int n, count;

	while ( cin >> n )
	{
		count = 0;
		for ( int a = 0; a < 10; a++ )
		{
			for ( int b = 0; b < 10; b++ )
			{
				for ( int c = 0; c < 10; c++ )
				{
					for ( int d = 0; d < 10; d++ )
					{
						if ( a + b + c + d == n )
						{
							count++;
						}
					}
				}
			}
		}
		printf("%d\n", count );
	}

	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,v,ans,a[100005],b[100005];
int main()
{
	scanf("%d%d",&n,&v);
	for (int i=1;i<=n;i++)
		scanf("%d%d",&a[i],&b[i]);
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	for (int i=n;i>=1&&b[i]>a[n]&&v>0;v-=b[i],i--,ans++);
	if (v>0) ans=ans+v/a[n]+(v%a[n]!=0);
	printf("%d\n",ans);
}

Measured memory_bytes: 1024
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main() {
    int r; cin>>r;
    cout<<3.14159*2*r<<endl;
}

Measured memory_bytes: 3788
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n, q; cin >> n >> q;
  string s; cin >> s;
  V<> c(n + 1);
  for (int i = 0; i < n - 1; ++i) {
    c[i + 1] = c[i] + (s[i] == 'A' and s[i + 1] == 'C');
  }
  while (q--) {
    int l, r; cin >> l >> r, --l, --r;
    cout << c[r] - c[l] << '\n';
  }
}

Measured memory_bytes: 1488
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N,M = map(int,input().split())
fr = [[] for _ in range(N)]
for _ in range(M):
    x,y,z = map(int,input().split())
    fr[x-1].append(y-1)
    fr[y-1].append(x-1)
used = [-1]*N #-1なら未探索。数字はrenketuのindex
renketu = []
index = 0
def dfs(fr,cur,parent,index,li):
    children = fr[cur]
    for chi in children:
        if chi == parent or used[chi] != -1:
            continue
        used[chi] = index
        li.append(chi)
        dfs(fr,chi,cur,index,li)
for i in range(N):
    if used[i] != -1:
        continue
    li = [i]
    used[i] = index
    dfs(fr,i,-1,index,li)
    index += 1
    renketu.append(li)
n = len(renketu)
print(n)

Measured memory_bytes: 122412
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-ffloat-store") // to restrict undesirable precision
#pragma GCC optimize ("-fno-defer-pop")// to pop argument of function as soon as it returns
#define all(a) a.begin(),a.end()
#define ll long long int
#define ld long double
ll power(ll a,ll b,ll m){ if(b==0) return 1; if(b==1) return a%m; ll t=power(a,b/2,m)%m; t=(t*t)%m; if(b&1) t=((t%m)*(a%m))%m; return t;}
ll modInverse(ll a, ll m) { return power(a, m-2, m); }
#define ps push_back
#define fs first
#define takeline cin.ignore();
#define sc second
#define N 3000005
#define endl "\n"
#define mod 1000000007
//((1.0l)*BIG MULTIPLY MAGIC?)
// string to integer stoi()
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();
//-----------------------------------------------
int main(){
	
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	ll x,y;
	cin>>x>>y;

	ll an=0;
	if(x==1) an+=300000;
	else if(x==2) an+=200000;
	else if(x==3) an+=100000;

	if(y==1) an+=300000;
	else if(y==2) an+=200000;
	else if(y==3) an+=100000;

	if(x==1&&y==1) an+=400000;
	cout<<an;
	return 0;
}

Measured memory_bytes: 764
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1e9+7;
const int INF=1e9;
const ll LINF=(ll)1e18;

int main(){
    string s,t,u;
    int a,b;
    cin>>s>>t>>a>>b>>u;
    if(s==u)a--;
    else b--;
    cout<<a<<" "<<b<<endl;
}


Measured memory_bytes: 256
H,W = list(map(int, input().split()))
B = []
for _ in range(H):
  B.append(input())
  
A = [[999999 for _ in range(W)] for _ in range(H)]
A[0][0] = 0 if B[0][0] == "." else 1

for i in range(H):
  for j in range(W):
    if i+j == 0:
      continue
    X,Y = 999999, 999999
    if i > 0:
      X = A[i-1][j] 
      X += 1 if B[i-1][j] == '.' and B[i][j] == '#' else 0
    if j > 0:
      Y = A[i][j-1]
      Y += 1 if B[i][j-1] == '.' and B[i][j] == '#' else 0
    A[i][j] = min(X,Y)
    
print(A[H-1][W-1])
#for i in range(H):
#  print(A[i])

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

using namespace std;

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

    if(a>=b && a>=c){
        cout << a * 10 + b + c << endl;
    }

     if(b>a && b>=c){
        cout << b * 10 + a + c << endl;
    }

     if(c>b && c>a){
        cout << c * 10 + b + a << endl;
    }

    return 0;
}

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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>
#include<complex>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, double> pid;
typedef pair<double, int> pdi;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;

const double EPS = 1e-9;

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

	int N;
	cin >> N;
	vector<int> A(N);

	rep(i, 0, N)cin >> A[i];

	vector<int> IMOS(N + 1, 0);

	int ans = 0;
	while (true)
	{
		bool ok = false;
		int sum = 0;
		rep(i, 0, N)
		{
			sum += IMOS[i];
			IMOS[i] = 0;
			A[i] += sum;
			if (A[i] >= N)
			{
				ok = true;
				int t = A[i] / N;
				A[i] -= N * t;
				ans += t;
				IMOS[0] += t;
				IMOS[i] -= t;
				IMOS[i + 1] += t;
			}
		}
		if (!ok)break;
	}

	cout << ans << endl;

	return 0;
}


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

#define INF INT_MAX/2;
#define MOD 1000000007

using namespace std;

using ll = long long;
using ull = unsigned long long ;

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

   ll n;
   cin>>n;
   vector<ll>v(n);
   for(ll i=0;i<n;i++)cin>>v[i];
   map<ll,ll>m0,m1;
   for(ll i=0;i<n;i++){
      if(i%2==0){
         m0[v[i]]++;
      }
      else{
         m1[v[i]]++;
      }
   }
   vector<pair<ll,ll> >p0,p1;
   for(auto it:m0){
      p0.push_back(make_pair(it.second,it.first));
   }
   for(auto it:m1){
      p1.push_back(make_pair(it.second,it.first));
   }
   ll MAX = -INF;
   ll a = MAX;
   sort(p0.rbegin(),p0.rend());
   sort(p1.rbegin(),p1.rend());
   if(p0[0].second == p1[0].second){
      if(p0.size()>1) MAX = max(p0[1].first+p1[0].first,MAX);
      if(p1.size()>1) MAX = max(p0[0].first+p1[1].first,MAX);
   }
   else MAX = max(p0[0].first+p1[0].first,MAX);
   if(MAX == a){
      MAX = n/2;
   }
   cout<<n-MAX;
   return 0; 
}


Measured memory_bytes: 9592
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

#define ll       long long
#define PR       pair<ll, ll>
#define READ(f)  freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)

const int N = 3e5 + 5;
const int MOD = 1e9 + 7;
const double PI = 2 * acos(0.0);
//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
//    ios::sync_with_stdio(false);
//    cin.tie(0);
    ll n;
    cin >> n;
    ll sum = 0;
    for (int i = 1; i <= n; i++) {
        if (i % 5 == 0 && i % 3 == 0) {
            continue;
        } else if (i % 3 == 0) {
            continue;
        } else if (i % 5 == 0) {
            continue;
        } else {
            sum += i;
        }
    }
    cout << sum << '\n';
    return 0;
}


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

using namespace std;

typedef long long int lli;

int n, m, p;
vector<vector<pair<int, int>>> edge(2501, vector<pair<int, int>>()), redge(2501, vector<pair<int, int>>());
vector<int> score(2501, -2000000000), used(2501, 0), pass(2501, 0);

void dfs(int crnt, int t) {
    used[crnt] = 1;
    for (auto x : edge[crnt]) {
        int bb = x.first, cc = x.second;
        
        if (used[bb]) {
            if (score[crnt]+cc-p > score[bb] && pass[bb]) {
                score[n] = 2000000000;
                // cout << "## " << crnt << " " << bb << endl;
            }
            continue;
        }

        if (score[crnt]+cc-p > score[bb]) {
            score[bb] = score[crnt]+cc - p;
            dfs(bb, t+1);
        }
    }

    used[crnt] = 0;
    return;
}

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

    cin >> n >> m >> p;

    int a, b, c;
    for (int i=0; i<m; i++) {
        cin >> a >> b >> c;
        edge[a].push_back(make_pair(b, c));
        redge[b].push_back(make_pair(a, c));
    }

    queue<int> qu; qu.push(n);
    while (!qu.empty()) {
        int x = qu.front(); qu.pop();
        used[x] = 1;
        pass[x] = 1;
        for (auto e : redge[x]) {
            if (used[e.first]) continue;
            qu.push(e.first);
        }
    }

    used = vector<int>(2501, 0);
    score[1] = 0;
    dfs(1, 1);
/*
    for (int i=1; i<=n; i++) cout << score[i] << " ";
    cout << endl;
*/
    cout << ((score[n] == 2000000000) ? -1 : max(0, score[n])) << endl;

    return 0;
}


Measured memory_bytes: 4096
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
#define MOD (1000000007)
#define INF (1e9)
#define INFL (1e18)

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
template<class T>using arr=vector<vector<T>>;
template<class T>int popcount(T &a){int c=0; rep(i, 8*(int)sizeof(a)){if((a>>i)&1) c++;} return c;}
template<class T>void pr(T x){cout << x << endl;}
template<class T>void prvec(vector<T>& a){rep(i, a.size()-1){cout << a[i] << " ";} pr(a[a.size()-1]);}
template<class T>void prarr(arr<T>& a){rep(i, a.size()) if(a[i].empty()) pr(""); else prvec(a[i]);}
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;
    int a = 0;
    if(s=="SSS") a = 0;
    else if(s=="SRR") a = 2;
    else if(s=="SRS") a = 1;
    else if(s=="SSR") a = 1;
    else {
        rep(i, 3){
            if(s[i]=='S') break;
            a++;
        }
    }
    pr(a);
    return 0;}

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

int main() {
	// your code goes here
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n,k;
	cin>>n;
	cin>>k;
	vector<int>v(n);
	vector<int>arr(n);//stores minimum energy to reach ith pillar
	arr[0]=0;
	for(int i=0;i<n;i++)
	{
		cin>>v[i];
		arr[i]=INT_MAX;
		
	}
	arr[0]=0;
//	cout<<arr[0];
//	arr[1]=abs(v[0]-v[1]);
//	cout<<arr[1];
	for(int i=0;i<n;i++)
	{
		for(int j=1;j<=k;j++)
		{
			if(i+j<n)
			{
			//	cout<<"ok";
			//	cout<<arr[i+j]<<" "<<(arr[i]+abs(v[i+j]-v[i]));
				arr[i+j]=min(arr[i+j],(arr[i]+abs(v[i+j]-v[i])));
				
			}
			
		}
	//	cout<<arr[i];
	}
	cout<<arr[n-1];
	return 0;
}

Measured memory_bytes: 1024
n = int(input())
d = list(map(int, input().split()))

d.sort()
# print(d)
this = 0
# 奇数
if n % 2 == 1:
    this = n % 2 + 1
    answer=d[this+1]-d[this]
# 偶数
else:
    this=n//2
    answer=d[this]-d[this-1]

print(answer)

Measured memory_bytes: 14396
#include <stdio.h>
 
int main(){
    int j,s_length = 0;
    char s[101],p[101];
    scanf("%s",s);
    scanf("%s",p);
 
    for(int i = 0; s[i] != '\0';i++) s_length++;
 
    for(int left = 0;s[left] != '\0';left++){
        for(j = 0;p[j] != '\0' && p[j] == s[(left+j)%s_length];j++);
        if(p[j] == '\0'){
            printf("Yes\n");
            return 0;
        }
    }
    printf("No\n");
    return 0;
}


Measured memory_bytes: 2652
//0519-Worst Sportwriter
#include <bits/stdc++.h>
using namespace std;
short data[5000][5000];
vector<int> win(5000);
vector<int> unknown(5000);
int main(){
	int n,m;	cin>>n>>m;
	for(int t=0;t<m;t++){
		int i,j;	cin>>i>>j;	i--;	j--;
		data[i][j]=1;	data[j][i]=-1;
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(i==j)	continue;
			if(data[i][j]==1)	win[i]++;
			else if(data[i][j]==0)	unknown[i]++;
		}
	}
	vector<int> rank(n,0);
	int another=0;
	for(int i=1;i<=n;i++){
		int next=-1;
		int nwin=0;
		for(int j=0;j<n;j++){
			if(win[j]==(n-i)&&unknown[j]==0){
				rank[j]=i;	cout<<j+1<<endl;
				next=-1;
				break;
			}
			else if(win[j]+unknown[j]==(n-i)){
				if(rank[j]!=0)	continue;
				if(next==-1){	next=j;	nwin=win[j];	}
				else if(nwin<win[j]){	next=j;	nwin=win[j];	another=1;	}
				else 	another=1;
			}
		}
		if(next!=-1){
			rank[next]=i;	cout<<next+1<<endl;
			for(int j=0;j<n;j++){
				if(next==j)	continue;
				if(data[next][j]==0){
					data[next][j]=1;	data[j][next]=-1;
					unknown[j]--;
				}
			}
			win[next]+=unknown[next];	unknown[next]=0;
		}
	}
	cout<<another<<endl;
	return 0;
}
			

Measured memory_bytes: 50084
#include <math.h>
#include <iostream>
using namespace std;

int yakusuu(int);

int main() {
	int n, cnt = 0; cin >> n;
	for (int i = 1; i <= n; i += 2) {
		if (yakusuu(i) == 8)
			cnt++;
	}
	cout << cnt << endl;
	return 0;
}

int yakusuu(int a) {
	int cnt = 1;
	for (int i = 2; i <= a; i++) {
		if (a%i == 0)
			cnt++;
	}
	return cnt;
}

Measured memory_bytes: 384
#include<iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <queue>
#include <deque>
#include <map>
#include <stack>
#include<bitset>
#include<list>
#include<cassert>
#include<numeric>

using namespace std;

const int N = 1e5 + 5;
vector<int> graph[N];
int deg[N];
int dp[N];
int child[N];
int root;
bool mark[N];
int n;

void dfs(int v)
{
	mark[v] = true;
	for (int i = 0; i < graph[v].size(); i++)
	{
		int u = graph[v][i];
		if (!mark[u])
		{
			dfs(u);
			if (dp[u] == 0)
			{
				child[v]++;
			}
		}
	}
	for (int i = 0; i < graph[v].size(); i++)
	{
		int u = graph[v][i];
		dp[v] += dp[u];
	}
	dp[v] += max(child[v] - 1, 0);
}

bool isPath()
{
	int cnt = 0;
	for (int i = 0; i < n; i++)
	{
		if (deg[i] == 1)
		{
			cnt++;
		}
		if (deg[i] > 2)
		{
			root = i;
			return false;
		}
		if (deg[i] == 2)
		{
			root = i;
		}
	}
	if (cnt != 2)
	{
		return false;
	}
	return true;
}

int main() 
{
	cin >> n;
	for (int i = 0; i < n - 1; i++)
	{
		int u, v;
		cin >> u >> v;
		deg[u]++;
		deg[v]++;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	if (isPath())
	{
		cout << 1;
		exit(0);
	}
	dfs(root);
	cout << dp[root];


}



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

int main(){
  int n;
  cin >> n;
  vector<int> x(n), y(n);
  for(int i = 0; i < n; i++){
    cin >> x.at(i) >> y.at(i);
  }
  long double sum = 0;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      sum += sqrt((x.at(i)-x.at(j))*(x.at(i)-x.at(j))+(y.at(i)-y.at(j))*(y.at(i)-y.at(j))); 
    }
  }
  int n1kai = 1;
  for(int i = 1; i < n; i++){
    n1kai *= i;
  }
  int nkai = 1;
  for(int i = 1; i < n+1; i++){
    nkai *= i;
  }
  cout << setprecision(10) << sum * n1kai / double(nkai);
}

Measured memory_bytes: 256