akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
int main(void){
  int n,d,i,j,k,s,ans=0;
  cin >> n >> d;
  vector<int> sq{1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361
                 ,400,441,484,529,576,625,676,729,784,841,900,961,1024,1089,1156
                 ,1225,1296,1369,1444,1521,1600,1681,1764,1849,1936,2025,2116,2209
                 ,2304,2401,2500,2601,2704,2809,2916,3025,3136,3249,3364,3481,3600
                 ,3721,3844,3969,4096,4225,4356,4489,4624,4761,4900,5041,5184,5329
                 ,5476,5625,5776,5929,6084,6241,6400,6561,6724,6889,7056,7225,7396
                 ,7569,7744,7921,8100,8281,8464,8649,8836,9025,9216,9409,9604,9801
                 ,10000,10201,10404,10609,10816,11025,11236,11449,11664,11881,12100
                 ,12321,12544,12769,12996,13225,13456,13689,13924,14161,14400,14641
                 ,14884,15129,15376,15625,15876};
  vector<vector<int>> p(n+3,vector<int>(d+3,0));
  for (i=0;i<n;i++) for (j=0;j<d;j++) cin >> p.at(i).at(j);
  for (i=0;i<n-1;i++) for (j=i+1;j<n;j++){
    s=0;
    for (k=0;k<d;k++) s+=(p.at(i).at(k)-p.at(j).at(k))*(p.at(i).at(k)-p.at(j).at(k));
    for (k=0;k<126;k++) if (s==sq.at(k)) break;
    if (k!=126) ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
N=int(input())
h=list(map(int,input().split()))
dp=[0]*(N+1)
dp[0]=0
dp[1]=abs(h[1]-h[0])
for i in range(1,N-1):
	dp[i+1]=min(dp[i-1]+abs(h[i+1]-h[i-1]),dp[i]+abs(h[i+1]-h[i]))
print(dp[N-1])

Measured memory_bytes: 13928
#include  <iostream>
#include  <stdio.h>
#include <algorithm>
#include <map>
#include <math.h>

using namespace std;
#include <vector>
#define rep(i,n) for (ll i = 0; i < (n) ; i++)
#define INF 1e9
#define llINF 1e18
#define base10_4 10000      //1e4
#define base10_5 100000     //1e5
#define base10_6 1000000    //1e6
#define base10_7 10000000   //1e7
#define base10_8 100000000  //1e8
#define base10_9 1000000000 //1e9

#define MOD 1000000007
#define pb push_back
#define ll long long
#define ull unsigned long long
#define vint vector<int>
#define vll vector<ll>

//#include <stack>
//#include <queue>

// #include <iomanip>
//  cout << fixed << setprecision(15) << y << endl;

string ans_Yes = "Yes"; 
string ans_No = "No"; 
string ans_yes = "yes"; 
string ans_no = "no"; 

ll A;
ll B;
ll C;
ll N;
ll M;
ll K;

ll ltmp;
string stmp;
double dtmp;

vector<ll> G[2*base10_5+10];
ll root_point[2*base10_5+10]={};
ll value[2*base10_5+10]={};
ll visited[2*base10_5+10]={};


void calcValue(ll target,ll parent_point){
    value[target] += parent_point;
    visited[target]=1;

    rep(gi,G[target].size()){
        ll next = G[target][gi];
        if(visited[next]==0) calcValue(next,value[target]);
    }
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    cin >> M;

    ll from,to;
    rep(ni,N-1){
        cin >> from;
        cin >> to;
        G[from].push_back(to);
        G[to].push_back(from);
    }
    ll target,point;
    rep(mi,M){
        cin >> target;
        cin >> point;
        root_point[target]+=point;
    }
    for( ll ni = 1 ; ni <=N ; ni++ ){
        value[ni] = root_point[ni];
    }
    calcValue(1,0);

    for( ll ni = 1 ; ni <=N ; ni++ ){
        cout << value[ni] << " ";
    }
   

}

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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repr(i, n) for(int i = (int)(n); i >= 0; i--)
#define repm(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define repmr(i, m, n) for(int i = (int)(n); i >= (int)(m); i--)
#define all(x) (x).begin(),(x).end()
#define inf 2e9

using namespace std;
typedef long long int lli;
typedef long long ll;

vector<string> split(string str, char del) {
    int first = 0;
    int last = str.find_first_of(del);
 
    vector<string> result;
 
    while (first < str.size()) {
        string subStr(str, first, last - first);
 
        result.push_back(subStr);
 
        first = last + 1;
        last = str.find_first_of(del, first);
 
        if (last == string::npos) {
            last = str.size();
        }
    }
 
    return result;
}

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

    vector<string> ss = split(s,',');

    cout << ss[0] << " " << ss[1] << " " << ss[2] << endl;
}


Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

A, B, C, D = MAP()

taka = -(-C//B)
ao = -(-A//D)
if taka <= ao:
	print("Yes")
else:
	print("No")


Measured memory_bytes: 10000
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=100005,INF=1<<30;
vector<pair<int,int>> S[MAX];
vector<int> dis(MAX);

void dijkstra(int u){
    dis[u]=0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> PQ;
    
    PQ.push(make_pair(0,u));
    while(!PQ.empty()){
        int a=PQ.top().first;
        int b=PQ.top().second;
        PQ.pop();
        if(dis[b]<a) continue;
        for(int i=0;i<S[b].size();i++){
            int c=S[b][i].first;
            int d=S[b][i].second;
            if(dis[c]>dis[b]+d){
                dis[c]=dis[b]+d;
                PQ.push(make_pair(dis[c],c));
            }
        }
    }
    return;
}//a,dが長さ

int main(){
    
    int K;cin>>K;
    for(int i=0;i<K;i++){
        dis[i]=INF;
    }
    
    for(int i=0;i<K;i++){
        S[i].push_back({(i+1)%K,1});
        S[i].push_back({(i*10)%K,0});
    }
    
    dijkstra(1);
    
    cout<<dis[0]+1<<endl;
}


Measured memory_bytes: 6904
fun main(args: Array<String>) {
    val (n, m, c) = readLine()!!.split(" ").map { it.toInt() }
    val b = readLine()!!.split(" ").map { it.toInt() }
    val a = (1..n).map { readLine()!!.split(" ").map { it.toInt() } }
    var count = 0
    var sum = 0
    for (value in a) {
        for (i in value.indices) {
            sum += value[i] * b[i]
        }
        sum += c
        if (sum > 0) count++
        sum = 0
    }

    println(count)
}

Measured memory_bytes: 37860
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i=0;i < (int)(n);i++)

int main(){
  int n;
  string s;
  cin >> n;
  int mx=0;
  map<string,int> q;
  rep(i,n){
    string t;
    cin >> t;
    if (q.count(t)) q[t]++;
    else q[t]=0;
    mx=max(q[t],mx);
  }
  vector<string> ans;
  for(auto w:q){
    if (w.second== mx){
      ans.push_back(w.first);
    }
  }
  sort(ans.begin(),ans.end());
  for (int j=0;j < ans.size();j++){
    cout << ans[j] << endl;
  }

  return 0;
}



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

int main(int argc, char const *argv[])
{
	 ios_base::sync_with_stdio(false);
     cin.tie(NULL);
	
  int n; cin>>n;
  string s;
  cin>>s;
  if(n % 2 ==1){
    cout<<"No\n";
    return 0;
  }
  string s1 = s.substr(0,n/2);
  string s2 = s.substr(n/2);
  if(s1==s2){
    cout<<"Yes\n";
  }else{
    cout<<"No\n";
  }
  
  
  
	return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
ABs = []
for i in range(N):
  A, B = map(int, input().split())
  ABs.append((A, B))
ABs.sort(key=lambda AB: AB[0])
#print(ABs)
r = 0
m = 0
for i in range(N):
  A, B = ABs[i]
  if m+B >= M:
    r += A*(M-m)
    break
  else:
    r += A*B
    m += B
print(r)


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

int main(){
    int h, w, k; cin >> h >> w >> k;
    vector<string> g(h); int b = 0;
    for (auto i = 0; i < h; i++) {
        cin >> g[i];
        for (auto j = 0; j < w; j++) if(g[i][j] == '#') b++;
    }

    int ans = 0;
    for (auto i = 0; i < (1 << h); i++) {
        for (auto j = 0; j < (1 << w); j++) {
            int rest = 0;
            for (auto l = 0; l < h; l++) {
                for (auto m = 0; m < w; m++) {
                    if(i & (1 << l) or j & (1 << m)) {
                        if(g[l][m] == '#') rest++;
                    }
                }
            }
            if((b - rest) == k) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3564
loop do
  h, w = gets.chomp.split(" ").map(&:to_i)
  break if h == 0 && w == 0
  puts "#" * w
  while (h - 2 > 0) do
    puts "#" + "." * (w - 2) + "#" 
    h -= 1
  end
  puts "#" * w if h >= 2
  puts ""
end

Measured memory_bytes: 8840
#include <bits/stdc++.h>
#define ll long long
#define ar array
#define AC ios_base::sync_with_stdio(0);
const int M = 1e9+7;
using namespace std;

int main(){
    AC
    int k;
    cin>>k;
    int sum=0, len=1;
    while(1){
        sum = sum*10+7;
        sum%=k;
        if(sum==0){
            cout<<len<<endl;
            return 0;
        }
        if(len>k){
            cout<<-1<<endl;
            return 0;
        }
        len++;
    }
}

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

int main() {
  long n, a, b;
  cin >> n >> a >> b;
  long w = n / (a + b);
  long r = n % (a + b);
  long m = r > a ? a : r;
  long result = w * a + m;
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N,M;
    int i;
    cin >> N >> M;
    long int a;
    long int sum =0;
    for(i=0;i<M;i++){
        cin >> a;
        sum += a;
    }
    if(sum>N)cout << -1 << endl;
    else cout << N-sum << endl;
}

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

using ll = long long;
#define int long long
using P = pair<int, int>;

#define LOG(variable) cerr << #variable":\t" << (variable) << endl
#define LOGCON(i, container) for(int (i) = 0; (i) < (container).size(); ++(i)) cerr << (i) << ":\t" << (container)[(i)] << endl
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(i, r, n) for (int i = (r); i < (n); ++i)
#define REPR(i, n) for(int i = (n); i >= 0; --i) // from n to 0
#define REPRS(i, n, r) for(int i = (n); i >= (r); --i) // from n to r
#define REPOBJ(itr, obj) for(auto itr = (obj).begin(); itr != (obj).end() ; ++itr)
#define REPROBJ(itr, obj) for(auto itr = (obj).rbegin(), e = (obj).rend(); itr != e; ++itr)
#define COUTB(x) cout << (x) << "\n"
#define COUTS(x) cout << (x) << " "
#define PB push_back
#define SORT(obj) sort((obj).begin(), (obj).end())
#define SORTR(obj) sort((obj).begin(), (obj).end(), greater<>())
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define PI (acos(-1))
template<typename T = int>
T in() {T a; cin >> a; return a;}
/***** MAIN *****/
signed main() {
  int n; cin >> n;
  vector<int> v(n);
  REP(i,n) {
    cin >> v[i];
  }
  // sort(ALL(v));
  int ans = 0;
  REP(i,n) {
    REPS(j, i+1, n) {
      REPS(k, j+1, n) {
        if(v[i] == v[j] || v[i] == v[k] || v[k] == v[j]) continue;
        if(v[i] >= v[j] + v[k]) continue;
        if(v[j] >= v[i] + v[k]) continue;
        if(v[k] >= v[j] + v[i]) continue;
        ++ans;
      }
    }
  }
  cout << ans;
  cout << "\n";
  return 0;
}
/***** MAIN *****/


Measured memory_bytes: 3624
n,x = map(int,input().split())
l = list(map(int,input().split()))

a = [sum(l[:x+1]) for x in range(len(l))]
b = []
for i in range(len(a)):
    if a[i] <= x:
        b.append(a[i])

print(b.index(b[-1])+2)

Measured memory_bytes: 3060
#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <algorithm>
    #include <queue>
    #include <stack>
     
    using namespace std;
    typedef long long ll;
    typedef vector<ll> vl;
    typedef vector<vl> vvl;
    typedef pair<ll,ll> P;
    typedef vector<P> vpl;
    #define rep(i,n) for(ll i=0; i<(n); i++)
    #define REP(i,a,b) for(ll i=(a); i<(b); i++)
    #define all(x) (x).begin(), (x).end()
    #define rall(x) (x).rbegin(), (x).rend()
    const int inf = 1<<30;
    const ll linf = 1LL<<62;
    const int mod = 1e9 + 7;
    const int MAX = 510000;
    const int V = 100005;
     
    int main(){
        ll n,k; cin >> n >> k;
        ll a = 1;
        rep(i,n){
            a = min(a*2,a+k);
        }
        cout << a << endl;
    }

Measured memory_bytes: 256
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = int(a); i < int(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
const long long INFLL = 1LL << 60;
const int INFINT = 1 << 30;
const long long MOD = 1e9 + 7;

template <class T> void vecout(T V) {
    auto t = V.begin();
    while(t != V.end()) {
        cout << *t++;
        if(t != V.end()) cout << " ";
    }
    cout << endl;
};

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

    int n, m;
    cin >> n;
    vector<int> A(n);
    rep(i, n) cin >> A[i];
    cin >> m;
    vector<int> B(m);
    rep(i, m) cin >> B[i];

    cout << (A < B) << "\n";
}



Measured memory_bytes: 3220
import java.io.BufferedReader;
import java.io.*;
import java.io.IOException;
import java.io.InputStream;
import java.util.StringTokenizer;

public class Main  {

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int a=sc.nextInt();
		int b= sc.nextInt();
		int g = gcd(a, b);
		System.out.println(1l*a*b/g);
		
	}
	static int gcd(int a,int b) {
		if(a==0)return b;
		return gcd(b%a,a);
	}
	  static class Scanner {
	        StringTokenizer st;
	        BufferedReader br;
	 
	        public Scanner(FileReader r) {
	            br = new BufferedReader(r);
	        }
	 
	        public Scanner(InputStream s) {
	            br = new BufferedReader(new InputStreamReader(s));
	        }
	 
	        public String next() throws IOException {
	            while (st == null || !st.hasMoreTokens())
	                st = new StringTokenizer(br.readLine());
	            return st.nextToken();
	        }
	 
	        public int nextInt() throws IOException {
	            return Integer.parseInt(next());
	        }
	 
	        public long nextLong() throws IOException {
	            return Long.parseLong(next());
	        }
	 
	        public String nextLine() throws IOException {
	            return br.readLine();
	        }
	 
	        public double nextDouble() throws IOException {
	            String x = next();
	            StringBuilder sb = new StringBuilder("0");
	            double res = 0, f = 1;
	            boolean dec = false, neg = false;
	            int start = 0;
	            if (x.charAt(0) == '-') {
	                neg = true;
	                start++;
	            }
	            for (int i = start; i < x.length(); i++)
	                if (x.charAt(i) == '.') {
	                    res = Long.parseLong(sb.toString());
	                    sb = new StringBuilder("0");
	                    dec = true;
	                } else {
	                    sb.append(x.charAt(i));
	                    if (dec)
	                        f *= 10;
	                }
	            res += Long.parseLong(sb.toString()) / f;
	            return res * (neg ? -1 : 1);
	        }
	 
	        public boolean ready() throws IOException {
	            return br.ready();
	        }
	    }
}


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

#define ll long long
#define ar array

//lets hash!
const int p=37, MOD=1e9+9;
int n, oc[26];
ll ans=0;
string s[200000];
map<ar<int, 2>, ar<int, 26>> cnt; //<num letters, hash>

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

	cin >> n;
	for (int i=0; i<n; ++i)
		cin >> s[i];
	sort(s, s+n, [](const string &a, const string &b) {return a.size()>b.size();});
	for (int i=0; i<n; ++i) {
		for (char c: s[i])
			++oc[c-'a'];
		ll hsh=0, pp=1;
		for (int j=s[i].size()-1; j>=0; --j) {
			int num=(s[i].size()-1)-j;
			ar<int, 2> cur={num, (int)hsh};
			ar<int, 26> &x=cnt[cur];
			if (j==0) {
				ans+=x[s[i][j]-'a'];
			}
			for (int k=0; k<26; ++k)
				if (oc[k]>0)
					++x[k];
			--oc[s[i][j]-'a'];
			hsh=(hsh+pp*(s[i][j]-'a'+1))%MOD;
			pp=pp*p%MOD;
		}
	}
	cout << ans;
	return 0;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
*/


Measured memory_bytes: 166556
import sys


input = sys.stdin.readline
N = int(input())
S = [input().replace('\n', '')[::-1] for _ in range(N)]
S1 = []
Slong = []
for s in S:
    if len(s) == 1:
        S1.append(s)
    else:
        Slong.append(s)

ans = 0
# 2文字以上同士のついを数える
Slong = sorted(Slong, key=lambda x: x[:-1])
for i in range(len(Slong)):
    s = Slong[i]
    j = i + 1
    n = len(s)-1
    while j<len(Slong) and Slong[j][:n] == s[:n]:
        ans += Slong[j][n:].find(s[-1]) != -1
        j += 1

# 1文字同士
S1 = sorted(S1)
for i in range(len(S1)):
    s = S1[i]
    j = i + 1
    while j<len(S1) and S1[j] == s:
        ans += 1
        j += 1


# 1->2以上
a2z = [chr(i) for i in range(97, 97+26)]
wcnt = {i: 0for i in a2z}
for s in Slong:
    for c in set(s):
        wcnt[c] += 1
for s in S1:
    ans += wcnt[s]
print(ans)


Measured memory_bytes: 167792
#include <bits/stdc++.h>
#define reg register
#define ll long long
#define ull unsigned long long
#define db double
#define pi pair<int, int>
#define pl pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vpi vector<pi>
#define vpl vector<pl>
#define pb push_back
#define er erase
#define SZ(x) (int) x.size()
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mkp make_pair
#define dmin(x, y) ((x) < (y) ? (x) : (y))
#define dmax(x, y) ((x) > (y) ? (x) : (y))
#define checkmax(x, y) ((x) < (y) ? ((x) = (y)) : (x))
#define checkmin(x, y) ((x) > (y) ? ((x) = (y)) : (x))
#define ms(data_name) memset(data_name, 0, sizeof(data_name))
#define msn(data_name, num) memset(data_name, num, sizeof(data_name))
#define For(i, j) for(reg int (i) = 1; (i) <= (j); ++(i))
#define For0(i, j) for(reg int (i) = 0; (i) < (j); ++(i))
#define Forx(i, j, k) for(reg int (i) = (j); (i) <= (k); ++(i))
#define Forstep(i , j, k, st) for(reg int (i) = (j); (i) <= (k); (i) += (st))
#define fOR(i, j) for(reg int (i) = (j); (i) >= 1; (i)--)
#define fOR0(i, j) for(reg int (i) = (j) - 1; (i) >= 0; (i)--)
#define fORx(i, j, k) for(reg int (i) = (k); (i) >= (j); (i)--)
#define tour(i, u) for(reg int (i) = head[(u)]; (i) != -1; (i) = nxt[(i)])
using namespace std;
char ch, B[1 << 20], *S = B, *T = B;
#define getc() (S == T && (T = (S = B) + fread(B, 1, 1 << 20, stdin), S == T) ? 0 : *S++)
#define isd(c) (c >= '0' && c <= '9')
int rdint() {
  int aa, bb;
  while(ch = getc(), !isd(ch) && ch != '-');
  ch == '-' ? aa = bb = 0 : (aa = ch - '0', bb = 1);
  while(ch = getc(), isd(ch))
    aa = aa * 10 + ch - '0';
  return bb ? aa : -aa;
}
ll rdll() {
  ll aa, bb;
  while(ch = getc(), !isd(ch) && ch != '-');
  ch == '-' ? aa = bb = 0 : (aa = ch - '0', bb = 1);
  while(ch = getc(), isd(ch))
    aa = aa * 10 + ch - '0';
  return bb ? aa : -aa;
}
ll a, b, c, d;
ll gcd(ll a, ll b) {
  return !b ? a : gcd(b, a % b);
}
ll lcm(ll a, ll b) {
  return a / gcd(a, b) * b;
}
inline void work() {
  a = rdll();
  b = rdll();
  c = rdll();
  d = rdll();
  cout << (b - a + 1) - (b / c - (a - 1) / c) - (b / d - (a - 1) / d) + (b / lcm(c, d) - (a - 1) / lcm(c, d)) << endl;
}
int main() {
  // freopen("input.txt", "r", stdin);
  work();
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;

#define all(v) v.begin(), v.end()

const ll mod=1000000007;

ll countBits(ll in){
  int res=0;
  for(;in>0;in>>=1){
    if((in&0x01)!=0){
      res++;
    }
  }
  return res;
}

template<typename T>
void show2dVector(vector<vector<T>>& v){
  for(int i=0;i<v.size();i++){
    int m=v[i].size();
    cout<<i<<" : ";
    for(int j=0;i<m;i++){
      cout<<v[i][j]<<" ";
    }
    cout<<endl;
  }
}

void bfs(const vector<vector<int>>&g, int v, vector<bool>& seen){
  seen[v]=true;
  cout<<v<<" ";
  for(auto next: g[v]){
    if(seen[next]){
      continue;
    }
    bfs(g,next,seen);
  }
}

bool dfs(vector<vector<int>> &g,int start,int goal,vector<bool>&seen){
  bool res=false;
  seen[start]=true;
  if(start==goal){
    return true;
  }
  for(auto next: g[start]){
    if(seen[next]){
      continue;
    }
    res=dfs(g,next,goal,seen);
    if(res){
      break;
    }
  }
  return res;
}

ll gcd(ll a,ll b) {
  return b? gcd(b,a%b): a;  
}
ll lcm(ll a,ll b) {
  return a*b/gcd(a,b);
}
bool isLowerCase(char c){
  return (c>='a'&&c<='z');
}

ll powm(ll a,ll n, ll m){
  ll ret=1;
  while(n>0){
    if(n%2==1){
      ret=(ret*a)%m;
    }
    n>>=1;
    a=(a*a)%m;
  }
  return ret;
}

const string yesno(bool ans){
  return (ans?"Yes":"No");
}
int main() {
  int n,k;cin>>n>>k;
  vector<int> a(n+1);
  for(int i=1;i<=n;i++){
    cin>>a[i];
  }
  for(int i=0;i<k;i++){
    vector<int> val(n+1,0);
    for(int j=0;j<n;j++){
      int idx=j+1;
      int l,r;
      l=max(idx-a[idx],1);
      r=min(idx+a[idx],n);
      val[l]++;
      if(r+1<=n){
        val[r+1]--;
      }
    }
    a[0]=0;
    for(int j=0;j<n;j++){
      int idx=j+1;
      a[idx]=a[idx-1]+val[idx];
    }
    int maxcnt=0;
    for(int index=0;index<n;index++){
      int p=index+1;
      if(a[p]==n){
        maxcnt++;
      }
    }
    if(maxcnt==n){
      break;
    }
  }
  for(int i=0;i<n;i++){
    cout<<a[i+1]<<" \n"[i==n-1?1:0];
  }
  return 0;
}


Measured memory_bytes: 4848
#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
  int N;
  //long long int a[3000];
  long long int v;
  scanf("%d", &N);

  long long int max = 0;

  for (int i = 0; i < N; i++) {
    scanf("%lld", &v);
    max += v - 1;
  }
  
  printf("%lld\n", max);
}


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

namespace CompetitiveProgCsLib
{
	class MainProg
	{
		static string R => Console.ReadLine();
		static int RI => int.Parse(R);
		static double RD => double.Parse(R);
		static int[] RIs => R.Split(' ').Select(int.Parse).ToArray();
		static double[] RDs => R.Split(' ').Select(double.Parse).ToArray();
		static void Out(object obj) => Console.WriteLine(obj);
		static void Outb(bool b) => Out(b ? "Yes" : "No");
		static void OutB(bool b) => Out(b ? "YES": "NO");

		static void Main(string[] args)
		{
			var n = RI;
			var list = GetPrimeList(55555).Where(x => x % 5 == 1);

			var ans = list.Take(n).ToArray();
			for (int i = 0;i < n;i++)
			{
				Console.Write(ans[i]);
				if (i + 1 != n) Console.Write(" ");
				else Out("");
			}
		}

		/// <summary>
		/// エラトステネスのふるい。nまでの素数リストを返す。
		/// 配列の要素が0でなければ素数
		/// </summary>
		/// <param name="n"></param>
		/// <returns></returns>
		public static int[] SieveOfEratosthenes(int n)
		{
			var primes = Enumerable.Range(0, n + 1).Select(i => i).ToArray();
			primes[1] = 0;
			for (int i = 2; i * i <= n; i++)
			{
				if (primes[i] != 0)
				{
					for (int j = i * i; j <= n; j += i) primes[j] = 0;
				}
			}
			return primes;
		}

		/// <summary>
		/// nまでの素数リストを作成する
		/// </summary>
		/// <param name="n"></param>
		/// <returns></returns>
		public static IEnumerable<int> GetPrimeList(int n)
		{
			return SieveOfEratosthenes(n).Where(x => x != 0);
		}
	}
}


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


int main() {
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++){
    cin>>a[i];
}
int res=1;
int low= a[0];
for(int i=1;i<n;i++){
    if(a[i]<low){
        low=a[i];
        res++;
    }
}
cout<<res;

  return 0;
}

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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(), (v).end()

typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, P> PP;

set<string> st;
string s,t;

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

	cin>>s>>t;
	REP(i,s.size()) {
		bool flg=true;
		REP(j,t.size()) {
			if(s[i+j]=='?') continue;
			if(s[i+j]!=t[j]) {
				flg=false;
				break;
			}
		}
		if(flg) {
			string tmp;
			REP(j,i) tmp+=(s[j]=='?'?'a':s[j]);
			tmp+=t;
			FOR(j,i+t.size(),s.size()) tmp+=(s[j]=='?'?'a':s[j]);
			st.insert(tmp);
		}
	}
	if(st.size()) cout<<*st.begin()<<endl;
	else cout<<"UNRESTORABLE"<<endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
typedef long long ll;
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 long long INF = 1LL << 60;
const int inf = 1001001001;
const int mod = 1000000007;
using pint=pair<ll,ll>;
 
// union by size + path having
class UnionFind {
public:
   vector <ll> par; // 各元の親を表す配列
   vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)
 
   // Constructor
   UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {
       for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
   }
   void init(ll sz_) {
       par.resize(sz_);
       siz.assign(sz_, 1LL);  // resize だとなぜか初期化されなかった
       for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
  }
 
   // Member Function
   // Find
   ll root(ll x) { // 根の検索
      while (par[x] != x) {
           x = par[x] = par[par[x]]; // x の親の親を x の親とする
       }
       return x;
  }
 
   // Union(Unite, Merge)
   bool unite(ll x, ll y) {
       x = root(x);
       y = root(y);
       if (x == y) return false;
       // merge technique（データ構造をマージするテク．小を大にくっつける)
       if (siz[x] < siz[y]) swap(x, y);
       siz[x] += siz[y];
       par[y] = x;
       return true;
  }
 
  bool same(ll x, ll y) { // 連結判定
       return root(x) == root(y);
  }
 
  ll size(ll x) { // 素集合のサイズ
      return siz[root(x)];
  }
};
 
ll modpow(ll x, ll n) {
   x = x%mod;
   if(n==0) return 1;  //再帰の終了条件
 
   else if(n%2==1) {
       return (x*modpow(x, n-1))%mod;  //nが奇数ならnを1ずらす
   }
   else return modpow((x*x)%mod, n/2)%mod;  //nが偶数ならnが半分になる
}
 
ll com(ll n, ll k) {
   ll x = 1;
   for(int i=n-k+1; i<=n; i++) {
      x = x*i%mod;
   }
 
   ll y = 1;
   for(int i=1; i<=k; i++) {
       y = y*i%mod;
   }
   y = modpow(y, mod-2);
 
   return x*y%mod;
}
 
int main(){

    ll n,a,b,cntb=0,tsuuka=0;
    string s;
    cin >> n >> a >> b >> s;
    rep(i,n){
        if(s[i]=='c') cout << "No" << endl;
        else if(s[i]=='a'){
            if(tsuuka<a+b){
                cout << "Yes" << endl;
                tsuuka++;
            }
            else cout << "No" << endl;
        }
        else if(s[i]=='b'){
            cntb++;
            if(tsuuka<a+b && cntb<=b){
                cout << "Yes" << endl;
                tsuuka++;
            }
            else cout << "No" << endl;
        }
    }
 
}

Measured memory_bytes: 896
#include <stdio.h>

int main(void) {
    int H, W;
    scanf("%d %d", &H, &W);

    char S[H][W];
    for (int i = 0; i < H; i++) {
        scanf("%s", S[i]);
    }

    int A[H][W];
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            A[i][j] = 0;
        }
    }

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (S[i][j] == '#') {
                A[i][j] = -10000;
                if (j < W - 1) {
                    A[i][j + 1]++;
                }
                if (j > 0) {
                    A[i][j - 1]++;
                }

                if (i < H - 1) {
                    A[i + 1][j]++;
                    if (j < W - 1) {
                        A[i + 1][j + 1]++;
                    }
                    if (j > 0) {
                        A[i + 1][j - 1]++;
                    }
                }

                if (i > 0) {
                    A[i - 1][j]++;
                    if (j < W - 1) {
                        A[i - 1][j + 1]++;
                    }
                    if (j > 0) {
                        A[i - 1][j - 1]++;
                    }
                }
            }
        }
    }

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (A[i][j] >= 0) {
                printf("%d", A[i][j]);
            } else {
                printf("#");
            }
        }
        printf("\n");
    }

    return 0;
}

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

