akhauriyash/Code-Regression huggingface dataset:
#[allow(unused_imports)]
use std::io::{stdin, Read, StdinLock};
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::str::FromStr;
#[allow(unused_imports)]
use std::collections::{HashSet, HashMap, BinaryHeap, VecDeque};
#[allow(unused_imports)]
use std::vec::Vec;

#[allow(dead_code)]
const INF: i32 = 1000_000_000;
#[allow(dead_code)]
const INFLL: i64 = 1000_000_000_000_000_000;
#[allow(dead_code)]
const EPS: f64 = 1.0e-10;
#[allow(dead_code)]
const MOD: i32 = 1000_000_007;
#[allow(dead_code)]
const MODLL: i64 = 1000_000_007;

struct Scanner<'a> {
    cin: StdinLock<'a>,
}

#[allow(dead_code)]
impl<'a> Scanner<'a> {
    fn new(cin: StdinLock<'a>) -> Scanner<'a> {
        Scanner {cin: cin}
    }
    fn read1<T: FromStr>(&mut self) -> Option<T> {
        let token = self.cin.by_ref().bytes().map(|c| c.unwrap() as char)
                    .skip_while(|c| c.is_whitespace())
                    .take_while(|c| !c.is_whitespace())
                    .collect::<String>();
        token.parse::<T>().ok()
    }
    fn read<T: FromStr>(&mut self) -> T {
        self.read1().unwrap()
    }
}



fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);

    let (h, w): (usize, usize) = (sc.read(), sc.read());
    let mut map: Vec<Vec<char>> = vec![Vec::new(); h];
    let mut cnt = 0;
    for i in 0..h {
        let s: String = sc.read();
        map[i] = s.chars().collect();
        for j in 0..map[i].len() {
            if map[i][j] == '#' {
                cnt += 1;
            }
        }
    }
    let map = map;
    let cnt = cnt;

    let mut dist: Vec<Vec<i32>> = vec![vec![INF; w]; h];
    dist[0][0] = 1;
    let mut que: VecDeque<(usize, usize)> = VecDeque::new();
    que.push_back((0, 0));
    let dx = [0, 1, 0, -1];
    let dy = [1, 0, -1, 0];
    while let Some((y, x)) = que.pop_front() {
        for i in 0..4 {
            if i == 2 && y == 0 || i == 3 && x == 0 {
                continue;
            }
            let (ny, nx) = (y as i32 + dy[i], x as i32 + dx[i]);
            let (ny, nx): (usize, usize) = (ny as usize, nx as usize);
            if ny >= h || nx >= w || map[ny][nx] == '#' || dist[ny][nx] != INF {
                continue;
            }
            dist[ny][nx] = dist[y][x] + 1;
            que.push_back((ny, nx));
        }
    }
    if dist[h - 1][w - 1] == INF {
        println!("-1");
    } else {
        let ans = h * w - cnt - dist[h - 1][w - 1] as usize;
        println!("{}", ans);
    }
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;

typedef long long int lli;
typedef pair<int, int> ii;

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;}

#ifdef LOCAL
	#define eprintf(...) printf(__VA_ARGS__)
#else
	#define eprintf(...) 1
#endif

#define ROUNDUP(a, b) 		( ((a) + ((b) - 1) ) / b)
#define SET_ZERO(a)	 		( memset((a), 0, sizeof(a)))
#define SET_NUM_ARRAY(a,b)	( memset((a), b, sizeof(a)))
//#define int long long int //dont forget to change int to signed

const int BIGINT = 1000000007;

int main() {
	int N;
	scanf("%d", &N);
	int A[100000];
	for (int i = 0; i < N; i++) {
		scanf("%d", &A[i]);
	}
	sort(A, A+N);

	if (N%2 && A[0] != 0) {
		printf("0\n");
		return 0;
	}
	for (int i = 0; i < N - N%2; i++) {
		if (A[i+N%2] != i + (i+1)%2 + N%2) {
			printf("0\n");
			return 0;
		}
	}

	int ans = 1;
	for (int i = 0; i < N/2; i++) {
		ans = (ans*2)%BIGINT;
	}
	printf("%d\n", ans);
	return 0;
}


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

int main() {
  int a,b,c;
  cin >> a >> b >> c;
  for ( int i=1 ; i<=b ; i++){
    if ((a*i)%b==c){
      cout << "YES" << endl;
      return 0 ;
    }
  }
  cout << "NO" << endl;
}

