akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

//t秒間でx、y方向合わせてt移動できる
/*次の目標点までの時間dtで、dl = dx + dyとして、dt >= dl
でdtとdlの偶奇が一致してたら移動可能
*/
int main(){
  int N;
  cin >> N;
  vector<int> t(N+1);
  vector<int> x(N+1);
  vector<int> y(N+1);
  rep(i,N){
      cin >> t[i+1];
      cin >> x[i+1];
      cin >> y[i+1];
  }
  bool flag = true;
  for(int i = 0;i<=N-1;i++){
      int dt = t[i+1] - t[i];
      int dl = abs(x[i+1]-x[i]) + abs(y[i+1]-y[i]);
      if(dt >= dl && dt%2 == dl%2) continue;
      else {
          flag = false;
          break;
      }
  }
  if(flag) cout << "Yes" <<endl;
  else cout << "No" <<endl;

 }

Measured memory_bytes: 1408
#include <algorithm>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef unsigned long ul;
typedef long long ll;
typedef pair<ul, ul> P;
map<int, int> dp;
#define REP(i, n) for (int i = 0; i < n; i++)

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int A, P;
  cin >> A >> P;
  cout << int((A * 3 + P) / 2) << endl;

  return 0;
}


Measured memory_bytes: 256
n = int(input())
lst = [int(i) for i in input().split()]
sortlst = [i + 1 for i in range(len(lst))]
non_match = 0
for a, b in zip(lst, sortlst):
	if a != b:
		non_match += 1
if non_match == 2 or non_match == 0:
	print('YES')
else:
	print('NO')

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n, ans, a[N];
signed main () {
	scanf ("%lld", &n);
	for (int i = 1; i <= n; i ++) {
		scanf ("%lld", &a[i]);
		if (a[i] & 1)
			ans ^= 1;
	}
	if (ans)
		puts ("NO");
	else
		puts ("YES");
	return 0;
}


Measured memory_bytes: 4440
import java.util.*;

public class Main {

	static int head = 0;

	static void f(int i, char[] r) {
		if (i == head) {
			if (r[i] == '9') {
				++head;
				f(i + 1, r);
				r[i] = (char) Math.max('0', r[i + 1] - 1);
			} else {
				++r[i];
			}
		} else if (r[i] == '9' || Math.abs(++r[i] - r[i + 1]) > 1) {
			f(i + 1, r);
			r[i] = (char) Math.max('0', r[i + 1] - 1);
		}
	}

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		char[] r = new char[11];
		Arrays.fill(r, '0');
		for (int k = s.nextInt(); k > 0; --k) {
			f(0, r);
		}
		System.out.println(new StringBuilder(String.valueOf(r))
				.reverse().toString().replaceFirst("^0+", ""));
	}
}


Measured memory_bytes: 23636
#include<bits/stdc++.h>
using namespace std;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define IN freopen("in.txt", "r", stdin);
#define endl '\n'
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
typedef long long ll;
typedef vector<int> VI;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;


void update(int q,int& last,int& d){
    if(d and q%2 != last%2)d=3-d;
    last=q;
}

pair<VI,VI> solve(int n,string& T){
    if(!n){
        VI p = {0};
        VI W(sz(T),0);
        return {p,W};
    }
    auto pp=solve(n-1,T);
    const auto& p=pp.fi, w=pp.se;
    VI new_w(sz(w));
    int pot=sz(p);
    VI D(3*pot);
    for(int i=0;i<3;i++)for(int x=0;x<pot;x++)D[i*pot+x]=i;
    VI last(3*pot,0);
    int q=0;
    for(int i=0;i<sz(T);i++){
        int k=w[i];
        for(int x=k;x<3*pot;x+=pot){
            update(q,last[x],D[x]);
            if(D[x]==2)new_w[i]=x;
        }
        if(T[i]=='S')q++;
        if(T[i]=='R'){
            for(int x=k;x<3*pot;x+=pot)D[x]=(D[x]+1)%3;
        }
    }
    VI new_p(3*pot);
    for(int i=0;i<3*pot;i++){
        update(q,last[i],D[i]);
        new_p[i]=p[i%pot]+D[i]*pot;
    }
    return {new_p,new_w};
}

int main(){
    IOS;
    int n;string s;
    cin>>n>>s;
    VI p=solve(n,s).fi;
    for(int x:p)cout<<x<<' ';
    cout<<endl;
    return 0;
}

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


def main():
    from collections import deque

    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    dist = [[-1 for __ in range(w)] for _ in range(h)]
    blacks = deque()

    # See:
    # http://drken1215.hatenablog.com/entry/2019/05/05/223200?_ga=2.177845805.987014750.1556545680-1855989383.1556545680
    # https://blog.kichi2004.jp/2019/05/agc033/
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                dist[i][j] = 0
                blacks.append((i, j))

    while blacks:
        current = blacks.popleft()
        cur_x = current[1]
        cur_y = current[0]

        for i in range(4):
            next_x = cur_x + dx[i]
            next_y = cur_y + dy[i]

            if next_x < 0 or next_x >= w or next_y < 0 or next_y >= h:
                continue

            if dist[next_y][next_x] == -1:
                dist[next_y][next_x] = dist[cur_y][cur_x] + 1
                blacks.append((next_y, next_x))

    ans = 0

    for i in range(h):
        for j in range(w):
            ans = max(ans, dist[i][j])

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 122824
#include <bits/stdc++.h>
#define rep(I,n) for (int I = 0; I < (n); ++I)
#define FOR(I,k,n) for(int I=(k);I<(n);++I)
using namespace std;
typedef long long ll;
 
int main() {
    
    string s;
    cin >> s;
    
    int ans;
    
    if (s == "SUN"){
        
        ans =7;
        
    }
    
    if (s == "MON"){
        
        ans =6;
        
    }
    
    if (s == "TUE"){
        
        ans =5;
        
    }
    
    if (s == "WED"){
        
        ans =4;
        
    }
    
    if (s == "THU"){
        
        ans =3;
        
    }
    
    if (s == "FRI"){
        
        ans =2;
        
    }
    
    if (s == "SAT"){
        
        ans =1;
        
    }
    
    cout << ans <<endl;
  
  
    
  
  
  return 0;
}

