akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;
typedef vector<int> vi;
typedef long long ll;
#define FORE(x,xs) for (auto& x : xs)

bool isPrime(int n) {
    if (n&1 == 0) return false;
    for (int i = 3; 1ll * i * i <= n; i += 2)
        if (n%i == 0) return false;
    return true;
}

vi getDivs(int n) {
    vi divs;
    for (ll i = 2; i*i <= n; i++) {
        if (n%i == 0) {
            divs.push_back(i);
            while (n%i == 0) n /= i;
        }
    }
    if (n != 1) divs.push_back(n);
    return divs;
}

int gcd (int a, int b) {
    if (a > b) swap(a, b);
    while (a) {
        int k = b%a;
        b = a;
        a = k;
    }
    return b;
}

const int MAX = 1e4+10;

vi primes;
int N;
ll A[MAX];

bool check(ll p) {
    vector<ll> c(p-1);
    if (A[0] % p != 0) return false;
    for (int n = 1; n <= N; n++) c[n%(p-1)] += A[n];
    for (int i = 0; i < p-1; i++) if (c[i] % p != 0) return false;
    return true;
}

int main() {
    primes.push_back(2);
    cin >> N;
    for (int i = 3; i <= N; i += 2) if (isPrime(i)) primes.push_back(i);
    for (int i = N; i >= 0; i--) cin >> A[i];

    set<int> ans;

    int d = abs(A[0]);
    for (int i = 0; i <= N; i++) d = gcd(d, abs(A[i]));
    vi v = getDivs(d);
    FORE (x, v) ans.insert(x);

    FORE (p, primes) if (check(p)) {
        ans.insert(p);
    }

    vi ans_v;
    copy(ans.begin(), ans.end(), std::back_inserter(ans_v));
    sort(ans_v.begin(), ans_v.end());

    FORE (a, ans_v) cout << a << endl;
}

Measured memory_bytes: 384
while True:
    d, w, h = map(int, input().split())
    if d == 0:
        break
    n = int(input())
    a, b = sorted([d, w, h])[:2]
    t = pow(pow(a, 2) + pow(b, 2), 0.5) // 2
    for _ in range(n):
        print("OK" if int(input()) > t else "NA")

Measured memory_bytes: 7584
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<bitset>
#include <functional>
using namespace std;
#define MAX_V 100 + 2
int indegree[MAX_V], outdegree[MAX_V];
int n, m, s, t;
#define INF 0x3f3f3f3f
///////////////////////////////最小?用流?始///////////////////////////////////////////

typedef pair<int, int> P;	// first保存最短距?，second保存?点?号
//用于表示?的??体
struct edge
{
	int to;		// ?点
	int cap;	// 容量
	int cost;	// ?用
	int rev;	// 反向?
	edge(int to, int cap, int cost, int rev) :to(to), cap(cap), cost(cost), rev(rev){}
};
int V;			// ?点数
vector<edge> G[MAX_V];	// ?的?接表
int h[MAX_V];	// ?点的?
int dist[MAX_V];// 最短距?
int prevv[MAX_V];	// 最短路中的前??点
int preve[MAX_V];	// 最短路中的前??点??的?

// 向?中?加一条从from到to的容量?cap?用?cost的?
void add_edge(int from, int to, int cap, int cost)
{
	G[from].push_back(edge(to, cap, cost, G[to].size()));
	G[to].push_back(edge(from, 0, -cost, G[from].size() - 1));
}

// 求解从s到t流量?f的最小?用流，如果没有流量?f的流，?返回-1
int min_cost_flow(int s, int t, int f)
{
	int res = 0;
	memset(h, 0, sizeof(h));
	while (f > 0)
	{
		// 使用Dijkstra算法更新h
		priority_queue<P, vector<P>, greater<P> > que;
		memset(dist, INF, sizeof(dist));
		dist[s] = 0;
		que.push(P(0, s));
		while (!que.empty())
		{
			P p = que.top(); que.pop();
			int v = p.second;
			if (dist[v] < p.first) continue;
			for (int i = 0; i < G[v].size(); ++i)
			{
				edge &e = G[v][i];
				if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to])
				{
					dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
					prevv[e.to] = v;
					preve[e.to] = i;
					que.push(P(dist[e.to], e.to));
				}
			}
		}
		if (dist[t] == INF)
		{
			// 不能再?广
			return -1;
		}
		for (int v = 0; v < V; ++v)
		{
			h[v] += dist[v];
		}

		// 沿s到t的最短路尽量?广
		int d = f;
		for (int v = t; v != s; v = prevv[v])
		{
			d = min(d, G[prevv[v]][preve[v]].cap);
		}
		f -= d;
		res += d * h[t];
		for (int v = t; v != s; v = prevv[v])
		{
			edge &e = G[prevv[v]][preve[v]];
			e.cap -= d;
			G[v][e.rev].cap += d;
		}
	}
	return res;
}

void clear()
{
	for (int i = 0; i < V; ++i)
	{
		G[i].clear();
	}
}


///////////////////////////SubMain//////////////////////////////////
int main()
{
	scanf("%d%d", &n, &m);
	V = n + 2;
	t = V - 1;
	s = 0;
	int total = 0;
	for (int i = 1; i <= m; i++)
	{
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		x++, y++;
		add_edge(x, y, INF, -z);
		outdegree[x]++, indegree[y]++;
		total += z;
	}

	int max_f = 0;
	for (int i = 1; i <= n; i++)
	{
		if (indegree[i] > outdegree[i])
		{
			add_edge(s, i, indegree[i] - outdegree[i], 0);
			max_f += indegree[i] - outdegree[i];
		}
		else
		{
			add_edge(i, t, outdegree[i] - indegree[i], 0);
		}
	}

	min_cost_flow(1, n, 1);
	add_edge(n, 1, INF, -dist[n]);
	int ans = min_cost_flow(s, t, max_f);
	printf("%d\n", ans - total);
	return 0;
}

Measured memory_bytes: 3228
n,c=map(int,input().split())

xv=[]
xv_rev=[]

for _ in range(n):
    x,v=map(int,input().split())
    xv.append((x,v))
    xv_rev.append((c-x,v))

xv_rev=xv_rev[::-1]

right=[0]*n
right_re=[0]*n