Measured memory_bytes: 3580
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin >> s;
  if(s.size()%2==1){
    cout << "No" << endl;
    return 0;
  }
  sort(s.begin(),s.end());
  for(int i=0;i<s.size()/2;i++){
    if(s[i*2]!=s[i*2+1]){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 256
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

from fractions import gcd
from math import sqrt
def pfact(num):
    global dt
    if num&1 == 0:
        num >>= 1
        if dt[2]:
            dt[2] = 0
        else:
            return 'setwise coprime'
    while num&1 == 0:
        num >>= 1
    for i in range(3,int(sqrt(num))+1,2):
        if num%i == 0:
            num //= i
            if dt[i]:
                dt[i] = 0
            else:
                return 'setwise coprime'
        while num%i == 0:
            num //= i
    if num>2:
        if dt[num]:
            dt[num] = 0
        else:
            return 'setwise coprime'
    return 'pairwise coprime'

n = inp()
x = ip()
t = x[0]
for i in range(1,n):
    t = gcd(t,x[i])
    if t == 1:
        break
if t != 1:
    ans = 'not coprime'
else:
    ans = 'pairwise coprime'
    dt = {i+1:1 for i in range(10**6)}
    for i in x:
        if pfact(i) == 'setwise coprime':
            ans = 'setwise coprime'
            break
print(ans)


Measured memory_bytes: 218600
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

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

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

signed main(){
	int n,a[100010],b[100010];
	vector<P> vec;
	cin >> n;
	for(int i = 0;i < n;i++){
		cin >> a[i] >> b[i];
		vec.emplace_back(a[i] + b[i],i);
	}
	sort(all(vec),greater<P>());
	int ans = 0;
	for(int i = 0;i < n;i++){
		if(i % 2 == 0) ans += a[vec[i].second];
		else ans -= b[vec[i].second];
	}
	cout << ans << endl;
}

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

using namespace std;

void solve(){

	ll n,k;
	cin>>n>>k;

	// cout<<min(abs(n%k), (abs(n - n%k) % k))<<endl;
	cout<<min(abs(n%k), abs(k  - (n - (n/k)*k)) % k)<<endl;
}

int main(){

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	ll t;
	// cin>>t;
	t=1;
	while(t--){
		solve();
	}

}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
  string S;
  int len, cnt1 = 0, cnt2 = 0;
  cin >> S;
  len = S.length();

  //case1: 偶数番目0、奇数番目1,case2: 偶数番目1、奇数番目0
  for(int i = 0; i < len; i += 2) 
    if(S[i] == '0') ++cnt2;
    else ++cnt1;
  for(int i = 1; i < len; i += 2) 
    if(S[i] == '0') ++cnt1;
    else ++cnt2;
  cout << min(cnt1, cnt2) << endl;
  return 0;
}


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

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

int main(){
    int n,k;
    cin>>n;
    string s;
    cin>>s;
    cin>>k;

    rep(i,n){
        if(s[i]!=s[k-1]) s[i]='*';
    }
    cout<<s<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mit map<int,int>::iterator
#define sit set<int>::iterator
#define itrm(g,x) for(mit g=x.begin();g!=x.end();g++)
#define itrs(g,x) for(sit g=x.begin();g!=x.end();g++)
#define ltype int
#define rep(i,j,k) for(ltype(i)=(j);(i)<=(k);(i)++)
#define rap(i,j,k) for(ltype(i)=(j);(i)<(k);(i)++)
#define per(i,j,k) for(ltype(i)=(j);(i)>=(k);(i)--)
#define pii pair<int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
#define fastio ios::sync_with_stdio(false)
const int inf=0x3f3f3f3f,mod=1000000007;
const double pi=3.1415926535897932,eps=1e-6;
int n;
int main()
{
    scanf("%d",&n);
    printf("%d\n",(n-1)/2);
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
const int Mod=1000000007;
//-, 0,1,00,01,11,001,011,0011;
const int trans[2][310000]={{1,3,4,1,6,7,4,8,7},{2,0,5,1,2,5,4,5,7}};
int dp[310000][10];
char s[310000];
int main(){
	scanf("%s",s+1);
	int n=strlen(s+1);
	dp[0][0]=1;
	for (int i=1;i<=n;i++)
		for (int j=0;j<=8;j++){
			if (s[i]!='1') (dp[i][trans[0][j]]+=dp[i-1][j])%=Mod;
			if (s[i]!='0') (dp[i][trans[1][j]]+=dp[i-1][j])%=Mod;
		}
	printf("%lld\n",(1ll*dp[n][2]+dp[n][5]+dp[n][7]+dp[n][8])%Mod);
	return 0;
} 


Measured memory_bytes: 12160
#include <cmath>
#include <iostream>
#include <vector>

int main(){
  int N;
  std::cin >> N;

  int h_max = 0, h_cont = 0, h_before = -1;
  for(int i = 0; i < N; i++){
    int h;
    std::cin >> h;
    if(h <= h_before){
      h_cont++;
    }else{
      h_cont = 0;
    }
    h_before = h;
    h_max = std::max(h_max, h_cont);
  }
  std::cout << h_max << std::endl;

  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long

using namespace std;

int main(){

    LL x,y;cin>>x>>y;
    cout<<(abs(y-x)>1 ? "Alice":"Brown")<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<ll,ll> pp;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> super_set;

#define x1 dfds
#define y1 dsfdsfe
#define pb push_back
#define forn(i,n) for(ll i = 1;i<=n;++i)
#define fi first
#define sc second
#define endl '\n'
#define po(x) (1ll<<x)
const ll DIM = 50+7;
const ll INF = 10E17;
struct node{
    ll fi,sc,th;
};
vector<node> G[DIM];
ll C[DIM],D[DIM],dp[DIM][10007];
const bool operator>(const node &a,const node &b){
    return a.fi>b.fi;
}
int main()
{

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll n,m,ss;
    cin>>n>>m>>ss;
    ll sum = 0;
    forn(i,m){
        ll x,y,a,b;
        cin>>x>>y>>a>>b;
        sum+=a;
        G[x].pb({y,a,b});
        G[y].pb({x,a,b});
    }
    forn(i,n)cin>>C[i]>>D[i];
    memset(dp,-1,sizeof(dp));
    priority_queue<node,vector<node>,greater<node> > Q;
    sum*=2;
    ss = min(ss,sum);
    Q.push({0,1,ss});
    dp[1][ss] = 0;

    while(!Q.empty()){
        pp t = {Q.top().sc,Q.top().th};
       // cout<<dp[t.fi][t.sc]<<endl;
        Q.pop();
        if (C[t.fi]+t.sc<=sum && (dp[t.fi][t.sc+C[t.fi]]==-1 || dp[t.fi][t.sc+C[t.fi]]>dp[t.fi][t.sc]+D[t.fi])){
            dp[t.fi][t.sc+C[t.fi]] = dp[t.fi][t.sc]+D[t.fi];
            Q.push({dp[t.fi][t.sc+C[t.fi]],t.fi,t.sc+C[t.fi]});
        }
        for(node to:G[t.fi]){
            if (to.sc>t.sc)continue;
            if (dp[to.fi][t.sc-to.sc]==-1 || dp[to.fi][t.sc-to.sc]>dp[t.fi][t.sc]+to.th){
                dp[to.fi][t.sc-to.sc] = dp[t.fi][t.sc]+to.th;
                Q.push({dp[to.fi][t.sc-to.sc],to.fi,t.sc-to.sc});
            }
        }
    }
    for(ll i = 2;i<=n;++i){
        ll res = INF;
        for(ll j = 0;j<=sum;++j){
            if (dp[i][j]!=-1)
            res = min(res,dp[i][j]);
        }
        cout<<res<<endl;
    }
    return 0;
}


Measured memory_bytes: 13936
/*|In The Name Of Allah|*/

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6+5;
const int M = 555;

int n;
string s;
int cnt = 1;

int main() {
    cin >> n >> s;
    for(int i = 1; i < n; i++){
        cnt += s[i] != s[i - 1];
    }
    cout << cnt << endl;
}


Measured memory_bytes: 512
N = int(input())
A = [int(c) for c in input().split()]
B = [int(c) for c in input().split()]

s = sum(A)
for i,v in enumerate(B):
    n = min(v, A[i])
    m = v - A[i] if v > A[i] else 0
    A[i] = A[i] - n
    A[i + 1] = A[i+1] - min(m, A[i+1])

e = sum(A)

print(s-e)


Measured memory_bytes: 18468
#include<iostream>
#include<iomanip>
#include<math.h>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#define INF 1000000000ll
#define MOD 1000000007ll
#define EPS 1e-8
#define rep(i,m) for(long long i=0; i<m; ++i)
#define repp(i,n,m) for(long long i=n; i<m; ++i)
#define all(v) v.begin(),v.end()
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int> > vii;
typedef vector<long long> vl;
typedef vector<vector<long long> > vll;

int main() {
	ios::sync_with_stdio(false);
	while(1) {
		int r,c;
		cin>>r>>c;
		if(r==0&&c==0) break;
		vii snbi(r,vi(c));
		rep(i,r) {
			rep(j,c) cin>>snbi[i][j];
		}
		ll ret=0;
		rep(bit,(1<<r)) {
			vi used(r,false);
			ll buf=bit;
			rep(i,r) {
				if(buf%2==1) used[i]=true;
				buf/=2;
			}
			ll res=0;
			rep(i,c) {
				ll foo=0;
				rep(j,r) if(used[j]^snbi[j][i]) ++foo;
				res+=max(foo,r-foo);
			}
			ret=max(ret,res);
		}
		cout<<ret<<endl;
	}
}

Measured memory_bytes: 3440
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int dx[] = {+1,-1, 0, 0};
const int dy[] = { 0, 0,+1,-1};
int main() {
	int H, W, K;
	cin >> H >> W >> K;
	int x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	-- x1; -- y1; -- x2; -- y2;
	vector<string> C(H);
	for (auto& x : C) cin >> x;
	vector<vector<vector<pair<int,int>>>> dist(H, vector<vector<pair<int,int>>>(W, vector<pair<int,int>>(4, {1<<30,-1})));
	priority_queue<pair<pair<int,int>,tuple<int,int,int>>> Q;
	for (int k = 0; k < 4; ++ k) {
		dist[x1][y1][k] = {0,0};
		Q.push({{0,0}, make_tuple(x1,y1,k)});
	}
	while (!Q.empty()) {
		auto top = Q.top();
		pair<int,int> d = {-top.first.first, -top.first.second};
		int x0 = get<0>(top.second);
		int y0 = get<1>(top.second);
		int k0 = get<2>(top.second);
		Q.pop();
		if (dist[x0][y0][k0] != d) continue;
		if (x0 == x2 && y0 == y2) {
			cout << d.first << endl;
			return 0;
		}
		for (int k = 0; k < 4; ++ k) {
			int xx = x0 + dx[k];
			int yy = y0 + dy[k];
			if (!(0 <= xx && xx < H && 0 <= yy && yy < W && C[xx][yy] == '.')) continue;
			pair<int,int> dd;
			if (k0 == k && d.second < 0) {
				dd = {d.first, d.second+1};
			} else {
				dd = {d.first+1, 1-K};
			}
			if (dd < dist[xx][yy][k]) {
				dist[xx][yy][k] = dd;
				Q.push({{-dd.first,-dd.second}, make_tuple(xx,yy,k)});
			}
		}
	}
	cout << -1 << endl;
}


Measured memory_bytes: 144848
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

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

int input[52],n,summ;
int used[52];
int cnt[14];

bool dfs(vector<int> &v,int sum) {
    if(v.size() == n) return true;
    rep(i,14) {
        if(cnt[i] == 0) continue;
        if((sum-i)%i == 0) {
            cnt[i]--;
            v.push_back(i);
            if(dfs(v,sum-i)) return true;
            v.pop_back();
            cnt[i]++;
        }
    }
    return false;
}

int main() {
    while(cin>>n, n) {
        summ = 0;
        memset(cnt, 0, sizeof(cnt));
        memset(used, -1, sizeof(used));
        rep(i,n) {
            cin>>input[i];
            summ += input[i];
            cnt[input[i]]++;
        }
        rep(i,52) used[i] = -1;

        sort(input, input+n);
        reverse(input, input+n);
        vector<int> ans;
        if(dfs(ans,summ)) {
            reverse(ans.begin(), ans.end());
            rep(i,n-1) cout<<ans[i]<<" ";
            cout<<ans[n-1]<<endl;
        }else{
            cout<<"No"<<endl;
        }
    }
}

Measured memory_bytes: 912
from typing import List


def max_heapify(heap: List[int], idx: int) -> None:
    left_idx = (2 * (idx + 1)) - 1
    right_idx = (2 * (idx + 1))

    if len(heap) - 1 >= left_idx and heap[left_idx] > heap[idx]:
        largest_idx = left_idx
    else:
        largest_idx = idx

    if len(heap) - 1 >= right_idx and heap[right_idx] > heap[largest_idx]:
        largest_idx = right_idx

    if largest_idx != idx:
        heap[largest_idx], heap[idx] = heap[idx], heap[largest_idx]
        max_heapify(heap, largest_idx)


def build_max_heap(heap: List[int]) -> None:
    for idx in range(len(heap) // 2 - 1, -1, -1):
        max_heapify(heap, idx)


if __name__ == "__main__":
    node_num = int(input())
    heap = list(map(lambda x: int(x), input().split()))

    build_max_heap(heap)

    print(" " + " ".join([str(elem) for elem in heap]))



Measured memory_bytes: 67024
#include <stdio.h>

int fin(int h[],int N){
    int a=0;
    for(int i=0;i<N;i++){
       if(h[i]!=0) a++;
   }
   if(a == 0) return 1;
   else return 0;
}

void look(int h[],int N){
    for(int i=0;i<N;i++) printf("h[%d]:%d\n",i,h[i]);
}

int main(void){
    int N;
    scanf("%d",&N);
    int h[N];
    for(int i=0;i<N;i++) scanf("%d",&h[i]);
    
    int j,k,m,l,r,r_now,len,counter=0;
    
    if(fin(h,N)){
        printf("0");
        return 0;
    }
    
    while(1){
        
        l=0;
        r=0;
        r_now=0;
        len=0;
        
        for(j=0;j<N;j++){
            if(h[j] == 0) continue;
            for(k=j;k<N;k++){
                if(h[k] == 0){
                    r_now = k-1;
                    break;
                } else if(k == N-1) r_now=k;
            }
            if(r_now-j>=len){
                len = r_now-j;
                r=r_now;
                l=j;
            }
        }
        
        for(m=l;m<=r;m++) h[m]--;
        
        counter++;
        
        if(fin(h,N)){
            printf("%d",counter);
            return 0;
        }
        
        //printf("counter:%d\n",counter);
        //look(h,N);
    }
    
    return 0;
}


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

#define endl "\n"

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	int n;	cin>>n;
	vector< pair<int,int> > V(n+1);
	V[0]={0,1};

	for(int i=1;i<=n;i++){
		cin>>V[i].first>>V[i].second;
		V[i].second=10-V[i].second;
	}
	// T1 < T2 < T3 < ...
	//for(int i=1;i<=n;i++){
	//	V[i].second*=V[i-1].second;
	//	//大きくなるだろ
	//}


	int q;	cin>>q;
	for(int i=0;i<q;i++){
		int l,r;	cin>>l>>r;
		int lPos,rPos,NG;

		rPos=0,NG=n+1;
		while(NG-rPos>1){
			int mid=(rPos+NG)/2;
			if(r<=V[mid].first)NG=mid;
			else rPos=mid;
		}
		//rPos: R以前で起きた最後の地震
		//cout<<rPos<<endl;

		lPos=0;	NG=n+1;
		while(NG-lPos>1){
			int mid=(lPos+NG)/2;
			if(V[mid].first<=l)lPos=mid;
			else NG=mid;
		}
		//cout<<lPos<<endl;
		//lPos: L以前に起きた最後の地震
		double ans=1000000000.0;
		for(int i=lPos+1;i<=rPos;i++){
			ans=ans/10.0*V[i].second;
		}

		//printf("%.8lf\n",ans);
		cout<<ans<<endl;

	}


	return 0;
}



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

using namespace std;
using ll=long long;

void solve() {
    ll n,m;
    cin >> n >> m;
    if (n==1||m==1) {
        cout << 1; return;
    }
    cout << (n*m+1)/2;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}


Measured memory_bytes: 256
package main

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

func main() {
	sc.Split(bufio.ScanWords)
	n, T := nextInt(), nextInt()
	t := nextInts(n)

	ans := 0

	for i := 0; i < n; i++ {
		start, end := t[i], t[i]+T
		for j := i; j < n; i, j = j, j+1 {
			if t[j] > end {
				break
			}
			end = t[j] + T
		}
		ans += end - start
	}
	puts(ans)
	wt.Flush()
}

var (
	sc  = bufio.NewScanner(os.Stdin)
	rdr = bufio.NewReaderSize(os.Stdin, 1000000)
	wt  = bufio.NewWriter(os.Stdout)
)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, _ := strconv.Atoi(next())
	return i
}

func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(next(), 64)
	return f
}

func nextInts(n int) []int {
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i] = nextInt()
	}
	return slice
}

func nextFloat64s(n int) []float64 {
	slice := make([]float64, n)
	for i := 0; i < n; i++ {
		slice[i] = nextFloat64()
	}
	return slice
}

func nextMega() string {
	buf := make([]byte, 0, 1000000)
	for {
		l, p, _ := rdr.ReadLine()
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}

func putf(format string, a ...interface{}) {
	fmt.Fprintf(wt, format, a...)
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}


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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
typedef long long ll;
const int INT_INF = 1e9;
const ll INF = 1LL << 30;
const ll MOD = 1e9 + 7;


int main() {
    int n; cin >> n;
    // sortするためvectorとpairでkey/value管理
    V<P<ll, ll> > v1(100010), v2(100010);
    for(int i = 0; i < n; i++){
        ll v; cin >> v;
        if(i % 2 == 0){
            v1[v].first++;
            v1[v].second = v;
        }else{
            v2[v].first++;
            v2[v].second = v;
        }
    }

    // 大きい順にソート
    sort(ALL(v1), greater<P<ll, ll>>());
    sort(ALL(v2), greater<P<ll, ll>>());

    ll t = 0;
    // 一番大きい数字が同じだったら2番目に大きい数字も考慮する
    if(v1[0].second == v2[0].second){
        t = max(v1[0].first + v2[1].first, v1[1].first + v2[0].first);
    }else{
        t = v1[0].first + v2[0].first;
    }

    // 総数から大きい数字を引いた値が書き換える数
    cout << n - t << endl;

}


Measured memory_bytes: 3328
N = int(input())
A = list(map(int, input().split()))

def sol(S):
    ret = 0
    for a in A[1:]:
        b = a
        if S * (S + b) > 0:
            b = (abs(S) + 1) * (1 if S < 0 else -1)
        if S + b == 0:
            b = b - 1 if S > 0 else b + 1
        ret += abs(b - a)
        S += b
    return ret

if A[0] == 0:
    ans = min(sol(1), sol(-1)) + 1
else:
    ans = min(sol(A[0]), sol(-1 if A[0] > 0 else 1) + abs(A[0]) + 1)
print(ans)


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

using namespace std;

#define INF 1000000007
#define int long long
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, n) FOR(i, 0, n)
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
int lcm(int a, int b) { return a / gcd(a, b) * b; }
signed main()
{
    int N, M;
    cin >> N >> M;
    priority_queue<int> A;
    rep(i, N)
    {
        int a;
        cin >> a;
        A.push(a);
    }
    rep(i, M)
    {
        A.push(A.top() / 2);
        A.pop();
    }
    int ans = 0;
    rep(i, N)
    {
        ans += A.top();
        A.pop();
    }
    cout << ans << endl;
}


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


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    string a,b;
    cin>>a>>b;
    ll cnt=0;
    for(ll i=0;i<b.size();i++){
        if(a[i]==b[i]) cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}


Measured memory_bytes: 256
n = int(input())
point = [0]
price = 0
point += list(map(int,input().split()))
point.append(0)
for j in range(len(point)):
  price += abs(point[j-1] - point[j])
for k in range(1,len(point)-1):
  pp = price - abs(point[k-1]-point[k]) - abs(point[k]-point[k+1]) + abs(point[k-1]-point[k+1])
  print(pp)

Measured memory_bytes: 13920
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val monsters = readLine()!!.split(' ').map { it.toInt() }
    val r = monsters.slice(1 until n).fold(monsters.first()) { a, b ->
        if (a > b) {
            return@fold gcd(a, b)
        } else {
            return@fold gcd(b, a)
        }
    }
    println(r)
}