int main(int argc, char const *argv[])
{
	ll n, ans = 0, an;
	cin >> n;
	map<ll, int> m;
	vector<ll> a, b(1);

	for(int i = 1; i <= 50; i++)
		b.push_back(b.back() + i);

	/*for(auto i: b)
		cout << i << ' ';
	cout << endl;*/

	for(ll i = 2; i*i <= n; i++)
	{
		while(n % i == 0)
		{
			n /= i;
			m[i]++;
		}
	}
	if(n > 1)
		m[n]++;
/*
	for(auto i: m)
		cout << i.first << ' ' << i.second << endl;
*/
	ll l;

	for(auto i: m)
	{
		l = i.second;
		// cout << l << '\n';
		auto it = lower_bound(b.begin(), b.end(), l);
		if(*it == l)
			ans += it - b.begin();
		else
			ans += (--it) - b.begin();
	}

	cout << ans;

	return 0;
}

Measured memory_bytes: 3616
#include <iostream>
#include <algorithm>
#define rep(i, n) for(int i=0; i<n; i++)
using namespace std;

int main(){
  int N;
  cin >> N;
  int A[N];
  rep(i, N)
    cin >> A[i];
  //ここまで入力

  //ソートをしても一般性を失わない
  sort(A, A+N);

  //i番目までのモンスターで体力が最小になるような殺し合い
  int dp[N];
  dp[0] = A[0];
  
  rep(i, N-1){
    //i番目までの最適解の状態で
    //i+1番目を考慮する
    int rest = __gcd(A[i+1], dp[i]);
    //体力の残りが0ならば，dp[i]が最適である
    if(rest == 0)
      dp[i+1] = dp[i];
    //体力がなにかしら残っていれば，restが最適
    else
      dp[i+1] = rest;
  }

  cout << dp[N-1] << endl;

  return 0;
}


