akhauriyash/Code-Regression huggingface dataset:
def main():
    n = int(input())
    tree = [[] for _ in range(n+1)]

    for i in range(n-1):
        a, b, c = map(int, input().split())
        tree[a].append([b, c])
        tree[b].append([a, c])

    q, k = map(int, input().split())

    from collections import deque
    que = deque([k])
    visit = [-1 for _ in range(n+1)]
    visit[k] = 0
    while que:
        pos = que.popleft()
        for i, j in tree[pos]:
            if visit[i] < 0:
                visit[i] = visit[pos]+j
                que.append(i)
    for i in range(q):
        x, y = map(int, input().split())
        print(visit[x]+visit[y])

if __name__=="__main__":
    main()

Measured memory_bytes: 51928
X  = int(input())

if 400 <= X <= 599:
    print(8)
elif 600 <= X <= 799:
    print(7)
elif 800 <= X <= 999:
    print(6)
elif 1000 <= X <= 1199:
    print(5)
elif 1200 <= X <= 1399:
    print(4)
elif 1400 <= X <= 1599:
    print(3)
elif 1600 <= X <= 1799:
    print(2)
elif 1800 <= X <= 1999:
    print(1)


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

int main() {
    int N;
    cin >> N;
    vector<int> b(N);
    for (auto& e : b)
        cin >> e;
    int sum = 0;
    for (int i = 0; i < N-1; i++) {
        for (int j = i+1; j < N; j++) {
            sum += b[i] * b[j];
        }
    }
    cout << sum;
}

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

using namespace std;

int main() {
    string str;
    cin >> str;
    
    long long int K;
    cin >> K;
    
    vector<long long int> vec;
    char pre=str[0];
    long long int cur=0;
    for(int i=0; i<str.size(); i++) {
        if(pre==str[i]) {
            cur++;
        } else {
            vec.push_back(cur);
            cur=1;
        }
        pre = str[i];
    }
    vec.push_back(cur);

    long long int ans=0;
    if(str[0]==str[str.size()-1]) {
        if(vec.size()==1) {
            ans = vec[0]*K/2;
        } else {
            for(int i=1; i<vec.size()-1; i++) {
                ans += vec[i]/2;
            }
            ans *= K;
            ans += vec[0]/2+vec[vec.size()-1]/2+(vec[0]+vec[vec.size()-1])/2*(K-1);
        }
    } else {
        for(int i=0; i<vec.size(); i++) {
            ans += vec[i]/2;
        }
        ans *= K;
    }
    
    cout << ans << endl;
    
    return 0;
    
}

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

int main()
{
  int n;
  char s[10010];
  cin >>n>>s;
  int len = strlen(s);
  for(int i=0;i<len;i++)
  {
    int x = s[i]-'A';
    x = (x+n)%26;
    putchar('A'+x);
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
using namespace std;
const long long mod=1000*1000*1000+7;
long long ans,ap[30];
int n,i;
string s;
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n;
    cin>>s;
    for(i=0;i<n;i++)
        ap[s[i]-'a']++;
    ans=1;
    for(i=0;i<26;i++)
        ans=(1LL*ans*(ap[i]+1))%mod;
    cout<<(ans-1+mod)%mod;
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int mod = 1000000007;

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

    ll ten = 1;
    for(ll i = 0; i < n; i++)
    {
        ten = ten * 10 % mod;
    }
    ll nine = 1;
    
    for(ll i = 0; i < n; i++)
    {
        nine = nine * 9 % mod;
    }

    ll eight = 1;
    for(ll i = 0; i < n; i++)
    {
        eight = eight * 8 % mod;
    }

    ll res = ten - (nine + nine) + eight;
    res = (res % mod + mod) % mod; 
    
    cout << res << "\n";
    return 0;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < (n); i++)
#define RREP(i, s, n) for (int i = s; i < (n); i++)
#define ALL(a) a.begin(), a.end()
#define RALL(a) a.rbegin(), a.rend()
using namespace std;
using ll = long long;
typedef pair<int, int> pint;
const ll MOD = 1000000007;
const ll INF = MOD * MOD;
const int inf = (1<<29);

int main() {

    int n;
    cin >> n;

    vector<ll> a(n), b(n);
    REP(i, n) {
        cin >> a[i];
        b[i] = a[i] - (i+1);
    }

    sort(ALL(b));

    ll tmp = b[b.size() / 2];
    ll sum = 0;

    for (int i = 0; i < n; i++) {
        sum += abs(b[i] - tmp);
    }

    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 3328
import java.util.Scanner;
 
class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int x = sc.nextInt();
		int count = 0;
		for (int i = 0; i < m; i++) {
			int a = sc.nextInt();
			if (a < x) {
				count++;
			} 
		}
		System.out.println(Math.min(count, m - count));
	}
}

Measured memory_bytes: 21332
use std::io::Read;