private fun gcd(a: Int, b: Int): Int {
    val r = a % b
    if (r == 0)
        return b

    return gcd(b, r)
}


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

int main(){
	string A,B;
	cin >> A >> B;
	if(A.size()>B.size()){
		cout << "GREATER" << endl;
		return 0;
	}
	if(A.size()<B.size()){
		cout << "LESS" << endl;
		return 0;
	}
	for(int i=0;i<A.size();i++){
		if(A[i]>B[i]){
		cout << "GREATER" << endl;
		return 0;
		}
		if(A[i]<B[i]){
		cout << "LESS" << endl;
		return 0;
		}
	}
	cout << "EQUAL" << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int x,y,w,h,a,i,j,n,k,l,t;
  int catx[101],caty[101],nekokazu[101];

  for(t=0;t<101;t++){
    nekokazu[t]=0;
  }
  
  scanf("%d",&a);

  for(i=0;i<a;i++){
   
    scanf("%d %d %d %d",&x,&y,&w,&h);
    scanf("%d",&n);
    
    for(j=0;j<n;j++){
      scanf("%d %d",&catx[j],&caty[j]);
    }
    
    for(k=0;k<n;k++){
      if( catx[k]<= x+w  && caty[k]<=y+h && catx[k]>=x && caty[k]>=y){
	nekokazu[i]+=1;
      }
    }
  }
  
  for(l=0;l<a;l++){
    printf("%d\n",nekokazu[l]);
  }
  
  return 0;
}