Measured memory_bytes: 1024
/*-- ILSH  --*/
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back 
#define pop pop_back
#define mp make_pair
#define vii vector < ll >
#define vll vector < ll > 
#define dt cout<<"HERE\n";
#define pii pair < ll , ll >
#define pll pair < ll , ll >
#define vpi vector < pii >
#define vpl vector < pll >
#define fi first
#define se second 
#define sz size 
#define len length 
const ll inf=1e18+1e17;
const ll mod =1e9+7;
//const ll mod = 998244353;

ll modInverse(ll a,ll m){ll m0=m;ll y=0,x=1;if(m == 1)return 0;while(a> 1){ll q=a/m;ll t=m;m=a%m,a=t;t=y;y=x-q*y;x=t;}if(x<0)x+=m0;return x;}  
ll powm(ll a,ll b){a=a%mod;ll res=1;while(b){if(b&1)res=(res*a)%mod;a=	(a*a)%mod;b>>=1;}return (res%mod);}
const int N=1e5+5;
vii g[N];
int arr[N][2];
void solve(){
	int n;
	cin>>n;
	int m;
	cin>>m;
	for ( int i=0;i<n;i++){
		arr[i][0]=1;
		arr[i][1]=0;
	}
	arr[0][1]=1;
	for ( int i=0;i<m;i++){
		int x,y;
		cin>>x>>y;
		x--;y--;
		if ( arr[x][0]!=0){
			arr[y][1]=arr[y][1]|arr[x][1];
			arr[x][0]--;
			arr[y][0]++;
			arr[x][1]=(arr[x][0]>0?arr[x][1]:arr[x][0]);
		}
	}	
	int cnt=0;
	for ( int i=0;i<n;i++)
		if ( arr[i][1])
			cnt++;
	cout<<cnt<<'\n';


}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie( NULL);
	cout.tie(NULL);
	ll t=1;
	//cin>>t;
	for ( ll i=1;i<=t;i++){
		//cout<<"Case #"<<i<<": ";
    	solve();
    }
}

