akhauriyash/Code-Regression huggingface dataset:
INF = 10 ** 18

A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
xyc = [list(map(int, input().split())) for _ in range(M)]

answer = INF
for x, y, c in xyc:
    answer = min(answer, a[x - 1] + b[y - 1] - c)
answer = min(answer, min(a) + min(b))

print(answer)


Measured memory_bytes: 38568
from collections import Counter
n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))
D=Counter(d);T=Counter(t)
x=0
for i in list(set(t)):
  if D[i]<T[i]:
    x=1
    break
if x==0:print('YES')
else:print('NO')

Measured memory_bytes: 65240
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=220;
const int mod=1000000007;
int n,m,k,X[N],Y[N],F[N],c[N][N],dfn[N],low[N],inq[N],S[N],fla[N],tot=1,top; long long ans=1;
vector<int>V[N];
void dfs(int x,int f){
    dfn[x]=low[x]=tot++,inq[x]=1,S[++top]=x;
    for(int t,i=0;i<V[x].size();i++){
        t=V[x][i]; if(t==f)continue;
        if(!dfn[t]){
            dfs(t,x),low[x]=min(low[t],low[x]);
            if(low[t]>=dfn[x]){
                int edg=0,cnt=0;
                do{fla[S[top]]=1,inq[S[top]]=0;}while(S[top--]!=t); fla[x]=1;
                for(int i=1;i<=m;i++) if(fla[X[i]]&&fla[Y[i]]) ++edg;
                for(int i=1;i<=n;i++) if(fla[i]) ++cnt,fla[i]=0;
                if(edg==cnt-1)(ans*=k)%=mod;
                else if(edg==cnt)(ans*=F[edg])%=mod;
                else (ans*=c[edg+k-1][k-1])%=mod;
            }
        }
        else if(inq[x])low[x]=min(low[x],dfn[t]);
    }
}
int gcd(int x,int y){return y?gcd(y,x%y):x;}
int qpw(int x,int n){
    int ret=1; for(;n;n>>=1,x=1ll*x*x%mod)
    if(n&1) ret=1ll*ret*x%mod; return ret;
}
int main(){
    scanf("%d%d%d",&n,&m,&k),c[0][0]=1;
    for(int i=1;i<=m;i++)scanf("%d%d",X+i,Y+i),V[X[i]].pb(Y[i]),V[Y[i]].pb(X[i]);
    for(int i=1;i<=m+k;i++) for(int j=0;j<=m+k;j++) c[i][j]=(c[i-1][j]+(j?c[i-1][j-1]:0))%mod;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++)(F[i]+=qpw(k,gcd(i,j)))%=mod;
        F[i]=1ll*F[i]*qpw(i,mod-2)%mod;
    }
    for(int i=1;i<=n;i++)if(!dfn[i])dfs(i,0);
    printf("%lld\n",ans);
}


Measured memory_bytes: 384
#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int ls = 15;
int l[] = {0,1,2,3,4,5,6,7,8,9,5,4,3,2,1};
int main(void){
  int n;
  cin >> n;
  for(int i = 0; i < n; i++){
    int a,b;
    cin >> a >> b;
    if(0 < a && a <= 5 && a > b){
      a = ls - a;
    }

    for(int j = a; l[j%ls] != b; j++){
      cout << l[j%ls] << ' ';
    }
    cout << b << endl;
  }
}

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

int main()
{
   int a,b,c,d;
   cin>>a>>b>>c>>d;
   int l=a+b;
   int r=c+d;
   if(l>r)cout<<"Left\n";
   else if(l==r)cout<<"Balanced\n";
   else cout<<"Right\n";

}


Measured memory_bytes: 256
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,k = inpl()
res = 1
for i in range(n):
    if i == 0:
        res *= k
    else:
        res *= k-1
print(res)

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

int n;

int main()
{
	while(cin>>n){
		map<int,int> a,b;
		for(int i=0,x;i<n;++i)
		{
			cin>>x;
			if(i%2==0){
				++a[x];
			}else{
				++b[x];
			}
		}
		int a1=0,a2=0,b1=0,b2=0;
		int s1=0,s2=0,t1=0,t2=0;
		for(auto c:a)
		{
			if(a1<c.second){
				a2=a1;	s2=s1;
				a1=c.second;	s1=c.first;
			}else	if(a2<c.second){
				a2=c.second;	s2=c.first;
			}
		}
		for(auto c:b)
		{
			if(b1<c.second){
				b2=b1;	t2=t1;
				b1=c.second;	t1=c.first;
			}else	if(b2<c.second){
				b2=c.second;	t2=c.first;
			}
		}
//		cout<<a1<<" "<<s1<<endl;
//		cout<<a2<<" "<<s2<<endl;
//		cout<<b1<<" "<<t1<<endl;
//		cout<<b2<<" "<<t2<<endl;
		int ans=n;
		if(s1!=t1)	ans=n-a1-b1;
		else{
			ans=min(n-a1-b2,n-a2-b1);
		}
		cout<<ans<<endl;
	}
	
	return 0;
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
#define rep(i,n) for (ll i=0;i<n;++i)
#define rep2(i,a,b) for (ll i=a;i<b;++i)
const ll MOD=1000003;
const ll INF=1e9;
const ll IINF=1e18;
const double EPS=1e-8;
const double pi=acos(-1);

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

int main(){
    string S,T;
    cin >> S >> T;
    int s=S.size(),t=T.size();
    vector<vector<int>> dp(s+1,vector<int>(t+1,INF));
    rep(i,s+1) dp[i][0]=i;
    rep(i,t+1) dp[0][i]=i;
    rep(i,s){
        rep(j,t){
            if (S[i]==T[j]) dp[i+1][j+1]=dp[i][j];
            else dp[i+1][j+1]=min(dp[i][j],min(dp[i+1][j],dp[i][j+1]))+1;
        }
    }
    cout << dp[s][t] << endl;
}


Measured memory_bytes: 6836
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<time.h>
//もう二度とつかわん//
//    ↓ ↓　↓　　 //
#define ll long long
//    ↑　↑　↑    //
//フェルマー方程式の恨み//
#define rep(i,n) for(int i=0;i<n;i++)
#define ggr getchar(); getchar();return 0;
using namespace std;
//素数判定
bool prime(ll n) {
	if (n == 1)return false;
	for (int i = 2; i*i <= n; i++) {
		if (n%i == 0)return false;
	}
	return true;
}
signed main() {
	string s;
	cin >> s;
	ll n = s.size();
	for (int i = n - 1; i >= 0; i--) {
		if (i - 4 >= 0 && s.substr(i - 4, 5) == "dream") {
			i -= 4;
		}
		else if (i - 4 >= 0 && s.substr(i - 4, 5) == "erase") {
			i -= 4;
		}
		else if (i - 6 >= 0 && s.substr(i - 6, 7) == "dreamer") {
			i -= 6;
		}
		else if (i - 5 >= 0 && s.substr(i - 5, 6) == "eraser") {
			i -= 5;
		}
		else {
			puts("NO");
			ggr
		}
	}
	puts("YES");
	ggr
}


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

int main() {
	int n,d,i,a;
	long int x;
	cin>>n>>d>>x;
	for(i=0;i<n;i++)
	  { cin>>a;
	      x+=((d-1)/a+1);
	  }
	cout<<x;  
	// your code goes here
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int C = sc.nextInt();
        if (A == B && B == C)
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}


Measured memory_bytes: 21972
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
	#define eprintf(...) 42
#endif

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef long double ld;
#define mp make_pair
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 100100;
int a[N];
int b[N];
int n;

int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	bool allPos = 1, allNeg = 1;
	for (int i = 0; i < n; i++) {
		if (a[i] >= 0) {
			b[i] = 1;
			allNeg = false;
		} else {
			b[i] = -1;
			allPos = false;
		}
	}
	if (allPos || allNeg) {
		int x = 0;
		for (int i = 0; i < n; i++)
			if (abs(a[i]) < abs(a[x]))
				x = i;
		b[x] *= -1;
	}
	int sum = 0;
	for (int i = 0; i < n; i++)
		sum += a[i] * b[i];
	printf("%d\n", sum);
	int p = -1, q = -1;
	for (int i = 0; i < n; i++) {
		if (b[i] == 1) {
			if (p == -1)
				p = i;
		} else {
			if (q == -1)
				q = i;
		}
	}
	for (int i = 0; i < n; i++) {
		if (i == p || i == q) continue;
		if (b[i] == 1) {
			printf("%d %d\n", a[q], a[i]);
			a[q] -= a[i];
		} else {
			printf("%d %d\n", a[p], a[i]);
			a[p] -= a[i];
		}
	}
	printf("%d %d\n", a[p], a[q]);

	return 0;
}