sumv=0
#時計回り
for i,(x,v) in enumerate(xv):
    if i==0:
        sumv=v
        right[i]=max(0,sumv-x)
        right_re[i]=max(0,sumv-2*x)
    else:
        sumv+=v
        right[i]=max(right[i-1],sumv-x)
        right_re[i]=max(right_re[i-1],sumv-2*x)    

sumv=0
left=[0]*n
left_re=[0]*n

#反時計周り
for i,(x,v) in enumerate(xv_rev):
    if i==0:
        sumv=v
        left[i]=max(0,sumv-x)
        left_re[i]=max(0,sumv-2*x)
    else:
        sumv+=v
        left[i]=max(left[i-1],sumv-x)
        left_re[i]=max(left_re[i],sumv-2*x)    

ans=0
for i in range(n):
    if i==n-1:
        ans=max(ans,right[i])
        ans=max(ans,left[i])
    else:
        ans=max(ans,right[i]+left_re[n-i-2])
        ans=max(ans,left[i]+right_re[n-i-2])

print(ans)


Measured memory_bytes: 94392
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,l,x[300030],t[300030],ans,a[300030],b[300030];
bool del[300030];
int st[300030],tp;
int main()
{
	scanf("%d %d",&n,&l);
	for(int i=1;i<=n;++i)scanf("%d",&x[i]);
	for(int i=1;i<=n;++i)scanf("%d",&t[i]);
	for(int i=1;i<=n;++i)
	{
		ans+=(t[i]-1)/(2*l);
		t[i]=(t[i]-1)%(2*l)+1;
		a[i]=t[i]<=2*(l-x[i]);
		b[i]=t[i]<=2*x[i];
	}
	for(int i=1;i<=n;++i)if(!a[i]&&!b[i])++ans,del[i]=1;
	if(a[n]==1&&b[n]==0)b[n]=1;
	for(int i=1;i<=n;++i)
		if(!del[i])
		{
			if(a[i]==1&&b[i]==0)
			{
				if(tp)del[st[tp]]=1,del[i]=1,--tp,++ans;
			}
			if(a[i]==1&&b[i]==1)st[++tp]=i;
		}
	tp=0;
	for(int i=n;i;--i)
		if(!del[i])
		{
			if(a[i]==0&&b[i]==1)
			{
				if(tp)del[st[tp]]=1,del[i]=1,--tp,++ans;
			}
			if(a[i]==1&&b[i]==1)st[++tp]=i;
		}
	int last=0;
	for(int i=1;i<=n;++i)
		if(!del[i]&&a[i]==1&&b[i]==1)
		{
			if(last)del[last]=del[i]=1,last=0,++ans;
			else last=i;
		}
	for(int i=1;i<=n;++i)ans+=!del[i];
	++ans;
	if(!del[n]&&a[n]==1)--ans;
	printf("%lld",2ll*ans*l);
	return 0;
}


Measured memory_bytes: 6272
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}

void Eratos(bool isp[],ll n){
    rep(i,n+1) isp[i]=1;
    for(ll i=2;i*i<=n;i++){
        if(isp[i]){
            for(ll j=i;i*j<=n;j++){
                isp[i*j]=0;
            }
        }
    }
}

int main(){
    ll q,np[(ll)1e5+1]={},cnt=0,l,r;
    bool isp[(ll)1e5+1];
    cin>>q;
    Eratos(isp,1e5);
    for(ll i=3;i<=1e5;i++){
        if(isp[i]&&isp[(i+1)/2]) cnt++;
        np[i]=cnt;
    }
    rep(i,q){
        cin>>l>>r;
        cout<<np[r]-np[l-1]<<endl;
    }
    return 0;
}

Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
int len;
string s;
int main()
{
 //freopen(".in","r",stdin);
 //freopen(".out","w",stdout);
 cin>>s;
 len=s.size();
 cout<<s[0];
 cout<<len-2;
 cout<<s[len-1]<<endl;
 return 0;
}

Measured memory_bytes: 256
n=int(input())
li=list(map(int,input().split()))
q=[]
if n==1:
  print(0)
else:
  a=0
  for i in range(n-1):
    if li[i] >= li[i+1]:
      a+=1
    else:
      q.append(a)
      a=0
  q.append(a)
  print(max(q))

Measured memory_bytes: 14224
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
#define rep(i, a, n) for (ll i = (a); i < (n); i++)
#define debug(x) cerr << #x << ": " << x << endl;
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;}