Measured memory_bytes: 6692
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;
  bool ans = 1;
  vector<int> a(n);
  for(int i=0;i<n;i++){
    cin >> a.at(i);
  }
  sort(a.begin(),a.end());
  for(int i=0;i<n-1;i++){
    if(a.at(i) == a.at(i+1))
      ans = 0;
  }
  if(ans){
    cout << "YES" << endl;
  }
  else
    cout << "NO" << endl;
}

Measured memory_bytes: 4016
// Grundy数
#include <bits/stdc++.h>
#define REP(i,n) for (long long i=0;i<(n);i++)
#define FOR(i,a,b) for (long long i=(a);i<(b);i++)
#define dump(x)  cerr << #x << " => " << (x) << endl
#define MIN(vec) *min_element(vec.begin(), vec.end())
#define MAX(vec) *max_element(vec.begin(), vec.end())
#define UNIQ(vec) vec.erase(unique(vec.begin(), vec.end()),vec.end()) //ソートの必要あり
#define IN(n,m)  (!(m.find(n) == m.end()))
#define FINDL(vec,x) (lower_bound(vec.begin(),vec.end(),x) - vec.begin())
#define FINDU(vec,x) (upper_bound(vec.begin(),vec.end(),x) - vec.begin())
#define EQ(a,b) (abs(a - b) < 1e-10)
using namespace std;
typedef long long LL;
constexpr int dx[4] = {0,1,0,-1};
constexpr int dy[4] = {1,0,-1,0};
constexpr long double pi = M_PI;
constexpr double eps = 1e-10;
constexpr long mod = 1000000007;
// LONG_MAX,LLONG_MAX
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class Key,class Value> ostream& operator << (ostream &s, map<Key,Value> M)
{ for ( auto itr = begin(M); itr != end(M); ++itr) { s << itr->first << ":" << itr->second; } return s;}