Measured memory_bytes: 604
#include<stdio.h>
int max(int a,int b){
  if(a>b) return a;
  return b;
}
int min(int a,int b){
  if(a>b) return b;
  return a;
}
int main(void){
  int n,m,i,l=0,r=1000000,ans=0;
  scanf("%d %d",&n,&m);
  int li,ri;
  for(i=0;i<m;i++){
    scanf("%d %d",&li,&ri);
    l = max(li,l);
    r = min(ri,r);
  }
  for(i=0;i<=n;i++) if(l<=i && i<=r) ans++;
  printf("%d\n",ans);
  return 0;
}

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

int main()
{
	int A, B;
	cin >> A >> B;

	if( A % 3 == 0 || B % 3 == 0 || ( A + B ) % 3 == 0 ) {
		cout << "Possible" << endl;
	}
	else {
		cout << "Impossible" << endl;
	}

	return 0;
}


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

using namespace std;

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vs = vector<string>;
using vld = vector<ld>;
using vvld = vector<vld>;

typedef pair<ll, ll> P;

#define bit(n) (1LL << (n))

//#define int long long

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

#define rep(i, n) for (ll i = 0; i < n; i++)
#define REP(i, n) for (ll i = 1; i < n; i++)

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define FORm(i, m) for (auto i = m.begin(); i != m.end(); i++)