Measured memory_bytes: 2688
def Main(N, X):
    av = round(sum(X)/N)
    ans = 0
    for i in range(N):
        ans += (X[i]-av)**2
    return ans

def main():
    N = int(input())
    X = list(map(int, input().split()))
    print(Main(N, X))

if __name__ == '__main__':
    main()

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

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

signed main(){

  int v,e;
  cin>>v>>e;
  vector<vector<int>> adj(v);
  rep(i,e){
    int s,t;cin>>s>>t;
    adj[s].emplace_back(t);
  }

  auto bfs = [&](int s){
    queue<int> que;
    vector<int> visited(v);
    visited[s] = 1;
    for(auto nv:adj[s])que.emplace(nv);
    while(!que.empty()){
      int v = que.front();
      que.pop();
      if(v==s){
        cout<< 1 <<endl;
        exit(0);
      }
      if(visited[v])continue;
      visited[v] = 1;
      for(auto nv:adj[v]){
        que.emplace(nv);
      }
    }
  };

  rep(i,v){
    bfs(i);
  }
  cout<< 0 <<endl;

}


Measured memory_bytes: 3160
/**
 * C - Maximal Value
 * https://atcoder.jp/contests/abc140/tasks/abc140_c
 **/

#include<iostream>

using namespace std;

const int MAX_N = 100;

int N;
int B[MAX_N];

void solve() {
    int ans;
    for(int i=0; i<N; i++) {
        if(i==0) {
            ans += B[0];
        } else if (i==N-1) {
            ans += B[N-2];
        } else {
            ans += min(B[i-1], B[i]);
        }
    }
    cout << ans << endl;
}

int main() {
    cin >> N;
    for(int i=0; i<N-1; i++) {
        cin >> B[i];
    }
    solve();
}

Measured memory_bytes: 256
package main

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

func main() {
	n := getInt()
	ans := 0.0
	if n%2 == 0 {
		ans = 0.5
	} else {
		ans = float64((n+1)/2) / float64(n)
	}

	fmt.Println(ans)
}

// -----------------------------------------

var sc = bufio.NewScanner(os.Stdin)

func init() {
	// buf := 200001
	// sc.Buffer(make([]byte, buf), buf)
	sc.Split(bufio.ScanWords)
}

func getInt() int {
	i, err := strconv.Atoi(getString())
	if err != nil {
		panic(err)
	}
	return i
}

func getFloat() float64 {
	f, err := strconv.ParseFloat(getString(), 64)
	if err != nil {
		panic(err)
	}
	return f
}

func getString() string {
	sc.Scan()
	s := sc.Text()
	return s
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define M 500010

using namespace std;

int A[M], B[M], X[2][M], Y[2][M], ans = 0, n;

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &A[i]);
	for(int i = 1; i <= n; i++) scanf("%d", &B[i]);
	for(int i = 0; i < 29; i++) {
		int xcnt[2], ycnt[2];
		xcnt[0] = (xcnt[1] = (ycnt[0] = (ycnt[1] = 0)));
		for(int j = 1; j <= n; j++) X[!!(A[j] & (1 << i))][++xcnt[!!(A[j] & (1 << i))]] = A[j] & ((1 << i) - 1);
		for(int j = 1; j <= n; j++) Y[!!(B[j] & (1 << i))][++ycnt[!!(B[j] & (1 << i))]] = B[j] & ((1 << i) - 1);
		sort(X[0] + 1, X[0] + xcnt[0] + 1);
		sort(Y[0] + 1, Y[0] + ycnt[0] + 1);
		sort(X[1] + 1, X[1] + xcnt[1] + 1);
		sort(Y[1] + 1, Y[1] + ycnt[1] + 1);
		int flag = 0;
		for(int T1 = 0; T1 <= 1; T1++)
			for(int T2 = 0; T2 <= 1; T2++) {
				int t = ycnt[T2];
				for(int j = 1; j <= xcnt[T1]; j++) {
					while(t && X[T1][j] + Y[T2][t] >= (1 << i)) t--;
				flag ^= ((T1 + T2) & 1 ? t : ycnt[T2] - t);
				}
			}
		flag &= 1;
		ans += flag << i;
	}
	printf("%d\n", ans);
	return 0;
}

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

