akhauriyash/Code-Regression huggingface dataset:
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{BinaryHeap, HashMap};

#[allow(dead_code)]
type Graph = Vec<Vec<usize>>;

fn main() {
    input! {
        n: usize,
        a: [i64; n],
    }
    let mut aa = a
        .iter()
        .enumerate()
        .map(|(i, &v)| (v, i + 1))
        .collect::<Vec<(i64, usize)>>();
    aa.sort_by_key(|x| x.0.abs());
    aa.reverse();
    println!("{}", 2 * n);
    if aa[0].0 >= 0 {
        println!("{} {}", aa[0].1, 1);
        println!("{} {}", aa[0].1, 1);
        for i in 1..n {
            println!("{} {}", i, i + 1);
            println!("{} {}", i, i + 1);
        }
    } else {
        println!("{} {}", aa[0].1, n);
        println!("{} {}", aa[0].1, n);
        for i in (2..n + 1).rev() {
            println!("{} {}", i, i - 1);
            println!("{} {}", i, i - 1);
        }
    }
}


Measured memory_bytes: 4352
import java.util.*;
 
public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
      	String x = sc.next();
      	String y = sc.next();
		Map<String, Integer> map = new HashMap<>();
      	map.put("A", 10);
      	map.put("B", 11);
      	map.put("C", 12);
      	map.put("D", 13);
      	map.put("E", 14);
      	map.put("F", 15);
      	
      	if(map.get(x) < map.get(y)) {
        	System.out.println("<");  
        } else if(map.get(x) > map.get(y)) {
        	System.out.println(">");  
        } else {
         	System.out.println("=");
        }
    }
}

Measured memory_bytes: 22996
N = int(input())
A = list(map(int, input().split()))  # N+1体のモンスター
B = list(map(int, input().split()))  # N人の勇者

before_A = sum(A)
# 一つ目の街の処理を先に行う
if A[0] >= B[0]:  # モンスターの数の多いなら
    A[0] -= B[0]
    B[0] = 0
else:  # 勇者のキャパシティの方が大きいなら
    B[0] -= A[0]
    A[0] = 0

# i番目の街について処理を行なっていく
for i in range(1, N):
    if B[i-1] > 0:  # まだ以前の勇者にキャパが残ってるなら
        tmp = min(A[i], B[i-1])
        A[i] -= tmp
        B[i-1] -= tmp

    if A[i] > 0:  # まだi番目の街にモンスターが残っているならば
        tmp = min(A[i], B[i])
        A[i] -= tmp
        B[i] -= tmp

if (A[-1] > 0) & (B[-1] > 0):
    tmp = min(A[-1], B[-1])
    A[-1] -= tmp
    B[-1] -= tmp

after_A = sum(A)
# 
# print(A)
# print(B)

print(before_A - after_A)


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

typedef long long ll;
typedef long double ld;


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	
	int n;
	cin>>n;
	int ara[n];
	for(int i=0;i<n;i++) cin>>ara[i];
	
	int cnt=0;
	
	for(int i=1;i<n-1;i++)
	{
		if((ara[i]>ara[i-1] && ara[i]<ara[i+1]) || (ara[i]<ara[i-1] && ara[i]>ara[i+1])) cnt++;
	}
	
	cout<<cnt;
	
	
			
	return 0;
}



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

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        if (sc.nextInt() == 1) {
            System.out.println("Hello World");

        } else {
            System.out.println(sc.nextInt() + sc.nextInt());
        }
    }

}


Measured memory_bytes: 21716
from itertools import combinations_with_replacement as cbr
N,M,Q = list(map(int, input().split()))
X = []
for _ in range(Q):
  X.append(list(map(int, input().split())))
  
ans = -1
for p in cbr(range(1,M+1), N):
  wk = 0
  for x in X:
    a,b,c,d = x
    if p[b-1] - p[a-1] == c:
      wk += d
  ans = max(wk,ans)
  
print(ans)

Measured memory_bytes: 68032
#include <bits/stdc++.h>
 
using namespace std;
 
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(), a.end()
#define rep(i, st, n) for (int i = (st); i < (n); ++i)
#define debug(x) std::cout << #x << ": " << x << endl
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
 
template <typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; }
template <typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; }

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
#ifdef DEBUG
    freopen("in", "r", stdin);
#endif

    int N, V, P;
    ll M;
    cin >> N >> M >> V >> P;
    vector<ll> A(N);
    for (auto &x : A) cin >> x;
    sort(all(A));
    reverse(all(A));

    auto valid = [&](int k)
    {
        if (k < P)
            return true;
        if (A[k] + M < A[P - 1])
            return false;
        ll sum = 0;
        for (int i = 0; i < P - 1; ++i)
            sum += M;
        for (int i = k; i < N; ++i)
            sum += M;
        for (int i = P - 1; i < k; ++i)
            sum += min(M, A[k] + M - A[i]);
        if (sum < M * V)
            return false;
        return true;
    };

    ll vl = -1;
    ll vr = N;
    while (vr - vl > 1)
    {
        int k = (vl + vr) / 2;
        if (valid(k))
            vl = k;
        else
            vr = k;
    }
    cout << vl + 1 << '\n';

    return 0;
}




Measured memory_bytes: 1024
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
typedef long long ll;
const ll longinf=1LL<<60;
using namespace std;

int n,k;
int a[200000];
int t;
char c;