Measured memory_bytes: 256
import sys
from bisect import bisect_right, bisect_left
input = sys.stdin.readline
n, m, v, p = [int(x) for x in input().strip().split()]
araw = sorted([int(x) for x in input().strip().split()])
a = list(reversed(araw))

def f(x, n, m, v, p, a, araw):
    c = p - (n - bisect_right(araw, a[x-1]+m)) - 1
    if c < 0:
        return False
    vote = m * (v - 1)
    a[x-1] += m
    thr = a[x-1]
    for i, aa in enumerate(a, start=1):
        if vote <= 0:
            break
        if i == x:
            continue
        if aa > thr:
            a[i-1] += m
            vote -= m
        elif aa == thr:
            if c:
                a[i-1] += m
                vote -= m
                c -= 1
        elif thr - aa < m:
            if c:
                a[i-1] += m
                vote -= m
                c -= 1
            else:
                v_ = min(vote, thr - aa, m)
                a[i-1] += v_
                vote -= v_
        else:
            a[i-1] += m
            vote -= m
    return vote <= 0

x = 0
l = 1
r = n + 1
while l < r:
    x = (l + r) // 2
    if f(x, n, m, v, p, a[:], araw):
        l = x + 1
    else:
        r = x
print(l-1)

Measured memory_bytes: 14396
// Problem: D - Friends
// Contest: AtCoder - AtCoder Beginner Contest 177
// URL: https://atcoder.jp/contests/abc177/tasks/abc177_d
// Parsed on: 2020-08-29 17:30:05
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <algorithm>
#include <cmath>
#include <iostream>
#include <numeric>
#include <string>
#include <unordered_map>
#include <vector>

#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);

using namespace std;

int root(vector<int>& dsu, int a) {
    if (dsu[a] == a) {
        return a;
    }
    return dsu[a] = root(dsu, dsu[a]);
}

int findRoot(vector<int> const& dsu, int node) {
    if (dsu[node] == node)
        return node;
    else
        return findRoot(dsu, dsu[node]);
}

void insert(vector<int>& dsu, int to, int from, vector<int>& size) {
    to = root(dsu, to);
    from = root(dsu, from);

    if (to != from) {
        if (size[to] < size[from]) swap(to, from);

        dsu[from] = to;
        size[to] += size[from];
    }
}

int main() {
    fastio;
    int n, m;
    cin >> n >> m;
    vector<int> dsu(n), size(n);

    for (int a = 0; a < n; a++) {
        dsu[a] = a;
        size[a] = 1;
    }

    while (m--) {
        int aa, ba;
        cin >> aa >> ba;
        aa--;
        ba--;
        insert(dsu, aa, ba, size);
    }

    for (auto& e : dsu) e = findRoot(dsu, e);

    unordered_map<int, int> ds;
    for (auto& e : dsu) ds[e]++;

    int ans = ds[0];
    for (auto& e : ds)
        if (e.second > ans) ans = e.second;
    cout << ans;

    return 0;
}


Measured memory_bytes: 12252
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))
 
using namespace std;
 
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
 
const ll INF=1e9+7;

int main(){
    string s,t;
    cin >> s >>t;
    ll n=s.length();
    ll m=t.length();
    vector<vector<ll>> dp(n+1,vector<ll>(m+1));
    rep(i,n){
        rep(j,m){
            if(s[i]==t[j]){
                dp[i+1][j+1]=dp[i][j]+1;
            }
            else{
                dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
            }
        }
    }
    string ans="";
    while(n!=0 && m!=0){
        if(dp[n][m]==dp[n-1][m]){
            n--;
        }
        else if(dp[n][m]==dp[n][m-1]){
            m--;
        }
        else{
            ans+=s[n-1];
            n--;
            m--;
        }
    }
    reverse(ans.begin(),ans.end());
    cout << ans << endl;
    return 0;
} 


Measured memory_bytes: 70784
N, P = map(int, raw_input().split())
max_N = 40
if N == 1:
    print P
elif N >= max_N:
    print 1
else:
    res = 1
    i = 2
    while i ** N <= P:
        if P % (i ** N) == 0:
            res = i
        i += 1
    print res


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

using namespace std;

#define LOG(...) fprintf(stderr,__VA_ARGS__)
//#define LOG(...)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

struct Circle {
    int x, y, r, c;
};

int main() {
    int n;
    while (cin >> n, n) {
        vector<Circle> circles;
        REP(i, n) {
            int x, y, r, c;
            cin >> x >> y >> r >> c;
            circles.push_back({x, y, r, c});
        }

        vi overlap(n);
        REP(i, n-1) {
            FOR(j, i+1, n) {
                Circle c1 = circles[i];
                Circle c2 = circles[j];
                if (
                    pow(c1.x - c2.x, 2) + pow(c1.y - c2.y, 2) < pow(c1.r + c2.r, 2)
                ) {
                    overlap[j] |= 1 << i;
                }
            }
        }

        vb dp(1 << n);
        dp[(1 << n) - 1] = true;
        for (int m = (1 << n) - 1; m >= 0; m--) {
            if (!dp[m]) continue;
            REP(i, n-1) {
                FOR(j, i+1, n) {
                    if (m & (1 << i) && m & (1 << j) &&
                        circles[i].c == circles[j].c &&
                        (overlap[i] & m) == 0 && (overlap[j] & m) == 0) {
                        int mm = m & ~(1 << i) & ~(1 << j);
                        dp[mm] = true;
                    }
                }
            }
        }

        int res = 0;
        REP(m, 1 << n) {
            if (dp[m]) {
                res = max(res, n - __builtin_popcount(m));
            }
        }
        cout << res << endl;
    }
}

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

int main() {
	int N, count = 0, MIN = 0;
	string S;
	cin >> N >> S;
	for (int i = 0; i < N; i++) {
		if (S[i] == '(') count++;
		else count--;
		MIN = min(MIN, count);
	}
	for (int i = 0; i < MIN * -1; i++) {
		cout << '(';
	}
	cout << S;
	for (int i = 0; i < count - MIN; i++) {
		cout << ')';
	}
}

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