const int INF=1000000007;
int dp[1000010][2][2];

signed main()
{
	int n;
	cin>>n;
	dp[1][0][0]=8,dp[1][1][0]=dp[1][0][1]=1;
	for(int i=2;i<=n;i++){
		dp[i][0][0]=dp[i-1][0][0]*8 % INF;
		dp[i][1][0]=(dp[i-1][0][0]+dp[i-1][1][0]*9) % INF;
		dp[i][0][1]=(dp[i-1][0][0]+dp[i-1][0][1]*9) % INF;
		dp[i][1][1]=(dp[i-1][1][0]+dp[i-1][0][1]+dp[i-1][1][1]*10) % INF;
	}
	cout<<dp[n][1][1]<<"\n";
	return 0;
}

Measured memory_bytes: 34828
#include <stdio.h>

int main(){
    int n, i, j;
    scanf("%d", &n);
    int a[100];
    for (i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    for (j = n-1; j >= 0; j--){
        (j != 0) ? printf("%d ", a[j]) : printf("%d", a[j]);
    }
    printf("\n");
    return 0;
}

Measured memory_bytes: 600
n = int(input())
num = 26
arr = []
ans = ""
moji = "abcdefghijklmnopqrstuvwxyz"
flg = False

ar = []
n = n - 1
for i in range(10000):
    arr.append(n % num)
    n = n // num - 1
    if n < 0:
        break

arr.reverse()

ans = ""

for i in arr:
    ans +=moji[i]
print(ans)

Measured memory_bytes: 9192
#include<bits/stdc++.h>
using namespace std;
const int N = 16;
double x[N], y[N], z[N], d[1 << N], e[1 << N] = {1e15};
vector<int> c;
int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  for(int i = 0;i < n;i++)
    cin >> x[i] >> y[i] >> z[i];
  for(int i = 1;i < 1 << n;i++){
    c.clear();
    for(int j = 0;j < n;j++)
      if(i & (1 << j))
	c.push_back(j);
    bool o[N];
    fill(o, o + N, 0);
    priority_queue<pair<double, int>> q;
    q.push(make_pair(0, c[0]));
    while(!q.empty()){
      auto w = q.top();
      q.pop();
      if(o[w.second])
	continue;
      d[i] += w.first;
      o[w.second] = true;
      for(int s : c)
	if(!o[s])
	  q.push(make_pair(-hypot(x[w.second] - x[s], y[w.second] - y[s]), s));
    }
    for(int s : c)
      d[i] += z[s];
    d[i] /= c.size();
    for(int j = 1;j < 1 << c.size();j++){
      int t = 0;
      for(int k = 0;k < c.size();k++)
	if(j & (1 << k))
	  t += 1 << c[k];
      e[i] = max(e[i], min(d[t], e[i & (~t)]));
    }
  }
  cout << setprecision(12) << e[(1 << n) - 1] << endl;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep2(i, a, n) for(ll i = a; i < (ll)(n); i++)
#define memi cout << endl
#define kono(n) cout << fixed << setprecision(n)
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define hina cout << ' '
#define in(n) cin >> n
#define in2(n, m) cin >> n >> m
#define in3(n, m, l) cin >> n >> m >> l
#define out(n) cout << n
const ll mei = (ll)1e9 + 7;

int main(){
  string a, b;
  ll t;
  t = 0;
  in2(a, b);
  ll s = stoi(a + b);
  vector<ll> d(1000);
  rep(i, 1000)
    d[i] = i * i;
  rep(i, 1000){
    if(d[i] == s)
      t++;
  }
  if(t)
    out("Yes");
  else
    out("No");
  memi;
}

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

int main()
{
	int A[5];
	cin >> A[0] >> A[1] >> A[2] >> A[3] >> A[4];
	int ans = 0;
	int amari = 100;
	for (int i = 0; i < 5; i++)
	{
		if (A[i] % 10 == 0)
		{
			ans += A[i];
		}
		else
		{
			ans += (A[i] / 10) * 10 + 10;
			if (amari > (A[i] % 10))
			{
				amari = A[i] % 10;
			}
		}
	}

	if (amari != 100)
	{
		ans = ans - 10 + amari;
	}

	cout << ans;
	return 0;
	
}

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

int main(){
  string n;
  cin >> n;
  for(int i = 0; i < 3; i++){
    if(n.at(i) == '1') cout << 9;
    else cout << 1;
  }
  
  cout << endl;
  return 0;
}

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

using namespace std;


int main() {
  double a, b, h, m;
  cin >> a >> b >> h >> m;
  double time;
  time = 60 * h + m;
  cout << fixed << setprecision(40);
  double c;
  c = 11LL * time / 360LL;
  
  double d;
  d = a * a + b * b - 2 * a * b * cos(3.14159265358979323846264338327950288419716939937510 * c);
  double x = pow(d, 0.5);
  cout << x;
  return 0;
}

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

const int MAX_V = 1e3;
const int INF = 2e9;

int main(){
    int N, W; cin >> N >> W;
    vector<ll> w(N), v(N);
    for (int i = 0; i < N; i++)
    {
        cin >> w[i] >> v[i];
    }

    vector<ll> dp(MAX_V * N + 1); //dp[i] := 価値i以上にできる一番小さい重さ
    for (int i = 0; i < MAX_V * N + 1; i++)
    {
        dp[i] = INF;
    }
    
    dp[0] = 0;

    for (int i = 0; i < N; i++)
    {
        for (int j = MAX_V * N; j >= 0; j--)
        {
            if(j - v[i] >= 0 )dp[j] = min(dp[j], dp[j - v[i]] + w[i]);
        }
        
    }
    int ans = 0;
    for (int i = 0; i <= MAX_V * N; i++)
    {
        if(dp[i] <= W) ans = max(ans, i);
    }
    cout << ans << endl;
    
}

Measured memory_bytes: 1152
/**
 *    author        : Saurav Paul 
 *    created       : July 12, 2020 9:02 PM
 *    Problem Name  : A - Payment
 *    Problem Limit : 2000 ms , 1024 MB
 *    Problem Url   : https://atcoder.jp/contests/abc173/tasks/abc173_a
**/

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

int main(){
    ios_base::sync_with_stdio(false);
    long long x;
    cin >> x;
    x = x%1000;
    cout << (x?1000-x:0) << endl ;

    return 0 ;
}


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

typedef long long int ll; 
#define MOD 1000000007
#define ON 200000
#define rep(i,n) fp(i,0,n)  
#define fp(i,a,b) for(ll i=(a);i<(b);++i)
#define fn(i,a,b) for(ll i=(a);i>(b);i--)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define FF first
#define SS second
typedef pair<ll, ll> pll; 
typedef vector<pll> vpll;
typedef vector<ll> vll;
#define rs(t) string t;cin>>t
#define ri(t) int t;cin>>t
#define rll(t) long long int t;cin>>t
#define MK make_pair
#define PB push_back
#define PO pop_back
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
///// This part below is only for debug, not used /////
template<typename T> ostream &operator<<(ostream &os, const vector<T> &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const deque<T> &vec){ os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa){ os << "(" << pa.first << "," << pa.second << ")"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;
///// END /////

# define M_PI           3.14159265358979323846 

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  double r;
  cin >> r;

  cout << 2.0 * M_PI * r << endl;
  return 0;
  
}

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

#define ASC(vec) vec.begin(), vec.end()    // 昇順ソート 例：sort(ASC(vec));
#define DESC(vec) vec.rbegin(), vec.rend() // 降順ソート 例：sort(DESC(vec));
#define rep(i, n) for (int i = 0; i < (n); i++)
#define Rep(i, n) for (int i = 1; i < n; i++)
#define REP(i, vec) for (auto i = vec.begin(); i != vec.end(); ++i)

const int       mod = 1000000007;
const int       inf = (1 << 21);
const long long INF = 1LL << 60;

using ii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
using vd = vector<double>;
using vb = vector<bool>;
using vl = vector<ll>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvb = vector<vector<bool>>;
using vii = vector<pair<int, int>>;
using vll = vector<pair<ll, ll>>;

template<class T>
inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T>
inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T>
inline T GCD(T a, T b) { return b ? GCD(b, a % b) : a; }
template<class T>
inline T LCM(T a, T b) { return (a + (b - 1)) / b; }
template<class T>
inline T round_int(T a, T b) {return (a + (b - 1)) / b; }

constexpr array<int, 9> dx = { 0, 1, 0, -1, -1, 1, 1, -1, 0 };
constexpr array<int, 9> dy = { 1, 0, -1, 0, 1, 1, -1, -1, 0 };

// ──────────────────────────────────────────────────────────────────

bool cmp(const ii a, const ii b) {
	return a.second < b.second;
}

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

	vii p(m);
	rep(i, m) {
		cin >> p[i].first >> p[i].second;
	}

	sort(ASC(p), cmp);

	int res = 0;
	int end_time = 0;
	rep(i, m) {
		if (p[i].first >= end_time) {
			res++;
			end_time = p[i].second;
		}
	}
	cout << res << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const ll N = 1e2 + 5;

int n, k;
ll dp[N][5][2];
char s[N];

ll solveI()
{
    for(int i = n ; i >= 0 ; i--) dp[i][0][0] = dp[i][0][1] = 1;
    for(int i = n - 1 ; i >= 0 ; i--)
    {
        for(int j = 1 ; j <= k ; j++)
        {
            dp[i][j][1] = 9 * dp[i + 1][j - 1][1] + dp[i + 1][j][1];
            if(s[i] != '0') dp[i][j][0] = (s[i] - '1') * dp[i + 1][j - 1][1] + dp[i + 1][j - 1][0] + dp[i + 1][j][1];
            else dp[i][j][0] = dp[i + 1][j][0];
        }
    }
    return dp[0][k][0];
}

int main()
{
    scanf("%s%d", s, &k);
    n = strlen(s);
    printf("%lld\n", solveI());
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
  int no_of_input,operations;
  string input;
  cin >> no_of_input >> operations;
  cin >> input;
  int ans = 0;
  for(int i=0;i<no_of_input;){
    int pos = i;
    while(i<no_of_input&&input.at(i)==input.at(pos)){
      i++;
    }
    ans += i-pos-1;
  }
  cout << min(no_of_input-1,ans+operations*2);
}

Measured memory_bytes: 512
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <cmath>
using namespace std;

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

int w;
stack <int> st;

int main(){
	while(cin>>w){
		rep(i,10){
			if(w>=(int)pow(2.0,(double)9-i)){
				w-=(int)pow(2.0,(double)9-i);
				st.push((int)pow(2.0,(double)9-i));
			}
		}
		cout<<st.top();
		st.pop();
		while(!st.empty()){
			cout<<" "<<st.top();
			st.pop();
		}
		cout<<endl;
			
	}
	return 0;
	
}

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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define PI 3.14159265358979
#define MOD 1000000007 // = 10^9 + 7

using namespace std;
using ll = long long;


void solve()
{
	ll a, b, k;
	cin >> a >> b >> k;

	cout << max(0LL, a - k) << " " << max(0LL, b + min(0LL, (a - k)));
}

int main()
{
	fastio;
	solve();

	return 0;
}

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

int main() {
	int N, M;
	int a[100];
	int count[51];
	int loop;

	for (loop = 0; loop < 51; loop++)count[loop] = 0;
	cin >> N >> M;
	for (loop = 0; loop < 2 * M; loop++) {
		cin >> a[loop];
		count[a[loop]]++;
	}
	for (loop = 1; loop <= N; loop++)cout << count[loop] << "\n";
	return 0;
}

Measured memory_bytes: 256
N, M, C= map(int, input().split())
B = list(map(int, input().split()))
A = [0]*N
for n in range(N):
    A[n] = list(map(int, input().split()))
counter = 0    

for n in range(N):
    S = C
    for m in range(M):
        S += A[n][m]*B[m]
    if S > 0:
        counter += 1
        
print(counter)

Measured memory_bytes: 3064
def main
  n = gets.chomp.to_i
  n.times do
    mcxi1,mcxi2 = gets.chomp.split(' ').map{ |x| to_integer(x)}
    puts to_mcxi(mcxi1 + mcxi2)
  end
end

def to_integer mcxi
  integer = 0
  num = 1
  mcxi.each_char do |c|
    if c =~ /[2-9]/
      num = c.to_i
      next
    end

    integer += num * get_divisor(c)
    num = 1
  end
  integer
end

def to_mcxi integer
  mcxi = ''
  mcxi << get_mcxi(integer, 1000)
  mcxi << get_mcxi(integer % 1000, 100)
  mcxi << get_mcxi(integer % 100, 10)
  mcxi << get_mcxi(integer % 10, 1)
  mcxi
end

def get_mcxi integer, divisor
  mcxi = ''
  i = integer / divisor
  unless i == 0
    mcxi << i.to_s unless i == 1
    mcxi << get_unit(divisor)
  end
  mcxi
end

def get_unit integer
  case integer
  when 1000; 'm'
  when 100; 'c'
  when 10; 'x'
  when 1; 'i'
  end
end

def get_divisor unit
  case unit
  when 'm'; 1000
  when 'c'; 100
  when 'x'; 10
  when 'i'; 1
  end
end

main

Measured memory_bytes: 6148
# import math
# import itertools
# import numpy as np

def insertionSort(A, n, g, cnt):
  for i in range(g,n):
    v = A[i]
    j = i - g
    
    while j >= 0 and A[j] > v:
      A[j+g] = A[j]
      j = j - g   
      cnt += 1

    A[j+g] = v

  return [A, cnt]

def shellSort(A, n):
  cnt = 0

  # if n > 4:
  #   G = [4,1]
  # else:
  #   G = [1]

  G = [1]
  i = 1

  while G[0] + 3 ** i < n:
    G.insert(0, G[0] + 3 ** i)
    i += 1

  m = len(G)

  for i in range(m):
    A, cnt = insertionSort(A, n, G[i], cnt)

  return [m, G, A, cnt]

def main():
  n = int(input())
  A = [int(input()) for _ in range(n)]

  m, G, A, cnt = shellSort(A, n)

  print(m)
  print(*G)
  print(cnt)
  for num in A:
    print(num)

if __name__ == '__main__':
  main()


Measured memory_bytes: 45520
n, m = map(int, input().split())
l = [0] * n
ac, wa = 0, 0
for i in range(m):
    p, s = input().split()
    p = int(p)
    if l[p - 1] != -1 and s == "AC":
        ac += 1
        wa += l[p - 1]
        l[p - 1] = -1
    if l[p - 1] != -1 and s == "WA":
        l[p - 1] += 1
print(ac, wa)

Measured memory_bytes: 3828
#include <cstdio>


const int MAXN=1e5+10;
using ll=long long int;

struct Node{
    int lbound,rbound;
    ll diff;
    ll sum;
    Node *left,*right;
};

Node segtree[MAXN*2];
Node* next_pos=segtree;
int n,q;

Node* build(int left,int right){
    auto* cur=next_pos;
    next_pos++;
    cur->lbound=left;
    cur->rbound=right;

    cur->diff=0;
    

    int mid=(left+right)/2;

    //リーフノードのケース
    if (right-left==1) return cur;

    cur->left=build(left,mid);
    cur->right=build(mid,right);
    //総和を集計
    cur->sum=0;
    return cur;
}

//シングルノードの更新
void update(Node& self,ll d){
    self.diff+=d;
    self.sum+=d*(self.rbound-self.lbound);
}

void update(Node& self,int l,int r,int u){
    int mid=(self.lbound+self.rbound)/2;
    
    if (self.rbound-self.lbound!=1&&self.diff!=0){
        update(*self.left,self.diff);
        update(*self.right,self.diff);
        self.diff=0;
    }

    if (l==self.lbound&&r==self.rbound){
        update(self,u);
    }else if (l>=mid){
        update(*self.right,l,r,u);
        self.sum=self.left->sum+self.right->sum;
    }else if (r<=mid){
        update(*self.left,l,r,u);
        self.sum=self.left->sum+self.right->sum;
    }else{
        update(*self.left,l,mid,u);
        update(*self.right,mid,r,u);
        self.sum=self.left->sum+self.right->sum;
    }
}

//シングルポイント
int query(Node& self,int i){
    // puts("q");
    if (self.rbound-self.lbound==1&&self.lbound==i) return self.diff;
    int mid=(self.lbound+self.rbound)/2;
    if (i>=mid) return query(*self.right,i)+self.diff;
    else return query(*self.left,i)+self.diff;
}

//区間
ll query(Node& self,int l,int r){
    int mid=(self.lbound+self.rbound)/2;

    //更新があるノードの区間をプッシュボタン
    if (self.rbound-self.lbound!=1&&self.diff!=0){
        update(*self.left,self.lbound,mid,self.diff);
        update(*self.right,mid,self.rbound,self.diff);
        self.diff=0;
    }

    if (l==self.lbound&&r==self.rbound){
        return self.sum;
    }else if (l>=mid){
        return query(*self.right,l,r);
    }else if (r<=mid){
        return query(*self.left,l,r);
    }else{
        return query(*self.left,l,mid)+query(*self.right,mid,r);
    }
}

int main(){
    scanf("%d%d",&n,&q);
    build(1,n+1);
    for(int i=0;i<q;i++){
        int t;
        scanf("%d",&t);
        if (t==0){
            int s,t,x;
            scanf("%d%d%d",&s,&t,&x);
            update(segtree[0],s,t+1,x);
        }else{
            int l,r;
            scanf("%d%d",&l,&r);
            printf("%lld\n",query(segtree[0],l,r+1));
        }

    }
    return 0;
}


Measured memory_bytes: 10548
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=100005;
int n,l,r,a[N],b[N],c[N],ans;
 
signed main()
{
	cin>>n;
	for (int i=1;i<=n;++i)
		cin>>a[i];
	for (int i=1;i<=n;++i)
		cin>>b[i];
	for (int i=1;i<=n;++i)
		cin>>c[i];
	sort(a+1,a+1+n);
	sort(b+1,b+1+n);
	sort(c+1,c+1+n);
	l=0;
	r=1;
	for(int i=1;i<=n;++i)
	{
		for (;l<n&&a[l+1]<b[i];++l);
		for (;r<=n&&c[r]<=b[i];++r);
		ans+=l*(n-r+1);
	}
	cout<<ans;
	return 0;
}

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

int solve();

int main()
{
	printf("%d\n", solve());

	return 0;
}

int solve()
{
	int N;
	scanf("%d", &N);
	std::vector<int> d(100'001);
	for (int i{}; i < N; i++)
	{
		int tmp;
		scanf("%d", &tmp);
		d[tmp]++;
	}
	int count{};
	for (int i{1}; i <= 100'000; i++)
	{
		d[i] += d[i - 1];
		if (d[i] == N / 2)
			count++;
	}
	return count;
}

Measured memory_bytes: 640
/*The woods are lovely, dark and deep,
But I have promises to keep,
And miles to go before I sleep,
And miles to go before I sleep.*/

//PRABHJOT SINGH A.K.A. PRABHI
//~~~~~conquizztador~~~~~


#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define pb push_back
#define fi first
#define se second
#define MOD 1000000007
const int maxn= 100010;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string t;
    cin>>t;
    for(int i=0;i<t.length();++i)
    {
    	if(t[i]=='?')
    		t[i]='D';
    }
    cout<<t<<endl;
}

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

using namespace std;

#define f0r(a, b) for (long long a = 0; a < b; a++)
#define f1r(a, b, c) for (long long a = b; a < c; a++)
#define f0rd(a, b) for (long long a = b; a >= 0; a--)
#define f1rd(a, b, c) for (long long a = b; a >= c; a--)
#define ms(arr, v) memset(arr, v, sizeof(arr))
#define mp(a, b) make_pair(a, b)
#define pb push_back
#define f first
#define s second

#define ao(a, n) {for (int ele = 0; ele < n; ele++) { if (ele) cout << " "; cout << a[ele]; } cout << endl;}

typedef long long ll;
typedef double ld;
typedef long double lld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

const ll inf = 1e12;
const ll mod = 1e9 + 7;

typedef tuple<long long, int, int> ti;

ll d[55]; ll c[55];

ll dists[55][2505];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    ll n, m, s; cin >> n >> m >> s;

    vector<pair<ll, pair<ll, ll> > > graph[n+1];



    f0r(i, m) {
        ll u, v, a, b;

        cin >> u >> v >> a >> b;

        u--; v--;

        graph[u].pb(mp(v, mp(a, b)));
        graph[v].pb(mp(u, mp(a, b)));
    }

    f0r(i, n) {
        cin >> c[i] >> d[i];
    }

    ms(dists, 127);

    priority_queue<ti, vector<ti>, greater<ti>> pq;

    dists[0][min(s, 2500LL)] = 0;

    pq.emplace(0, 0, min(s, 2500LL));

    while(!pq.empty()) {
        auto [di, u, amt] = pq.top();

        pq.pop();

        if (di > dists[u][amt])
            continue;

        if (di + d[u] < dists[u][min(amt + c[u], 2500LL)]) {
            dists[u][min(amt + c[u], 2500LL)] = di + d[u];
            pq.emplace(dists[u][min(amt + c[u], 2500LL)], u, min(amt + c[u], 2500LL));
        }

        for (auto x: graph[u]) {
            ll a = x.s.f;
            ll b = x.s.s;
            ll v = x.f;


            if (amt >= a && di + b < dists[v][amt - a]) {
                dists[v][amt - a] = di + b;
                pq.emplace(dists[v][amt - a], v, amt - a);
            }
        }
    }

    for (int i=1; i<n; i++)
        cout << *min_element(dists[i], dists[i] + 2505) << endl;


}




Measured memory_bytes: 6312
#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int main()
{
  int N, M; cin >> N >> M;
  vector<int> hist(M + 1);
  for (int i = 0; i < N; i++) {
    int K; cin >> K;
    for (int j = 0; j < K; j++) {
      int A; cin >> A;
      hist[A]++;
    }
  }
  int ans = accumulate(hist.begin(), hist.end(), 0, [&](int acc, int i) {
      return acc + (i == N);
      });
  cout << ans << endl;

  return 0;
}

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

using namespace std;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vd = vector<double>;
using vs = vector<string>;
using vvvd = vector<vector<vd>>;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    vd dpr1(N+1, 0.);
    vector<vd> dpr2(N+1, dpr1);
    vvvd dp(N+1, dpr2);

    for(int b3=0;b3<=N;b3++) {
        for(int b2=0;(b3+b2)<=N;b2++) {
            for(int b1=0;(b3+b2+b1)<=N;b1++) {
                int S = (b3 + b2 + b1);
                if (S == 0) continue;
                dp[b1][b2][b3] = N;
                if (b1 > 0) dp[b1][b2][b3] += b1*dp[b1-1][b2][b3];
                if (b2 > 0) dp[b1][b2][b3] += b2*dp[b1+1][b2-1][b3];
                if (b3 > 0) dp[b1][b2][b3] += b3*dp[b1][b2+1][b3-1];
                dp[b1][b2][b3] /= S;
            }
        }
    }

    vi c(3, 0);
    for(int i=0;i<N;i++){
        int a;
        cin >> a;
        c[a-1]++;
    }
    // cout << c[0] << " " << c[1] << " " << c[2] << endl;

    cout << setprecision(18);
    cout << dp[c[0]][c[1]][c[2]] << endl;
    


    return 0;
}