int main()
{
    int ans=0;
    cin>>n>>k;
    for (int i=1; i<=n; ++i)
    {
        cin>>c;
        if (c=='L')
        {
            if (t>0 && a[t]==0) ans++;
            else
            {
                t++;
                a[t]=0;
            }
        }
        else if (c=='R')
        {
            if (t>0 && a[t]==1) ans++;
            else
            {
                t++;
                a[t]=1;
            }
        }
    }
    if (t%2==0)
    {
        int two = t/2-1;
        int one = 1;
        if (two>=k) ans += k*2;
        else ans += two*2+1;
    }else
    {
        int two = t/2;
        int one = 0;
        if (two>=k) ans += k*2;
        else ans += two*2;
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int L,R,d;
  cin >> L >> R >> d;
  
  int counter=0;
  for(int i=L;i<=R;i++){
    if(i%d==0){
      counter++;
    }
  }
  
  cout << counter << endl;
}

Measured memory_bytes: 3612
#include <cstdio>
#include <vector>

typedef long long LL;
const int Mod = 1000000007;
const int MN = 5005;

inline int qPow(int b, int e) {
	int a = 1;
	for (; e; e >>= 1, b = (LL)b * b % Mod)
		if (e & 1) a = (LL)a * b % Mod;
	return a;
}

int N, M, A[MN], Fac[MN];
std::vector<int> G[MN];
int K, B[MN];

int vis[MN];
void DFS(int u) {
	++B[K], vis[u] = 1;
	for (int v : G[u]) DFS(v);
}
void DFS2(int u, int o) {
	vis[u] = 1;
	for (int v : G[u])
		if (!vis[v]) DFS2(v, o);
		else if (v == o) ++M;
}

int dp[MN][MN];

int main() {
	scanf("%d", &N), Fac[0] = 1;
	for (int i = 1; i <= N; ++i) scanf("%d", &A[i]), Fac[i] = (LL)Fac[i - 1] * i % Mod;
	for (int i = 1; i <= N; ++i) if (~A[i]) G[A[i]].push_back(i);
	for (int i = 1; i <= N; ++i) if (!~A[i]) ++K, DFS(i);
	for (int i = 1; i <= N; ++i) if (!vis[i]) DFS2(i, i);
	dp[0][0] = 1;
	for (int i = 1; i <= K; ++i) {
		dp[i][0] = 1;
		for (int j = 1; j <= i; ++j)
			dp[i][j] = (dp[i - 1][j] + (LL)dp[i - 1][j - 1] * B[i]) % Mod;
	}
	dp[K][1] -= K;
	int Ans = (LL)M * qPow(N - 1, K) % Mod;
	for (int j = 1; j <= K; ++j) Ans = (Ans + (LL)dp[K][j] * Fac[j - 1] % Mod * qPow(N - 1, K - j)) % Mod;
	Ans = ((LL)N * qPow(N - 1, K) % Mod - Ans + Mod) % Mod;
	printf("%d\n", Ans);
	return 0;
}

Measured memory_bytes: 70192
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma warning(disable : 4996)
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<time.h>
#include<random>
#include<array>


using namespace std;

#define REP(i, n) for(int i = 0;i < (n);++i)
#define REPR(i, n) for(int i = n-1;i >= 0;--i)
#define FOR(i, m, n) for(int i = m;i < n;++i)
#define FORR(i, m, n) for(int i = m-1;i >= n;--i)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define print(x) cout<<(x)<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define lb(v,n) lower_bound(v.begin(), v.end(), (n))
#define ub(v,n) upper_bound(v.begin(), v.end(), (n))
#define int long long
//#define double long double
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i,v.size())cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
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; }
typedef pair<int, int>P;
std::random_device rd;
std::mt19937 mt(rd());
constexpr int MOD = 1e9 + 7; constexpr int MAX = 200020;
const double pi = acos(-1); constexpr double EPS = 1e-8;
constexpr ll INF = 1e16;
typedef array<int, 3>arr3;
void die(string s) { cout << s << endl; exit(0); }
int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };

void solve() {
	string S; cin >> S;
	int K; cin >> K;
	int N = S.size();
	REP(i, N-1) {
		int num = S[i] - 'a';
		int need = 26-num;
		if (S[i] == 'a')need = 0;
		if (K >= need) {
			K -= need;
			S[i] = 'a';
		}
	}
	K %= 26;
	int num = S[N - 1] - 'a';
	num = (num + K) % 26;
	S[N-1] = (char)('a'+num);
	print(S);
}


signed main() {
	solve();
}



Measured memory_bytes: 512
#include<bits/stdc++.h>
long long int dp[100001][100]={};
bool tf[100001][100]={};
long int dpcalc(long int v,int i,long int a[][2],long int n)
{
    if(v<=0)
    return 0;
    if(i==n)
     return 100000000001;
    if(tf[v][i])
    return dp[v][i];
    tf[v][i]=1;
    dp[v][i]=std::min(dpcalc(v,i+1,a,n),dpcalc(v-a[i][1],i+1,a,n)+a[i][0]);
    return dp[v][i];
   }
 

long int knapsack(long int a[][2],long int n,long int w)
{for(long int v=100001;v>=0;v--)
 {long long int ans=dpcalc(v,0,a,n);
  if(ans<=w)
    return v;
   }
 return 0;
  
}


  
int main()
{long int n,w;
 std::cin>>n>>w;
 long int a[n][2];
 for(int i=0;i<n;i++)
 std::cin>>a[i][0]>>a[i][1];
 std::cout<<knapsack(a,n,w);
 return 0;

}

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


//      DEEP


using namespace std;
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define fwd(i,a,n) for(int i=a;i<=n;i++)
#define bak(i,a,n) for(int i=a;i>=n;i--)
#define all(v) v.begin(),v.end()
#define pb push_back

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<int,int> pi;
typedef set<int> si;
const ll mod = 1e9 + 7;
ull power(ull x,ull y){
   if(y==0) return 1;
   else{
     if(y%2==0) return power(x*x,y/2);
     else return x*power(x*x,(y-1)/2);
   }
}
ull gcd(ull x,ull y){
   if(y==0)return x;
   return gcd(y,x%y);
}
int main(){
    boost;
    int TESTS=1;
    //cin>>TESTS;
    while(TESTS--){
        ll n,k;
      cin>>n>>k;
      if(n==k || k==1)cout<<0<<endl;
      else{
          n=n%k;
          if(k-n<n)cout<<k-n<<endl;
          else cout<<n<<endl;
      }
    }
}
/* Be careful about integer ranges;
   Check the corner cases before submitting.
*/