template <class T>
inline void chmax(T& a, T b) {
  a = std::max(a, b);
}
template <class T>
inline void chmin(T& a, T b) {
  a = std::min(a, b);
}

#define mod (ll)(1e9 + 7)
// #define mod (998244353ll)

const long long INF = 1LL << 60;

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);

  char c;
  cin >> c;
  if (c >= 'a' && c <= 'z') {
    cout << "a" << endl;
  } else {
    cout << "A" << endl;
  }

  return 0;
}


Measured memory_bytes: 3648
//49
#include<iostream>

using namespace std;

int main(){
  int n;
  cin>>n;
  while(n--){
    char s[100001];
    cin>>s;
    int i[2];
    for(int j=0;j<2;j++){
      char l=0,r=0;
      for(i[j]=0;s[i[j]];i[j]++){
	((i[j]%2^j)?r:l)=s[i[j]];
	if(l==r)break;
	if(s[j]>0&&(l=='U'&&(r=='L')||l=='R'||l=='D'&&(r=='L')))break;
      }
    }
    cout<<(s[i[0]]&&s[i[1]]?"No":"Yes")<<endl;
  }
  return 0;
}

Measured memory_bytes: 1248
#include<iostream>
using namespace std;
#define MAX 500000
#define SENTINEL 2000000000

int L[MAX/2+2], R[MAX/2+2];
int cnt;

void merge(int A[], int n, int left, int mid, int right){
    int n1 = mid-left;
    int n2 = right-mid;
    for(int i=0; i<n1; i++){
        L[i] = A[left+i];
    }
    for(int i=0; i<n2; i++){
        R[i] = A[mid+i];
    }
    L[n1] = R[n2] = SENTINEL;
    int i=0, j=0;
    for(int k=left; k<right; k++){
        cnt++;
        if(L[i] <= R[j]){
            A[k] = L[i++];
        }else{
            A[k] = R[j++];
        }
    }
}

void mergeSort(int A[], int n, int left, int right){
    if(left+1<right){
        int mid = (left+right)/2;
        mergeSort(A, n, left, mid);
        mergeSort(A, n, mid, right);
        merge(A, n, left, mid, right);
    }
}

int main(){
    int A[MAX], n, i;
    cnt = 0;
    
    cin >> n;
    for(i=0; i<n; i++) cin >> A[i];
    
    mergeSort(A, n, 0, n);
    
    for(i=0; i<n; i++){
        if(i) cout << " ";
        cout << A[i];
    }
    
    cout << endl;
    cout << cnt << endl;
    
    return 0;
}

Measured memory_bytes: 6900
N = int(input())
A = [int(i) for i in input().split()]

ans = 0
minus_cnt = 0
min_abs = float("inf")
for a in A:
    if a < 0:
        minus_cnt += 1
    ans += abs(a)
    min_abs = min(min_abs, abs(a))

if minus_cnt % 2 == 0:
    print(ans)
else:
    print(ans - min_abs * 2)

Measured memory_bytes: 14284
# https://atcoder.jp/contests/tenka1-2018-beginner/submissions/6799589
# combinationを使うところ

def main():
    from itertools import combinations

    N = int(input())

    # {1,...,N}*2を分割
    # k個の集合があって
    # 各集合は他のk-1個の集合に対し共通要素を1個ずつ合わせてk-1個の要素をもつ

    k = 1
    while (k - 1) * k < N * 2:
        k += 1
    cond = (k - 1) * k == N * 2

    if not cond:
        print('No')
        return

    sets = tuple(set() for _ in range(k))
    for common_component, (set_idx_1, set_idx_2) in enumerate(combinations(range(k), r=2), start=1):
        sets[set_idx_1].add(common_component)
        sets[set_idx_2].add(common_component)

    print('Yes')
    print(k)
    for set_ in sets:
        print(len(set_), *set_)


if __name__ == '__main__':
    main()


Measured memory_bytes: 22224
main = do
    a:b:c:d:_ <- fmap (fmap read . words) getLine 
    (s, g) <- solve a b c d
    putStr $ show s
    putStr " "
    putStrLn $ show g