int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,K;
    cin >> N >> K;
    vector<int> A(N);
    vector<int> dp(K+1,-1);
    REP(i,N) cin >> A[i];
    REP(i,A[0]) dp[i] = 0;

    vector<int> usedGrundy(N+1,0);
    FOR(k,A[0],K+1) {
        int cnt = 0;
        fill(usedGrundy.begin(),usedGrundy.end(),0);
        for(int a : A) {
            if (a > k) break;
            if (dp[k-a] != -1 ) {
                cnt++;
                usedGrundy[dp[k-a]] = 1;
            }
        }
        if (cnt == 0) continue;
        REP(i,N+1) {
            if(usedGrundy[i] == 0) {
                dp[k] = i;
                break;
            }
        }
    }

    if (dp[K] == 0) cout << "Second" << endl;
    else cout << "First" << endl;
}



Measured memory_bytes: 640
N = int(input())
H = list(map(int,input().split()))

#ATcorder DP frog1
def DP(h,n):
     #初期化
        dp = [0]*n
        dp[0] = 0
        dp[1] = abs(h[0] - h[1])
    #DP
        for i in range(2,n):
            dp[i] = min((dp[i-2] + abs(h[i] - h[i-2])), (dp[i-1] + abs(h[i] - h[i-1])))
            
        return dp[n-1]