int main() {
    string s;
    cin >> s;
    ll ans = 0;
    for(ll i = 0; i < (ll)s.size(); i++) {
        for (ll j = 1; j <= (ll)s.size() - i; j++) {
            string t = s.substr(i, j);
            bool ok = true;
            for(auto c : t) {
                if (c == 'A' || c == 'C' || c == 'G' || c == 'T') continue;
                else ok = false;
            }
            if (ok) chmax(ans, (ll)t.size());
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
import sys
N=int(input())

if N==1:
    print(0)
    sys.exit()

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
target=factorization(N)
ans=0
for i in target:
    count=1
    while(i[1]>=count):
        ans+=1
        i[1]-=count
        count+=1
print(ans)    


Measured memory_bytes: 63440
import collections
n = int(input())
A = collections.Counter([int(x) for x in input().split()])
lst1 = [-1]
lst2 = [-1]
for l, c in A.items():
  if c > 1:
    lst1.append(l)
  if c > 3:
    lst2.append(l*l)
lst1.sort()
if len(lst1)-1>1 or len(lst2)-1>0:
  if len(lst1)-1>1:
    print(max(max(lst2), lst1[-1]*lst1[-2]))
  else:
    print(max(lst2))
else:
  print(0)

Measured memory_bytes: 18600
#include "bits/stdc++.h"
using namespace std;
#define int long long
int a,b,v,w,t;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>a>>v>>b>>w>>t;
	if(v<=w)
	{
		cout<<"NO"<<endl;
		return 0;
	}
	cout<<(t*(v-w)>=abs(a-b)?"YES":"NO")<<endl;
	return 0;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,w,i,j,a,b;cin >> n >> w;
    int dp[n+1][w+1] = {};
    for(i=1;i<=n;i++){
        cin >> a >> b;
        for(j=0;j<=w;j++){
            if(j<b) dp[i][j] = dp[i-1][j];
            else dp[i][j] = max(dp[i-1][j],dp[i][j-b]+a);
        }
    }
    cout << dp[n][w] << endl;
}


Measured memory_bytes: 7040
from collections import Counter

n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7

primes = [
  2,  3,  5,  7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
 71, 73, 79, 83, 89, 97,101,103,107,109,113,127,131,137,139,149,151,157,163,
167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,
271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,
389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,
503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,
631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,
757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,
883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,
1009
]

def prime_factorize(n):
    res = []
    i = 0
    while primes[i] * primes[i] <= n:
        if n % primes[i] == 0:
            res.append(primes[i])
            n //= primes[i]
        else:
            i += 1
    if n != 1:
        res.append(n)
    return res


lcm_factors = Counter()
for ai in a:
    prime_factors = prime_factorize(ai)
    counter = Counter(prime_factors)
    for k, v in counter.items():
        if k in lcm_factors:
            lcm_factors[k] = max(lcm_factors[k], v)
        else:
            lcm_factors[k] = v

lcm = 1
for k, v in lcm_factors.items():
    lcm *= pow(k, v, MOD)
    lcm %= MOD

ans = 0
for ai in a:
    ans += lcm * pow(ai, MOD - 2, MOD)
    ans %= MOD

print(ans)

Measured memory_bytes: 4980
#include<bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
const ll MOD = 1e9+7;

int main(){
  
  
  int n,q; cin>>n>>q;
  atcoder::dsu d(n);
  while(q--){
    int t,u,v; cin>>t>>u>>v;
    if(t==0){
      d.merge(u,v);
    }
    else{
      cout<<d.same(u,v)<<endl;
    }
  }
  
}


Measured memory_bytes: 4008
package main

import (
        "fmt"
)

func solution(s string) int {
        l := len(s)
        out := 0
        for i := 0; i <= l; i++ {
                for j := i + 1; j <= l; j++ {
                        t := s[i:j]
                        if isACGT(t) {
                                out = max(out, len(t))
                        }
                }
        }
        return out
}

func max(x, y int) int {
        if x > y {
                return x
        }
        return y
}

func isACGT(s string) bool {
        for _, r := range s {
                if r == 'A' || r == 'C' || r == 'G' || r == 'T' {
                        continue
                } else {
                        return false
                }
        }
        return true
}

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


Measured memory_bytes: 1768
require 'set'
d_op = {'N' => [0, 1], 'E' => [1, 0], 'S' => [0, -1], 'W' => [-1, 0]}
until (n = gets.to_i) == 0
  targets = n.times.reduce(Set.new) {|s| s << gets.split(' ').map(&:to_i).to_a }
  pos = [10, 10]
  gets.to_i
    .times
    .map { gets.chomp.split(' ') }
    .lazy
    .each {|d, l|
      break if targets.empty?
      op = d_op[d]
      l.to_i.times {
        pos = pos.zip(op).map {|a| a.reduce(:+) }.to_a
        targets.delete pos
      }
    }
  puts targets.empty? ? 'Yes' : 'No'
end

Measured memory_bytes: 6200
import sys
import fractions
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

A, B, K = [int(x) for x in readline().rstrip().split()]
gcd_ = fractions.gcd(A, B)


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

    divisors.sort()
    return divisors
print(make_divisors(gcd_)[-K])

Measured memory_bytes: 13552
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define C 0.5772156649
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define pil pair<int,ll>
#define pii pair<int,int>
#define ull unsigned long long
#define base 1000000000000000000
#define fio ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

const double g=10.0,eps=1e-12;
const int N=200000+10,maxn=200000+10,inf=0x3f3f3f3f;

int a[N];
int main()
{
    int n; scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    int cnt=unique(a+1,a+1+n)-a-1;
    cout<<cnt<<endl;
    return 0;
}
/********************

********************/


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

public class Main {

	public static void main(String[] args) throws IOException {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskX solver = new TaskX();
		solver.solve(1, in, out);
		out.close();
	}

	static int INF = 1 << 30;
	static int modP = 1000000007;

	static class TaskX {
		public void solve(int testNumber, InputReader in, PrintWriter out) {

			int n = in.nextInt();
			long[] a = in.nextLongArray(n);
			long[] sum = new long[n];

			Arrays.sort(a);
			sum[0] = a[0];
			for (int i = 1; i < n; i++) {
				sum[i] = sum[i-1] + a[i];
			}

			int count = 1;
			for (int i = n-2; i >= 0; i--) {
				if (2 * sum[i] >= a[i+1]) {
					count++;
				} else {
					break;
				}
			}

			out.println(count);

		}
	}

	static class InputReader {
		BufferedReader in;
		StringTokenizer tok;

		public String nextString() {
			while (!tok.hasMoreTokens()) {
				try {
					tok = new StringTokenizer(in.readLine(), " ");
				} catch (IOException e) {
					throw new InputMismatchException();
				}
			}
			return tok.nextToken();
		}

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

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

		public double nextDouble() {
			return Double.parseDouble(nextString());
		}

		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextInt();
			}
			return res;
		}

		public long[] nextLongArray(int n) {
			long[] res = new long[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextLong();
			}
			return res;
		}

		public InputReader(InputStream inputStream) {
			in = new BufferedReader(new InputStreamReader(inputStream));
			tok = new StringTokenizer("");
		}

	}

}


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

using namespace std;

#define rep(i,n) for(long i=1;i<n;i++)

int main(){
  long n;
  string s;
   cin >> n >> s;
 
  vector<long> d(n,0);
  
  
  if(s[0]=='(') d[0]++;
  else d[0]--;
  
  long x=min(long(0),d[0]);
  
  rep(i,n){
   d[i]=d[i-1];
    if(s[i]=='(') d[i]++;
    else d[i]--;
    x=min(x,d[i]);
  }
  
  string res="";
  rep(i,max(long(0),-1*x)+1) res+='(';
    res+=s;
  rep(i,max(long(0),d[n-1]-1*x)+1) res+=')';
  
  cout << res << endl;
}


Measured memory_bytes: 256
a=input()
b=input()
if a==1 and b==2:
  print "3"
elif a==2 and b==3:
  print "1"
elif a==3 and b==1:
  print "2" 
elif a==3 and b==2:
  print "1"
elif a==2 and b==1:
  print "3"
else:
  print "2"