Measured memory_bytes: 216832
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();

		sc.close();

		int divisor = 0;

		for (; a <=b; a++) {
			if (c%a == 0) divisor++;
		}
		System.out.println(divisor);
	}
}



Measured memory_bytes: 26404
#include<algorithm>
#include<cstring>
#include<cctype>
#include<cstdio>
#include<set>
#define rep(i,x,y) for(int i=x; i<=y; ++i)
#define repd(i,x,y) for(int i=x; i>=y; --i)
#define mid (l+r>>1)

using namespace std;
typedef long long LL;
const int mod=1000003;
int q;
LL x,d,n;
LL flv[mod],inv[mod];

LL getmi(LL a,LL x)
{
	LL rt=1;
	while(x)
	{
		if(x&1) rt=rt*a%mod;
		a=a*a%mod,x>>=1;
	}
	return rt;
}

int main()
{
	flv[0]=1;
	rep(i,1,mod-1) flv[i]=flv[i-1]*i%mod,inv[i]=getmi(flv[i],mod-2);
	scanf("%d",&q);
	while(q--)
	{
		scanf("%lld%lld%lld",&x,&d,&n);
		if(x==0) puts("0");
		else if(d==0) printf("%lld\n",getmi(x,n));
		else
		{
			x=x*getmi(d,mod-2)%mod;
			if(x+n-1>=mod) puts("0");
			else
				printf("%lld\n",flv[x+n-1]*inv[x-1]%mod*getmi(d,n)%mod);
		}
	}
	return 0;
}