int main(){
  int N, K;
  cin >> N >> K;
  
  string s;
  cin >> s;
  if(s.at(K-1) == 'A'){
    s.at(K-1) = 'a';
  }else if(s.at(K-1) == 'B'){
    s.at(K-1) = 'b';
  }else if(s.at(K-1) == 'C'){
    s.at(K-1) = 'c';
  }
  
  cout << s << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define db(a) cout << fixed << #a << " = " << a << endl;

using namespace std;

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


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	string S;
	cin >> S;
	if (S.back() == 's') {
		S += "es";
	} else {
		S += 's';
	}
	cout << S << endl;
}



Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int N;
  cin >> N;
  
  vector<int> H(N);
  for(int i=0;i<N;i++){
    cin >> H.at(i);
  }
  
  int ans=1;
  int x=H.at(0);
  
  for(int j=1;j<N;j++){
    x=max(x,H.at(j));
    if(x<=H.at(j)){
      ans++;
    }
  }
  
  cout << ans << endl;
  
}

Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
#ifdef LOCAL
#define debug(x) cerr << #x << ": " << x << endl
#else
#define debug(x)
#endif
int dx[4]={ 1,0,-1,0 };
int dy[4]={ 0,1,0,-1 };

int N, M;
int A[100000], B[100000];
int L[200000], R[200000];
vector<int> z;

int s[100000], l[200000], r[200000];
vector<pair<int,int>> edge[100001];

bool visited[100001];
pair<int, int> par[100001]; //par, edge
int depth[100001];
void dfs(int n, int p, int e, int d){
	if(visited[n]) return;
	visited[n] = true;
	par[n] ={ p, e };
	depth[n] = d;
	rep(i, edge[n].size()){
		dfs(edge[n][i].first, n, edge[n][i].second, d+1);
	}
}
set<pair<int, int>> pq;
bool exist[200001] ={};
bool ans[200001] ={};

signed main(){
	scanf("%d%d", &N, &M);
	rep(i, N){
		scanf("%d%d", A+i, B+i);
		z.pb(A[i]);
	}
	rep(i, M) scanf("%d%d", L+i, R+i);
	sort(all(z));
	//z.erase(unique(all(z)), z.end());
	rep(i, N){
		int tmp = lower_bound(all(z), A[i]) - z.begin();
		s[tmp] = B[i];
	}
	rep(i, M){
		l[i] = lower_bound(all(z), L[i]) - z.begin();
		r[i] = upper_bound(all(z), R[i]) - z.begin(); //半開区間
	}

	//
	
	rep(i, M){
		edge[l[i]].pb({ r[i], i+1 });
		edge[r[i]].pb({ l[i], i+1 });
	}
	rep(i, N+1){
		dfs(i, -1, -1, 0);
		if(i == 0 && s[i] == 1){
			pq.insert({ -depth[i], i });
			exist[i] = true;
		}
		if(0 < i && i < N && s[i-1] != s[i]){
			pq.insert({ -depth[i], i });
			exist[i] = true;
		}
		if(i == N && s[i-1] == 1){
			pq.insert({ -depth[i], i });
			exist[i] = true;
		}
	}
	
	while(!pq.empty()){
		int d = -pq.begin()->first;
		int n = pq.begin()->second;
		pq.erase(pq.begin());
		exist[n] = false;
		if(d == 0){
			cout << -1 << endl;
			return 0;
		}
		ans[par[n].second] = !ans[par[n].second];
		if(exist[par[n].first]){
			auto itr = pq.find({ -(d-1), par[n].first });
			pq.erase(itr);
			exist[par[n].first] = false;
		}
		else{
			pq.insert({ -(d-1), par[n].first });
			exist[par[n].first] = true;
		}
	}

	int c = 0;
	rep(i, M+1){
		if(ans[i]) c++;
	}
	cout << c << endl;
	rep(i, M+1){
		if(ans[i]){
			cout << i;
			c--;
			if(c > 0) cout << " ";
		}
	}
	cout << endl;
}


Measured memory_bytes: 21880
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

import sys
sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    N, M = l_inpl()

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

    for _ in range(M):
        Li, Ri, Di = l_inpl()
        Li, Ri = Li - 1, Ri - 1
        G[Li].append((Ri, Di))
        G[Ri].append((Li, -Di))

    # ある点からの距離
    x = [INF] * (N+1)

    # 計算によって得たx[s]が正しいか
    def dfs(s, cost):
        # node_startまでの距離が未探索
        if x[s] == INF:
            x[s] = cost
            # s->tの距離の整合性
            for t, d in G[s]:
                if dfs(t, cost + d) == False:
                    return False
        return x[s] == cost

    for i in range(N):
        # if x[i] is not None: # 探索済み
        #     continue
        if x[i] == INF and dfs(i, 0) == False:
            print("No")
            return
    print("Yes")

if __name__ == "__main__":
    main()

Measured memory_bytes: 150444
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ACB170_B
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] array = Console.ReadLine().Split(' ');
            int X = int.Parse(array[0]);
            int Y = int.Parse(array[1]);
            bool is_exist = false;

            for (int i = 0; i <= X; i++)
            {
                if( (2 * i) + (4 * (X - i)) == Y)
                {
                    is_exist = true;
                    break;
                }
            }

            if (is_exist)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
}


Measured memory_bytes: 27476
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}
const ll INF = 1LL<<60;
const ll M = pow(10,9)+7;
/*template*/