print(DP(H,N))

Measured memory_bytes: 13980
# A - Multiple Array
import numpy as np

N = int(input())
A = np.zeros(N, dtype=int)
B = np.zeros(N, dtype=int)
ans = 0

for i in range(N):
    A[i], B[i] = map(int, input().split())
for i in range(1,N+1):
    tmp = -(A[N-i] + ans) % B[N-i]
    ans += tmp
    
print(ans)

Measured memory_bytes: 14004
object Main {
  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)
    val length = sc.nextInt()
    val input = Array.fill(length)(sc.nextInt())

    val hasDuplicateValue = input.sorted
      .foldLeft((false, 0)) { (memo, value) =>
        val ans = if (memo._1) {
          true
        } else {
          memo._2 == value
        }
        (ans, value)
      }
      ._1

    val ans = if (hasDuplicateValue) "NO" else "YES"
    println(ans)
  }
}


Measured memory_bytes: 70480
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
vector<ll>color;
void dfs(vector<vector<pair<ll,ll>>> &G,ll v,ll cur=0){
    color[v]=cur;
    for(auto x: G[v]){
        ll a=x.first;
        ll w=x.second;
        if(color[a]!=-1) continue;
        ll c=(cur+w)%2;
        dfs(G,a,c);
    }
}
int main() {
    ll n;
    cin >> n;
    ll odd=0;
    vector<vector<pair<ll,ll>>>graph(n);
    for(ll i=0;i<n-1;i++){
        ll u,v,w;
        cin >> u >> v >> w;
        u--;v--;
        graph[u].push_back({v,w});
        graph[v].push_back({u,w});
    }
    color.assign(n,-1);
    dfs(graph,0);
    for(ll i=0;i<n;i++){
        cout << color[i] << endl;
    }
}