fn main() {
    let mut buf = String::new();
    let _ = std::io::stdin().read_to_string(&mut buf);
    let mut it = buf.split_whitespace();
    let n: usize = it.next().unwrap().parse().unwrap();
    if n%2 == 0 {
        println!("{}", n);
    } else {
        println!("{}", 2*n);
    }
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
#define inf 1000000000
#define N 200009
using namespace std;

int n,tot,cnt,tp,dfsclk,q[N],fst[N],pnt[N<<1],nxt[N<<1];
int lf[N],rg[N],id[N],anc[N],sz[N],son[N],fa[N],d[N],f[N];
long long ans; char s[N];
struct node{ int x,y; }a[N],b[N],c[N];
bool operator <(node u,node v){ return u.x<v.x; }
void mdy(node &u,node v){
	u.x=max(u.x,v.x); u.y=min(u.y,v.y);
}
void add(int x,int y){
	pnt[++tot]=y; nxt[tot]=fst[x]; fst[x]=tot;
}
int find(int x,int y){
	int t=x;
	for (; anc[x]!=anc[y]; x=fa[anc[x]]) t=anc[x];
	return x==y?t:id[lf[y]+1];
}
void calc(int x){
	int i,y;
	if (b[x].x) c[cnt=1]=b[x]; else cnt=0;
	for (i=fst[x]; i; i=nxt[i]){
		y=pnt[i];
		if (y!=fa[x]) c[++cnt]=a[y];
	}
	sort(c+1,c+cnt+1);
	int l=0,r=c[cnt].x-1;
	if (b[x].x==c[cnt].x) r=min(r,a[x].x);
	else{
		for (i=fst[x]; i; i=nxt[i]){
			y=pnt[i];
			if (y!=fa[x] && c[cnt].x==a[y].x){
				r=min(r,b[y].x); break;
			}
		}
	}
	//cout<<x<<endl;
	if (s[x]=='0'){
		l=inf;
		for (i=1; i<=cnt; i++){
			//y=c[i].y;
			//if (!y) continue;
			if (c[i].y<inf) l=min(l,c[i].x);
			//else l=min(l,c[i].y+c[cnt-1].x+c[i].y);
			//cout<<"?	"<<y<<endl;
			//if (lf[y]<=lf[x] && lf[x]<=rg[y]){
			//	y=find(x,y);
			//	cout<<"	"<<c[i].z<<endl;
			//}
			//else{
			//	cout<<"	"<<c[i].z<<' '<<b[y].x<<endl;
			//	l=min(l,c[i].z+b[y].x-1);
			//}
		}
	}
	//cout<<"  "<<l<<' '<<r<<endl;
	ans+=max(0,r-l+1);
}
void dfs(int x){
	int i,y; sz[x]=1;
	for (i=fst[x]; i; i=nxt[i]){
		y=pnt[i];
		if (y!=fa[x]){
			fa[y]=x; d[y]=d[x]+1;
			dfs(y); sz[x]+=sz[y];
			if (sz[y]>sz[son[x]]) son[x]=y;
			mdy(a[x],a[y]);
		}
	}
	a[x].x++; a[x].y++;
	if (s[x]=='1') a[x].y=1;
}
void dvd(int x,int tp){
	int i,y;
	lf[x]=++dfsclk; id[dfsclk]=x; anc[x]=tp;
	if (son[x]) dvd(son[x],tp);
	for (i=fst[x]; i; i=nxt[i]){
		y=pnt[i];
		if (y!=fa[x] && y!=son[x]) dvd(y,y);
	}
	rg[x]=dfsclk;
}
void dfs2(int x){
	int i,y;
	for (i=fst[x],tp=0; i; i=nxt[i]){
		y=pnt[i];
		if (y!=fa[x]) q[++tp]=y;
	}
	node tmp=b[x];
	for (i=1; i<=tp; i++){
		y=q[i];
		mdy(b[y],tmp);
		mdy(tmp,a[y]);
	}
	for (i=tp,tmp=(node){-inf,inf}; i; i--){
		y=q[i];
		mdy(b[y],tmp);
		mdy(tmp,a[y]);
	}
	for (i=1; i<=tp; i++){
		b[q[i]].x++; b[q[i]].y++;
	}
	if (s[x]=='1')
		for (i=1; i<=tp; i++){
			b[q[i]].y=1;// b[q[i]].z=1;
		}
	for (i=fst[x]; i; i=nxt[i]){
		y=pnt[i];
		if (y!=fa[x]) dfs2(y);
	}
}
int main(){
	scanf("%d",&n);
	int i,x,y;
	for (i=1; i<n; i++){
		scanf("%d%d",&x,&y);
		add(x,y); add(y,x);
	}
	scanf("%s",s+1);
	for (i=1; i<=n; i++) a[i].y=b[i].y=inf;
	dfs(1); dvd(1,1); dfs2(1);
	for (i=1; i<=n; i++) calc(i);
	printf("%lld\n",ans+1);
	return 0;
}


Measured memory_bytes: 24576
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int N, K;
    int x = 1;
    cin >> N >> K;
    for (int i = 0; i < N; i++){
        if (x < K){
            x *= 2;
        }
        else {
            x += K;
        }
    }
    cout << x << endl;
}

Measured memory_bytes: 256
def fun():
     print('ac')
     print('AC')
     print('ACAC')
     print('ac')
A,B=map(int,input().split())
if A==1:
     A=15
if B==1:
     B=15
if A>B:
     print('Alice')
elif A==B:
     print('Draw')
else:
     print('Bob')

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

#ifdef DEBUG
#include "inc/debug.hpp"
#else
#define debug(...) 42
#endif

template<typename T>
void chmin(T &a, const T &b){ a = min(a, b); }

template<typename A, size_t N, typename T>
void static_fill(A (&arr)[N], const T &val){
    fill((T*)arr, (T*)(arr+N), val);
}

const int INF = 1e6;
int dp[1<<18][51];

int main() {
    static_fill(dp, INF);

    int N;
    cin >> N;
    vector<int> A(N), B(N);
    for (int i=0; i<N; ++i) cin >> A[i];
    for (int i=0; i<N; ++i) cin >> B[i];

    // 位置iにあるカードを位置jに置くときの表の数字
    auto face = [&](int i, int j){
        return abs(i-j) % 2 ? B[i] : A[i];
    };

    for (int i=0; i<N; ++i) {
        dp[1<<i][face(i, 0)] = 0;
    }
    for (int mask=1; mask<(1<<N); ++mask) {
        for (int i=0; i<51; ++i) {
            for (int j=0; j<N; ++j) {
                if ((mask >> j) & 1) continue;
                
                int p = __builtin_popcount(mask);
                if (i <= face(j, p)) {
                    int inv = __builtin_popcount(mask / (1<<(j+1)));
                    chmin(dp[mask|(1<<j)][face(j, p)], dp[mask][i] + inv);
                }
            }
        }
    }
    int res = INF;
    for (int i=0; i<51; ++i) {
        res = min(res, dp[(1<<N)-1][i]);
    }
    cout << (res == INF ? -1 : res) << endl;

    return 0;
}


Measured memory_bytes: 52480
a = int(input().strip())
b = int(input().strip())
c = int(input().strip())
x = int(input().strip())

if a * 500 + b *100 + c * 50 < x:
    print(0)