Measured memory_bytes: 16384
package main

import "bufio"
import "fmt"
import "os"

func main() {
    // input
    var reader = bufio.NewReaderSize(os.Stdin, 10000000)
    var s, _, _ = reader.ReadLine()
    var t, _, _ = reader.ReadLine()

    // solve
    var next = make([][26]int, len(s) + 1)
    for c := 0; c < 26; c ++ {
        next[len(s)][c] = len(s)
    }
    for i := len(s) - 1; i >= 0; i -- {
        next[i] = next[i + 1]
        next[i][int(s[i] - 'a')] = i
    }

    var k = 0
    for _, c := range t {
        if next[0][int(c - 'a')] == len(s) {
            k = -1
            break
        }
retry:
        var i = k % len(s)
        k += next[i][int(c - 'a')] - i
        if next[i][int(c - 'a')] < len(s) {
            k += 1
        } else {
            goto retry
        }
    }

    // output
    var writer = bufio.NewWriter(os.Stdout)
    defer writer.Flush()
    fmt.Fprintln(writer, k)
}


Measured memory_bytes: 24320
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <regex>
#define ull unsigned long long
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,j,n) for(int i = j; i < n; i++)
#define RFOR(i,j,n) for(int i = j-1; i >= n; i--)
#define PREC(n) fixed << setprecision(n)
#define print_array(v) REP(__k, v.size()) { cout << v[__k]; if(__k != v.size()-1) cout << " "; else cout << endl; }
using namespace std;

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

	int N;
	cin >> N;
	vector<int> a(N);
	REP(i, N) cin >> a.at(i);
	vector<int> b(a);
	sort(b.begin(), b.end());
	int diff = 0;
	REP(i, N) diff += a.at(i) == b.at(i);
	int Q;
	cin >> Q;
	REP(q, Q) {
		if(diff == N) {
			cout << q << endl;
			return 0;
		}
		int x, y;
		cin >> x >> y;
		x--, y--;
		diff -= (a.at(x) == b.at(x));
		diff -= (a.at(y) == b.at(y));
		swap(a.at(x), a.at(y));
		diff += (a.at(x) == b.at(x));
		diff += (a.at(y) == b.at(y));
	}
	cout << (diff == N ? Q : -1) << endl;
}