solve :: Int -> Int -> Int -> Int -> IO (Float, Int)
solve a b c d = pure (s, g)
    where 
        s = fromIntegral a * fromIntegral b / 2.0
        g = if mod a 2==0 && mod b 2==0 && div a 2 ==c && div b 2 ==d
            then 1
            else 0

Measured memory_bytes: 508
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
	ll n, ans = 0;
	cin >> n;
	for (int i = 1; i < n; i++){
		for (int j = 1; j * j <= i; j++){
			if (i % j == 0) ans += 2;
			if (j * j == i) ans--;
		}
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 3760
#include<iostream>
#include<cstdio>
#include<iomanip>
using namespace std;
long long n,m,d;
double ans;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>d;
    ans=1.0;
    if(d==0) ans=ans*(n-d)/n*(m-1)/n;
    else ans=2*ans*(n-d)/n*(m-1)/n;
    cout<<fixed<<setprecision(10)<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){

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

  int i,b,f,r,v,house[5][4][11] = {};

  for ( i = 0 ; i < n ; i++ ){
    scanf("%d %d %d %d", &b, &f, &r, &v);
    house[b][f][r] = house[b][f][r] + v;
  }

  int j,k;
  
  for ( i = 1 ; i <= 4 ; i++ ){
    for ( j = 1 ; j <= 3 ; j++ ){
      for ( k = 1 ; k <= 10 ; k++ ){
	printf(" %d", house[i][j][k]);
      }
      printf("\n");
    }
    if ( i == 4 ) break;
    printf("####################\n");

  }

  return 0;

}

Measured memory_bytes: 612
a = []
b = int(input())
a.append(b)
c = int(input())
a.append(c)
d = int(input())
a.append(d)
e = int(input())
a.append(e)
if len(a) == 4 and all(1 <= item <= 1000 for item in a):
    print(min(a[0] + a[2], a[0] + a[3], a[1] + a[2], a[1] + a[3]))
else:
    print('hoge!')

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

int main()
{
    string s;
    cin >> s;
    if ((s[0] == s[1]) && (s[0] == s[2]))
    {
        cout << "No" << endl;
    }
    else
    {
        cout << "Yes" << endl;
    }
    return 0;
}

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

typedef long long ll;