Measured memory_bytes: 3616
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <bitset>
#include <vector>
#include <queue>
#include <map>
#include <set>

#define i64 int64_t
#define ff(ii,nn,mm) for(int ii=nn;ii<mm;ii++)
#define st(vvv) sort(vvv.begin(),vvv.end())
#define rvs(vvv) reverse(vvv.begin(),vvv.end())
int inf = 1000000007;

using namespace std;

int main() {
	int n;
	cin >> n;
	int lowest = 100;
	int sum = 0;
	ff(i, 0, n) {
		int a;
		cin >> a;
		if (a % 10 != 0) {
			lowest = min(lowest, a);
		}
		sum += a;
	}
	if (lowest == 100) lowest = sum;
	if(sum%10!=0) lowest = 0;
	cout << sum - lowest << endl;
	return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	result := 0.0
	var times int
	fmt.Scan(&times)
	for i := 0; i < times; i++ {
		var price float64
		var kind string
		fmt.Scan(&price)
		fmt.Scan(&kind)
		if kind == "BTC" {
			price *= 380000.0
		}
		result += price
	}
	fmt.Println(result)

}

Measured memory_bytes: 512
W = input()
w = len(W)

TLIST = []
while True:
    T = input()
    
    if T=='END_OF_TEXT':
        break
    
    T = T.lower()
    Tlist = T.split(' ')
    TLIST.append(Tlist)

TLISTl = len(TLIST)

count = 0
for i in range(TLISTl):
    text = TLIST[i]
    textl = len(text)
    for k in range(textl):
        if text[k]==W :
            count += 1

print(count)


Measured memory_bytes: 5560
#include <iostream>
using namespace std;
int main(void)
{
	int N, A[100], key, i, j, k;
	cin >> N;
	for (i = 0; i < N; i++)
		cin >> A[i];
	for (i = 0; i < N; i++)
	{
		cout << A[i];
		if (i < N-1)
			cout << " ";
		else
			cout << endl;
	}
	for (j = 1; j < N; j++)
	{
		key = A[j];
		i = j-1;
		while (i >= 0 && A[i] > key)
		{
			A[i+1] = A[i];
			i--;
		}
		A[i+1] = key;
		for (k = 0; k < N; k++)
		{
			cout << A[k];
			if (k < N-1)
				cout << " ";
			else
				cout << endl;
		}
	}
	return 0;
}

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

//型定義
typedef long long ll;

//定数
const ll INF=1e+18;
const int MOD=1e+9+7;

//REPマクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REP2(i,a,b) for(ll i=a;i<(ll)(b);i++)
#define REPD2(i,a,b) for(ll i=a;i>(ll)(b);i--)

//vectorの扱い
#define ALL(x) (x).begin(),(x).end() //sortなどの引数省略
#define SIZE(x) ((ll)(x).size()) //size
#define MAX(x) *max_element(ALL(x)) //最大値
#define MIN(x) *min_element(ALL(x)) //最小値

//グローバル変数


//ライブラリ挿入


int main(){
    int N;
    cin >> N;
    int a,b;
    ll c;
    vector<vector<pair<int,ll>>> G(N);
    REP(i,N-1){
        cin >> a >> b >>c;
        a--;
        b--;
        G[a].push_back(make_pair(b,c));
        G[b].push_back(make_pair(a,c));
    }
    int Q,K;
    cin >> Q >> K;

    vector<int> x(Q),y(Q);
    int tmp1,tmp2;
    REP(i,Q){
        cin >> tmp1>>tmp2;
        x[i]=tmp1-1;
        y[i]=tmp2-1;
    }

    //ダイクストラ O(ElogV)
    // データ構造
    vector<ll> dist(N, INF); // 全頂点を「未訪問」に初期化
    priority_queue<int> que;

    // 初期条件 (頂点 0 を初期ノードとする)
    dist[K-1] = 0;
    que.push(K-1); // 0 を橙色頂点にする

    // 開始 (キューが空になるまで探索を行う)
    while (!que.empty()) {
        int v = que.top(); // 優先度キューから先頭頂点を取り出す
        que.pop();

        // v から辿れる頂点をすべて調べる
        for (auto itr=G[v].begin();itr!=G[v].end();itr++) {
            // 新たな頂点 nv について距離が短いなら更新
            int nv=itr->first;
            ll cost =itr->second;
            if(dist[v]+cost<dist[nv]){
                dist[nv] = dist[v] + cost;
                que.push(nv);
            }
        }
    }

    
    
    REP(i,Q){
        cout << dist[x[i]]+dist[y[i]] << endl;
    }
    
}

Measured memory_bytes: 10864
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
int main()

{
  int a,b,c,x,y,z,n;
  cin>>a>>b>>c;
  x=a*100;
  y=b*10;
  z=c*1;
   n=x+y+z;

   if(n%4==0)
   cout<<"YES"<<endl;
   else
   cout<<"NO"<<endl;

 return 0;
}








Measured memory_bytes: 3552
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define endl '\n'
#define eps 0.000000001
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define IO ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
const int INF=0x3f3f3f3f;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
const int maxn=1e5+5;
int main(){
	string s,t;cin>>s>>t;
	int len=s.length();
	ll cnt=0;
	rep(i,0,len-1){
		if(s[i]!=t[i]) ++cnt;
	}
	cout<<cnt<<endl;
}


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