Measured memory_bytes: 5176
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char[] x = sc.next().toCharArray();
		int N = x.length;
		
		int t=0,s=0;
		for(int i=0; i<N; i++) {
			if(x[i]=='T') {
				if(s>0) {
					s--;
				} else {
					t++;
				}
			} else {
				s++;
			}
		}
		
		System.out.println(t+s);
		sc.close();
	}
}


Measured memory_bytes: 14980
#include <iostream>
#include <vector>
using namespace std;
 
int main() {
  int n;
  cin >> n;
  if (n == 0) {
    cout << 0;
    return 0;
  }
  vector<int> h(n);
  vector<int> cost(n);
  for (int i = 0; i < n; ++i) {
    cin >> h[i];
  }
  for (int i = 0; i < n; ++i) {
    if (i == 0)
      cost[i] = 0;
    else if (i == 1) {
      cost[i] = abs(h[i] - h[i-1]);
    }
    else {
      int c1 = abs(h[i] - h[i - 1]) + cost[i - 1];
      int c2 = abs(h[i] - h[i - 2]) + cost[i - 2];
      cost[i] = min(c1, c2);
    }
  }
  cout << cost[n - 1];
}

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

int main() {
  const int M = 10000;

  int N, K;
  cin >> N >> K;
  vector<int> plan(N + 1, 0);
  for(int i = 1; i <= K; ++i) {
    int A, B;
    cin >> A >> B;
    plan[A] = B;
  }

  int dp[101][4][2] = {};
  dp[0][0][0] = 1;
  for(int i = 0; i < N; ++i) for(int j = 0; j <= 3;  ++j) for(int k = 0; k < 2; ++k) {
    if(plan[i + 1]) {
      if(j == plan[i + 1]) {
        if(k == 0) dp[i + 1][plan[i + 1]][1] = (dp[i + 1][plan[i + 1]][1] + dp[i][j][k]) % M;
      } else {
        dp[i + 1][plan[i + 1]][0] = (dp[i + 1][plan[i + 1]][0] + dp[i][j][k]) % M;
      }
    } else {
      for(int nj = 1; nj <= 3; ++nj) {
        if(k == 1 && j == nj) continue;
        if(j == nj) {
          dp[i + 1][nj][1] = (dp[i + 1][nj][1] + dp[i][j][k]) % M;
        } else {
          dp[i + 1][nj][0] = (dp[i + 1][nj][0] + dp[i][j][k]) % M;
        }
      }
    }
  }

  int ans = 0;
  for(int j = 0; j <= 3; ++j) for(int k = 0; k < 2; ++k) ans = (ans + dp[N][j][k]) % M;
  cout << ans << endl;
}