Measured memory_bytes: 12568
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define rep(i,n) for(ll i = 0; i < (ll)(n); i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll INF = 1LL << 60;
bool used[26];
int main(){
    string s;
    cin >> s;
    int n = s.size();
    if(n<26){
        rep(i,n) used[s[i]-'a'] = true;
        rep(i,26){
            if(!used[i]){
                s += char('a' + i);
                cout << s << endl;
                return 0;
            }
        }
    }
     used[s[25]-'a'] = true;
     string s2 = s;
     s2.pop_back();
     s2.pop_back();
    for(int i=25; i>0; i--){
        if(s[i-1]>s[i]){
            used[s[i-1]-'a'] = true;
            if(!s2.empty())s2.pop_back();
            continue;
        }
        rep(j,n){
            //cout << s[j-1] << endl;
            if(used[j]&&s[i-1]-'a'<j) {
                s2+=(char)('a'+j);
                cout << s2 << endl;
                return 0;
            }
        }
        return 0;
    }
    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() 
{
    int a, b, c;
    cin >> a >> b >> c;
    if(a <= b && b <= c)
        cout << a << " " << b << " " << c << endl;
    else if(a <= c && c <= b)
        cout << a << " " << c << " " << b << endl;
    else if(b <= c && c <= a)
        cout << b << " " << c << " " << a << endl;
    else if(b <= a && a <= c)
        cout << b << " " << a << " " << c << endl;
    else if(c <= b && b <= a)
        cout << c << " " << b << " " << a << endl;
    else if(c <= a && a <= b)
        cout << c << " " << a << " " << b << endl;
}


Measured memory_bytes: 3104
n, k, c = list(map(int, input().split()))
s = input()

b = []

d = -1
for i in range(k):
    while s[d] == 'x':
        d -= 1
    b.append(n+d)
    d -= c+1

d = 0
for i in range(k):
    while s[d] == 'x':
        d += 1
    if d == b[-i-1]:
        print(d+1)
    d += c+1

Measured memory_bytes: 12764
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <limits>
#include <numeric>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;


int main()
{
	int x, a;
	cin >> x >> a;
	if (x < a)cout << 0 << endl;
	else cout << 10 << endl;

	return 0;
}

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

int main() {
  int S;
  cin>>S;
  int Nums[4];
  Nums[0]=S/1000;
  Nums[1]=(S-Nums[0]*1000)/100;
  Nums[2]=(S-Nums[0]*1000-Nums[1]*100)/10;
  Nums[3]=S%10;
  int flag=0;
  for(int i=0;i<4;i++){
    if(i!=0){
      if(Nums[i-1]==Nums[i]){
        flag=1;
        break;
      }
    }
    if(i!=3){
      if(Nums[i+1]==Nums[i]){
        flag=1;
        break;
      }      
    }
  }
    if(flag==0){
      cout<<"Good"<<endl;
    }else{
      cout<<"Bad"<<endl;
  }  
}


Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;

namespace ABC
{
    class ProgramA
    {
        static void Main(string[] args)
        {
            var inputs = Console.ReadLine().Split(" ");
            var n = long.Parse(inputs[0]);
            var m = long.Parse(inputs[1]);
            var k = long.Parse(inputs[2]);

            var r1 = n + m;
            var r2 = n + k;
            var r3 = k + m;

            var result = Math.Min(r1, r2);
            result = Math.Min(r3, result);
            Console.WriteLine(result);
        }
    }
}


Measured memory_bytes: 27552
#include <bits/stdc++.h>
typedef long long L;
using namespace std;
   
#define U [100005]={}
map<L,L> path U;
L P U,E U,Z U,H U,C U,A U,O U,X U,B U,
k,n,a,b,c,p,r;
char s U;
L D(L a){
    Z[a]=1;
    for(map<L,L>::iterator I=path[a].begin();I!=path[a].end();I++){
        L d=I->first;
        if(d-P[a]){
            P[d]=a;
            E[d]=E[a]+1;
            C[d]=I->second;
            D(d);
            Z[a]+=Z[d];
            if(!H[a]|Z[H[a]]<Z[d])
                H[a]=d;
        }
    }
}
     
L G(L a){
    r=A[a]+A[P[a]]+C[a];
    return r%k?r:0;
}
     
L M(L i){
    for(r=0;i;r+=B[i],i-=i&-i);
    return r;
}
L S(L i,L x){
    for(x=G(x)-M(i+1)+M(i++);
        i<100005;B[i]+=x,i+=i&-i);
}
   
main(){
    for(cin>>n>>k;p<n-1;p++)
        cin>>a>>b>>c,
        path[a][b]=path[b][a]=c;
    D(0);
     
    for(c=p=0;p<n;p++)
        if(!p|H[P[p]]-p)
        for(a=p;!c|a;a=H[a])
            O[a]=c++,
            X[a]=p,
            S(O[a],H[a]);
     
    for(cin>>a;cin>>s>>a>>b;)
        if(*s&2){
            for(c=0;p=X[a],n=X[b],p-n;a=P[p])
                E[p]<E[n]?swap(p,n),swap(a,b),0:0,
                c+=M(O[a])-M(O[p])+G(p);
            cout<<c+abs(M(O[a])-M(O[b]))<<endl;
        }else
            A[a]+=b,
            S(O[a],H[a]),
            a?S(O[a]-1,a):0;
}

Measured memory_bytes: 31884
#include<iostream>

int main(){
int x,A,B,s,t;

std::cin >> x >> A >> B;

s=x-A;
t=x-B;
if(s<0){
    s=A-x;
}

if(t<0){
    t=B-x;
}

if(s>t){
std::cout << "B" << std::endl;
}

if(t>s){
std::cout << "A" << std::endl;
}
return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
int z,N,Y;
cin>>N>>Y;
for(int x=0;x<=Y/10000;x++)
  for(int y=0;y<=(Y-x*10000)/5000;y++)
  {z=N-x-y;
  if(z>=0 and x*10000+y*5000+z*1000==Y)
     {cout<<x<<" "<<y<<" "<<z;
      return 0;
      }
   }
cout<<"-1 -1 -1";
return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
//increase stack size
#pragma comment(linker, "/STACK:16777216")

ll mxm() {return LLONG_MIN;}
template<typename... Args>
ll mxm(ll a, Args... args) { return max(a,mxm(args...)); }

ll mnm() {return LLONG_MAX;}
template<typename... Args>
ll mnm(ll a, Args... args) { return min(a,mnm(args...)); }

template<class T> ostream& operator<<(ostream& os,vector<T> V){
	os<<"[ ";for(auto v:V)os<<v<<" ";return os<<"]";
}
template<class L,class R> ostream& operator<<(ostream& os,pair<L,R> P){
	return os<<"("<<P.first<<","<<P.second<<")";
}

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__,__VA_ARGS__)
template<typename Arg1>
void __f(const char* name,Arg1&& arg1){
	cout<<name<<" : "<<arg1<<endl;
}
template <typename Arg1,typename... Args>
void __f(const char* names,Arg1&& arg1,Args&&... args){
	const char* comma=strchr(names+1,',');cout.write(names,comma-names)<<" : "<<arg1<<" | ";__f(comma+1,args...);
}
#else
#define trace(...) 1
#endif

#define ld long double
#define pll pair<ll,ll>
#define ii pair<int,int>
#define vll vector<ll>
#define vii vector<ii>
#define vi vector<int>
#define vpll vector<pll>
#define vld vector<ld>
#define vvld vector<vld>
#define vvi vector<vi>
#define vvll vector<vll>
#define vvpll vector<vpll>
#define vvii vector<vii>
#define I insert
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x)	x.begin(),x.end()

const int mod=1e9+7;
// 128 bit: __int128
inline int add(int a,int b){a+=b;if(a>=mod)a-=mod;return a;}
inline int sub(int a,int b){a-=b;if(a<0)a+=mod;return a;}
inline int mul(int a,int b){return (a*1ll*b)%mod;}
inline int power(int a,int b){int rt=1;while(b>0){if(b&1)rt=mul(rt,a);a=mul(a,a);b>>=1;}return rt;}
inline int inv(int a){return power(a,mod-2);}

struct compare{
	bool operator() (const int &a,const int &b) const{
		return a>b;
	}
};

int main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout<<setprecision(25);
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	for(int i = 0; ;i++){
		c -= b, a -= d;
		if(c <= 0){
			cout << "Yes" << endl;
			return 0;
		}
		if(a <= 0){
			cout << "No" << endl;
			return 0;
		}
	}			
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)n; i++)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<pi, pi> pp;
typedef pair<ll, ll> pl;
const double EPS = 1e-9;
const ll MOD = 998244353;
const int inf = 1 << 30;
const ll linf = 1LL << 60;