else:
    count = 0
    for a_n in range(a+1):
        for b_n in range(b+1):
            for c_n in range(c+1):
                if (a_n * 500) + (b_n * 100) + (c_n * 50) == x:
                    count += 1
                else:
                    continue
    print(count)


Measured memory_bytes: 2940
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <regex>
#include <map>
#include <set>
using namespace std;
using ll = long long;

int main() {
    int a;
    string s;
    cin >> a >> s;
    
    if(a>=3200){
        cout << s << endl;
    }else{
        cout << "red" << endl;
    }
    
    
}



Measured memory_bytes: 256
//x??????????????°??§????????¨??????????????????
//????????????????????????????????´??°???????????¨??????????????????
//????????????????????????
#include<iostream>
using namespace std;

int main()
{
	int n,x;
	cin>>n;
	for(int i =1; i <=n ; i++){
	x=i;
	while(1){
	
		if(x%3==0){
			cout << " " <<i;
			break;
			}
		while(x){
		
			if(x%10==3){
				cout << " " <<i;
				break;
				}
			x/=10;
			}
		break;
		}
	}
	cout << endl;		
return 0;
}		
		
	

Measured memory_bytes: 1160
N,W = map(int,input().split())
w_L,v_L = [],[]

dp = [[0]*(W+1) for _ in range(N+1)]

for _ in range(N):
    w,v = map(int,input().split())
    w_L.append(w)
    v_L.append(v)

for i in range(N):
    for w in range(W+1):
        if w - w_L[i] >= 0:
            dp[i+1][w] = max(dp[i][w],dp[i][w-w_L[i]] + v_L[i])
            continue
        dp[i+1][w] = dp[i][w]

print(dp[N][W])

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

typedef long long ll;

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

	int m, n;
	while (true) {
	    cin>>m;
	    if(m==0) break;
		int sx[m], sy[m];
		for (int i = 0; i < m; i++) cin >> sx[i] >> sy[i];
		cin >> n;
		int cx[n], cy[n];
		for (int i = 0; i < n; i++) cin >> cx[i] >> cy[i];
		typedef pair<int, int> P;
		set<P> st;
		for (int i = 0; i < n; i++) st.insert(P(cx[i], cy[i]));
		for (int i = 0; i < n; i++) {
			int dx = cx[i] - sx[0], dy = cy[i] - sy[0];
			bool flg = false;
			for (int j = 0; j < m; j++) {
				if (st.count(P(sx[j]+dx, sy[j]+dy))) {
					continue;
				}
				flg = true;
				break;
			}
			if (flg) {
				continue;
			}
			cout << dx << ' ' << dy << endl;
			break;
		}
	}

	return 0;
}



Measured memory_bytes: 3192
#include<iostream>
#include<cmath>
using namespace std;
int main() {
	int n; cin >> n;
	int a[114514];
	a[0] = 0;
	for (int i = 1; i <= n; i++)cin >> a[i];
	a[n + 1] = 0;
	int sum = 0;
	for (int i = 1; i <= n + 1; i++)sum += abs(a[i - 1] - a[i]);
	for (int i = 1; i <= n; i++) {
		cout << sum - abs(a[i + 1] - a[i]) - abs(a[i] - a[i - 1]) + abs(a[i + 1] - a[i - 1]);
		cout << endl;
	}
	return 0;
}

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

#define FOR(i,b,e) for (int i = (b); i <= (e); i++)
#define FORD(i,b,e) for (int i = (b); i >= (e); i--)
#define SIZE(c) ((int) (c).size())

#define pb push_back
#define st first
#define nd second

using namespace std;


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

typedef vector <int> VI;
typedef vector <ll> VL;
typedef vector <bool> VB;
typedef vector <pii> VP;

typedef vector <VI> VVI;
typedef vector <VL> VVL;
typedef vector <VB> VVB;
typedef vector <VP> VVP;

const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000000000000001LL;


int main() {
    ios_base::sync_with_stdio(false);

    ll a, b, c;
    cin >> a >> b >> c;

    cout << b + min(c, a + b + 1);

    return 0;
}

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

int main() {
  int n, q;
  string s;
  cin >> n >> s >> q;
  vector<set<int>> is(26);
  rep(i,n) is[s[i]-'a'].insert(i);
  rep(qi,q) {
    int ty;
    cin >> ty;
    if (ty == 1) {
      int i; char c;
      cin >> i >> c;
      --i;
      is[s[i]-'a'].erase(i);
      s[i] = c;
      is[s[i]-'a'].insert(i);
    } else {
      int l, r;
      cin >> l >> r;
      --l;
      int ans = 0;
      rep(i,26) {
        auto it = is[i].lower_bound(l);
        if (it != is[i].end() && *it < r) ++ans;
      }
      printf("%d\n", ans);
    }
  }
  return 0;
}

Measured memory_bytes: 24196
#pragma GCC optimize("Ofast")  
#include<bits/stdc++.h>
using namespace std;

#define ll 				long long
#define eb 				emplace_back
const long long 		MOD = 1e9 + 7;
#define rep(i,n) 		for (int (i) = 0; (i) < (n); (i)++) 
#define REP(i,k,n)  	for (int (i) = (k); (i) <= (n); (i)++) 
#define REPR(i,k,n) 	for (int (i) = (k); (i) >= (n); (i)--)
#define watch(x) 		cout << (#x) << " = " << (x) << endl
#define t(x)			int x; cin >> x; while(x--)

int main()
{
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	
	/*---- continue Coding ;----*/

	string s;
	cin >> s;
	ll int ans = 0;
	rep(i, s.length()){
		int p = s[i] - '0';
		ans+=p;
	}
	if(ans%9 == 0){
		cout << "Yes" << "\n";
	}else{
		cout << "No" << "\n";
	}
	
	/*---- break ;----*/

	cerr<<"Execution time: "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<endl; 
	return 0;
}