int main() {
  int64_t N, A, B;
  cin >> N >> A >> B;
  
  if ( A%2 == B%2 ){
    cout << (B-A)/2 << endl; 
  }
  else {
    cout << min ( (A+B-1)/2 , (2*N-A-B+1)/2 ) << endl;
  }
}


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

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

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;

int main(void) {
  int m, f, r, mf;
  char result;
  while(1) {
    cin >> m >> f >> r;
    if(m + f + r == -3) break;

    mf = m + f;

    string result;
    if(m * f < 0) {
      result = 'F';
    }else if(mf >= 80) {
      result = 'A';
    }else if(mf >= 65) {
      result = 'B';
    }else if(mf >= 50) {
      result = 'C';
    }else if(mf >= 30) {
      if(r >= 50) result = 'C';
      else result = 'D';
    }else {
      result = 'F';
    }

    cout << result << endl;

  }
}



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

int main()
{
  int ans=0;
  vector<int> a(1000000,0);
  cin >> a.at(0);
  for(int i=1; i<1000000; i++){
    if(a.at(i-1)%2==0) a.at(i)=a.at(i-1)/2;
    else a.at(i)=a.at(i-1)*3+1;
    for(int j=0; j<i; j++){
      if(a.at(j)==a.at(i)){
        ans=i+1;
        break;
      }
    }
    if(ans!=0) break;
  }
  cout << ans << endl;
}

Measured memory_bytes: 4096
#include <cstdio>

int main() {
  int A, B, C, D;
  scanf("%d %d %d %d", &A, &B, &C, &D);

  int L = A + B;
  int R = C + D;
  if (L > R) {
    puts("Left");
  } else if (L < R) {
    puts("Right");
  } else {
    puts("Balanced");
  }
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef vector<ull> vul;
#define For(i, n) for(ll i = 0; i < n; i++)
#define len(n) (ll)(n).size()
#define FAST_IO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define Sort(a) sort(a.begin(), a.end())

ll dp[(ll)1e5];
vl h;
ll n;

int main() {
    FAST_IO;
    cin >> n;
    h.resize(n);
    For(i, n) cin >> h[i];
    for (ll i = 1; i < n; i++) dp[i] = -1;
    For(i, n) {
        for (ll z = 1; z <= 2 && i + z < n; z++) {
            if (dp[i + z] != -1) dp[i + z] = min(dp[i + z], dp[i] + abs(h[i] - h[i + z]));
            else dp[i + z] = dp[i] + abs(h[i + z] - h[i]);
        }
    }
    cout << dp[n - 1] << '\n';
    return 0;
}

Measured memory_bytes: 4704
N = int(input())

A = []
B = []

for i in range(N):
  Data = list(map(int, input().split()))
  A.append(Data[0])
  B.append(Data[1])
  
ma = 10e10
for i in range(N):
  if A[i] > B[i]:
    if B[i] < ma:
      ma = B[i]

if ma == 10e10:
  print(0)
else:
  print(sum(A) - ma)

Measured memory_bytes: 4916
def resolve():
    '''
    code here
    '''

    S = input()
    N = len(S)

    a_list = [ 0 for _ in range(N+1)]


    for i in range(N):
        if S[i] == '<':
            a_list[i+1] = a_list[i] + 1
    # print(a_list)
    for i in range(N):
        if S[-1*(i+1)] == '>':
            a_list[-1*(i+2)] = max(a_list[-1*(i+1)] + 1, a_list[-1*(i+2)])

    # print(a_list)
    
    print(sum(a_list))


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 24036
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring> //memset(dp,0,sizeof(dp))
#include <functional>
#include <cctype>
#include <locale>
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
typedef pair<int,int> P;
typedef pair<long long,long long> Pll;
#define fout(num) cout << fixed << setprecision(20) << (num) << endl
//s[i]=tolower(s[i]); islower(s[i]); cout << tolower(s[i])はバグ
//vector<vector<ll>> dp(n,vector<ll>(n))
//exist x map o setconst ll MOD = 1e9+7;return fac[n]*(finv[k]*finv[n-k] % MOD) % MOD;

signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n; cin >> n;
    vector<int>a(n);
    int sum=0;
    rep(i,n){
        cin>>a[i];
        sum+=a[i];
    }
    sort(ALL(a));
    int x=sum/n;
    ll ans=0;
    rep(i,n){
        ans+=(a[i]-x)*(a[i]-x);
    }
    x++;
    ll res=0;
    rep(i,n){
        res+=(a[i]-x)*(a[i]-x);
    }
    chmin(ans,res);
    x-=2;
    res=0;
    rep(i,n){
        res+=(a[i]-x)*(a[i]-x);
    }
    chmin(ans,res);
    cout << ans << endl;
}



Measured memory_bytes: 3660
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define se second
#define fi first
#define ll long long
#define INF INT_MAX
#define mod 1000000007
#define chutiyaap ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
ll pw(ll a, ll b) {
    if (b == 0) return 1;
    ll t = pw(a, b / 2);
    if (b % 2 == 0) return (t * t)%mod;
    else return ((t * t)%mod * a)%mod;
}
int main()
{
	string s,t;cin>>s>>t;
	int n=s.length(),m=t.length();
	int maxi=0,cnt=0;
	for(int i=0;i<n-m+1;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(s[i+j]==t[j])cnt++;
		}
		maxi=max(maxi,cnt);
		cnt=0;
	}
	cout<<m-maxi;
}


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