Measured memory_bytes: 2568
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using P = pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll INF = 5e15;
int main(){
    ll N;
    cin >> N;
    ll ans = 0;
    for(ll keta = 0; keta < 10; keta++){
        ll m = pow(3, keta + 1);
        for(ll i = 0; i < m; i++){
            ll tmp = 0;
            ll j = i;
            bool a = 0, b = 0, c = 0;
            for(ll cnt = 0; cnt <= keta; cnt++){
                ll po = j % 3;
                j /= 3;
                tmp *= 10;
                (po == 0 ? a : (po == 1 ? b : c)) = 1;
                if(po == 0) tmp += 3;
                else if(po == 1) tmp += 5;
                else if(po == 2) tmp += 7;
            }
            if(tmp <= N && a && b && c){
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define pi  pair<int,int>
#define pl  pair<ll,ll>
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define N 200000+5

int main() {
// #ifndef ONLINE_JUDGE
//     freopen("input.txt","r",stdin);
//     freopen("output.txt","w",stdout);
// #endif
    ll n,i;
    cin>>n;
    ll a[n];
    for(i=0;i<n;i++)
        cin>>a[i];
    ll ans[n];
    ans[0]=0,ans[1]=abs(a[1]-a[0]);
    for(i=2;i<n;i++)
    {
        ans[i]=min(ans[i-1]+abs(a[i-1]-a[i]) ,  ans[i-2]+abs(a[i-2]-a[i]));
    }
    cout<<ans[n-1]<<endl;
    
    return 0;
    
}

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

using namespace std;

void RewriteDp(int a, vector<bool>& dp) {
	for (int i = 1; a*i <= 1000000; i++)
	{
		dp[a * i] = true;
	}
}

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

	vector<int> a(n);
	vector<bool> dp(1000001, false);
	dp[0] = true;

	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	sort(a.begin(), a.end());

	int ans = 0;

	for (int i = 0; i < n; i++)
	{
		if(dp[a[i]]) continue;
		else {
			RewriteDp(a[i], dp);
			if(a[i]!=a[i+1]) ans++;
		}
	}
	
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3968
import sys
input=sys.stdin.readline
n=int(input())
h=tuple(map(int,input().split()))
dp=[0]*n
dp[1]=abs(h[1]-h[0])
for i in range(2,n):
    dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]))
print(dp[n-1])

Measured memory_bytes: 20616
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(a) int(a.size())
const int N=2e5+10;

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

int n,pre[N],suf[N];
char s[N];

int main() {
	cin>>n;scanf("%s",s+1);
	for(int i=1;i<=n;i++) pre[i]=pre[i-1]+(s[i]=='#');
	for(int i=n;i;i--) suf[i]=suf[i+1]+(s[i]=='.');
	int ans=1e9;
	for(int i=1;i<=n+1;i++) ans=min(ans,pre[i-1]+suf[i]);
	cout<<ans;
	return 0;
}


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

using namespace std;

//string findDayYear (string s){

//}

int32_t main()
{
    time_t start, end;
    time(&start);
    ios_base::sync_with_stdio(false);

    ///////////////////////////////////////////////////////
    int a[3];
    cin>>a[0]>>a[1]>>a[2];
    sort(a,a+3);
    cout<<a[0]+a[1];
    ///////////////////////////////////////////////////////

    time(&end);
    double time_taken = double(end - start); 
    //cout << "Time taken by program is : " << fixed << time_taken << setns << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, m;
ll a[100005];
ll sig[2 * 100005];
ll ct[2 * 100005];
ll neg[2 * 100005];

int main () {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    ll all = 0;
    
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
        a[i]--;
    }
 
    for(int i = 1; i < n; ++i) {
 
        // calc operations without favorite
        ll d = a[i] - a[i - 1];
        if (d < 0) d += m;
        all += d;
 
        // add range
        ll l = a[i - 1];
        ll r = a[i];
        if (l > r) r += m;
        if (l + 1 >= r) continue;
        sig[l + 2]++;
        sig[r + 1]--;
        neg[r + 1] += r - l - 1;
    }
 

    ll pct = 0;
    ll cur = 0;

    for(int i = 0; i < 2 * m - 1; ++i) {
        pct += sig[i];
        cur += pct;
        cur -= neg[i];
        ct[i] = cur;
    }

    ll mmax = 0;
    for(int i = 0; i < m; ++i) {
        ll cd = ct[i];
        if (i + m < 2 * m - 1) cd += ct[i + m];
        mmax = max(mmax, ct[i] + ct[i + m]);
    }
 
    cout << all - mmax << endl;
    
}

Measured memory_bytes: 4992
#include<iostream>
#include<utility>
#include<vector>
#include<algorithm>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define all(v) v.begin(),v.end()
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

int main(){
	ll n,k;
	cin>>n>>k;
	ll ans,a,b;
	ll l[n],r[n];
	vector<pll> vec;
	rep(i,n){
		cin>>a>>b;
		vec.pb(pll(a,b));
	}
	sort(all(vec));
	rep(i,n){
		a=vec[i].first;b=vec[i].second;
		if(i==0)l[0]=1;
		else l[i]=r[i-1];
		r[i]=l[i]+b;
		if(l[i]<=k && k<r[i])ans=a;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3440
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<queue>
#include<bitset>
#define LL long long
using namespace std;
inline int read( )
{
  int sum=0;char c=getchar( );bool f=0;
  while(c<'0'||c>'9') {if(c=='-') f=1;c=getchar( );}
  while(c>='0'&&c<='9') {sum=sum*10+c-'0';c=getchar( );}
  if(f) return -sum;
  return sum;
}
const int N=405,M=100005;
int n,m,A[M],B[M];
bitset<N>R[N];bool can[N];
int main( )
{
  int i,j,ans=0;
  n=read( );m=read( );
  for(i=1;i<=m;i++) A[i]=read( ),B[i]=read( );
  for(i=1;i<=n;i++)
    {
      R[i][i]=1;can[i]=1;
      for(j=m;j>=1;j--)
	{
	  if(R[i][A[j]]&&R[i][B[j]]) {can[i]=0;break;}
	  if(R[i][A[j]]) R[i][B[j]]=1;
	  else if(R[i][B[j]]) R[i][A[j]]=1;
	}
    }
  for(i=1;i<=n;i++)
    if(can[i])
      for(j=i+1;j<=n;j++)
	if(can[j]&&(R[i]&R[j]).none( )) ans++;
  printf("%d",ans);
  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
#define MAX 10005
#define MAXE MAX * (MAX - 1) / 2 + 1

struct edge { int u , v; double cost; };
struct node { double x , y; };
bool comp(const edge& e1 , const edge& e2){
    return e1.cost > e2.cost;
}

int V , E;
int par[MAX], rank[MAX];
node node[MAX];
edge es[MAXE];

void init(int n){
    for(int i = 0; i <= n; i++){
        par[i] = i;
        rank[i] = 0;
    }
}

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

void unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y) return;

    if(rank[x] < rank[y]){ 
        par[x] = y;
    }else{
        par[y] = x;
        if(rank[x] == rank[y]) rank[x]++;
    }
}

double kruskal(){
    std::sort(es , es + E , comp);
    init(V);
    double res = 0;
    for(int i = 0;i < E;i++){
        edge e = es[i];
        if(find(e.u) != find(e.v)){
            unite(e.u , e.v);
        }else{
            res += e.cost;
        }
    }
    return res;
}

int main(){
    std::cin >> V >> E;
    for(int i = 1;i <= V;i++){
        std::cin >> node[i].x >> node[i].y;
    }
    for(int i = 0;i < E;i++){
        std::cin >> es[i].u >> es[i].v;
        es[i].cost = std::sqrt(std::pow((node[es[i].u].x - node[es[i].v].x) , 2) + std::pow((node[es[i].u].y - node[es[i].v].y) , 2));
    }
    std::cout << std::fixed << std::setprecision(3) << kruskal() << "\n";
}


Measured memory_bytes: 3872
#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++)
const int inf=100000000;
int n,m,x,tmp,ans;
std::vector<int> cost;
std::vector<vector<int> > intel;

std::vector<int> isv(vector<int> tv,int i){
    rep(j,m){
        tv.at(j)+=intel.at(i).at(j);
    }
    return tv;
}

int dfs(int i,int csum, vector<int> isum){
    if(i==n) {
        rep(j,m) if(isum.at(j)<x) csum=inf;
        return csum;
    }

    return min(dfs(i+1,csum,isum),dfs(i+1,csum+cost.at(i),isv(isum,i)));
}


void solve(){
    std::vector<int> isum(m);
    ans=dfs(0,0,isum);
    if(inf==ans) cout<<"-1"<<endl;
    else cout<<ans<<endl;
}

int main(){
    cin>>n>>m>>x;
    rep(i,n){
        intel.emplace_back();
        cin>>tmp;
        cost.emplace_back(tmp);
        rep(j,m){
            cin>>tmp;
            intel.at(i).emplace_back(tmp);
        }
    }

    solve();
    return 0;
}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define INF 999999999
#define mod 10e9+7

#define rep(i,n) for(int i=0;i<n;i++)
int main(){
   ll b,n,all=0;
      double t,a,mini=INF;
   cin >> n >> t >> a ; 
   vector<double> h(n); 
   rep(i,n) {
      cin >> h.at(i);
      if(mini>abs(a-t+h.at(i)*0.006)){
        b=i+1;
        mini=abs(a-t+h.at(i)*0.006);
      }
     
      
      }

cout << b << endl;

   
  }



Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<cassert>

typedef long long int ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<signed(n);i++)
#define EREP(i,n) for(int i=1;i<=signed(n);i++)
#define ALL(a) (a).begin(),(a).end()
using std::cout;
using std::vector;
using std::endl;
using std::cin;
using std::string;
using std::max;
using std::min;
using std::abs;
//#define EVEL 1
#ifdef EVEL
#define DEB(X) cout << #X << ":" <<X<<" " ;
#define TF(f) f ? cout<<"true  " : cout<<"false ";
#define END cout<<"\n";
#else
#define DEB(X) {}
#define TF(f) {}
#define END {}
#endif
const int MOD = 1000000007;
const ll INF = 5000000000000;
//typedef std::pair<int, int> P;
struct edge { int to;double cost; };
#define VMAX 1010

     ll N,M,K;
     ll A[200010],B,C;
     ll P[11];
     ll ans;
     char S[100];
int main() {
    cin>>K>>N;
    ll s=0;
    REP(i,N){
        cin>>A[i];
        if(i>0){
            ans+=A[i]-A[i-1];
            s=max(s,A[i]-A[i-1]);
        }
    }
    ans+=K+A[0]-A[N-1];
    ans-=max(s,K+A[0]-A[N-1]);
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1792
using System;
using System.Collections.Generic;
using System.Collections;
using System.Collections.Specialized;
using System.Linq;
using System.Text;
using System.IO;
using System.Reflection;
using static System.Math;
using System.Numerics;
static class Program{
	const int mod=(int)1e9+7;
	static List<Tuple<int,int>>[] li;
	static bool[] b;
	static int p;
	static long d;
	static void Main(){
		Sc sc=new Sc();
		int[] s=sc.Ia;
		int n=s[0];
		li=new List<Tuple<int,int>>[n];
		b=new bool[n];
		for(int i=0;i<n;i++){
			li[i]=new List<Tuple<int,int>>();
		}
		for(int i=0;i<n-1;i++){
			int[] e=sc.Ia;
			li[e[0]].Add(Tuple.Create(e[1],e[2]));
			li[e[1]].Add(Tuple.Create(e[0],e[2]));
		}
		
		Fu(0,0);
		b=new bool[n];
		Fu(p,0);
		
		Console.WriteLine("{0}",d);
	}
	static void Fu(int a,int g){
		b[a]=true;
		if(d<g){p=a;d=g;}
		for(int i=0;i<li[a].Count;i++){
			if(!b[li[a][i].Item1]){Fu(li[a][i].Item1,g+li[a][i].Item2);}
		}
	}
}

public class Sc{
	public int I{get{return int.Parse(Console.ReadLine());}}
	public long L{get{return long.Parse(Console.ReadLine());}}
	public double D{get{return double.Parse(Console.ReadLine());}}
	public string S{get{return Console.ReadLine();}}
	public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}
	public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}
	public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}
	public string[] Sa{get{return Console.ReadLine().Split();}}
	public object[] Oa{get{return Console.ReadLine().Split();}}
	public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),int.Parse);}}
	public int[] Ia3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),int.Parse);}
	public int[] Ia3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),int.Parse);}
	public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}}
	public long[] La3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),long.Parse);}
	public long[] La3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),long.Parse);}
	public T[] Arr<T>(int n,Func<T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f();}return a;}
	public T[] Arr<T>(int n,Func<int,T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i);}return a;}
	public T[] Arr<T>(int n,Func<string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(Console.ReadLine().Split());}return a;}
	public T[] Arr<T>(int n,Func<int,string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i,Console.ReadLine().Split());}return a;}
}