Measured memory_bytes: 3124
#include<stdio.h>
#include<math.h>
long gcd2(long a, long b){
	char g = 0;
	while(a){
		if((a&1) && (b&1)){
			if(a<b){
				b = (b-a)>>1;
			}else{
				a = (a-b)>>1;
			}
		}else if(a&1){
			b >>= 1;
		}else if(b&1){
			a >>= 1;
		}else{
			a >>= 1;
			b >>= 1;
			g++;
		}
	}
	return b<<g;
}

long a, b;
int i;
int f;
int main(void){
	scanf("%ld%ld", &a, &b);
	a = gcd2(a, b);
	for(i=2; i<=sqrt(a); i++){
		if(a%i==0){
			f++;
			a/=i;
			while(a%i==0){
				a/=i;
			}
		}
	}
	if(a==1){
		printf("%d\n", f+1);
	}else{
		printf("%d\n", f+2);
	}
}


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

using namespace std;

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

typedef long long ll;

const int Inf = 1e9;
const double EPS = 1e-9;

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

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

int bitCount(long bits) {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll x;
    cin >> x;
    ll t = x / 11;
    x %= 11;
    if (x >= 7) {
      cout << t * 2 + 2 << endl;
    } else if (x >= 1) {
      cout << t * 2 + 1 << endl;
    } else {
      cout << t * 2 << endl;
    }

    return 0;
}


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


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    string slowo;
    cin >> slowo;
    int a=slowo[0]-48,b=slowo[1]-48,c=slowo[2]-48,d=slowo[3]-48;
    if(a + b + c + d == 7){
        cout <<a<<"+"<<b<<"+"<<c<<"+"<<d<<"=7";
        return 0;
    }
    if(a + b + c - d == 7){
        cout <<a<<"+"<<b<<"+"<<c<<"-"<<d<<"=7";
        return 0;
    }
    if(a + b - c - d == 7){
        cout <<a<<"+"<<b<<"-"<<c<<"-"<<d<<"=7";
        return 0;
    }
    if(a - b - c - d == 7){
        cout <<a<<"-"<<b<<"-"<<c<<"-"<<d<<"=7";
        return 0;
    }
    if(a - b + c + d == 7){
        cout <<a<<"-"<<b<<"+"<<c<<"+"<<d<<"=7";
        return 0;
    }
    if(a - b - c + d == 7){
        cout <<a<<"-"<<b<<"-"<<c<<"+"<<d<<"=7";
        return 0;
    }
    if(a - b + c - d == 7){
        cout <<a<<"-"<<b<<"+"<<c<<"-"<<d<<"=7";
        return 0;
    }
    if(a + b - c + d == 7){
        cout <<a<<"+"<<b<<"-"<<c<<"+"<<d<<"=7";
        return 0;
    }

}