int main() {
	ios::sync_with_stdio(0);
	
	int a, b;
	cin >> a >> b;
	cout << "100 100\n";
	vector<vector<char>> white(50, vector<char>(100, '#'));
	vector<vector<char>> black(50, vector<char>(100, '.'));
	
	int i = 1, j = (i%2 + 1) * 2;;
	
	while (--a) {
		white[i][j] = '.';
		j += 4;
		if (j >= 90) {
			i++;
			j = (i%2 + 1) * 2;
		}
	}
	i = 1; j = (i%2 + 1) * 2;;
	while (--b) {
		black[i][j] = '#';
		j += 4;
		if (j >= 90) {
			i++;
			j = (i%2 + 1) * 2;
		}
	}
	for (i = 0; i < 50; i++) {
		for (j = 0; j < 100; j++) {
			cout << white[i][j];
		}
		cout << '\n';
	}
	for (i = 0; i < 50; i++) {
		for (j = 0; j < 100; j++) {
			cout << black[i][j];
		}
		cout << "\n";
	}
	
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import java.util.function.*;

public class Main {
	public final int MOD = (int)1e9 + 7;
	
	public void solve(BufferedReader br) throws IOException {
		int n = Integer.parseInt(br.readLine());
		int[] dp = new int[3];
		for (int i = 0; i < n; i++) {
			int[] c = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
			if (i == 0) {
				dp[0] = c[0];
				dp[1] = c[1];
				dp[2] = c[2];
				continue;
			}
			int[] new_dp = new int[3];
			Arrays.fill(new_dp, -((int)1e9 + 7));
			for (int j = 0; j < 3; j++) {
				for (int k = 0; k < 3; k++) {
					if (j != k) new_dp[k] = Math.max(new_dp[k], c[k] + dp[j]);    
				}
			}
			dp[0] = new_dp[0];
			dp[1] = new_dp[1];
			dp[2] = new_dp[2];
			//System.out.println(Arrays.toString(new_dp));
		}	
		System.out.println(Math.max(dp[0], Math.max(dp[1], dp[2])));
	}
	
	public long mathPow(long base, long exp, long mod) {
		long res = 1;
		base = base % mod;
		while (exp > 0) {
			if ((exp & 1) == 1) res = (res * base ) % mod;
			exp = exp >> 1;
			base = (base * base) % mod;
		}
		return res;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		new Main().solve(br);
	}
}



Measured memory_bytes: 51708
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string>
#include<iostream>
#include<cctype>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include <algorithm>
#include<math.h>
#include<set>
#include<map>
#include <sstream>
#include<iomanip>
#include <ctype.h>

//#include<bits/stdc++.h>


using namespace std;
int main() {
	
	int n;
	int a = 0,b;
	cin >> n;
	b = n;
	while (b) {
		a += b % 10;
		b /= 10;
	}
	if (n%a)cout << "No" << endl;
	else cout << "Yes" << endl;


	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define IFOR(i,a,b) for(int i=(b-1);i>=(a);--i)
#define RPT(i,a,b) for(int i=(a);i<((a)+(b));++i)
#define IRPT(i,a,b) for(int i=((a)+(b)-1);i>=(a);--i)
#define ALL(x) x.begin(),x.end()

template<class T> using V = vector<T>;
template<class T> using V2 = V<V<T>>;
using P = pair<ll,ll>;


void solve(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n, m; cin >> n >> m;
  V<P> v;
  FOR(i,0,n){
    int a, b; cin >> a >> b;
    if(a>m) continue;
    v.emplace_back(a,b);
  }
  sort(ALL(v));
  reverse(ALL(v));
  ll ans = 0;
  priority_queue<P> que;
  IFOR(d,0,m){
    while(!v.empty()){
      auto p = v[v.size()-1];
      if(p.first+d>m) break;
      que.push(P(p.second, p.first));
      v.pop_back();
    }
    if(!que.empty()){
      auto p = que.top();
      que.pop();
      ans += p.first;
    }
  }
  cout << ans << endl;
}

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

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

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

    int n, x;
    cin >> n >> x;

    int res = 1;
    int dist = 0;
    rep(i, n){
        int l;
        cin >> l;

        dist += l;
        if(dist > x){
            cout << res << endl;
            return 0;
        }
        ++res;
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
int main() {
	int a[101] = { 0 };
	int A;
	int M_C = 0;
	while (cin >> A) {
		a[A]++;
		M_C = max(M_C, a[A]);
	}
	for (int i = 1; i <= 100;i++) {
		if (a[i] == M_C) cout << i << endl;
	}
}

Measured memory_bytes: 3080
n = int(input())
si = [input() for _ in range(n)]
ans_str = ['AC x', 'WA x', 'TLE x', 'RE x']
ans = [0]*4
for i in range(n):
    if si[i] == 'AC':
        ans[0] += 1
    elif si[i] == 'WA':
        ans[1] += 1
    elif si[i] == 'TLE':
        ans[2] += 1
    elif si[i] == 'RE':
        ans[3] += 1
    
for i in range(4):
    print(ans_str[i], ans[i])

Measured memory_bytes: 16196
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>
#include <functional>

using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template<typename T> using VT = vector<T>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define EB emplace_back
#define GREATER(T) T, VT<T> greater<T>
template<typename T> inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

int main(void) {
    int X;
    cin >> X;

    int ans;
    if (X<600) ans=8;
    else if (X<800) ans=7;
    else if (X<1000) ans=6;
    else if (X<1200) ans=5;
    else if (X<1400) ans=4;
    else if (X<1600) ans=3;
    else if (X<1800) ans=2;
    else if (X<2000) ans=1;

    cout << ans << endl;
}

Measured memory_bytes: 3640
/*Template by hemnath_d(Enlightened by chamow)*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define vec vector<ll>
#define pll pair<ll,ll>
#define fastread ios_base::sync_with_stdio(false); cin.tie(NULL);
#define pb push_back
#define mp make_pair
#define fx first
#define sx second
#define inf 100000000000000
#define minf -100000000000000
#define maxi 100005

int main()
{
    fastread;
    char a;
    cin>>a;
    cout<<(char)(a+1)<<endl;
    return 0;
}

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

using namespace std;

vector<int> Adj[100005];

int a[100005], b[100005];

int N;

int used[100005];

int K;
int color[100005];


void visit(int k, int c) {

	//cout << "k= " << k << endl;

	int j = c + 1; if (j > K) { j = 1; }

	for (int i : Adj[k]) {
		if (color[i] == 0) {
			color[i] = j; 
			j++; if (j > K) { j = 1; }

			int next;
			if (a[i] == k) { next = b[i]; }
			else { next = a[i]; }
			//cout << "next= " << next << endl;
			visit(next, color[i]);
		}
	}
}

int main(void) {

	cin >> N;

	for (int i = 1; i <= N - 1; i++) {
		cin >> a[i] >> b[i];
		Adj[a[i]].push_back(i);
		Adj[b[i]].push_back(i);
	}

	for (int i = 1; i <= N - 1; i++) {
		K = max(K, (int) Adj[i].size());
	}

	visit(1, 0);

	cout << K << endl;

	for (int i = 1; i <= N - 1; i++) {
		cout << color[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 7936
N=int(input())
li=[0]*N
for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            temp=x**2+y**2+z**2+x*y+y*z+z*x
            if temp<=N:
                li[temp-1]+=1
for i in range(N):
    print(li[i])


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

using namespace std;

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

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> a(N);
  REP(i, N) cin >> a[i];
  vector<ll> sum1(N + 1), sum2(N + 1);
  sum1[0] = 0, sum2[0] = 0;
  REP(i, N) {
    sum1[i + 1] = sum1[i] + a[i];
    sum2[i + 1] = sum2[i] + max(0ll, 1ll * a[i]);
  }
  ll ans = 0;
  REP(i, N - K + 1) {
    ll tmp = sum2[i] - sum2[0] + max(0ll, sum1[i + K] - sum1[i]) + sum2[N] -
             sum2[i + K];
    ans = max(ans, tmp);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(V) V.begin(),V.end()

ll big = LLONG_MAX / 100;
ll seg[262144];

void upq(int s, int t, ll v, int k, int l, int r) {
	if (r < s || t < l) {
		return;
	}

	if (s <= l && r <= t) {
		seg[k] = v;
		return;
	}

	if (seg[k] != big) {
		seg[k * 2] = seg[k];
		seg[k * 2 + 1] = seg[k];
		seg[k] = big;
	}

	upq(s, t, v, k * 2, l, (l + r) / 2);
	upq(s, t, v, k * 2 + 1, (l + r) / 2 + 1, r);
}

ll getq(ll x) {
	x += 131072;
	ll a = big;
	while (x) {
		if (seg[x] != big) {
			a = seg[x];
		}
		x /= 2;
	}
	return a;
}

ll bs(ll x, int ng, int ok) {
	if (ok - ng == 1)return ok;
	int mid = (ng + ok) / 2;
	if (getq(mid) > x) {
		ok = mid;
	}
	else {
		ng = mid;
	}
	return bs(x, ng, ok);
}

int main(){
	for (int i = 0;i < 262144;i++)seg[i] = big;
	ll N, M;
	cin >> N >> M;
	ll L, R, C;
	vector<tuple<ll, ll, ll>> V(M);
	for (int i = 0;i < M;i++) {
		cin >> L >> R >> C;
		L--;R--;
		V[i] = make_tuple(L, R, C);
	}

	sort(all(V));

	ll val, ind;
	upq(0, 0, 0, 1, 0, 131071);
	for (int i = 0;i < M;i++) {
		tie(L, R, C) = V[i];
		val = getq(L);
		if (val == big)continue;
		val += C;
		ind = bs(val, L, N);
		if (ind <= R) {
			upq(ind, R, val, 1, 0, 131071);
		}
	}

	if (getq(N - 1) == big)
		cout << -1 << endl;
	else
		cout << getq(N - 1) << endl;
}

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

int h,w;
int fie[61][61];
int data[61][61][4];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ok[4];
bool flag;

void dfs(int x,int y){
	int muki=1;
	int ug=0;
	while(1){
		int lv=0;
		if(x==0 && y==0){
			if(ok[0]==1 && ok[1]==1 && ok[2]==1){
				ok[3]=1;
				return;
			}
		}
		if(x==w-1 && y==0){
			ok[2]=1;
			ug=1;
		}
		if(x==w-1 && y==h-1){
			ok[1]=1;
			ug=2;
		}
		if(x==0 && y==h-1){
			ok[0]=1;
			ug=3;
		}
		for(int i=0;i<4;i++){
			if(data[y][x][i]!=ug && data[y][x][i]!=-1)return;
		}
		if(data[y][x][muki]!=-1)return;
		data[y][x][muki]=ug;
		for(int i=0;i<4;i++){
			int dl=(muki+1-i+4)%4;
			int nx=x+dx[dl],ny=y+dy[dl];
			if(nx<0 || nx>=w || ny<0 || ny>=h)continue;
			if(fie[ny][nx]==0){
				muki=dl;
				y=ny;
				x=nx;
				break;
			}
		}
	}
}

int main(void){
	while(1){
		scanf("%d%d",&h,&w);
		if(h==0 && w==0)break;
		memset(fie,-1,sizeof(fie));
		for(int i=0;i<h;i++){
			string str;
			cin >> str;
			for(int j=0;j<w;j++){
				if(str[j]=='.')fie[i][j]=0;
				else fie[i][j]=-1;
			}
		}
		memset(data,-1,sizeof(data));
		flag=true;
		memset(ok,0,sizeof(ok));
		dfs(0,0);
		for(int i=0;i<4;i++){
			if(ok[i]==0)flag=false;
		}
		printf("%s\n",flag?"YES":"NO");
	}
	return 0;
}

Measured memory_bytes: 3224
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
#define all(x) (x).begin(), (x).end()
#define fsp(x) fixed << setprecision(x)
#define xout cerr
const ll inf = LLONG_MAX;
const long double pi = acos(-1);
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//const ll p = 1e9 + 7;
	//const ll p = 998244353;

	ll n;
	cin >> n;
	for (ll i = 1; i <= 3500; i++) {
		for (ll j = i; j <= 3500; j++) {
			if (4 * i * j - n * i - n * j <= 0) continue;
			if ((n * i * j) % (4 * i * j - n * i - n * j) == 0) {
				cout << i << " " << j << " " << (n * i * j) / (4 * i * j - n * i - n * j) << endl;
				return 0;
			}
		}
	}
}
/*
4abc == nbc + nac + nab
(4ab - nb - na)c == nab
c == nab / (4ab - nb - na)*/


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<functional>
#include<map>
#include<iomanip>
#include<limits>
#include<unordered_set> 
#include<cmath>
    using namespace std;
    //long long p = 998244353;
    long long p = 1000000007;
#define int long long
#define vel vector<long long>
#define vvel vector<vel>
#define rep(i,n) for(int i=0;i<n;i++)
#define sor(v) sort(v.begin(),v.end())
#define mmax(a,b) a=max(a,b)
#define mmin(a,b) a=min(a,b)
#define mkp make_pair
#define pin pair<int,int>
#define qin pair<pin,int>
#define V vector
#define Endl endl
#define veb vector<bool>
#define fcout cout << fixed << setprecision(15)
#define rev(s) reverse(s.begin(),s.end())
#define lower(h,val) lower_bound(h.begin(),h.end(),val)-h.begin()
#define upper(h,val) upper_bound(h.begin(),h.end(),val)-h.begin()
    int max_kai = 150000;
    vel kai(max_kai, 1);
    vel inv_kai;
    int rui(int a, int n, int mod) {
        if (n == 0) { return 1 % mod; }
        int x = rui(a, n / 2, mod);
        x *= x; x %= mod;
        if (n % 2 == 1) { x *= a; x %= mod; }
        return x;
    }
    vel pa;
    int root(int x) {
        if (pa[x] == -1) { return x; }
        int ans = root(pa[x]); pa[x] = ans;
        return ans;
    }
    void marge(int x, int y) {
        x = root(x);
        y = root(y);
        if (x != y) { pa[x] = y; }
    }
    int gcd(int x, int y) {
        if (x < y) { return gcd(y, x); }
        if (y == 0) { return x; }
        return gcd(y, x % y);
    }
    long long modinv(long long a, long long m) {
        long long b = m, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        u %= m;
        if (u < 0) u += m;
        return u;
    }
    signed main() {
        int a, b; cin >> a >> b;
        cout << (a ^ b) << endl;
        return 0;
    }
// プログラムの実行: Ctrl + F5 または [デバッグ] > [デバッグなしで開始] メニュー
// プログラムのデバッグ: F5 または [デバッグ] > [デバッグの開始] メニュー

// 作業を開始するためのヒント: 
//    1. ソリューション エクスプローラー ウィンドウを使用してファイルを追加/管理します 
//   2. チーム エクスプローラー ウィンドウを使用してソース管理に接続します
//   3. 出力ウィンドウを使用して、ビルド出力とその他のメッセージを表示します
//   4. エラー一覧ウィンドウを使用してエラーを表示します
//   5. [プロジェクト] > [新しい項目の追加] と移動して新しいコード ファイルを作成するか、[プロジェクト] > [既存の項目の追加] と移動して既存のコード ファイルをプロジェクトに追加します
//   6. 後ほどこのプロジェクトを再び開く場合、[ファイル] > [開く] > [プロジェクト] と移動して .sln ファイルを選択します


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

typedef long long ll;

int main(){
    int x,y,a,b,c;
    cin>>x>>y>>a>>b>>c;
    int p[a], q[b], r[c], re[x], gr[y],m=c-1,l=0, o=0;
    ll sum=0;
    for(int i=0;i<a;i++) cin >> p[i];
    for(int i=0;i<b;i++) cin >> q[i];
    for(int i=0;i<c;i++) cin >> r[i];
    sort(p, p+a);
    sort(q,q+b);
    sort(r, r+c);
    for(int i=0; i<x; i++){
        re[i] = p[i+a-x];
    }
    for(int i=0; i<y; i++){
        gr[i] = q[i+b-y];
    }
    
    while(m>=0 && (o<y || l<x)){
        if(l>=x && o<y) {
            if(gr[o] < r[m]) {
                gr[o] = r[m];
                m--;
                o++;
            }else break;
        }else if(l<x && o>=y){
            if(re[l] < r[m]) {
                re[l] = r[m];
                m--;
                l++;
            }else break;
        }else if(re[l]<=gr[o] && r[m] > re[l]){
            re[l] = r[m];
            m--;
            l++;
        }else if(re[l]>gr[o] && r[m] > gr[o]){
            gr[o] = r[m];
            m--;
            o++;
        }else break;
    }

    for(int i=0; i<x; i++) {
        sum+=re[i];
    }
    for(int i=0; i<y; i++) {
        sum+=gr[i];
    }
    cout << sum << endl;
}

Measured memory_bytes: 2176