Measured memory_bytes: 3872
#include <iostream>
#include <queue>
using namespace std;
int main() {
  int n;
  cin >> n;
  string s;
  cin >> s;
  priority_queue<int> r_index;
  priority_queue<int, vector<int>, greater<int>> w_index;
  for (int i = 0; i < n; ++i) {
    if (s.at(i) == 'R') r_index.push(i);
    else w_index.push(i);
  }

  if (r_index.empty() || w_index.empty()) {
    cout << 0 << endl;
  } else {
    int r = r_index.top(), w = w_index.top(), ans = 0;
    r_index.pop();
    w_index.pop();
    while (w - r < 1) {
      ++ans;
      w_index.push(r);
      r_index.push(w);
      r = r_index.top(); 
      w = w_index.top();
      r_index.pop();
      w_index.pop();
    }
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 4676
import java.util.Scanner;
public class Main {
    public static void main (String[] args) {
      
      Scanner scanner = new Scanner(System.in);
      int n = scanner.nextInt();	
      String s = scanner.next();	
      
      String w_char1 = " ";
      String w_char2 = " ";
      int r_cnt = 0;
      
      for (int i = 0;  i < n ; i ++ ) {
        w_char2 = s.substring(i, i + 1);
        if (w_char1.equals(w_char2)){
        }
        else{
          r_cnt ++;
          w_char1 = w_char2;
        }
      }
      
      System.out.println(r_cnt);

      return;
    }
  }


Measured memory_bytes: 31660
#include <cstdio>

bool search(int *A, int n, int key) {
    int i = 0;
    A[n] = key;
    while (A[i] != key) {
        ++i;
    }
    return i!= n;
}

int main() {
    int i, n, A[10000 + 1], m, q[500];
    int sum = 0;
    scanf("%d", &n);
    for (i = 0; i < n; ++i) {
        scanf("%d", &A[i]);
    }
    
    scanf("%d", &m);
    for (i = 0; i < m; ++i) {
        scanf("%d", &q[i]);
        if (search(A, n + 1, q[i])) 
            sum++;
    }
    printf("%d\n", sum);
    return 0;
}


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


int main(){
    int count;
    long answer = -1000000000;
    long mini = 10000000000;
    

    cin >> count;
    long r[count];
    for (int i = 0; i< count; i++){
        cin >> r[i];
        answer = max (r[i]-mini, answer);
        mini = min (r[i],mini);
    }
    cout << answer << endl;
    return 0;

}



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

using namespace std;

int main()
{
	string s, t = "CODEFESTIVAL2016";
	cin >> s;
	
	int n = 0;
	for (int i = 0; i < 16; i++) {
		if (s[i] != t[i]) {
			n++;
		}
	}
	cout << n << endl;

	return 0;
}

Measured memory_bytes: 256
n=int(input())
AB=[]
TMP=[]
cnt=0
key=True
for i in range(n):
    a,b=map(int,input().split())
    TMP.append(a)
    TMP.append(b)
    AB.append(TMP)
    TMP=[]
AB=sorted(AB, key=lambda x: x[1])
for i in range(n):
    cnt+=AB[i][0]
    if AB[i][1]<cnt:
        key=False
        
if key==True:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 42820
#include<iostream>
#include<algorithm>
#include<climits>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
#define INF INT_MAX/3
#define ALL(a) (a).begin(),(a).end()
#define PII pair<int,int>
#define PCC pair<char,char>
#define PCI pair<char,int>
#define PIC pair<int,char>
#define MP make_pair
#define DEBUG(x) cout<<#x<<": "<<x<<endl;

int main()
{
	int n;
	for (; cin >> n, n != 0;)
	{
		int Min = INF;
		int Max = -1;
		int sum = 0;
		REP(i, n)
		{
			int temp;
			cin >> temp;
			Min = min(Min, temp);
			Max = max(Max, temp);
			sum += temp;
		}
		sum =sum - Min - Max;
		int ans = sum / (n-2);
		cout <<ans<< endl;
	}
	return 0;
}

Measured memory_bytes: 3056
#include <iostream>
    using namespace std;
     
    int main(){
      string s;
      cin >> s;
      int l = (int)s.length();
      
      int loc_start = 0;
      int loc_end = 0;
      for(int i=0; i<l; i++){
        if( s[i] == 'A' ){
          loc_start = i;
          break;
        }
      }
      for(int i=l-1; i>=0; i--){
        if( s[i] == 'Z' ){
          loc_end = i;
          break;
        }
      }
      cout << loc_end - loc_start + 1 << endl;
      return 0;
    }

Measured memory_bytes: 640
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <math.h>
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <stack>
#include <queue>
#include <complex>
#include <set>
#include <list>
#include <iomanip>
#include <map>
#include <functional>
#include <string.h>

using namespace std;
static const double EPS = 1e-9;
typedef long long ll;
typedef unsigned long long ull;
#define rep(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a,0,sizeof(a))
#define minus(a) memset(a,0xff,sizeof(a))
#define chmax(a,b) a=min((a),(b))
#define chmin(a,b) a=max((a),(b))


#define MOD 1000000007

template <typename T>

class Bit {
public:
	vector<T> a;
	Bit(int n) {
		a.resize(n + 1);
	}
	void add(int x, T y) {
		for (int i = x; i < a.size(); i += (i&-i)) {
			a[i] += y;
		}
	}

	T sum(int x) {
		T ret = 0;
		for (int i = x; i > 0; i -= (i&-i)) {
			ret += a[i];
		}
		return ret;
	}
};

int comp(vector<ll> &a, vector<ll> &x) {
	x = a;
	int n = a.size();
	sort(a.begin(), a.end());
	a.erase(unique(a.begin(), a.end()), a.end());

	rep(i, n) {
		x[i] = lower_bound(a.begin(), a.end(), x[i]) - a.begin();
	}
	return a.size();
}

ll n, k;
vector<ll> a, x;

int main(){
	scanf("%lld %lld ", &n, &k);
	a.resize(n+1);
	a[0] = k;
	rep(i, n) {
		scanf("%lld ", &a[i+1]);
	}	
	rep(i, n + 1){
		a[i] -= k;
	}
	rep(i, n) {
		a[i + 1] += a[i];
	}
	
	comp(a, x);
	Bit<ll> bit(n+1);//
	ll ans = 0;
	
	rep(i, n + 1) {//
		ans += bit.sum(x[i]+1);
		bit.add(x[i] + 1, 1);

	}

	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
/*#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
/*template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;

#define LOCAL 0
#define dbg(x) cout << #x << " is " << x << "\n"
#define gll(x) scanf("%d",&x)
#define gll2(x,y) scanf("%d%d",&x,&y)
#define gll3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define gllarr(arr,n) f(i,n) gll(arr[i]);
#define sz(x) ((int)x.size())
#define s(x) sort(x.begin(),x.end())
#define all(v) v.begin(),v.end()
#define rs(v) { s(v) ; r(v) ; }
#define r(v) {reverse(all(v));}
#define pb push_back
#define f(i,n) for(int i=0;i<n;i++)
#define fr(i,n) for(int i=n-1;i>=0;i--)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)

const ll mod = (ll)1e9 + 7;
const ll inf = (ll)1e16;
const ld eps = 1e-12;
const ll N = (int)1e5 + 5;
const ll LOGN = 19;
const ld PI = 3.14159265358979323846;
inline ll mul(ll a, ll b, ll m = mod) { return (ll)(a * b) % m;}
inline ll add(ll a, ll b, ll m = mod) { a += b; if(a >= m) a -= m; if(a < 0) a += m; return a;}
inline ll power(ll a, ll b, ll m = mod) { if(b == 0) return 1; if(b == 1) return (a % m); ll x = power(a, b / 2, m); x = mul(x, x, m); if(b % 2) x = mul(x, a, m); return x;}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (LOCAL) {
        freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\input.txt", "r", stdin);
        freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\output.txt", "w", stdout);
    }
    int a, b;
    cin>>a>>b;
    int curr = 1;
    int ans = 0;
    while(curr < b) {
        curr += a - 1;
        ans++;
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 256
using System;

namespace ITP1_11_A
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] str = Console.ReadLine().Split(' ');
            int top = int.Parse(str[0]);
            int forward = int.Parse(str[1]);
            int right = int.Parse(str[2]);
            int left = int.Parse(str[3]);
            int back = int.Parse(str[4]);
            int bottom = int.Parse(str[5]);
            int tmp = 0;

            string operate = Console.ReadLine();
            char[] chara = operate.ToCharArray();

            foreach ( int c in chara)
            {
                switch (c)
                {
                    case 'E':
                        //forward = forward;
                        //back = back;
                        tmp = top;
                        top = left;
                        left = bottom;
                        bottom = right;
                        right = tmp;

                        break;
                    case 'N':
                        //right = right;
                        //left = left;
                        tmp = top;
                        top = forward;
                        forward = bottom;
                        bottom = back;
                        back = tmp;

                        break;
                    case 'W':
                        //forward = forward;
                        //back = back;
                        tmp = top;
                        top = right;
                        right = bottom;
                        bottom = left;
                        left = tmp;

                        break;
                    case 'S':
                        //right = right;
                        //left = left;
                        tmp = top;
                        top = back;
                        back = bottom;
                        bottom = forward;
                        forward = tmp;

                        break;
                }
            }

            Console.WriteLine(top);

        }
    }
}

Measured memory_bytes: 9260
#ABC141-C Attack Survival 
import numpy as np
N, K, Q = map(int, input().split())
A = np.array([int(input()) for _ in range(Q)])
Res = np.zeros(N)
for a in A:
    Res[a-1] += 1
for i in range(N):
    print('Yes') if Res[i] > Q - K else print('No') #Q-K+1回正解すれば生き残る

Measured memory_bytes: 17124
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,s,n) for(int i=(s); i<(n); i++)
#define all(v) v.begin(),v.end()
#define outve(v) for(auto i : v) cout << i << " ";cout << endl
#define outmat(v) for(auto i : v){for(auto j : i) cout << j << " ";cout << endl;}
#define in(n,v) for(int i=0; i<(n); i++){cin >> v[i];}
#define out(n) cout << (n) << endl
#define fi first
#define se second
#define pb push_back
#define mod 1000000007
#define infi 1900000000
#define infl 1100000000000000000
#define cyes cout << "Yes" << endl
#define cno cout << "No" << endl
#define csp << " " <<
#define outset(n) cout << fixed << setprecision(n);
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vs = vector<string>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vvp = vector<vector<pair<int,int>>>;
template<typename T> using ve = vector<T>;
template<typename T> using pq2 = priority_queue<T>;
template<typename T> using pq1 = priority_queue<T,vector<T>,greater<T>>;
template<typename T> bool chmax(T &a, T b) {if(a < b) {a = b;return 1;}return 0;}
template<typename T> bool chmin(T &a, T b) {if(a > b) {a = b;return 1;}return 0;}




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

    string S,T;
    cin >> S >> T;
    int ans = 0;
    rep(i,int(S.length())) if(S[i] != T[i]) ans++;
    cout << ans << endl;
    
    

    return 0;
}


Measured memory_bytes: 3788
N, M = map(int, input().split())
H = input().split()

Evaluation = [0] * N

for i in range(M):
  A, B = map(int, input().split())
  if int(H[A-1]) > int(H[B-1]):
    Evaluation[B-1] += 1
  elif int(H[A-1]) < int(H[B-1]):
    Evaluation[A-1] += 1
  else:
    Evaluation[A-1] += 1
    Evaluation[B-1] += 1

count = 0    
for i in range(N):
  if Evaluation[i] == 0:
    count += 1

print(count)

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

int main() {
    
    // 1. input.
    int S;
    cin >> S;
    
    // 2. calculate the time.
    int h = S / 3600;
    int m = (S - 3600 * h) / 60;
    int s = (S - 3600 * h - 60 * m) % 60;
    
    // 3. output answer.
    cout << h << ":" << m << ":" << s << endl;
    
    return 0;
    
}


Measured memory_bytes: 3076
// https://atcoder.jp/contests/abc087/tasks/arc090_a

#include <bits/stdc++.h>

using namespace std;

#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)
#define DUMP(a, n) REP(_i, n) printf("%d%c", a[_i], _i + 1 == n ? '\n' : ' ')
#define DUMP2D(a, n, m) REP(_i, n) REP(_j, m) printf("%d%c", a[_i][_j], _j + 1 == m ? '\n' : ' '); puts("")

const int N_MAX = 100;
const int A_IJ_MAX = 100;
const int I_MAX = 2;

int N;
int A[2][N_MAX];

void solve() {
  int sum = A[0][0];
  REP(i, N) sum += A[1][i];
  int ans = sum;
  REP(i, N - 1) {
    sum = sum + A[0][i + 1] - A[1][i];
    ans = max(ans, sum);
  }
  printf("%d\n", ans);
}

void input() {
  scanf("%d", &N);
  REP(i, 2) REP(j, N) scanf("%d", &A[i][j]);
}

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


Measured memory_bytes: 256
#include<cstdio>
using namespace std;
int n,m,k;
long long gcd(int x,int y)
{
	if (y==0) return x;
	return gcd(y,x%y);
}
void swap(long long &x,long long &y)
{
	long long t=x;x=y;y=t;
}
long long calculate(int r,int c)
{
	long long total=0;
	int pnum=0; 
	for (long long x=1;x<r;x++)
	{
		if (x*c>2*k-1+c*3) break;
		for (long long y=1;y<c;y++)
		{
			int start=x+1;
			long long s=2*k-1-(x*c-x*y-gcd(x,y));
			start=s/y-1;
			if (start<=x) start=x+1;
			if (start>=r) start=r-1;
			if (r<=x+1) continue;
			total+=(start-x-1);
		//	start=x+1;
			for (long long z=start;z<r;z++)
			{
				long long p=z*y-gcd(c-y,z)-gcd(z-x,c);
				if (x*c+z*y-x*y>2*k-1+c*3) break;
				if (p<=s) total++;
			}
			pnum++;
		//	printf("%d\n",total);
			if (pnum==9)
			{
				total++;total--;
			}
		}
	}
	total*=2;
	for (long long x=1;x<r;x++)
	{
		if (x*c>2*k-1+c*3) break;
		for (long long y=1;y<c;y++)
		{
			long long z=x;
			long long p=x*c+z*y-x*y-gcd(x,y)-gcd(c-y,z)-gcd(z-x,c);
			if (p<=2*k-1) total++;
		}
	}
	return total*2;
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	//n++;m++;
	long long ans=0;
	ans=calculate(n,m);
	ans=ans+calculate(m,n);
	printf("%lld\n",ans);
}


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

int main() {
	// your code goes here
    int n;
    cin>>n;
    
    string s;
    cin>>s;
    
    int count=0;
    for(int i=0;i<n-1;i++){
        if(s[i]!=s[i+1]){
            count++;
        }
    }
    
    cout<<count+1<<endl;
}


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

int main()
{
    int n,x;
    cin>>n>>x;
    
    int a[n];
    int ans=0;
    
    for(int i=0;i<n;i++) cin>>a[i];
    
    sort(a,a+n);

    
    for(int i=0;i<n;i++){
        if(a[i]<=x){
            x-=a[i];
            ans++;
        }
        else{
            cout<<ans<<endl;
            return 0;
        }
    }
    if(x!=0&&ans!=0) ans-=1;
    
    cout<<ans<<endl;
   
}

Measured memory_bytes: 256
import os
import sys

from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def is_ok(n):
    s = str(n)
    ok = True
    for a, b in zip(s, s[1:]):
        if not abs(int(a) - int(b)) <= 1:
            return False
    return True


@lru_cache(maxsize=None)
def rekkyo(n, d):
    if d == 0:
        return ['']
    ret = []
    if n > 0:
        for s in rekkyo(n - 1, d - 1):
            ret.append(str(n - 1) + s)
    for s in rekkyo(n, d - 1):
        ret.append(str(n) + s)
    if n < 9:
        for s in rekkyo(n + 1, d - 1):
            ret.append(str(n + 1) + s)
    return ret


K = int(sys.stdin.buffer.readline())

s = set()
for i in range(10):
    for j in range(1,11):
        a = rekkyo(i, j)
        s |= set(a)
a = list(sorted(set(list(map(int, s)))))
print(a[K])
# for aa in a:
#     print(aa)


Measured memory_bytes: 119240
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{HashMap, HashSet, BinaryHeap, VecDeque, BTreeSet, BTreeMap};
#[allow(unused_imports)]
use std::iter::FromIterator;
#[allow(unused_imports)]
use std::io::stdin;

mod util {
    use std::io::stdin;
    use std::str::FromStr;
    use std::fmt::Debug;

    #[allow(dead_code)]
    pub fn line() -> String {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.trim().to_string()
    }

    #[allow(dead_code)]
    pub fn gets<T: FromStr>() -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.split_whitespace()
            .map(|t| t.parse().unwrap())
            .collect()
    }
}

#[allow(unused_macros)]
macro_rules! get {
    ($t:ty) => {
        {
            let mut line: String = String::new();
            stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
                    get!($t)
                   ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
                    get!($($t),*)
                   ).collect::<Vec<_>>()
    };
    ($t:ty ;;) => {
        {
            let mut line: String = String::new();
            stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

#[derive(Eq, PartialEq, Clone, Debug)]
struct Rev<T>(pub T);

impl<T: PartialOrd> PartialOrd for Rev<T> {
    fn partial_cmp(&self, other: &Rev<T>) -> Option<Ordering> {
        other.0.partial_cmp(&self.0)
    }
}

impl<T: Ord> Ord for Rev<T> {
    fn cmp(&self, other: &Rev<T>) -> Ordering {
        other.0.cmp(&self.0)
    }
}

fn main() {
    let (h, _w) = get!(usize, usize);
    let mut c: Vec<Vec<usize>> = (0..10).map(|_| util::gets()).collect();
    let a: Vec<Vec<isize>> = (0..h).map(|_| util::gets()).collect();

    for k in 0..10 {
        for i in 0..10 {
            for j in 0..10 {
                c[i][j] = min(c[i][j], c[i][k] + c[k][j]);
            }
        }
    }

    let ans = a.iter()
        .flat_map(|v| v.clone().into_iter())
        .filter(|&n| n >= 0)
        .map(|n| c[n as usize][1])
        .sum::<usize>();

    println!("{}", ans);
}


Measured memory_bytes: 4352
#include<stdio.h>
#include<stdlib.h>
int compare(const void *a,const void *b){
return *(int*)a-*(int*)b;
}
int main(){
int n,m,a,sum[111111];
scanf("%d%d",&n,&m);
int i;
for(i=0;i<n;i++){
scanf("%d",&a);
if(i==0)
sum[0]=a;
else
sum[i]=sum[i-1]+a;
sum[i]=sum[i]%m;
}
qsort(sum,n,sizeof(int),compare);
long count=1,memory=-1,ans=0;
for(i=0;i<n;i++){
if(sum[i]==0)
ans++;
if(sum[i]!=memory){
ans+=count*(count-1)/2;
count=1;
memory=sum[i];
}
else
count++;
}
ans+=count*(count-1)/2;
printf("%ld\n",ans);
return 0;
}

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

int main(){
    string s;
    cin >> s;
    bool pok = false,sok = false;
    if(s[0] == '0'){
        if(s[1] != '0')pok = true;
    }
    if(s[0] == '1'){
        if(s[1] - '0' <= 2)pok = true;
    }
    if(s[2] == '0'){
        if(s[3] != '0')sok = true;
    }
    if(s[2] == '1'){
        if(s[3] - '0' <= 2)sok = true;
    }
    if(pok && sok){
        cout << "AMBIGUOUS" << endl;
    }else if(pok && !sok){
        cout << "MMYY" << endl;
    }else if(!pok && sok){
        cout << "YYMM" << endl;
    }else{
        cout << "NA" << endl;
    }
}

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

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

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <string>    
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll n, T, t[200008];

int main(){
	cin >> n >> T;
	for(ll i = 1; i <= n; i++){cin >> t[i];}
	
	ll ans = 0;
	for(ll i = 2; i <= n; i++){ans += min(t[i]-t[i-1], T);}
	ans += T;
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1792
#include <stdio.h>
int main(void)
{
    while (1) {
        int x, y, s, i, j, res;
        scanf("%d%d%d", &x, &y, &s);
        if (x==0) break;

        res=0;
        for(i=1;i<s;++i) {
            for(j=1;j<s;++j) {
#define f(x, t) x*(100+t)/100
                if (f(i, x)+f(j, x)==s)
#define max(x, y) (x>y?x:y)
                    res=max(res, f(i, y)+f(j, y));
            }
        }
        printf("%d\n", res);
    }
    return 0;
}

Measured memory_bytes: 600
#include <iostream>

using namespace std;

long long int A, B, C, D, ans = 0, smaller, larger;

int main() {
	cin >> A >> B >> C >> D;
	if (B < D) {
		smaller = B;
	}
	else {
		smaller = D;
	}
	if (A < C) {
		larger = C;
	}
	else {
		larger = A;
	}
	for (int i = larger; i <= smaller; i++) {
		ans++;
	}
	if (ans > 0) {
		ans--;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,k = inpm()
ans = 0
for i in range(k, n+2):
    L = i*(i-1)//2
    R = (n+n-i+1)*i//2
    ans += (R-L+1)%mod
    ans %= mod
print(ans)

Measured memory_bytes: 31136
W,H,N=map(int,input().split())
xya=[list(map(int,input().split())) for i in range(N)]

boundary=[0,0,W,H]

for i in range(N):
  a=xya[i][2]
  if a==1:
    if boundary[0]<xya[i][0]:
      boundary[0]=xya[i][0]
  elif a==2:
    if boundary[2]>xya[i][0]:
      boundary[2]=xya[i][0]
  elif a==3:
    if boundary[1]<xya[i][1]:
      boundary[1]=xya[i][1]
  else:
    if boundary[3]>xya[i][1]:
      boundary[3]=xya[i][1]
  if boundary[0]>=boundary[2] or boundary[1]>=boundary[3]:
    break

print(max(0,(boundary[2]-boundary[0])*(boundary[3]-boundary[1])))

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
const int dy[] = {1, 0, -1, 0};
const int dx[] = {0, 1, 0, -1};
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int k;
    cin >> k;
    vector<int> v;
    for(int i = 0; i < k; i++)
    {
        int x; cin >> x;
        v.push_back(x);
    }
    for(int i = 0; i < (1<<n); i++)
    {
        vector<int> w;
        for(int j = 0; j < n; j++)
        {
            if(i & (1<<j)) w.push_back(j);
        }
        int cnt = v.size();
        for(int j = 0; j < w.size(); j++)
        {
            for(int k = 0; k < v.size(); k++)
            {
                if(v[k] == w[j]) cnt--;
            }
        }
        if(cnt == 0)
        {
            cout << i << ":";
            for(int j = 0; j < w.size(); j++) cout << " " << w[j];
            cout << endl;
        }
    }
    return 0;
}



Measured memory_bytes: 3160
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

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

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

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

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


fn solve(x: i64, mut a: Vec<i64>) -> i64 {
    let mut res = 0;
    for i in 1..a.len() {
        let sum = a[i-1] + a[i];
        let mut diff = sum - x;
        if diff > 0 {
            if diff < a[i] {
                res += diff;
                a[i] -= diff;
            } else {
                res += diff;
                diff -= a[i];
                a[i] = 0;
                a[i-1] = diff;
            }
        }
    }
    res
}


fn main() {
    input!{
        n: usize,
        x: i64,
        a: [i64; n]
    }

    println!("{}", solve(x, a));
}




Measured memory_bytes: 6396
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>
#include <string>

#define reps(i,s,n) for(int (i) = (s); (i) < (n); (i)++)
#define rep(i,n) reps(i,0,n)
using namespace std;
using ll = long long;

vector<int> vs[26],vt[26];

int main(){
    string s,t;
    cin >> s >> t;
    int n = s.length();
    rep(i,n){
        int pos = s[i] - 'a';
        vs[pos].push_back(i);
        pos = t[i] - 'a';
        vt[pos].push_back(i);
    }
    vector<bool> check(26,false);
    
    rep(i,n){
        int p1 = s[i]-'a';
        int p2 = t[i]-'a';
        if(!check[p1]){
            rep(j,vs[p1].size()){
                if(vs[p1][j] != vt[p2][j]){
                    cout << "No" << endl;
                    return 0;
                }
            }
            check[p1] = true;
        }
    }

    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 3080
n = int(input())
a = list(map(int,input().split()))
ans = sum(a)

import collections
cca = collections.Counter(a)

for i in range(int(input())):
    b,c = map(int,input().split())
    num = cca[b]
    cca[b] = 0
    cca[c] += num 
    ans -= num*(b-c)
    
    print(ans)

Measured memory_bytes: 24156
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
map<string,int>mp;
int main()
{
    std::ios::sync_with_stdio(false);
    int n;
    cin>>n;
    int max1=0;
    for(int i=1;i<=n;i++)
    {
        string a;
        cin>>a;
        mp[a]++;
        max1=max(max1,mp[a]);
    }
    std::map<string,int>::iterator it=mp.begin();
    for(;it!=mp.end();it++)
    {
        if(it->second==max1)
            cout<<it->first<<endl;
    }
    return 0;
}


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

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define replrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) replrev(i,0,n)
#define repi(itr,ds) for(auto itr = ds.begin(); itr != ds.end(); ++itr)
#define mp make_pair
#define INF 2000000000
#define MOD 1000000007
#define PI 3.1415926536
typedef long long ll;
typedef pair<int, int> P;

int main() {
	int N;
	cin >> N;
	vector<ll> a(N), diff(N);
	ll sum = 0;
	rep(i, N) {
		cin >> a[i];
		sum += a[i];
	}
	if (N == 1) {
		cout << "YES" << endl;
		return 0;
	}
	if (sum % ((ll)N*(N + 1) / 2) != 0) {
		cout << "NO" << endl;
		return 0;
	}
	ll K = sum / ((ll)N*(N + 1) / 2);
	rep(i, N) {
		diff[i] = a[(i + 1) % N] - a[i];
	}
	ll num = 0;
	rep(i, N) {
		if (K < diff[i] || (K - diff[i]) % N != 0) {
			cout << "NO" << endl;
			return 0;
		}
		num += (K - diff[i]) / N;
	}
	if (num != K) {
		cout << "NO" << endl;
	}
	else {
		cout << "YES" << endl;
	}

	return 0;
}

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

using namespace std;

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

    int r , d , cur;
    cin >> r >> d >> cur;

    for (int i = 0 ;i < 10 ;i++) {
        cur = r * cur - d;
        cout << cur << '\n';
    }
}

Measured memory_bytes: 3648
#include"bits/stdc++.h"

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define FOR(k,m,n) for(ll (k)=(m);(k)<(n);(k)++)
#define REP(i,n) FOR((i),0,(n))
#define WAITING(str) int str;std::cin>>str;
#define DEBUGING(str) cout<< #str << " " str<<endl

constexpr int INF = (1 << 30);
constexpr ll INFL = (1ll << 60);
constexpr ll MOD = 1000000007;// 10^9+7
using ar3 = array<ll, 3>;


int main()
{
	ll N, Q;
	cin >> N >> Q;
	vector<ar3> xst(N);
	REP(i, N) {
		cin >> xst[i][1] >> xst[i][2] >> xst[i][0];
		xst[i][1] -= xst[i][0];
		xst[i][2] -= xst[i][0];
	}
	sort(xst.begin(), xst.end());

	set<ll> st;
	map<ll, ll> mp;
	REP(i, Q) {
		ll d;
		cin >> d;
		st.insert(d);
		mp[d] = i;
	}

	vector<ll> res(Q, -1);
	for (auto ar : xst) {
		ll x = ar[0];
		ll s = ar[1];
		ll t = ar[2];
		while (true) {
			auto itr = st.lower_bound(s);
			if (itr == st.end())break;
			ll d = *itr;
			if (d >= t)break;

			ll idx = mp[d];
			res[idx] = x;
			st.erase(itr);
		}
	}
	for (auto num : res)cout << num << endl;
	return 0;
}


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


using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define fore(i,a) for(auto &i:a)

typedef pair <int, int> P;
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
const int  INF = 1 << 30;
const ll INFL = 1LL<<60;
const ll mod =1000000007;





int main() {

	int n, k;
	cin >> n >> k;

	double nn = n, kk = k;
	double a = 0;

	FOR(i, 1, n + 1) {
		int b = (k - 1) / i;
		int cnt = 0;
		while (b) {
			b /= 2;
			cnt++;
		}
		a += 1 / (n*pow(2, cnt));
	}

	cout << fixed << setprecision(15) << a << endl;

}

Measured memory_bytes: 256
N = int(input())
*A, = map(int, input().split())

color = []
over = 0
for rate in A:
    if rate >= 3200:
        over += 1
    else:
        num = int(rate / 400)  # 0 ~ 7
        color.append(num)

color = set(color)
if len(color) == 0:
    mini = 1
    maxi = over

else:
    mini = len(color)
    maxi = mini + over
print("{} {}".format(mini, maxi))

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

int main(){
    string S;int K;cin>>S>>K;
    int N=S.size();
    set<string> a;
    rep(i,N){
        for(int j=1;j<=5;j++){
            if(i+j>N)continue;
            a.insert(S.substr(i,j));
        }
    }
    auto itr=a.begin();
    rep(i,K-1)itr++;
    cout<<*itr<<endl;
    return 0;
}

Measured memory_bytes: 1664
use std::io::*;
use std::str::FromStr;

fn main() {
    let n: usize = read();
    let m: usize = read();
    let mut x: Vec<i64> = (0..m).map(|_| read()).collect();
    if m < n {
        println!("{}", 0);
        return;
    }

    x.sort();
    let mut vec: Vec<i64> = vec![0; m-1];
    for i in 0..m-1 {
        vec[i] = x[i+1] - x[i];
    }
    vec.sort();
    let mut ans: i64 = 0;
    for i in 0..m-n {
        ans += vec[i];
    }
    println!("{}", ans);
}

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}

Measured memory_bytes: 6396