int main()
{
  ll a[3][3];
  for(ll i=0;i<3;i++)for(ll j=0;j<3;j++)cin>>a[i][j];
  ll n;cin>>n;
  ll hoge;
  for(ll k=0;k<n;k++){
    cin>>hoge;
    for(ll i=0;i<3;i++)for(ll j=0;j<3;j++)if(a[i][j]==hoge)a[i][j]=-1;
  }
  bool flag=false;
  for(ll i=0;i<3;i++){
    if(a[i][0]==-1 && a[i][1]==-1 && a[i][2]==-1)flag=true;
    if(a[0][i]==-1 && a[1][i]==-1 && a[2][i]==-1)flag=true;
  }
  if(a[0][0]==-1 && a[1][1]==-1 && a[2][2]==-1)flag=true;
  if(a[0][2]==-1 && a[1][1]==-1 && a[2][0]==-1)flag=true;
  string ans= flag ? "Yes":"No";
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
def divisors(N):
    res = []
    i = 1
    while i * i <= N:
        q, r = divmod(N, i)
        if r == 0:
            res.append(i)
            if i != q:
                res.append(q)
        i += 1
    res.sort()
    return res

N, M = map(int, input().split())
print(max(d for d in divisors(M) if d * N <= M))


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

int main(){
  int n,sum;
  cin>>n;
  int *value;
  int *cost;
  int *p;
  value=(int*)malloc(sizeof(int)*(n+1));
  cost=(int*)malloc(sizeof(int)*(n+1));
  p=(int*)malloc(sizeof(int)*(n+1));
  for(int i;i<n;i++){
    cin>>value[i];
  }
  sum=0;
  for(int j=0;j<n;j++){
    cin>>cost[j];
    p[j]=value[j]-cost[j];
    if(p[j]>0){
      sum+=p[j];
    }
  }
  cout<<sum<<endl;
  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define int long long
#define range(i, a, b) for(auto i = a; i < b; i++)
#define rep(i, a) range(i, 0, a)
#define all(a) (a).begin(),(a).end()
using namespace std;
const int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
const int MOD = 1000000007;
const long double EPS = 1e-8;
using vi = vector <int>;
using vvi = vector <vi>;

signed main() {
	int n;
	cin >> n;
	vi t, x, y;
	t = x = y = vi (n);
	rep (i, n) {
		cin >> t[i] >> x[i] >> y[i];
	}
	rep (i, n) {
		if ( i == 0
				 ? t[i] - abs(x[i]) - abs(y[i]) >= 0
					 && (t[i] - abs(x[i]) - abs(y[i])) % 2 == 0
				 : t[i] - t[i - 1] - abs(x[i] - x[i - 1]) - abs(y[i] - y[i - 1]) >= 0
					 && (t[i] - t[i - 1] - abs(x[i] - x[i - 1]) - abs(y[i] - y[i - 1])) % 2 == 0) {
			continue;
		}
		cout << "No" << endl;
		return 0;
	}
	cout << "Yes" << endl;
}


Measured memory_bytes: 2560
#include<iostream>
#include<memory.h>
#include<cmath>
using namespace std;
int main(){
	long long int a,b;
	while(cin>>a>>b){
		long long int arr[50],f=1;
		a--;
		memset(arr,0,sizeof(arr));
		for(int i=0;i<50;i++){
			if(b>=f){
				arr[i]=b/(f*2)*f+((b%(f*2))>=f?b%(f*2)-f+1:0);
			}
			else{
				break;
			}
			f*=2;
		}
		f=1;
		for(int i=0;i<50;i++){
			if(a>=f){
				arr[i]-=a/(f*2)*f+((a%(f*2))>=f?a%(f*2)-f+1:0);
			}
			else break;
			f*=2;
		}
		long long sum=0,bit=0;
		while(b){
			b/=2;
			bit++;
		}
		for(long long i=bit-1;i>=0;i--){
			if(arr[i]%2){
				sum+=pow(2LL,i);
			}
			else{
				continue;
			}
		}
		cout<<sum<<endl;
	}
}

Measured memory_bytes: 256
#[allow(unused_imports)]
use std::cmp::Reverse;

#[allow(unused_imports)]
use proconio::{
    fastout, input,
    marker::{Chars, Usize1},
};

#[allow(unused_imports)]
use itertools::Itertools;

const MOD: usize = 1000000007;

fn rec(v: usize, parent: usize, dp: &mut Vec<Vec<usize>>, adj: &Vec<Vec<usize>>) {
    let mut whites = 1;
    let mut blacks = 1;
    for &y in adj[v].iter() {
        if parent != y {
            rec(y, v, dp, adj);
            whites *= (dp[y][0] + dp[y][1]) % MOD;
            whites %= MOD;
            blacks *= (dp[y][0]) % MOD;
            blacks %= MOD;
        }
    }
    dp[v][0] = whites;
    dp[v][1] = blacks;
}

#[fastout]
pub fn main() {
    input! {
        n: usize,
    }
    if n == 1 {
        println!("2");
        return;
    }

    input! {
        v: [(Usize1, Usize1); n - 1],
    }
    let mut adj = vec![Vec::new(); n];
    v.into_iter().for_each(|(x, y)| {
        adj[x].push(y);
        adj[y].push(x);
    });

    let mut dp = vec![vec![0; 2]; n];
    rec(0, std::usize::MAX, &mut dp, &adj);
    println!("{}", (dp[0][0] + dp[0][1]) % MOD);
}


Measured memory_bytes: 22304
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
template <typename X> ostream& operator << (ostream& x,const vector<X>& v){for(ll i=0;i<v.size();++i) x<<v[i]<<" ";return x;}
template <typename X> ostream& operator << (ostream& x,const set<X>& v){for(auto it:v) x<<it<<" ";return x;}
template <typename X, typename Y> ostream& operator << (ostream& x, const pair<X,Y>& v) {x<<v.ff<<" "<<v.ss;return x;}
template <typename T, typename S> ostream& operator << (ostream& os, const map<T, S>& v) { for (auto it : v) os << it.first << "=>" << it.second << endl; return os; }
struct pair_hash {inline std::size_t operator()(const std::pair<ll, ll> & v) const {return v.first*31+v.second;}};
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC targett("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define speed ios_base::sync_with_stdio(false);cin.tie(NULL)
#define pb push_back
#define fr first
#define sc second
#define prnt(m) for(auto it = m.begin() ; it != m.end() ; ++it){cout<<*it<<endl;}
#define tra(it,m) for(auto it=m.begin();it!=m.end();++it)
#define dbg(x) cout<<#x<<" = "<<x<<'\n';
#define fri(i,s,n) for(ll i=s;i<n;i++)
#define mod 1000000007LL
#define mod2 998244353
#define vct2 vector<vector<ll>>
#define vct vector<ll>
#define pll pair<ll,ll>
#define rz(n) resize(n)
#define all(v) vdsd.begin(),v.end()
#define mkp make_pair
#define arrin(a,n) for(ll i = 0; i < n ; i++){cin>>a[i];}
#define arrout(a,n) for(ll i = 0;i < n; i++){cout<<a[i]<<" ";}
#define ex(s) cout<<s<<endl,exit(0);
#define inf 4e18
#define five 100005;
#define six 1000005;
#define printclock cerr<<"Time"<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
//_______________________________________________________________________________________
int main()
{
       int k;
       string s;
       cin>>k>>s;
       if(s.size()<=k){
              cout<<s;
       }
       else{
              fri(i,0,k){cout<<s[i];}
              cout<<"...";
       }
}


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

using namespace std;

const int MOD = 1000000007;

int dpL[5001][5001], dpR[5001][5001];

int main()
{
  int n, k;
  int a[5001];
  
  scanf("%d %d", &n, &k);
  
  dpL[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    a[i] = min(a[i], k);
    
    for (int j = 0; j <= k; j++) {
      dpL[i][j] = dpL[i - 1][j];
      if (j >= a[i]) dpL[i][j] |= dpL[i - 1][j - a[i]];
    }
  }
  
  for (int i = 0; i <= n; i++) {
    for (int j = 1; j <= k; j++) {
      dpL[i][j] += dpL[i][j - 1];
    }
  }
  
  dpR[n][0] = dpR[n][a[n]] = true;
  for (int i = n - 1; i >= 1; i--) {
    for (int j = 0; j <= k; j++) {
      dpR[i][j] = dpR[i + 1][j];
      if (j >= a[i]) dpR[i][j] |= dpR[i + 1][j - a[i]];
    }
  }
  
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    if (a[i] >= k) continue;
    
    bool need = false;
    if (i == n && dpL[i - 1][k - 1] - dpL[i - 1][k - a[i] - 1] > 0) {
      need = true;
    }
    else {
      for (int j = 0; j <= k - 1; j++) {
        if (dpR[i + 1][j] && dpL[i - 1][k - 1 - j] - (k - a[i] - j <= 0 ? 0 : dpL[i - 1][k - a[i] - j - 1]) > 0) {
          need = true;
        }
      }
    }
    cnt += !need;
  }
  
  printf("%d\n", cnt);
  
  return 0;
}

Measured memory_bytes: 195584
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,k,ans=0,res=0;
    cin>>a>>b>>c>>k;
    res=min(k,a);
    k=k-a;
    if(k>0)
    k=k-b;
    if(k>0)
    ans=min(k,c);
    cout<<res-ans<<"\n";
    return 0;
}

Measured memory_bytes: 3632
#include<iostream>
#include<cstdio>
#include<string>
#include<math.h>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<map>
#include<numeric>
#include<stack>
#include<queue>
#include<functional>
#include<cassert>
#include<set>
#define rep(a,b) for(int a=0;a<b;++a)
#define REP(a,b,c,d) for(int a=b;a<c;a+=d)
#define yes cout<<"Yes"<<endl
#define no cout<<"No"<<endl
#define mod 1000000007
using namespace std;
using ll = long long;
using p_i = pair<int, int>;
int f(int n) {
	if (n % 2 == 0)return n / 2;
	else return 3 * n + 1;
}
int main() {
	int s; cin >> s;
	vector<int> a(10000000), ans(10000000);
	a[0] = 1;
	a[1] = s;
	ans[a[1]] = 1;
	int num = 2;
	while (true) {
		a[num] = f(a[num - 1]);
		if (ans[a[num]] == 0)ans[a[num]] = 1;
		else {
			cout << num << endl;
			return 0;
		}
		++num;
	}
}

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

int main() {
    string a;
    string b;
    cin >> a >> b;
    int counter = 0;
    for (int i=0;i<3;i++){
        if (a[i] == b[i]){
            counter++;
        }
    }
    cout << counter << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>

using namespace std;

const int MAXLEN = 3e3+3;

char S[MAXLEN], T[MAXLEN];
int dp[MAXLEN][MAXLEN];

stack<char> sol;
void backtrack(int i, int j) {
  if (i < 0 || j < 0) return;
  if (S[i] == T[j]) {
    sol.push(S[i]);
    backtrack(i-1, j-1);
    return;
  }
  int left = j > 0 ? dp[i][j-1] : -1;
  int up = i > 0 ? dp[i-1][j] : -1;
  if (left > up) backtrack(i, j-1);
  else backtrack(i-1, j);
}
  

int main() {
  scanf("%s %s", S, T);
  const int len_s = strlen(S);
  const int len_t = strlen(T);
 
  for (int i = 0; i < len_s; ++i) {
    dp[i][0] = S[i] == T[0];
  }
  for (int i = 0; i < len_t; ++i) {
    dp[0][i] = S[0] == T[i];
  }

  for (int i = 1; i < len_s; ++i) {
    for (int j = 1; j < len_t; ++j) {
      dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
      dp[i][j] = max(dp[i][j], dp[i-1][j-1]+(S[i] == T[j]));
    }
  }

  backtrack(len_s-1, len_t-1);
  while (!sol.empty()) {
    printf("%c", sol.top());
    sol.pop();
  }
  return 0;
}


Measured memory_bytes: 35456
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define FOR(i, a, n) for (int i = (a); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
using namespace std;

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

    int n;
    while (cin >> n, n) {
        int l = 0, r = 0, p = 0, ans = 0;
        REP (i, n) {
            string f;
            cin >> f;
            if (f == "lu") l = 1;
            else if (f == "ru") r = 1;
            else if (f == "ld") l = 0;
            else r = 0;
            if (l == 1 && r == 1 && p == 0) {
                ans++;
                p = 1;
            } else if (l == 0 && r == 0 && p == 1) {
                ans++;
                p = 0;
            }
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 3232
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

score=0
A.append([0])
C.append([0])

score = sum(B)

for i in range(N):

    if A[i]+1 == A[i+1]:

        score += C[A[i]-1]
    

    
print(score)

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

typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(obj) (obj).begin(),(obj).end()

#define P pair<int,int>
#define V vector<int>
#define M map<int,int>
#define S set<int>
#define PQ priority_queue<int>
#define PQG priority_queue<int,V,greater<int>>

#define pb(a) push_back(a)
#define mp make_pair

#define dump(x)  cout << #x << " = " << (x) << "\n";
#define COUT(x) cout<<(x)<<"\n"

int main()
{
	int n, k = 0;
	cin >> n >> k;
	int ans = k * pow(k - 1, n - 1);
	COUT(ans);

	return 0;
}

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

int main() {
  string S;
  cin >> S;
  int ans = 0;
  for (int i=0 ; i<S.size()-1 ; i++) {
    if (S[i+1] != S[i]) ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<cmath>
#include<cstdio>
#define rep(i,n) for(int i=0; i<(n); ++i)
using namespace std;
using ll =long long;
using P = pair<int,int>;

int N;
int x[10],y[10];

double dist(int i, int j) {
    double dx = x[i] - x[j];
    double dy = y[i] - y[j];
    return pow(dx * dx + dy * dy, 0.5);
}

void solve(){
    cin >> N;
    for(int i=1; i<=N; i++) cin >> x[i] >> y[i];
    double sum = 0.0;    
    vector<int> cs(N);
    rep(i,N)  cs[i]=i+1;
    do{
        rep(i,N-1) sum += dist(cs[i],cs[i+1]);
    } while(next_permutation(cs.begin(), cs.end()));
    int aaa = 1;
    for(int i = 2; i <= N; i++) aaa *= i;
    cout << fixed << setprecision(10) << sum / aaa << endl;
    return;
}

int main(){
    solve();
    return 0;
}



Measured memory_bytes: 384
while True:
    n=int(input())
    if n==0:
        break
    s=list(map(int,input().split()))
    m2=(sum(s)/n)**2  
    nijou=[]
    for i in s:
        nijou.append(i**2)
    m3=sum(nijou)/len(nijou)  
    print('{:.8f}'.format((m3-m2)**0.5))


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

int main()
{
    int n,a,b;
    cin >> n >> a >> b;
    cout << min(n*a, b) << endl;    
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python
# coding: utf-8

# In[22]:


N,M = map(int, input().split())
ab = []
for _ in range(M):
    ab.append(list(map(int, input().split())))


# In[23]:


start = [sorted(ship)[1] for ship in ab if 1 in ship]
goal = [sorted(ship)[0] for ship in ab if N in ship]
if set(start) & set(goal):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")


# In[ ]:






Measured memory_bytes: 54732
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using ll = long long;
constexpr int INF = 1e9;
constexpr long long LINF = 1e18;
constexpr long long MOD = 1e9 + 7;

signed main() {
    string a;
    cin >> a;
    int n = a.size();
    int dp[n + 2];
    fill(dp, dp + n + 2, INF);
    dp[n] = 1;
    dp[n + 1] = 0;
    int nxt[n + 1][26];
    fill(nxt[0], nxt[n + 1], n);
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < 26; j++) {
            nxt[i][j] = nxt[i + 1][j];
        }
        nxt[i][a[i] - 'a'] = i;
        for (int j = 0; j < 26; j++) {
            dp[i] = min(dp[i], dp[nxt[i][j] + 1] + 1);
        }
    }
    string ans;
    int cur = 0;
    while(cur < n){
        for (int i = 0; i < 26; i++){
            if(dp[cur] == dp[nxt[cur][i] + 1] + 1){
                ans.push_back('a' + i);
                cur = nxt[cur][i] + 1;
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 24860
#include<iostream>
#include<cstdio>
using namespace std;
int a,b,ans;
int main()
{
    cin>>a>>b;
    if((a+b)%2==0)
    ans=(a+b)/2;
    else 
    ans=(a+b)/2+1;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
<?php

[$N] = fscanf(STDIN, "%d");
$map = array_fill(0,19,array_fill(0,19,0));
//$echo = "";
for($i=0;$i<$N;$i++){
    [$A] = fscanf(STDIN, "%s");
    $ex = explode(".",$A);
    if(!isset($ex[1])){
        $ex[1]=0;
    }else{
        $ex[1] = str_pad($ex[1],9,0);
    }
    $A = (int) ($ex[0] * 1000000000 + (int)$ex[1]);
//    echo $A;
    $ni = 0;
//    $echo .= $A;
    while($A%2 === 0 && $ni < 18){
        $A/=2;
        $ni++;
    }
    if($ni > 18){
        $ni = 18;
    }
    $go = 0;
    while($A%5 === 0 && $go < 18){
        $A/=5;
        $go++;
    }
    if($go > 18){
        $go = 18;
    }
//    $echo .= " ".$ni." ".$go.PHP_EOL;
    $map[$ni][$go]++;

}
//echo $echo;
$ans = 0;
for($i=0;$i<=18;$i++){
    foreach($map[$i] as $key => $value){
        if($value === 0){
            continue;
        }

        for($j=0; $j<=18;$j++){
            if($i+ $j < 18){
                continue;
            }
            foreach($map[$j] as $t_key => $t_value){

                if($t_value === 0){
                    continue;
                }
//                if($i === $j && $t_key  < $key){
//                    continue;
//                }
                if($t_key + $key >= 18){
                    if($i === $j && $t_key === $key){
                        $ans += (($value) * ($t_value -1));
//                        echo $i." ".$key." ".$j." ".$t_key.PHP_EOL;
//                        echo  ($value - 1) * ($t_value - 1).PHP_EOL;
                    }else{
                        $ans += ($value * $t_value);
//                        echo $i." ".$key." ".$j." ".$t_key.PHP_EOL;
//                        echo  $value * $t_value.PHP_EOL;
                    }

                }
            }
        }

    }


}
//echo $ans.PHP_EOL;
echo $ans/2;

Measured memory_bytes: 16236
#include<bits/stdc++.h>
#define ll long long
#define int long long
#define sze 10009
using namespace std;
int n,w;
string s1,s2;
string res="";



void dp_fn( int m, int n )
{
   int L[m+1][n+1];

   /* Following steps build L[m+1][n+1] in bottom up fashion. Note
      that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
   for (int i=0; i<=m; i++)
   {
     for (int j=0; j<=n; j++)
     {
       if (i == 0 || j == 0)
         L[i][j] = 0;
       else if (s1[i-1] == s2[j-1])
         L[i][j] = L[i-1][j-1] + 1;
       else
         L[i][j] = max(L[i-1][j], L[i][j-1]);
     }
   }

   // Following code is used to print LCS
   int index = L[m][n];

   // Create a character array to store the lcs string
   char lcs[index+1];
   lcs[index] = '\0'; // Set the terminating character

   // Start from the right-most-bottom-most corner and
   // one by one store characters in lcs[]
   int i = m, j = n;
   while (i > 0 && j > 0)
   {
      // If current character in X[] and Y are same, then
      // current character is part of LCS
      if (s1[i-1] == s2[j-1])
      {
          lcs[index-1] = s1[i-1]; // Put current character in result
          i--; j--; index--;     // reduce values of i, j and index
      }

      // If not same, then find the larger of two and
      // go in the direction of larger value
      else if (L[i-1][j] > L[i][j-1])
         i--;
      else
         j--;
   }

   // Print the lcs
   cout  << lcs<<endl;
}


int32_t main(){
      cin>>s1>>s2;
      int n1=s1.length();
      int n2=s2.length();

      dp_fn(n1,n2);
      //cout<<res<<endl;


}


Measured memory_bytes: 70656
#include<stdio.h>
 
long long Merge(int A[],int left,int mid,int right){
  int n1=mid-left;
  int n2=right-mid;
  int i,j,k;
  int L[n1+1],R[n2+1];
  long long res=0;
  for(i=0;i<n1;i++)L[i]=A[left+i];
  for(i=0;i<n2;i++)R[i]=A[mid+i];
  L[n1]=1000000001;
  R[n2]=1000000001;
   
  i=j=0;
  for(k=left;k<right;k++){
    if(L[i]<=R[j]){
      A[k]=L[i];
      i++;
    }else{
      A[k]=R[j];
      j++;
      res+= (long long)n1- (long long)i;
    }
  }
  return res;
}
 
long long Merge_Sort(int A[],int left,int right){
  int mid;
  long long res=0;
  if(left+1<right){
    mid=(left+right)/2;
 
    res+=Merge_Sort(A,left,mid);
    res+=Merge_Sort(A,mid,right);
    res+=Merge(A,left,mid,right);
     
  }
  return res;
}
 
int main(){
  int i,n,S[200000];
  long long x;
  scanf("%d",&n);
  for(i=0;i<n;i++)scanf("%d",&S[i]);
 
  x=Merge_Sort(S,0,n);
  printf("%ld\n",x);
  return 0;
}

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

int main() {
	int d, n; scanf("%d%d", &d, &n);

	if (n == 100) ++n; // 100番目はDが繰り上がるため
	int ans = pow(100, d) * n;

	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner

object Main {
  def main(args: Array[String]) {
    if (args.length > 0 && args(0) == "TEST") {
      println(test())
    } else {
      val input = io.Source.stdin.getLines().mkString("\n")
      println(solve(input).trim())
    }
  }

  def numWithNbits(n: Int): Int = (1 << n) - 1
  def checkBitOn(n: Int, b: Int): Int = (n >> (b - 1)) & 1
  def countBitsOn(n: Int, bl: List[Int]): Int = bl match {
    case Nil => 0
    case bh::bt => checkBitOn(n, bh) + countBitsOn(n, bt)
  }

  def isAllOn(n: Int, is: List[(List[Int], Int)]): Boolean = is match {
    case Nil => true
    case (bits, parity) :: irs => {
      val bitsCount = countBitsOn(n, bits)
      if (bitsCount % 2 != parity) false
      else isAllOn(n, irs)
    }
  }

  def solve(input: String): String = {
    val s: Scanner = new Scanner(input)
    val (n, m) = (s.nextInt, s.nextInt)
    val ks = List.fill(m)(List.fill(s.nextInt)(s.nextInt))
    val ps = List.fill(m)(s.nextInt)
    val is = ks.zip(ps)
    (0 to numWithNbits(n)).count(i => isAllOn(i, is)).toString()
  }

  val tests = List(
    """2 2
      |2 1 2
      |1 2
      |0 1
    """.stripMargin -> """1""",
    """2 3
      |2 1 2
      |1 1
      |1 2
      |0 0 1
    """.stripMargin -> """0""",
    """5 2
      |3 1 2 5
      |2 2 3
      |1 0
    """.stripMargin -> "8"
  )

  def test(): String = tests.map { case (i, o) => (i.trim(), o.trim()) }
    .zipWithIndex.map {
    case ((input, outputExpect), i) =>
      val output = solve(input).trim()
      val tnum = i + 1
      s"test$tnum:" + (
        if (output == outputExpect) "Passed"
        else s"Failed\nexpect:\n$outputExpect\noutput:\n$output")
  }
    .mkString("\n")
}

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

from collections import deque

N,*A = map(int,read().split())

B = deque()
for a in A:
    B.append(a)
    while True:
        if len(B) < 3:
            break
        x,y,z = B[-3],B[-2],B[-1]
        if x<=y>=z:
            B.pop()
            B.pop()
            B[-1] = x+z-y
            continue
        break

get = []
while B:
    if B[0] > B[-1]:
        x = B.popleft()
    else:
        x = B.pop()
    get.append(x)

answer = sum(get[::2]) - sum(get[1::2])

print(answer)

Measured memory_bytes: 3572
import itertools
import math

n, d = list(map(int, input().split()))
x_list = []

for _ in range(n):
    x_list.append(list(map(int, input().split())))

# 全探索でいける？
l = list(range(0, n))
c = itertools.combinations(l, 2)
integer_count = 0

for v in c:
    a_index = v[0]
    b_index = v[1]
    work_list = []
    for a, b in zip(x_list[a_index], x_list[b_index]):
        work_list.append((a - b) ** 2)
    length = math.sqrt(sum(work_list))

    if length.is_integer():
        integer_count += 1

print(integer_count)


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

using namespace std;

using i64 = int64_t;

const i64 MOD = 1e9 + 7;


signed main(){
    i64 n;
    cin >> n;
    vector<i64> a(n);
    for(auto& x : a)
        cin >> x;
    vector<vector<i64>> edges(n), childs(n);
    for(i64 i = 0; i < n - 1; ++i){
        i64 s, t;
        cin >> s >> t;
        --s, --t;
        edges[s].emplace_back(t);
        edges[t].emplace_back(s);
    }
    vector<i64> flag(n, 0);

    vector<i64> score = a;
    vector<i64> score_back = a;

    function<void(i64)> f = [&](i64 from){
        vector<pair<i64,i64>> sc;
        for(auto& to : edges[from]){
            if(flag[to])
                continue;
            flag[to] = 1;
            childs[from].emplace_back(to);
            f(to);
            sc.emplace_back(max(0L, score_back[to] - 2), max(0L, score[to] - 1));
        }
        i64 dif_max = 0;
        i64 sum = 0;
        for(auto& scc : sc){
            dif_max = max(dif_max, scc.second - scc.first);
            sum += scc.first;
        }
        score_back[from] += sum;
        score[from] += sum + dif_max;
    };
    flag[0] = 1;
    f(0);

    vector<i64> ans(n, 0);

    function<void(i64,i64,i64)> g = [&](i64 from, i64 par_val, i64 par_val_back){
        vector<pair<i64,i64>> v_diff;
        i64 sum = 0;
        sum += max(0L, par_val_back);
        v_diff.emplace_back(max(0L, par_val) - max(0L, par_val_back), -1);
        for(auto& to : childs[from]){
            sum += max(0L, score_back[to] - 2);
            v_diff.emplace_back(max(0L, score[to] - 1) - max(0L, score_back[to] - 2), to);
        }
        sort(v_diff.begin(), v_diff.end(), greater<pair<i64,i64>>());

        ans[from] = a[from] + sum + v_diff[0].first;

        for(auto& to : childs[from]){
            i64 nex_v = sum - max(0L, score_back[to] - 2);
            i64 nex_v_diff = v_diff[v_diff[0].second == to].first;
            g(to, nex_v + a[from] + nex_v_diff - 1, nex_v + a[from] - 2);
        }
    };
    g(0, 0, 0);

    cout << *max_element(ans.begin(), ans.end()) << endl;

}



Measured memory_bytes: 37904
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
string s;
LL ans,len;
LL count(LL a,LL i)
{
	LL s=0;
	LL cnt=i;
	i=pow(2,i);
	s+=i;
	for(int j=1;j<=len-cnt-1;j++)
	{
		s=s*10+i;
		i*=2;
	}
	return a*s;
}
int main()
{
	cin>>s;
	len=s.length();
	for(LL i=0;i<s.length();i++)
	{
		ans+=count(s[i]-'0',i);
	}
	printf("%lld",ans);
	return 0;
}


Measured memory_bytes: 384
package main

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

func main() {
	io := newIo()
	defer io.Flush()
	N := io.NextInt()
	S := io.Next()
	Q := io.NextInt()
	K := make([]int, Q)
	for q := range K {
		K[q] = io.NextInt()
	}

	var dList []int
	sumM := make([]int, N+1)
	sumC := make([]int, N+1)
	sumMC := make([]int, N+1)
	sumM[0] = 0
	sumC[0] = 0
	sumMC[0] = 0

	for i, s := range S {
		sumC[i+1] = sumC[i]
		sumMC[i+1] = sumMC[i]

		if s == 'D' {
			dList = append(dList, i)
		}
		if s == 'M' {
			sumM[i+1] = sumM[i] + 1
		} else {
			sumM[i+1] = sumM[i]
		}
		if s == 'C' {
			sumC[i+1] = sumC[i] + 1
			sumMC[i+1] = sumMC[i] + sumM[i]
		} else {
			sumC[i+1] = sumC[i]
			sumMC[i+1] = sumMC[i]
		}
	}
	for _, k := range K {
		result := 0
		for _, d := range dList {
			to := d + k
			if to > N {
				to = N
			}
			result += (sumMC[to] - sumMC[d]) - ((sumC[to] - sumC[d]) * sumM[d])
		}
		fmt.Println(result)
	}
}

type io struct {
	reader    *bufio.Reader
	writer    *bufio.Writer
	tokens    []string
	nextToken int
}

func newIo() *io {
	return &io{
		reader: bufio.NewReader(os.Stdin),
		writer: bufio.NewWriter(os.Stdout),
	}
}

func (io *io) Flush() {
	err := io.writer.Flush()
	if err != nil {
		panic(err)
	}
}

func (io *io) NextLine() string {
	var buffer []byte
	for {
		line, isPrefix, err := io.reader.ReadLine()
		if err != nil {
			panic(err)
		}
		buffer = append(buffer, line...)
		if !isPrefix {
			break
		}
	}
	return string(buffer)
}

func (io *io) Next() string {
	for io.nextToken >= len(io.tokens) {
		line := io.NextLine()
		io.tokens = strings.Fields(line)
		io.nextToken = 0
	}
	r := io.tokens[io.nextToken]
	io.nextToken++
	return r
}

func (io *io) NextInt() int {
	i, err := strconv.Atoi(io.Next())
	if err != nil {
		panic(err)
	}
	return i
}

func (io *io) NextFloat() float64 {
	i, err := strconv.ParseFloat(io.Next(), 64)
	if err != nil {
		panic(err)
	}
	return i
}

func (io *io) PrintLn(a ...interface{}) {
	fmt.Fprintln(io.writer, a...)
}

func (io *io) Printf(format string, a ...interface{}) {
	fmt.Fprintf(io.writer, format, a...)
}

func (io *io) PrintIntLn(a []int) {
	b := []interface{}{}
	for _, x := range a {
		b = append(b, x)
	}
	io.PrintLn(b...)
}

func (io *io) PrintStringLn(a []string) {
	b := []interface{}{}
	for _, x := range a {
		b = append(b, x)
	}
	io.PrintLn(b...)
}

func log(name string, value interface{}) {
	fmt.Fprintf(os.Stderr, "%s=%+v\n", name, value)
}


Measured memory_bytes: 59392
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iomanip>
using namespace std;

typedef long long ll;

#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=(b-1);i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;

#define MOD 1000000007

int main() {
  ll a,b;
  cin>>a>>b;
  a %= 500;
  if(a<=b){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 256