void dfs(int start, const vector<vector<int>> &graph, vector<int> &memo,vector<bool> &visited)
{
    visited[start] = true;
    for (int i = 0; i < graph[start].size(); ++i) {
        if(!visited[graph[start][i]]) {
            dfs(graph[start][i], graph, memo, visited);
        }
        memo[start] = max(memo[start], memo[graph[start][i]]+1);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    cin >> n >> m;

    vector<vector<int>> graph(n,vector<int>());
    for (int i = 0; i < m; ++i) {
        int temp1,temp2;
        cin >> temp1 >> temp2;
        graph[temp1-1].push_back(temp2-1);
    }
    vector<int> memo(n,0);
    vector<bool> visited(n,false);
    for (int i = 0; i < n; ++i) {
        if(!visited[i])
            dfs(i, graph, memo, visited);
    }
    int mMax = 0;
    for (int j = 0; j < memo.size(); ++j) {
        mMax = max(mMax, memo[j]);
    }
    cout << mMax;


}

Measured memory_bytes: 9600
#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
pair<int,int> a[101];
int c[101];
int main(){
int n,sum=0;
cin>>n;
r(i,n){
int q,w,e,r;
scanf("%d:%d-%d:%d",&q,&w,&e,&r);
a[i].first=q*60+w;
a[i].second=e*60+r;
}
int m;
cin>>m;
r(i,m){
int p;cin>>p;
r(j,p){
int q,w,e,r;
scanf("%d:%d-%d:%d",&q,&w,&e,&r);//cout<<q<<w<<e<<r<<endl;
q=q*60+w;
e=e*60+r;
r(k,n)if(a[k].first>=q&&e>=a[k].second)c[k]++;
}
}
cin>>m;
r(i,m){
int p;cin>>p;
r(j,p){
int q,w,e,r;
scanf("%d:%d-%d:%d",&q,&w,&e,&r);
q=q*60+w;
e=e*60+r;
r(k,n)if(a[k].first>=q&&e>=a[k].second&&c[k]){c[k]--;sum++;}
}
}
cout<<sum<<endl;
}

Measured memory_bytes: 3200
#include <bits/stdc++.h>
#define tam 100010
#define ull unsigned long long
 
using namespace std;
 
typedef long long ll;
typedef vector <int> vi;
typedef vector <ll> vl;
typedef pair <ll, ll> dl;
typedef pair <int, int> ii;
typedef vector <ii> vii;
typedef vector <vi> graph;
 
bool comp(int a, int b) {
	return a > b;
}
 
int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
 
	unsigned long long a;
	double b;
	cin >> a >> b;
	unsigned long long c = round(b * 100);
	unsigned long long ans = a * c;
	cout << (ans / 100) << "\n";
	return 0;
}

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

using namespace std;

const long MOD = 1000000007;
typedef pair<int, int> P;
typedef long long ll;