Measured memory_bytes: 256
In = list(map(int, list(input())))

import itertools
Bit = list(itertools.product(['+', '-'], repeat=3))

for l in Bit:
    seven = In[0]
    for i, bit in enumerate(l):
        if bit == '+':
            seven += In[i+1]
        else:
            seven -= In[i+1]
    if seven == 7:
        print("{}{}{}{}{}{}{}=7".format(In[0],l[0],In[1],l[1],In[2],l[2],In[3]))
        break

Measured memory_bytes: 3064
N = gets.to_i
h_list = gets.split.map(&:to_i)
INF = 2 << 60
dp = Array.new(N + 10) { INF }
dp[0] = 0
(N - 1).times do |i|
  dp[i + 1] = [
    dp[i + 1],
    dp[i] + (h_list[i] - h_list[i + 1]).abs
  ].min
  dp[i + 2] = [
    dp[i + 2],
    dp[i] + (h_list[i] - h_list[i + 2]).abs
  ].min if i + 2 < N
end
puts dp[N - 1]


Measured memory_bytes: 11404
# -*- coding: utf-8 -*-
H, W = map(int, input().split(' '))
table = [list(map(int, input().split(' '))) for _ in range(H)]

def get_next():
    for h in range(H):
        if h % 2:
            for w in range(W-1, -1, -1):
                yield h, w
        else:
            for w in range(W):
                yield h, w


ret = []
routes = list(get_next())
prv_h, prv_w = routes[0]
for h, w in routes[1:]:
    if table[prv_h][prv_w] % 2:
        ret.append((prv_h, prv_w, h, w))
        table[h][w] += 1

    prv_h, prv_w = h, w


print(len(ret))
for prv_h, prv_w, h, w in ret:
    print(prv_h + 1, prv_w + 1, h + 1, w + 1)






Measured memory_bytes: 85544
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <set>
using namespace std;

int main() {
	int n;
	cin >> n;
	set<int> a;
	for (int i = 0; i < n; ++i) {
		int ai;
		cin >> ai;
		auto ite = a.find(ai);
		if (ite == a.end()) {
			a.insert(ai);
		}
		else {
			a.erase(ite);
		}
	}
	cout << a.size() << endl;
}


Measured memory_bytes: 4864
N, W = map(int, input().split())
d = []
S = 0
for i in range(N):
    w, v = map(int, input().split())
    d.append((w, v))
    S += v
INF = float('inf')
dp = [[INF] * (S + 1) for i in range(N + 1)]
dp[0][0] = 0
for i in range(1, N + 1):
    for j in range(S + 1):
        w, v = d[i - 1]
        dp[i][j] = min(dp[i][j], dp[i - 1][j])
        if j + v <= S:
            dp[i][j + v] = min(dp[i][j + v], dp[i - 1][j] + w)

for i in range(S, -1, -1):
    if dp[N][i] <= W:
        print(i)
        exit()


Measured memory_bytes: 311312
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops") 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#define int long long
#define fr(i,a,b) for(int i = a ; i <= b ; ++i)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define pb push_back
#define fst first
#define snd second
using namespace __gnu_pbds;
using ordered_set =
 tree<int, null_type,less<int>,
 rb_tree_tag,tree_order_statistics_node_update>;
//find_by_order(k):returns iterator to kth element starting from 0
//order_of_key(k):returns count of elements strictly smaller than k
typedef long long ll;typedef pair<int, int> pii;
typedef vector<int> vi;typedef long double ld;
template<class T>
using min_heap = priority_queue<T,vector<T>,greater<T>>; 
template<typename T> T gcd(T a, T b){return(b?__gcd(a,b):a);}
template<typename T> T lcm(T a, T b){return(a*(b/gcd(a,b)));}
template<typename T> 
void remdup(vector<T>& v) {
	sort(all(v)); v.erase(unique(all(v)), v.end());
}
template<typename T> void re(vector<T> &v) {trav(i,v) cin >> i;}
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
#ifdef np
#include "C:\Users\navodit\Desktop\mycodes\pr.h"
#else
#define trace(...)
#endif

#define MOD 1e18  



const int  N = 2e5+5;
int dp[N+1][5];
void solve(){
	int n; 
	cin >> n ; 
	int side = (n%2)+1;
	vi v(n);
	re(v);
	fr(i,0,n){
		fr(j,0 ,side){
			dp[i][j] = -1*MOD;
		}
	}
	dp[0][0]=0;

	int ans = 0 ;
	fr(i,0,n-1){
		fr(j,0,side){
			dp[i+1][j+1] = max(dp[i][j],dp[i+1][j+1]);
			int cur = dp[i][j];
			if((i+j)%2==0)cur+=v[i];
			dp[i+1][j] = max(cur,dp[i+1][j]);
		}
	}
	cout << dp[n][side] << endl;
}

signed main() {
	unsyncIO();
	int tt =1 ;
	// cin >> tt;
	rep(i,0,tt) solve();













#ifdef np
	cout <<endl<<endl<< "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}


Measured memory_bytes: 12680