int n;
string s;
int x[300000];
ll r, g, b;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
	cin >> n;
	cin >> s;
	rep(i,s.size()) {
		if (s[i] == 'R') {
			r++;
			if (g > 0 && b > 0) {
				x[i] = 2;
				r--; g--; b--;
			} else if (r > g && r > b) {
				x[i] = 0;
			} else {
				x[i] = 1;
			}
		} else if (s[i] == 'G') {
			g++;
			if (r > 0 && b > 0) {
				x[i] = 2;
				r--; g--; b--;
			} else if (g > r && g > b) {
				x[i] = 0;
			} else {
				x[i] = 1;
			}
		} else {
			b++;
			if (r > 0 && g > 0) {
				x[i] = 2;
				r--; g--; b--;
			} else if (b > r && b > g) {
				x[i] = 0;
			} else {
				x[i] = 1;
			}
		}
	}
	ll ans = 1;
	rep(i,3*n) {
		if (x[i] == 0) {
			r++;
		} else if (x[i] == 1) {
			ans = ans * (r-g) % MOD;
			g++;
		} else {
			ans = ans * (g-b) % MOD;
			b++;
		}
	}
	rep(i,n) ans = ans * (i+1) % MOD;
	cout << ans << endl;
}

Measured memory_bytes: 1812
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define deb(x) cout << #x << " = "<< x << "\n";

signed main()
{
	//freopen("in.txt", "r",stdin);
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int k; cin >> k;
	queue<int> q;
	for(int i = 1; i <= 9; i++)
		q.push(i);
	set<int> vis;
	while(k--)
	{
		int x = q.front(); q.pop();
		if(k == 0)
		{
			cout << x << "\n";
			break;
		}
		
		if(x % 10 != 0)
		if(vis.find(x*10 + (x%10) - 1) == vis.end()) q.push(x*10 + (x%10) - 1);
		if(vis.find(x*10 + (x%10)) == vis.end()) q.push(x*10 + (x%10));
		if(x%10 != 9) if(vis.find(x*10 + (x%10) + 1) == vis.end()) q.push(x*10 + (x%10) + 1);
	}
}


Measured memory_bytes: 1792
// AtCoder template
// sabaより胡蝶しのぶさんの方が可愛いのではないか？
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < n; ++i)


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll n,k; cin >> n >> k;
    vector<ll> a(n), b(n); rep(i,n) cin >> a[i] >> b[i];
    vector<pair<ll,ll>> p(n);
    rep(i,n) p[i] = make_pair(a[i],b[i]);
    sort(p.begin(), p.end());
    vector<ll> bsum(n+1,0LL);
    rep(i,n) bsum[i+1] = bsum[i] + p[i].second;
    int idx = int(lower_bound(bsum.begin(), bsum.end(), k)-bsum.begin());
    idx--;
    cout << p[idx].first << "\n";
}

Measured memory_bytes: 4224
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string>
#include <queue>

using namespace std;

typedef long long int ll;
typedef long long int li;


int main(void){
    ll ans=0;
    li n;
    ll sum=0;
    cin >> n;
    li a[n+1],b[n+1],d[n+1],e[n+1],f[n+1];
    for(li i=1;i<n+1;i++)cin >> a[i];
    for(li i=1;i<n+1;i++)cin >> b[i];
    for(li i=1;i<n+1;i++){
        e[i]=a[i]-b[i];
        sum+=e[i];
    }
    if(sum<=0)cout << -1 << endl;
    else{
        sort(e+1,e+n+1);
      li sum1=0;
      for(li i=1;i<n+1;i++){d[i]=e[n-i+1];f[i]=e[n-i+1];}
        li m=n;
		for(li j=1;j<n+1;j++){if(e[j]>=0)break;ans++;sum1+=e[j];}
      
      for(li j=1;j<=n+1;j++){if(sum1>=0)break;ans++;sum1+=d[j];}
        cout << ans << endl;
    }
    return 0;
}



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

int main() {
  int n,m,a[50],b[50];
  
  vector<int> ans(50,0);
  
  cin >> n >> m;
  
  for(int i = 0;i < m; i++){
    cin >> a[i] >> b[i];
  }
  
  for(int i = 0; i < m; i++){
    ans[a[i] - 1] += 1;
    ans[b[i] - 1] += 1;
  }
  
  for(int i = 0; i < n; i++){
    cout << ans[i] << endl;
  }
}

Measured memory_bytes: 3608
/**
 *     author: qodjf
 *     created: 04.22.2020 20:59:57
 */
#include <bits/stdc++.h>
using namespace std;

int N, Z, W;
vector<int> a;

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

  cin >> N >> Z >> W;
  a.resize(N);
  for (int i = 0; i < N; i++) {
    cin >> a[i];
  }

  int ans = abs(a[N - 1] - W);
  if (N >= 2) {
    ans = max(ans, abs(a[N - 2] - a[N - 1]));
  }
  cout << ans << endl;
}


Measured memory_bytes: 256