int main(){
    int H, W;
    cin >> H >> W;

    int N;
    cin >> N;

    int a[N];
    for(int i=0; i<N; i++) cin >> a[i];

    int ind = 0;
    int ans[H][W];
    for(int i=0; i<H; i++){
        if(i % 2 == 0){
            for(int j=0; j<W; j++){
                ans[i][j] = ind+1;
                a[ind]--;
                if(a[ind] == 0) ind++;
            }
        }else{
            for(int j=W-1; j>=0; j--){
                ans[i][j] = ind+1;
                a[ind]--;
                if(a[ind] == 0) ind++;
            }
        }
    }

    for(int i=0; i<H; i++){
        for(int j=0; j<W; j++){
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}


Measured memory_bytes: 384
def main3():
    N, M = map(int, input().split())
    ng_step = set([int(input()) for _ in range(M)])

    dp = [0 for i in range(N + 1)]
    dp[0] = 1

    if 1 in ng_step:
        dp[1] = 0
    else:
        dp[1] = 1

    for i in range(2, N + 1):
        if i in ng_step:
            dp[i] = 0
        else:
            dp[i] = dp[i - 1] + dp[i - 2] 
    
    print(dp[N] % (10**9 + 7))

if __name__ == "__main__":
    main3()

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

int main()
{
	int k,n;
	cin>>k>>n;
	int a[n+1],b[n+1];
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<n;i++)b[i]=a[i+1]-a[i];
	b[n]=k-a[n]+a[1];
	int maxv=0;
	for(int i=1;i<=n;i++)
	   maxv=max(maxv,b[i]);
	cout<<k-maxv;
	return 0;
}

Measured memory_bytes: 1792
#include <stdio.h>

int A[1000000], n;

/* 二分探索 */
int binarySearch(int key) {
  int left = 0;
  int right = n;
  int mid;
  while(left < right) {
    mid = (left + right) / 2;
    if(key == A[mid]) return 1; /* keyを発見 */
    if(key > A[mid]) left = mid + 1; /* 後半を探索 */
    else if(key < A[mid]) right = mid; /* 前半を探索 */
  }
  return 0;
}

int main(void) {
  int i, q, k, sum = 0;
  scanf("%d",&n);
  for(i=0; i<n; i++) {
    scanf("%d",&A[i]);
  }
  scanf("%d",&q);
  for(i=0;i<q;i++) {
    scanf("%d",&k);
    if(binarySearch(k))
      sum++;
  }
  printf("%d\n",sum);
  return 0;
}


Measured memory_bytes: 2152
#include <cstdio>
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;

string s1,s2,s3;
int a,b;

int main(void){
	cin>>s1;
	cin>>s2;
	scanf("%d %d",&a,&b);
	cin>>s3;
	if(s3==s1)a--;
	else b--;
	printf("%d %d\n",a,b);
}

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

using namespace std;

int main(){
    int n;
    cin >> n;
    string a, b, c;
    cin >> a >> b >> c;
    int cnt = 0;
    for(int i = 0; i < n; i++){
        if((a[i] == b[i]) && a[i] == c[i]) continue;
        if(a[i] == b[i] || b[i] == c[i] || c[i] == a[i]){
            cnt++;
            continue;
        }
        cnt += 2;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
//#define int ll
typedef int Def;
//typedef ll Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
#define mt make_tuple
typedef tuple<int,int,int> tp;
typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-7;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(){
	string s,t;
	while(cin>>s>>t,s!="."){
		vs A,a,B,b;
		string r="";
		bool h=false;
		rep(i,s.size()){
			if(s[i]=='"'){
				if(h)A.pb(r);
				else a.pb(r);
				r="";
				h^=1;
			}else r+=s[i];
		}
		if(r!="")a.pb(r);
		r="";
		rep(i,t.size()){
			if(t[i]=='"'){
				if(h)B.pb(r);
				else b.pb(r);
				r="";
				h^=1;
			}else r+=t[i];
		}
		if(r!="")b.pb(r);
		h=true;
		if(A.size()!=B.size())h=false;
		int co=0;
		if(h)rep(i,A.size())if(A[i]!=B[i])co++;
		if(co>1)h=false;
		if(a.size()!=b.size())h=false;
		if(h)rep(i,a.size())if(a[i]!=b[i])h=false;
		if(s==t)cout<<"IDENTICAL"<<endl;
		else if(h)cout<<"CLOSE"<<endl;
		else cout<<"DIFFERENT"<<endl;;
	}
}













Measured memory_bytes: 3196
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>
#include<complex>

using namespace std;

#define ll long long
#define ld long double
#define EPS 1e-9
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;
typedef vector<pii> vp;
typedef vector<vi> vvi;

int gcd(int a, int b){if(b==0) return a;return gcd(b,a%b);}
int lcm(int a, int b){return a/gcd(a,b)*b;}


signed main(void) {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vvi a(10);
    rep(i,n){
        int c = s[i] - '0';
        a[c].push_back(i);
    }
    int ans = 0;
    /*
    rep(i,10){
        cout << i << ":";
        rep(j,a[i].size())cout << " " << a[i][j];
        cout << endl;
    }*/
    rep(i,10)rep(j,10)rep(k,10)if(a[i].size() && a[j].size() && a[k].size()){
        int p = a[i][0];
        int q = upper_bound(all(a[j]), p) - a[j].begin();
        if(q == a[j].size())continue;
        int r = upper_bound(all(a[k]), a[j][q]) - a[k].begin();
        if(r == a[k].size())continue;
        /*
        cout << " " << p << " " << q << " " << r << endl;
        cout << i << " " << j << " " << k << endl;
        */
        ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 768
local function str2tbl(s)
    local t = {string.byte(s, 1, #s)}
    for i=1, #t do
        t[i] = string.char(t[i])
    end
    return t
end

local function each_char2(s)
    return ipairs(str2tbl(s))
end

local function each_char(s)
    local f = function(_, i)
        i = i + 1
        if i <= #s then
            return i, string.sub(s, i, i)
        end
    end
    return f, nil, 0
end

function string.at(s, i)
    return string.sub(s, i, i)
end

-- C
local S = {}
while true do
    local c = io.read(1)
    if c == "1" then
        table.insert(S, 1)
    elseif c == "0" then
        table.insert(S, 0)
    else
        break
    end
end
local oddeven_01, oddeven_10 = 0, 0
for i=1,#S do
    local x = S[i]
    if i & 1 == 1 then
        -- odd
        if x == 1 then
            oddeven_01 = oddeven_01 + 1
        elseif x == 0 then
            oddeven_10 = oddeven_10 + 1
        end
    else
        -- even
        if x == 1 then
            oddeven_10 = oddeven_10 + 1
        elseif x == 0 then
            oddeven_01 = oddeven_01 + 1
        end
    end
end
local min = oddeven_01
if min > oddeven_10 then
    min = oddeven_10
end
print(min)


Measured memory_bytes: 2424
#include <bits/stdc++.h>
using namespace std;
int main(){
  
  vector<int> v(3);
  for(int i; i < 3; i++)
    cin >> v.at(i);
  
  sort(v.begin(), v.end());
  
  int j;
  int k;
  
  j = v.at(2) - v.at(1);
  k = v.at(1) - v.at(0);
  
  cout << j + k << endl;
}



Measured memory_bytes: 256
n, m = map(int, input().split())
elivation = list(map(int, input().split()))

observation_joint = dict()
for i in range(n):
    observation_joint[i] = []
# print(observation_joint)
while m:
    a,b = map(int, input().split())
    a-=1
    b-=1
    observation_joint[a].append(b)
    observation_joint[b].append(a)
    m-=1

# print(observation_joint)
count = 0
for obs, joints in observation_joint.items():
    if joints == []:
        count += 1
    else:
        good_obs = True
        for obs2 in joints:
            if elivation[obs2] >= elivation[obs]:
                good_obs = False
                break
        if good_obs:
            count += 1
print(count)


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

typedef long long ll;
ll N;
string S;
const ll MAX_N = 5000;
ll DP[MAX_N + 1][MAX_N + 1];
ll R;

int main() {
  cin >> N >> S;
  for (ll i = N - 1; i >= 0; --i) {
    for (ll j = N - 1; j >= 0; --j) {
      if (S[i] == S[j]) DP[i][j] = 1 + DP[i + 1][j + 1];
      R = max(R, min(DP[i][j], abs(i - j)));
    }
  }
  cout << R << endl;
}


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

long gcd(long a, long b) {
    if (b > a)  return gcd(b, a); 
    if (b == 0) return a;
    return gcd(a - b, b); 
}

int main() {
    long a, b;
    cin >> a >> b;
    long g = gcd(a, b); 
    long cnt = 1;

    long initg = g;
    for (long i = 2; i <= g; i++) {
        if (g % i == 0) {
            cnt++;
            while (g % i == 0) {
                g /= i;
            }   
        }   
        if (i * i > initg) break;
    }   
    if (g != 1) cnt++;
    cout << cnt << endl;
}

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

int main(){
  int n, m;
  cin >> n >> m;
  int a[n];
  int s = 0;
  rep(i,n) {
    cin >> a[i];
    s += a[i];
  }
  int c = 0;
  rep(i,n) {
    if(a[i] >= (s+4*m-1)/(4*m)) c++;
  }
  cout << (c >= m ? "Yes" : "No") << endl;
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <string>
#include <deque>
#define pb push_back
#define mod 1000000007
#define all(x) x.begin(),x.end()
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef pair<ll,ll> pll;

int n,m;
vector<vector<int> >g;
pii dame;
bool vis[55];
bool dfs(int x,int y){
  if(x==y) return true;
  if(vis[x]) return false;
  vis[x]=true;

  for(int i=0;i<g[x].size();i++){
    if((x==dame.first)&&(g[x][i]==dame.second)) continue;
    if(dfs(g[x][i],y)) return true;
  }
  return false;
}

int main(void){
  cin>>n>>m;
  int a,b;
  g.resize(n+1,vector<int>());
  vector<pii> p;
  for(int i=0;i<m;i++){
    cin>>a>>b;
    p.pb(pii(a,b));
    g[a].pb(b);
    g[b].pb(a);
  }
  int res=0;
  for(int i=0;i<m;i++){
    memset(vis,0,sizeof(vis));
    dame=p[i];
    if(!dfs(p[i].first,p[i].second)) res++;
  }
  cout<<res<<endl;
  return 0;
}


Measured memory_bytes: 256
from collections import OrderedDict
from itertools import cycle, islice
 
d = OrderedDict(("{} {} {}".format(b, f, r), 0) for b in range(1, 5)
                                                for f in range(1, 4)
                                                for r in range(1, 11))
 
n = int(input())
for _ in range(n):
    s = input()
    idx = s.rfind(" ")
    d[s[:idx]] += int(s[idx+1:])

data = d.values()
delim = "#" * 20
for i in range(0, 120, 10):
    print(" " + " ".join(map(str, islice(cycle(data), i, i+10))))
    if i in (20, 50, 80):
        print(delim)

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

#define MAX 100000

struct a{
  
  char name[10];
  int time;  

};

void initialize(void);
int isEmpty();
int isFull();
void enqueue(struct a);
struct a dequeue();

int head,tail;
struct a p[MAX],x;


int main( ){

  int n,q,i,count=0;

  initialize();

  scanf("%d%d",&n,&q);

  tail=n;
 
  // printf("%d",tail);
  
  
  for(i=0;i<n;i++){

    scanf("%s %d",p[i].name,&p[i].time);
    
  }

  //printf("wa-i1\n");
  
  while(1){

    // printf("wa-i\n");
    
    if(p[head].time-q<=0){

      // printf("wa-i3\n");
      
      count+=p[head].time;
      x=dequeue();
      printf("%s %d\n",x.name,count);
      if(isEmpty()==1) break;
    }
    else{

      // printf("wa-i4\n");
      count+=q;
      p[head].time=p[head].time-q;
      //printf("wa-i5\n");
      x = dequeue();
      //printf("wa-i6\n");
      enqueue(x);
    }

  }
  
  return 0;
}

void initialize(){

  head = tail = 0;

}

int isEmpty(){

  if(head == tail) return 1;
  else return 0;

}

int isFull(){

  if(head==(tail+1)%MAX) return 1;
  else return 0;

}

void enqueue(struct a x){

  if(isFull()==1){
    printf("?????????????????????\n");
    exit(1);
  }

  p[tail]=x;
  if(tail+1==MAX) tail = 0;
  else tail++;

}

struct a dequeue(){

  struct a x;

  if(isEmpty()==1){
    printf("??¢??????????????????\n");
    exit(2);
  }
    
  x=p[head];

  if(head+1==MAX) head=0;
  else head++;

  return x;

}
  




    

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

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

const int MN = 200010;

int N;
vi g[MN], g2[MN];
int maxi[MN];
int ans[MN];
vector<pii> dp[MN];

void pre(int v, int p, int ma) {
	maxi[v] = ma;

	for (int to : g[v]) if (to != p) {
		g2[v].pb(to);
		pre(to, v, max(ma, v));
	}
}

int calc(int v, int x) {
	for (pii data : dp[v]) {
		if (data.fi == x) {
			return data.se;
		}
	}

	int res = 0;
	for (int to : g2[v]) if (to < x) {
		res += (calc(to, x) + 1);
	}
	dp[v].eb(x, res);
	return res;
}

int dfs(int v) {
	for (int to : g2[v]) {
		if (maxi[v] > to) {
			ans[to] = ans[v] + calc(to, maxi[to]) - calc(to, maxi[v]);
		} else {
			ans[to] = ans[v] + calc(to, maxi[to]) + 1;
		}
		dfs(to);
	}
}

int main() {
	cin >> N;

	rep(i, N-1) {
		int a, b;
		cin >> a >> b; --a; --b;
		g[a].pb(b); g[b].pb(a);
	}

	pre(0, -1, -1);
	dfs(0);

	for (int i = 1; i < N; ++i) {
		cout << ans[i] << (i == N-1 ? '\n' : ' ');
	}

	return 0;
}

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

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

  for (int i = 0; i < s.size() - 1; i++)
  {
    for (int j = i + 1; j < s.size(); j++)
    {
      if (s.at(i) == s.at(j))
      {
        cout << "no" << endl;
        return 0;
      }
    }
  }
  cout << "yes" << endl;
}


Measured memory_bytes: 3592
#include <iostream>
using namespace std;
bool kaibun(string s) {
  int len=s.length();
  int center=len/2+1;
  for (int i=0,j=len-1; i<center; i++,j--) {
    if (s[i]!=s[j]) {
      return false;
    }
  }
  return true;
}
int main() {
  string S; cin>>S;
  if(!kaibun(S)) {
    cout<<"No"<<endl;
    return 0;
  }
  int N=S.length();
  string S1="";
  for (int i=0; i<(N-1)/2; i++) S1+=S[i];
  if(!kaibun(S1)) {
    cout<<"No"<<endl;
    return 0;
  }
  string S2="";
  for (int i=(N+3)/2-1; i<N; i++) S2+=S[i];
  if(!kaibun(S2)) {
    cout<<"No"<<endl;
    return 0;
  }
  cout<<"Yes"<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <tuple>
#include <utility>
#include <vector>
#define ll long long
#define itn int
#define endl '\n'
#define co(ans) cout<<ans<<endl
#define COYE cout<<"YES"<<endl
#define COYe cout<<"Yes"<<endl
#define COye cout<<"yes"<<endl
#define CONO cout<<"NO"<<endl
#define CONo cout<<"No"<<endl
#define COno cout<<"no"<<endl
#define FORE(i,a) for(auto &i:a)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define PB push_back
#define MP make_pair
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define EACH(V,i) for(typeof((V).begin()) i=(V).begin();i!=(V).end();++i)
#define equals(a,b) (fabs((a)-(b))<EPS)
#define INF ((1LL<<62)-(1LL<<31))
#define EPS 1e-10
#define PI 3.141592653589793238
#define MOD 1000000007
#define MAX 5100000
using namespace std;
using Graph=vector<vector<int>>;
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T>inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(){
  ll N,A,B;
  cin>>N>>A>>B;
  
  if((B-A)%2==0) co((B-A)/2);
  else{
    ll ans=(A+B)/2;
    chmin(ans,N-ans);
    co(ans);
  }
  return 0;
}

Measured memory_bytes: 256
#if 0
date +%Y.%m.%d

题解先咕着。
#endif
#include <cstdio>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;

struct {
	inline operator int () { int x; return scanf("%d", &x), x; }
	inline operator ll () { ll x; return scanf("%lld", &x), x; }
	template<class T> inline void operator () (T &x) { x = *this; }
	template<class T, class ...A> inline void operator () (T &x, A &...a)
	{ x = *this; this -> operator ()(a...); }
} read;

const int maxn = 205, mod = 998244353;

inline ll sq(ll x) { return x * x; }
inline bool in_line(ll x1, ll y1, ll x2, ll y2) {
	ll a = x1 * x2 + y1 * y2;
	ll b = (sq(x1) + sq(y1)) * (sq(x2) + sq(y2));
	/* debug("chk %lld %lld\n", sq(a), b); */
	return a >= 0 and sq(a) == b;
}

int x[maxn], y[maxn];
ll p2[maxn];

int main() {
	int n = read;
	for(int i = 1; i <= n; i ++)
		read(x[i], y[i]);

	p2[0] = 1;
	for(int i = 1; i <= n; i ++)
		p2[i] = (p2[i - 1] << 1) % mod;

	ll ans = 0;

	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= n; j ++)
			if(i != j) {
				int Dx = x[j] - x[i], Dy = y[j] - y[i];
				int tot = 0;
				for(int k = 1; k <= n; k ++)
					if(k != i and k != j) {
						int dx = x[k] - x[j], dy = y[k] - y[j];
						if(in_line(Dx, Dy, dx, dy))
							/* debug("%d %d %d\n", i, j, k), */
							++ tot;
					}
				ans += p2[tot];
			}

	/* debug("%lld\n", ans); */

	((ans %= mod) *= (mod + 1) >> 1) %= mod;
	ans = (p2[n] - n - 1 - ans + mod) % mod;

	printf("%lld\n", ans);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define mrep(i,j,n) for(int i = j; i < n; i++)
#define reps(i,n) for(int i = 1; i <= n; i++)
#define rrep(i,n) for(int i = n-1; i >= 0; i--)
#define rreps(i,n) for(int i = n; i >= 1; i--)
#define co(x) cout << x <<endl
#define cs(x) cout << x <<" "
#define el cout<<endl
#define cer(x) cerr << x <<endl
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define ERASE(x,val) x.erase(remove(ALL(x), val), x.end())

typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ll mod = 1e9 + 7;
template<class T>inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; }return false; }

int main()
{
	ll a, b, k; cin >> a >> b >> k;
	if (a > k)
	{
		co(a - k << " " << b);
	}
	else if (b > k - a)
	{
		co(0 << " " << b + a - k);
	}
	else
	{
		co(0 << " " << 0);
	}
	return 0;
}


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

int main(){
    int n;
    cin >> n;
    int h[n+1];
    rep(i,n) cin >> h[i+1]; 
    vector<int> dp(n+1,INF);
    dp[1] = 0; dp[2] = abs(h[2]-h[1]);
    for(int i = 3; i <= n; i++){
        dp[i] = min(dp[i-1] + abs(h[i]-h[i-1]), dp[i-2] + abs(h[i]-h[i-2]));
    }
    cout << dp[n] << endl;
    return 0;
}

Measured memory_bytes: 1024
#!/usr/bin/env pypy3
import collections
import itertools as it
import math
import numpy as np
 
#  = input()
#  = int(input())
yoko = [list(map(int, input().split())) for _ in range(3)]
is_flag = [False] * 9
#  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

yoko = list(np.array(yoko).flatten())

n = int(input())
for _ in range(n):
    b = int(input())

    if b in yoko:
        is_flag[yoko.index(b)] = True

is_flag = list(np.array(is_flag).reshape(3, 3))

line = is_flag # yoko
line += list(np.array(is_flag).T) # tate
line += [[line[0][0], line[1][1], line[2][2]], [line[0][2], line[1][1], line[2][0]]]

for l in line:
    if sum(l) == 3:
        print('Yes')
        break
else:
    print('No')
#print(yoko)
#print(tate)
#print(naname)


Measured memory_bytes: 12644