Measured memory_bytes: 41956
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
 
int main() {
  long long int N,ans,B;
  cin >> N;
  vector<long long int> A(N);
  rep(i,N){
    cin >> A.at(i);
  }
  sort(A.rbegin(),A.rend());
  ans=0;
  ans+=A.at(0);
  int k=1;
  rep(i,N-2){
    if(i%2==0){
      B=A.at(k);
      k++;
    }
    ans += B;
  }
  cout << ans << endl;
    
}

Measured memory_bytes: 4836
#include<stdio.h>
main()
{
    char a[123];scanf("%s",a);
    register int i=0;
    for(;a[i];++i)if(a[i]=='C')break;
    if(!a[i]){puts("No");return 0;}
    for(++i;a[i];++i)if(a[i]=='F')break;
    if(!a[i]){puts("No");return 0;}
    puts("Yes");
}

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

int main() {
    int Q;
    cin >> Q;
    vector<int> L(Q), R(Q);
    for (int i = 0; i < Q; i++)
        cin >> L[i] >> R[i];

    vector<bool> is_prime(100001, true);
    is_prime[0] = false; is_prime[1] = false;
    for (int i = 2; i * i <= 100000; i++) {
        if (is_prime[i]) {
            for (int j = 2 * i; j <= 100000; j += i) {
                is_prime[j] = false;
            }
        }
    }

    vector<int> cnt(100001);
    for (int i = 3; i <= 100000; i += 2) {
        if (is_prime[i] && is_prime[(i + 1) / 2]) cnt[i]++;
    }
    for (int i = 3; i <= 100000; i++) {
        cnt[i] += cnt[i - 1];
    }

    for (int i = 0; i < Q; i++) {
        int l = L[i], r = R[i];
        cout << cnt[r] - cnt[l - 1] << endl;
    }
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;

int E[111][111];

int main(){
  int N; cin>>N;
  int cnt=0;
  rep(i,N) rep(j,N){
    if(i>=j) continue;
    if(N%2&&i+j+2!=N) E[i][j]=1,cnt++;
    if(N%2==0&&i+j+2!=N+1) E[i][j]=1,cnt++;
  }
  cout<<cnt<<endl;
  rep(i,N) rep(j,N){
    if(E[i][j]) cout<<i+1<<" "<<j+1<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>

template<typename T>inline void read(T &x)
{
	char c=x=0;
	for(c=getchar();!isdigit(c);c=getchar());
	for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
}

namespace fuck
{
	typedef long long ll;
	const int N=100100,M=N*2;
	int begin[N],next[M],to[M];
	ll A[N],f[N];
	int n,e;
	void add(int x,int y,bool k=1)
	{
		to[++e]=y;
		next[e]=begin[x];
		begin[x]=e;
		if(k)add(y,x,0);
	}
	bool dfs(int p=1,int h=0)
	{
		ll sum=0,max=0;
		int cnt_son=0;

		for(int i=begin[p],q;i;i=next[i])
			if((q=to[i])!=h)
			{
				cnt_son++,dfs(q,p);

				sum+=f[q],max=std::max(max,f[q]);
			}
		if(!cnt_son)
		{
			f[p]=A[p];
			if(p==1)return !f[p];
			return 1;
		}
		if(sum<A[p] || sum>A[p]*2)return 0;

		if(max*2<=sum)f[p]=sum-2*(sum-A[p]);
		else if(sum-max<sum-A[p])return 0;
		else f[p]=sum-2*(sum-A[p]);

		if(p==1)
		{
			if(cnt_son>1 && f[p]!=0)return 0;
			if(cnt_son==1 && f[p]!=A[p])return 0;
		}

		return 1;
	}
	void initialize()
	{
		read(n);
		for(int i=1;i<=n;i++)read(A[i]);
		for(int i=1,u,v;i<n;i++)read(u),read(v),add(u,v);
	}
	void solve()
	{
		initialize();
		printf("%s\n",dfs()?"YES":"NO");
		
//		for(int i=1;i<=n;i++)
//			printf("%lld ",f[i]);
//		printf("\n");
	}
}
int main()
{
	fuck::solve();
	return 0;
}


Measured memory_bytes: 10368
n = int(input())
votelist = [list(map(int, input().split())) for _ in range(n)]

chlist = votelist[0]
for i in range(1, n):
    x = max(-(chlist[0]*-1 // votelist[i][0]), -(chlist[1]*-1 // votelist[i][1]))
    chlist[0] = votelist[i][0] * x
    chlist[1] = votelist[i][1] * x
    
print(sum(chlist))

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

int main(){
  int n,sum,result=100;
  cin >> n;
  vector<int> v(n);
  for(int i=0;i<n;i++) {
    cin >> v[i];
  }
  sum = accumulate(v.begin(),v.end(),0);
  for(int i=0;i<n-1;i++){
  	int s1=0,s2=0;
    for(int j=0;j<=i;j++){
      s1+=v[j];
    }
    s2=sum-s1;
    if(abs(s1-s2) <= result){
      result = abs(s1-s2);
    }
  }
  cout << result;
  return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys


def solve(N: int, X: "List[int]", L: "List[int]"):
    d = {}
    for i in range(N):
        d[X[i]]=L[i]

    d=sorted(d.items())


    toru1=0
    maeR=d[0][0]+d[0][1]
    for i in range(1,N):
        tsugiL=d[i][0]-d[i][1]
        if maeR>tsugiL:
            tsugiR=d[i][0]+d[i][1]
            toru1+=1
            if tsugiR<maeR:
                maeR=tsugiR
        else:
            maeR=d[i][0]+d[i][1]

    toru2=0
    maeL=d[N-1][0]-d[N-1][1]
    for i in reversed(range(N-1)):
        tsugiR=d[i][0]+d[i][1]
        if maeL<tsugiR:
            tsugiL=d[i][0]-d[i][1]
            toru2+=1
            if tsugiL<maeR:
                maeR=tsugiL
            toru2+=1
        else:
            maeL=d[i][0]-d[i][1]

    print(N-min(toru1,toru2))
    
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = [int()] * (N)  # type: "List[int]"
    L = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        X[i] = int(next(tokens))
        L[i] = int(next(tokens))
    solve(N, X, L)

if __name__ == '__main__':
    main()


Measured memory_bytes: 24628
#include <iostream>
#include <algorithm>
#include <utility>
#include <map>
#include <vector>
#include <cstring>
#include <climits>
#include <queue>
#include <cmath>
#include <iomanip>
#include <set>
#include <bitset>

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

int X, N;
bool has[105];
int main() {
	ios::sync_with_stdio(false);
	cin >> X >> N;
	for (int i = 0; i < 105; i++) has[i] = 1;
	for (int i = 0; i < N; i++) {
		int p;
		cin >> p;
		has[p] = 0;
	}
	int best = 1 << 30;
	int ans = 0;
	for (int i = 0; i < 105; i++) {
		if (!has[i]) continue;
		if (best > abs(i - X)) {
			best = abs(i - X);
			ans = i;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 3656
#include <iostream>

using namespace std;

int main(){
    int n;
    bool flag = false;
    cin >> n;

    for(int i = 0;i < 3;i++){
        int a;
        a = n%10;
        n /= 10;
        if(a == 7)flag = true;
    }

    if(flag)cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#include<vector>
using namespace std;
 
int main() {
  string a;
  cin>>a;
  for(int i=0;i<a.size();i++){
    if(i%2==0&&a.at(i)=='L'){
      cout<<"No";
      return 0;
    }
    if(i%2==1&&a.at(i)=='R'){
      cout<<"No";
      return 0;
    }
  }
  cout<<"Yes";
}

Measured memory_bytes: 256
N, M = map(int, input().split())
H = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]

Highest = [True for _ in range(N)]

for i, route in enumerate(AB):
    if H[route[0]-1] >= H[route[1]-1]:
        Highest[route[1]-1] = False
    if H[route[1]-1] >= H[route[0]-1]:
        Highest[route[0]-1] = False

print(Highest.count(True))

Measured memory_bytes: 32056
#include<stdio.h>
#include<stdlib.h>
#define NIL NULL

struct node{
  struct node *right;
  struct node *left;
  struct node *p;
  int key;
};
typedef struct node *Node;
Node root;

Node treeSearch(Node u, int k){
  if(u == NIL || k == u->key){return u;}
  if(k < u->key){return treeSearch(u->left,k);}
  else{return treeSearch(u->right,k);}
}

Node treeMinimum(Node x){
  while(x->left != NIL){
    x = x->left;
  }
  return x;
}

Node treeSuccessor(Node x){
  if(x->right != NIL){
    return treeMinimum(x->right);
  }
  Node y = x->p;
  while(y != NIL && x == y->right){
    x=y;
    y=y->p;
  }
  return y;
}

void treeDelete(Node z){
  Node y;
  Node x;
  if(z->left == NIL || z->right == NIL){
    y = z;
  }else{
    y = treeSuccessor(z);
  }

  if(y->left != NIL){
    x = y->left;
  }
  else{
    x = y->right;
  }

  if(x != NIL){
    x->p = y->p;
  }
  if(y->p == NIL){
    root = x;
  }else if(y == y->p->left){
    y->p->left = x;
  }else{
    y->p->right = x;
  }

  if(y != z){
    z->key = y->key;
  }
  free(y);
}
    

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x != NIL){
    y = x;
    if(z->key < x->key){
      x = x->left;
    }
    else{
      x = x->right;
    }
  }
  z->p = y;

  if(y == NIL){
    root = z;
  }
  else if(z->key < y->key){
    y->left = z;
  }
  else{
    y->right = z;
  }
}

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

void preorder(Node u){
  if(u == NIL){
    return;
  }
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}

    
int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root,x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}



Measured memory_bytes: 20444
def resolve():
    S = list(input())
    ans = [0 for _ in range(len(S) + 1)]
    cnt = 0
    for i in range(len(S)):
        if S[i] == "<":
            cnt += 1
            ans[i + 1] = max(cnt, ans[i + 1])
        else:
            cnt = 0
    cnt = 0
    for i in range(len(S), 0, -1):
        if S[i - 1] == ">":
            cnt += 1
            ans[i - 1] = max(cnt, ans[i - 1])
        else:
            cnt = 0
    print(sum(ans))


resolve()


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

#define vi vector<int>
#define vl vector<long>
#define vvi vector<vector<int>>
#define vvl vector<vector<long>>
#define pint pair<int, int>
#define plong pair<long, long>

int main() {
    long T1, T2, A1, A2, B1, B2;
    cin>>T1>>T2 >> A1 >> A2 >> B1 >> B2;
    long rel_A1 = A1 - B1, rel_A2 = A2 - B2;
    if(T1 * rel_A1 + T2 * rel_A2 == 0){
        cout << "infinity" << endl;
        return 0;
    }else{
        long d = T1 * rel_A1 + T2 * rel_A2;
        if(!((rel_A1 > 0) ^ (d > 0))){
            cout << 0 << endl;
            return 0;
        }else{
            d = (d < 0) ? -d : d;
            long l = (T1 * rel_A1 > 0) ? T1 * rel_A1 : -T1 * rel_A1;
            long count = (l/ d) * 2 + 1;
            if(l % d == 0) count--;
            cout << count << endl;
        }
    }
    return 0;

}

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

int main() {
	int N,M;
	cin >> N >> M;
	vector<int64_t>height(N);
	vector<int>vec(N,10);
	for(int i=0;i<N;i++){
		int H;
		cin >> H;
		height.at(i)=H;
	}
	for(int i=0;i<M;i++){
		int a,b,c,d;
		cin >> a >> b;
		c = min(a,b);
		d = max(a,b);
		if(height.at(c-1) < height.at(d-1)){
			vec.at(c-1)=0;
		}
		else if(height.at(c-1) > height.at(d-1)){
			vec.at(d-1)=0;
		}
		else if (height.at(c-1) == height.at(d-1)){
			vec.at(d-1)=0;
			vec.at(c-1)=0;
		}

	}
	int count = 0;
	for(int i=0;i<N;i++){
		if(vec.at(i)!=0){
			count++;
		}
	}
	cout << count << endl;

}



Measured memory_bytes: 4580
/*
读题不规范，爆零两行泪。
数据不清空，爆零两行泪。
多测不读完，爆零两行泪。
边界不特判，爆零两行泪。
贪心不证明，爆零两行泪。
D P 顺序错，爆零两行泪。
大小少等号，爆零两行泪。
变量不统一，爆零两行泪。
越界不判断，爆零两行泪。
调试不注释，爆零两行泪。
溢出不 l l，爆零两行泪。
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define X first
#define Y second
#define pb push_back
const int inf=0x3f3f3f3f3f3f3f3f;
int lowbit(int x){return x&-x;}
const int N=200000;
int n,d;
int a[N+1];
pair<int,int> p[N+1];
struct bitree{
	pair<int,int> mn[N+1];
	void init(){
		for(int i=1;i<=n;i++)mn[i]=mp(inf,0);
	}
	void chkmn(int x,pair<int,int> v){
		while(x<=n)mn[x]=min(mn[x],v),x+=lowbit(x);
	}
	int Mn(int x){
		pair<int,int> res(inf,0);
		while(x)res=min(res,mn[x]),x-=lowbit(x);
		return res.Y;
	}
}bit,bit_r;
vector<pair<int,int> > eg;
struct ufset{
	int fa[N+1];
	void init(){memset(fa,0,sizeof(fa));}
	int root(int x){return fa[x]?fa[x]=root(fa[x]):x;}
	bool mrg(int x,int y){
		x=root(x);y=root(y);
		if(x==y)return false;
		return fa[x]=y,true;
	}
}ufs;
int cst(pair<int,int> x){
	if(x.X>x.Y)swap(x.X,x.Y);
	return a[x.X]+a[x.Y]+(x.Y-x.X)*d;
}
bool cmp(pair<int,int> x,pair<int,int> y){
	return cst(x)<cst(y);
}
int kruskal(){
	sort(eg.begin(),eg.end(),cmp);
	int ans=0;
//	for(int i=0;i<eg.size();i++)printf("%lld %lld\n",eg[i].X,eg[i].Y);
	for(int i=0;i<eg.size();i++)ans+=ufs.mrg(eg[i].X,eg[i].Y)*cst(eg[i]);
	return ans;
}
signed main(){
	cin>>n>>d;
	for(int i=1;i<=n;i++)scanf("%lld",a+i),p[i]=mp(a[i],i);
	sort(p+1,p+n+1);
	bit.init();bit_r.init();
	for(int i=1;i<=n;i++){
		int mn1=bit.Mn(p[i].Y-1),mn2=bit_r.Mn(n-p[i].Y);
		if(mn1)eg.pb(mp(p[i].Y,mn1));
		if(mn2)eg.pb(mp(p[i].Y,mn2));
		bit.chkmn(p[i].Y,mp(p[i].X-p[i].Y*d,p[i].Y));bit_r.chkmn(n-p[i].Y+1,mp(p[i].X+p[i].Y*d,p[i].Y));
	}
	cout<<kruskal();
	return 0;
}
/*1
3 1000
1 100 1
*/

Measured memory_bytes: 22700
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ALL(x) x.begin(), x.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
random_device rnd;
mt19937 mt(rnd());
using ll = long long;
using lld = long double;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
using PII = pair<int, int>;
const int IINF = 1 << 30;
const ll INF = 1ll << 60;
const ll MOD = 1000000007;

int main()
{

    string s;
    cin >> s;
    s.insert(s.begin() + 4, ' ');
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tt;
    cin >> tt;
    while (tt--) {
        ll n, a, b, c, d;
        cin >> n >> a >> b >> c >> d;
        map<ll, ll> mp;
        mp[1] = d;
        function<ll(ll)> solve = [&](ll x) {
            if (x == 0) {
                return 0LL;
            }
            if (mp[x] != 0LL) {
                return mp[x];
            }
            ll res = 9e18;
            if (1.0 * x * d < 9e18) {
                res = x * d;
            }
            ll q = x % 2;
            res = min(res, solve(x / 2) + a + d * q);
            if (q) res = min(res, solve(x / 2 + 1) + a + d * (2 - q));
            q = x % 3;
            res = min(res, solve(x / 3) + b + d * q);
            if (q) res = min(res, solve(x / 3 + 1) + b + d * (3 - q));
            q = x % 5;
            res = min(res, solve(x / 5) + c + d * q);
            if (q) res = min(res, solve(x / 5 + 1) + c + d * (5 - q));
            return mp[x] = res;
        };
        cout << solve(n) << '\n';
    }
    return 0;
}


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

int main() {
    int N, res = 0, max = 0;;
    cin >> N;

    for (int i = 1; i <= N; i++) {
        int tmp = i;
        int cnt = 0;
        while (tmp % 2 == 0) {
            tmp /= 2;
            cnt++;
        }
        if (max <= cnt) {
            max = cnt;
            res = i;
        }
    }

    cout << res << endl;
}

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

using namespace std;

int main()
{
    int N;
    int ans=0;
    bool flag;
    string target;
    string instr;

    cin >> N;
    cin >> target;

    for(int i=0; i<N; ++i) {
        cin >> instr;
        for(int j=0; j<(int)instr.size(); ++j) {
            if(target[0]!=instr[j]) continue;
            for(int k=1; j+k*((int)target.size()-1)<(int)instr.size(); ++k) {
                flag=true;
                for(int l=1; l<(int)target.size(); ++l) {
                    if(target[l]!=instr[j+k*l]) {
                        flag=false;
                        break;
                    }
                }
                if(flag) {
                    ++ans;
                    break;
                }
            }
            if(flag) break;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3148
S = input()
key = 'keyence'

re = 'NO'
for i in range(1,7):
    bef = key[0:i]
    aft = key[i:]
    b_index = S.find(bef)
    a_index = S.rfind(aft)
    if b_index == 0 and a_index + len(aft) == len(S) : # 真ん中を抜けばいい場合
        re = 'YES'
        break
    elif (b_index == 0 or a_index + len(aft) == len(S)) and b_index + len(bef) == a_index: # 前後どちらかを抜く場合
        re = 'YES'
        break

print(re)

Measured memory_bytes: 3064