akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <iostream>

using namespace std;

#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int N, A[202020], M, X[202020];
i64 dp[202020];
i64 S[202020];

int uf[4040404];

int root(int p)
{
	return uf[p] < 0 ? p : (uf[p] = root(uf[p]));
}
void join(int p, int q)
{
	p = root(p);
	q = root(q);
	if (p == q) return;

	if (p < q) swap(p, q);
	uf[p] += uf[q];
	uf[q] = p;
}

const int OFS = 2010101;

void precalc()
{
	S[0] = 0;
	for (int i = 1; i < N; ++i) S[i] = S[i - 1] + A[i - 1];
	dp[N - 1] = 0;
//	i64 acc = A[N - 1] - dp[N - 1] - S[N - 1];
	for (int i = 0; i <= 2 * OFS; ++i) uf[i] = -1;

	vector<int> unres;
	for (int i = OFS; i >= -OFS; --i) unres.push_back(i);

	for (int i = N - 2; i >= 2; --i) {
		// acc = max(acc, A[i] - (acc + S[i + 1]) - S[i])
		int app = A[i] - S[i + 1] - S[i];
		while (!unres.empty()) {
			int v = unres[unres.size() - 1];
			if (v < app - v) {
				join(v + OFS, app - v + OFS);
				unres.pop_back();
			} else {
				break;
			}
		}

	}
}

i64 solve()
{
	i64 acc = A[N - 1] - S[N - 1];
	if (acc > OFS) {
	} else if (acc < -OFS) {
		acc = -acc;
	} else {
		acc = root(acc + OFS) - OFS;
	}
	/*
	for (int i = N - 2; i >= 2; --i) {
		acc = max(acc, A[i] - S[i + 1] - S[i] - acc);
	}
	*/

	for (int i = 1; i >= 1; --i) {
		dp[i] = acc + S[i + 1];
		acc = max(acc, A[i] - dp[i] - S[i]);
	}
	return dp[1] + A[0] - A[1];
}

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N - 1; ++i) scanf("%d", A + i);
	scanf("%d", &M);
	for (int i = 0; i < M; ++i) scanf("%d", X + i);

	precalc();
	for (int i = 0; i < M; ++i) {
		A[N - 1] = X[i];
		printf("%lld\n", solve());
	}
	return 0;
}


Measured memory_bytes: 35688
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main (){
	string str;
	int i;
	cin>>str;
	cin>>i;
	while (i--){
	string A,B;
	int X,Y;
		cin >> A >> X >> Y;
		if(A=="replace"){cin>>B;str.replace(str.begin()+X,str.begin()+Y+1,B);}else
		if (A=="reverse"){reverse(str.begin()+X,str.begin()+Y+1);}else
		{for(int gg=X;gg<=Y;gg++){cout<<str.at(gg);}cout<<endl;}
	}
	return 0;
}

/*switch(A){
			case "replace":cin>>B;str.replace(X,Y,B);break;
			//case "reverse":reverse(str.X,str.Y);break;
			case "print":for(int gg=X;gg<=Y;gg++){cout<<str.at(gg);}cout<<endl;break;		
		}*/

Measured memory_bytes: 1216
#include <iostream>
#include <math.h>
#include <cmath>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <deque>  
#include <iomanip>

using namespace std;

#define ll long long
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
#define rep(i, n) for(int i = 0; i < n; i++)
#define loop(i, a, n) for(int i = a; i < n; i++)
#define all(in) in.begin(), in.end()
#define vint vector<int>

int main(){
    int N; cin >> N;
    double ans = 0.0, A;
    rep(i, N){
        cin >> A;
        ans += 1.0/A;
    }
    ans = 1.0/ans;
    cout << setprecision(15) << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
class Main{
	static Scanner s = new Scanner(System.in);
	public static void main(String[] args) {
		int a,b,n;
		int[][] node;
		while((((a=s.nextInt())|(b=s.nextInt()))!=0)) {
			n=s.nextInt();
			node = new int[a][b];
			for(int i=n;i>0;i--)
				node[Integer.parseInt(s.next())-1][Integer.parseInt(s.next())-1]=-1;
			node[node.length-1][node[0].length-1]=1;

			ArrayDeque<Point> deque = new ArrayDeque<Point>();

			deque.add(new Point(node.length-1, node[0].length-1));

			Point p,buf;
			while((p=deque.poll())!=null) {
				if(p.x!=0&&node[p.x-1][p.y]!=-1) {
					node[p.x-1][p.y]+=node[p.x][p.y];
					if(!deque.contains(buf = new Point(p.x-1, p.y))) {
						deque.addFirst(buf);
					}
				}
				if(p.y!=0&&node[p.x][p.y-1]!=-1) {
					node[p.x][p.y-1]+=node[p.x][p.y];
					if(!deque.contains(buf = new Point(p.x, p.y-1))) {
						deque.add(buf);
					}
				}
			}
			/*
			for(int[] z:node)
				System.out.println(Arrays.toString(z));
			*/
			System.out.println(node[0][0]);
		}
	}
}
class Point{
	int x,y;
	Point(int x,int y) {
		this.x=x;
		this.y=y;
	}
	@Override
	public String toString() {
		return "("+x+","+y+")";
	}
	@Override
	public boolean equals(Object obj) {
		Point p=(Point) obj;
		return p.x==x&&p.y==y;
	}
}

Measured memory_bytes: 26224
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=1e5+5;

int main(){
	ll n,a[M],f=1,maxn;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		if(i==0) maxn=a[i];
		if(a[i]>maxn) maxn=a[i];
		else if(maxn-a[i]>1) f=0;
	}
	if(f) cout<<"Yes";
	else cout<<"No";
	
	return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;
public class Main {

    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int height = scan.nextInt();
        int width = scan.nextInt();
        int area = height*width;
        int lap = height*2 + width*2;
        System.out.println(area +" "+ lap);
        
    }
    
}


Measured memory_bytes: 26240
#include<stdio.h>
int main()
{
	int n, i;
	scanf("%d",&n);
	i = n%10;
	if (i==2 || i==4 || i==5 || i==7 || i==9)
		printf("hon");
	else if (i==0 || i==1 || i==6 || i==8)
		printf("pon");
	else
		printf("bon");
	return 0;
	
}

Measured memory_bytes: 1720
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t,a,p,c=0;
    vector<int>v,v1;
    cin>>t;
    for(int i=1; i<=t; i++)
    {
        cin>>a;
        v.push_back(a);
    }
    sort(v.begin(),v.end());
    p=sqrt(v[0]);
    for(int i=p; i>=1; i--)
    {
        if(v[0]%i==0)
        {
            v1.push_back(i);
            v1.push_back(v[0]/i);
        }
    }
    p=sqrt(v[t-1]);
    for(int i=p; i>=1; i--)
    {
        if(v[t-1]%i==0)
        {
            v1.push_back(i);
            v1.push_back(v[t-1]/i);
        }
    }
    sort(v1.begin(),v1.end());
    reverse(v1.begin(),v1.end());
    for(int i=0; i<v1.size(); i++)
    {
        c=0;
        for(int j=0; j<t; j++)
        {
            if(v[j]%v1[i]!=0)
            {
                c++;
                if(c==2)
                    break;
            }
        }
        if(c==1 || c==0)
        {
            cout<<v1[i]<<endl;
            break;
        }
    }
}


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

int main() {

  int a; 
  int b;
  int c;
  int d;
  cin >> a;
  cin >> b;
  cin >> c;
  cin >> d; 
  
  int l = a + b;
  int r = c + d;
  
    if (l > r) {
      cout << "Left" << endl;
    }

  	else if (l < r) {
      cout << "Right" << endl;
    }

  	else if (l = r) {
      cout << "Balanced" << endl;
    }
}


Measured memory_bytes: 256
/**
 *   author: Shubham Srivastava
 *   created: 01 September 2019  17:47:19
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    ll n;cin>>n;
    vector <ll> arr(n);
    for(int i=0;i<n;i++)
        cin>>arr[i];
    ll count = 0;
    ll ans = 0;
    for(int j=n-2;j>=0;j--){
        if(arr[j] >= arr[j+1]){
            count++;
            //cout<<"j: "<<j<<" "<<count<<endl;
            ans = max(ans,count);
        }
        else
            count = 0;
    }
    cout<<ans;
return 0;
}

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

int main(){
	int a,b,c,k;
	cin>>a>>b>>c>>k;
	
	if(a>=k)
		cout<<k; 
	else if(a<=k && a+b>=k)
		cout<<a;
	else
		cout<<a-(k-a-b);
		
	return 0;
}

Measured memory_bytes: 3600
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		try {
			int taryo = sc.nextInt();
			int ureshii500 = taryo / 500;
			int ureshii5 = (taryo - (ureshii500 * 500)) / 5;

			System.out.println((ureshii500 * 1000) + (ureshii5 * 5));

		} finally {
			sc.close();
		}
	}

}


Measured memory_bytes: 21972
#include <bits/stdc++.h>
#define debug(x) cerr << #x << ": " << x << '\n';
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;

int H, W;
char A[1000][1000];
int dist[1000][1000];

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

int main(void){
    cin >> H >> W;
    queue<P> que;
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            cin >> A[i][j];
            if(A[i][j] == '#'){
                dist[i][j] = 0;
                que.push(P(i, j));
            }else{
                dist[i][j] = INF;
            }
        }
    }

    int res = 0;

    while(not que.empty()){
        P p = que.front();
        que.pop();
        int y = p.first, x = p.second;

        for(int i = 0; i < 4; i++){
            int ny = y + dy[i], nx = x + dx[i];
            if(ny < 0 or H <= ny or nx < 0 or W <= nx or A[ny][nx] == '#' or dist[ny][nx] < INF) continue;
            dist[ny][nx] = dist[y][x] + 1;
            que.push(P(ny, nx));
            res = max(res, dist[ny][nx]);
        }
    }

    cout << res << '\n';

    return 0;
}

Measured memory_bytes: 13328
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, A: int, B: int, S: str):
    ans = []
    passed = 0
    passed_b = calc_passed_b(S)
    for i, s in enumerate(S):
        if s == "a" and passed < A + B:
            # 国内学生の通過
            passed += 1
            ans.append("Yes")
            continue
        if s == "b" and passed < A + B:
            # 海外学生の通過
            if passed_b[i] <= B:
                passed += 1
                ans.append("Yes")
                continue

        ans.append("No")

    for a in ans:
        print(a)
    return


def calc_passed_b(S: str) -> "List[int]":
    pass_b = []
    passed = 0
    for s in S:
        if s == "b":
            passed += 1
        pass_b.append(passed)
    return pass_b


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, A, B, S)


if __name__ == "__main__":
    main()


Measured memory_bytes: 8900
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
	ll s=0;char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) s=s*10+ch-'0',ch=getchar();
	return s;
}
const int N=2e5+5,mod=998244353;
int n;
int d[N],b[N];
inline ll qpow(ll a,ll b){
	ll res=1;
	for(;b;b>>=1,a=a*a%mod) if(b&1) res=res*a%mod;
	return res;
}
int main(){
	n=read();
	int mx=0;
	for(int i=1;i<=n;i++) scanf("%d",&d[i]),b[d[i]]++,mx=max(mx,d[i]);
	int s=0;ll ans=1;
	for(int i=1;i<=mx;i++) if(b[i]==0){
		printf("0");return 0;
	}
	if(b[0]!=1||d[1]!=0) {
		ans=0;
	}else {
		for(int i=1;i<=mx;i++) ans=ans*qpow(b[i-1],b[i])%mod;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 1024
#include<cstdio>
#include<iostream>
#include<cmath>

using namespace std;

int main(void) {

	int n;

	double t, a, h[1000], tmp = 100000, num;

	cin >> n >> t >> a;

	for (int i = 0; i < n; i++) {
		cin >> h[i];
		if (fabs(a - t + h[i] * 0.006) <= tmp) {
			tmp = fabs(a - t + h[i] * 0.006);
			num = i + 1;
		}
	}

	cout << num << "\n";

	return 0;
}

Measured memory_bytes: 256
A,B,C,D = map(int,input().split())
if B <= C :
    print(0)
elif D <= A :
    print(0)
elif A <= D and C <= B :
    if A <= C  and D <= B :
        print(D-C)
    elif C <= A and B <= D :
        print(B-A)
    elif (D-A) > (B-C) :
        print(B-C)
    else :
        print(D-A)
        

Measured memory_bytes: 3060
import java.io.*;
import java.util.*;

public class Main{

      public static void main(String []args)/*throws IOException*/{
        
        /*
        InputStreamReader reader=new InputStreamReader(System.in);
 
        BufferedReader input =
			new BufferedReader (new InputStreamReader (System.in));
			
		int key = reader.read();
		String str = input.readLine();
		*/
		Scanner stdIn = new Scanner(System.in);
		
		int x,ans;
		
		x = stdIn.nextInt();
        int b_max = (int)Math.sqrt(x);
		ans = 1;
        if(x >= 4){
		for(int i = 2;i <= b_max;i++){
		    for(int j = 2;Math.pow(i,j) <= x;j++){
		        if(ans < Math.pow(i,j))
		            ans = (int)Math.pow(i,j);
		    }
		}
        }
	    
		System.out.println(ans);
	
     }
}

Measured memory_bytes: 21844
#include<stdio.h>
int main(){
    int a=0,b=0,c=0,d=0,e=0;
    scanf("%d %d %d",&a ,&b ,&c);
    d=c-(a-b);
    if(d>0){
        printf("%d",d);
    }
    else{
        printf("0");
    }
    return 0;

    }


Measured memory_bytes: 128
import java.util.*; 

class Main{
public static void main(String[] args){
	Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
  		int[] a=new int[n];

  		long[] b=new long[n+1];
  		b[0]=0;
		for(int c=0;c<n;c++){
    		a[c]=sc.nextInt();
          	b[a[c]]++;
    	}
  		long d=0;
  
  		for(int c=0;c<n+1;c++){
        	d+=b[c]*(b[c]-1)/2;
        }
  		long ans=0;
  		for(int c=1;c<n+1;c++){
          if(b[a[c-1]]!=0){
        	ans=d-b[a[c-1]]*(b[a[c-1]]-1)/2+(b[a[c-1]]-1)*(b[a[c-1]]-2)/2;
          }else{
          ans=d;
          }
          System.out.println(ans);
        }
    
 	

    	
    }
}

Measured memory_bytes: 101600
#include <stdio.h>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <iostream>
#include<math.h>
#include<bitset>
#include<iomanip>
#include<queue>
using namespace std;

int main() {
	int N, K; cin >> N >> K;
	int ans = (N - 1)*(N - 2) / 2;
	if ((N - 1)*(N - 2) / 2 < K) { cout << -1 << endl; return 0; }
	cout << N * (N - 1) / 2 - K << endl;
	for (int i = 2; i <= N; i++)cout << 1 << " " << i << endl;
	for (int i = 2;i<N; i++) {
		for (int j = i + 1; j <= N; j++) {
			if (ans == K)break;
			cout << i << " " << j << endl;
			ans--;
		}
	}
}




Measured memory_bytes: 256
from math import *
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
def is_ok(arg):
    tmp=0
    for i in a:
        tmp+=ceil(i/arg)-1
    return tmp<=k


def meguru_bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok
print(meguru_bisect(0, max(a)))

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

#define rep(i,s,n) for (int i = (int)s; i < (int)n; i++)
#define ll long long
#define ld long double
#define pb push_back
#define eb emplace_back
#define All(x) x.begin(), x.end()
#define Range(x, i, j) x.begin() + i, x.begin() + j
#define lbidx(x, y) lower_bound(x.begin(), x.end(), y) - x.begin()
#define ubidx(x, y) upper_bound(x.begin(), x.end(), y) - x.begin()
#define llbidx(x, y, z) lower_bound(x.begin(), x.end(), z) - lower_bound(x.begin(), x.end(), y) // 二要素間の距離
#define deg2rad(deg) ((((double)deg)/((double)360)*2*M_PI))
#define rad2deg(rad) ((((double)rad)/(double)2/M_PI)*(double)360)
#define Find(set, element) set.find(element) != set.end()
#define Decimal(x) printf("%.10f\n", x) // 小数点を10桁まで表示
// debug用
#define PrintVec(x) for (auto elementPrintVec: x) { cout << elementPrintVec << " "; } cout << endl;
#define debug(x) cerr << #x << ": " << (x) << "\n";

typedef pair<int, int> PI;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<int>>> vvvl;
typedef vector<PI> vpi;
typedef vector<vector<PI>> vvpi;
typedef vector<vector<vector<PI>>> vvvpi;
typedef vector<PLL> vpl;
typedef vector<vector<PLL>> vvpl;
typedef vector<vector<vector<PLL>>> vvvpl;

int POWINT(int x, int n) {
  int ret = 1;
  rep(i, 0, n) ret *= x;
  return ret;
};

ll POWLL(ll x, int n) {
  ll ret = 1;
  rep(i, 0, n) ret *= x;
  return ret;
};

template<class T>
inline bool chmax(T &a, T b) {
  if(a < b) {
    a = b;
    return true;
  }
  return false;
};

template<class T>
inline bool chmin(T &a, T b) {
  if(a > b) {
    a = b;
    return true;
  }
  return false;
};

ll dx[9] = {0ll, -1ll, -2ll, 0ll, -1ll, -2ll, 0ll, -1ll, -2ll};
ll dy[9] = {0ll, 0ll, 0ll, -1ll, -1ll, -1ll, -2ll, -2ll, -2ll};

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

  ll h, w;
  cin >> h >> w;
  int n;
  cin >> n;

  vl X(n), Y(n);
  rep(i, 0, n) {
    cin >> Y[i] >> X[i];
  }

  set<PLL> black;
  rep(i, 0, n) {
    black.insert(make_pair(Y[i], X[i]));
  }

  vl ans(10, 0ll);
  set<PLL> s;
  rep(i, 0, n) {
    ll xi = X[i];
    ll yi = Y[i];
    rep(j, 0, 9) {
      ll ox = xi + dx[j];
      ll oy = yi + dy[j];
      if (1ll <= ox && ox <= w-2ll && 1ll <= oy && oy <= h-2ll) {
        s.insert(make_pair(oy, ox));
      }
    }
  }

  for (PLL pl: s) {
    ll y = pl.first;
    ll x = pl.second;
    int tmp = 0;
    for (ll i = 0ll; i < 9ll; i++) {
      ll r = i / 3ll;
      ll c = i % 3ll;
      if (Find(black, make_pair(y+r, x+c))) tmp++;
    }
    ans[tmp]++;
  };

  ans[0] = (h-2ll) * (w-2ll);
  rep(i, 1, 10) {
    ans[0] -= ans[i];
  }

  rep(i, 0, 10) {
    cout << ans[i] << endl;
  }

  return 0;
};


Measured memory_bytes: 64384
n,m,c=map(int,input().split())
b=list(map(int,input().split()))
a=[]
for _ in range(n):
  a.append(list(map(int,input().split())))
ans=0
for i in a:
  if sum([x*y for (x,y) in zip(i,b)])>-c:
    ans+=1
print(ans)

Measured memory_bytes: 3064
//#define _GLIBCXX_DEBUG

#include<bits/stdc++.h>
#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
const int INF= 1e9+5;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll> >vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
const ll MOD=1000000007LL;
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
struct edge{
  ll to,cost;
};
ll color[100010];
vector<vector<ll> >G(100010);
bool dfs(ll v,ll c){
  color[v]=c;
  rep(i,G[v].size()){
    if(color[G[v][i]]==c)return false;
    if(color[G[v][i]]==0&&!dfs(G[v][i],-c))return false;
  }
  return true;
}
    
int main(){
  ll n,m;cin>>n>>m;
  rep(i,m){
    ll a,b;cin>>a>>b;
    a--;b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  rep(i,n){
    if(color[i]==0){
      if(!dfs(i,1)){
        cout<<n*(n-1)/2-m<<endl;
        return 0;
      }
    }
  }
  ll plus=0,minus=0;
  rep(i,n){
    if(color[i]==1)plus++;
    else minus++;
  }
  cout<<plus*minus-m<<endl;
}
  
  
  

Measured memory_bytes: 8192
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define pb push_back
#define ifr(a, value) insert(a.begin(), value)
#define pf push_front
#define eb emplace_back
#define ef emplace_front
#define all(x) (x).begin(),(x).end()
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
#define szz(v) ((int)(v).size())  
#define vi vector<int>
#define vll vector<ll>
#define str string
#define fr(i, j, k) for(i = j; i < k; i++)
#define bk(i, j, k) for(i = j; i >= k; i--)
#define frit(a, it) for(__typeof((a).begin()) it = a.begin(); it != a.end(); ++it)
#define mem(ptr)  memset(ptr, 0, sizeof ptr)        // use fill() for value other than 0 //
#define rtn return 
#define clk fprintf(stderr, "\nTIME = %lf\n", 1.0 * clock()/CLOCKS_PER_SEC)
#define nl "\n"
#define inf 1LL<<61
#define dbg(x) (cerr << #x << ": " << x << "\n")
const long long mod = 1e9+7;

ll gcd(ll a,ll b) { return b==0 ? a : gcd(b, a%b); }   // no need to swap a, b, it auto. happens after first call //
ll expo(ll x, ll y){ ll res = 1; x = x % mod;  while (y > 0) { if (y & 1)res = (res*x) % mod; y = y>>1;x = (x*x) % mod;}return res;}
void matmul(ll a[][2], ll b[][2]) { ll tmp[2][2]; for(int i=0; i<2; i++) { for(int j=0; j<2; j++) { tmp[i][j] = 0; for(int k=0; k<2; k++) tmp[i][j] = (tmp[i][j] + a[i][k]*b[k][j]) % mod; }} for(int i=0; i<2; i++) for(int j=0; j<2; j++) a[i][j] = tmp[i][j]; }
ll fibo(int n)    // returns nth fibonacci number, also S(n) = f(n+2)-1
{ if(n == 0) return 0; else if(n == 1) return 1; ll T[2][2] = { {0, 1} , {1, 1} }; ll res[2][2] = { {1, 0}, {0,1} }; n--; while(n) { if(n & 1) matmul(res, T); n >>= 1; matmul(T, T); } return res[1][1]; }

void NO() {
	puts("-1");
	exit(0);
}

int main()
{
   // ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
	scanf("%d", &n);
	ll answer = 0;
	vector<int> in(n);
	for(int & x : in) scanf("%d", &x);
	if(in[0]) NO();
	for(int i = 1; i < n; ++i) if(in[i] > in[i-1] + 1) NO();
	int mapka[n];
    fill(mapka, mapka+n, 0);
	for(int i = 0; i < n; ++i)
    {
 //       dbg(i); dbg(in[i]); dbg(in[i]-i); 
		mapka[i-in[i]] = in[i];
    }
/*    map <int, int> :: iterator it;
    for(it = mapka.begin(); it != mapka.end(); ++it)
    {
        cout << it->ff << " " << it->ss << nl;
    } */
    
	for(int i=0; i<n; i++) 
    {
//        dbg(p.ff); dbg(p.second);
        answer += mapka[i];
    }
	printf("%lld\n", answer);
    return 0;
}

/* Errichto : Let (x, y) denote using an operation to make the x-th number equal to y, what requires (x-1,y-1).

For every (x,y) in the input we also need (x-1,y-1), (x-2, y-2) and so on. The goal is to count different pairs created this way. Imagine a grid. For every (x,y) mark all cells from (x,y) diagonally to (x-y,0). For every (x-y,0) achieved this way we want to know the size of the diagonal from that place and this is what we need the map for.   
*/ ///////////////

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


typedef long long ll;
    typedef pair <int, int> ii;
typedef pair <int, ii> iii;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;

#define iINF (1<<30)
#define INF (1LL<<59)
#define forn(i) for(int i = 0;i < n; ++i)
#define form(i,n) for(int i = 0 ;i < n; ++i)
#define NIL -1

const ll mod = 998244353;
ll n;
ll m;
ll ans;
string str;

int main(){
    ll h, max_h=0LL;
    cin>>n;
    ans=0LL;
    forn(i){
        cin>>h;
        if(h>=max_h){
            max_h=h;
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>
#include <memory.h>

using namespace std;

typedef long long ll;

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int a[3];
  for(int i=0;i<3;i++) cin >> a[i];
  sort(a, a+3);
  if((a[1] - a[0]) %2 == 0){
    cout << (a[2] - a[1]) + (a[1] - a[0])/2 << endl;
  }else{
    cout << (a[2] - a[1]) + (a[1] - a[0])/2 + 2 << endl;
  }
}

Measured memory_bytes: 256
# -*-coding: utf-8 -*-
N = int(input())
sp = []
for i in range(N):
    s = list(input().split())
    s.append(i+1)
    sp.append(s)

for i in range(N):
    sp[i][1] = int(sp[i][1])

sp.sort(key=lambda x:(x[0], -x[1]))

for i in range(N):
    print(sp[i][2])

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

int main(int argc, char *argv[]) {
  int n;
  std::cin >> n;
  std::vector<int> a(n);
  long sum = 0;
  for (int i = 0; i < n; ++i) {
    std::cin >> a.at(i);
    sum += a.at(i);
  }

  if (n == 2) {
    std::cout << std::abs(a.at(0) - a.at(1)) << std::endl;
    return 0;
  }

  long half = 0;
  long ans = 0;
  for (int i = 0; i < n; ++i) {
    if (sum <= half * 2) {
      ans = half * 2 - sum;
      if (0 < i) {
        ans = std::min(ans, sum - (half - a.at(i - 1)) * 2);
      }
      break;
    }
    half += a.at(i);
  }

  std::cout << ans << std::endl;
}


Measured memory_bytes: 1024
<?php
/**
 * ABC126
 * A - Changing a Character
 */

// $s = trim(fgets(STDIN));
// fscanf(STDIN, "%d %d", $a, $b);
// $n = array_map('intval', explode(' ', trim(fgets(STDIN))));

fscanf(STDIN, "%d %d", $n, $k);
$s = trim(fgets(STDIN));

$s[$k - 1] = strtolower($s[$k - 1]);

echo $s, PHP_EOL;


Measured memory_bytes: 4728
#include <stdio.h>

int main(){
	double a,b,c,d,e,f, x,y,dd;
	while(scanf("%lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&e,&f)>0){
		dd = (a*e-b*d);
		x=(c*e-b*f)/dd;
		y=(a*f-c*d)/dd;
		if(x==0)x=0;
		printf("%.3f %.3f\n",x,y);
	}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <algorithm>

int main () {
    int totalLinear;

    std::cin >> totalLinear;

    int length[totalLinear];

    for (int i=0; i<totalLinear; i++) {
        std::cin >> length[i];
    }

    std::sort(length, length+totalLinear);
    int maxLength = length[totalLinear-1];

    int sumLength = 0;
    for (int i=0; i<totalLinear-1; i++) {
        sumLength += length[i];
    }

    if(maxLength < sumLength) {
        std::cout << "Yes" << std::endl;
    } else {
        std::cout << "No" << std::endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int a,b;
    string t,u,c;
    cin>>t>>c;
    cin>>a>>b;
    cin>>u;
    if(u==t)cout<<--a<<" "<<b;
    else if (u==c)cout<<a<<" "<<--b;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
int main() {
  ll X;
  cin >> X;
  ll sum = 100;
  rep(i, 1000000000){
    if(sum >= X){
      cout << i << endl;
      return 0;
    }else{
      sum += sum / 100;
    }
 }
}

Measured memory_bytes: 3608
/* Simplicity and Goodness */

#include <bits/stdc++.h>
using namespace std;
#define scn(n) scanf("%d", &n)
#define lscn(n) scanf("%lld", &n)
#define pri(n) printf("%d ", (int)(n))
#define prin(n) printf("%d\n", (int)(n))
#define lpri(n) printf("%lld ", n)
#define lprin(n) printf("%lld\n", n)
#define deb(x) cout << #x << " = " << x << ' ';
#define rep(i, a, b) for(int i=(int)(a); i<(int)(b); i++)
#define tc int tt; scn(tt); while(tt --)
#define pb push_back
#define mp make_pair
#define F first
#define S second
using ll = long long;
const int inf = INT_MAX;
const int ninf = INT_MIN;
const int mod = 998244353;
const int N = 2e5+2;


int main()
{
    int h1, m1, h2, m2, k;
    cin >> h1 >> m1 >> h2 >> m2 >> k;

    int total = (h2 * 60 + m2) - (h1 * 60 + m1) - k;
    prin(total);
    return 0;
}

Measured memory_bytes: 3660
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort()

a = []
a.append(A[0])
c = []
c.append(1)
for i in range(N-1):
    if A[i] == A[i+1]:
        c[-1] += 1
    else:
        a.append(A[i+1])
        c.append(1)

ans = 0
if len(a) <= K:
    ans = 0
else:
    c.sort()
    for i in range(len(a)-K):
        ans += c[i]

print(ans)


Measured memory_bytes: 32336
n = int(input())-1
s = n//26
t = n%26
a = [chr(i) for i in range(97,97+26)]
if s == 0:
    ans = a[t]
elif s < 27:
    ans = a[s-1]+a[t]
else:
    s2 = (s-1)//26
    t2 = s%26
    if s2 < 27:
        ans = a[s2-1] + a[t2-1] + a[t]
    else:
        s3 = (s2-1)//26
        t3 = s2%26
        if s3 < 27:
            ans = a[s3-1] + a[t3-1] + a[t2-1] +a[t]
        else:
            s4 = (s3-1)//26
            t4 = s3%26
            if s4 < 27:
                ans = a[s4-1] + a[t4-1] + a[t3-1] +a[t2-1] +a[t] 
            else:
                s5 = (s4-1)//26
                t5 = s4%26
                if s5 < 27:
                    ans = a[s5-1] + a[t5-1] + a[t4-1] + a[t3-1] +a[t2-1] +a[t] 
                else:
                    s6 = (s5-1)//26
                    t6 = s5%26
                    if s6 < 27:
                        ans = a[s6-1] + a[t6-1]+ a[t5-1] + a[t4-1] + a[t3-1] +a[t2-1] +a[t]
                    else:
                        s7 = (s6-1)//26
                        t7 = s6%26
                        if s7 < 27:
                            ans = a[s7-1] + a[t7-1]+ a[t6-1]+ a[t5-1] + a[t4-1] + a[t3-1] +a[t2-1] +a[t]
                        else:
                            s8 = (s7-1)//26
                            t8 = s7%26
                            if s8 < 27:
                                ans = a[s8-1] + a[t8-1]+ a[t7-1]+ a[t6-1]+ a[t5-1] + a[t4-1] + a[t3-1] +a[t2-1] +a[t]
                            else:
                                s9 = (s8-1)//26
                                t9 = s8%26
                                if s9 < 27:
                                    ans = a[s9-1] + a[t9-1]+ a[t8-1]+ a[t7-1]+ a[t6-1]+ a[t5-1] + a[t4-1] + a[t3-1] +a[t2-1] +a[t]
                                else:
                                    s10 = (s9-1)//26
                                    t10 = s9%26
                                    if s10 < 27:
                                        ans = a[s10-1] + a[t10-1] + a[t9-1]+ a[t8-1]+ a[t7-1]+ a[t6-1]+ a[t5-1] + a[t4-1] + a[t3-1] +a[t2-1] +a[t] 
               
print(ans)

Measured memory_bytes: 9312
#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

int x;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> x;
    cout << 360 / __gcd(x, 360) << endl;
}


Measured memory_bytes: 3636
import sys
input = sys.stdin.readline

class segtree:
    x_unit=0 # 単位元
    x_func=max  # 関数
    def __init__(self,n):
        self.n=n
        self.x=[self.x_unit]*(2*n)
    def build(self, seq):
        for i,j in enumerate(seq, self.n):  # n番目からseqをx配列に移していく
            self.x[i] = j
        for i in range(self.n-1, 0, -1):
            self.x[i] = self.x_func(self.x[i*2], self.x[i*2+1])
    def update(self,i,j): # 1点更新
        i += self.n
        self.x[i]=j
        while i>1:
            i//=2 # 更新後、木の上へと登っていくついでに更新
            self.x[i]=self.x_func(self.x[i*2], self.x[i*2+1])
    def fold(self,l,r): # 区間[l, r)の最小値などを取得 
        l+=self.n
        r+=self.n
        val_l=self.x_unit
        val_r=self.x_unit
        while l<r:
            if l & 1: # lが奇数
                val_l=self.x_func(val_l,self.x[l])
                l+=1 # 偶数に調節
            if r & 1: # rが奇数
                r-=1 # 開区間なので1個前は偶数番目の要素
                val_r=self.x_func(val_r,self.x[r])
            l //= 2
            r //= 2
        return self.x_func(val_l,val_r)
    def find_j(self, l, v):
        r=self.n
        if self.fold(l, r)<v:
            return r
        else:
            while r-l>1:
                l1=l
                r1=l+(r-l)//2
                l2=l+(r-l)//2
                r2=r
                if self.fold(l1, r1)>=v:
                    l=l1
                    r=r1
                else:
                    l=l2
                    r=r2
            return l

n,q=map(int,input().split()) 
seg=segtree(n)
*a,=map(int,input().split())
seg.build(a)
for i in range(q):
    t,x,y=map(int,input().split()) 
    if t==1:
        x-=1
        seg.update(x, y)
    elif t==2:
        print(seg.fold(x-1,y))
    else:
        print(seg.find_j(x-1, y)+1)



Measured memory_bytes: 106004
import std.stdio,std.math,std.string,std.conv,std.typecons,std.format;
import std.algorithm,std.range,std.array;

T[] readarr(T=long)(){return readln.chomp.split.to!(T[]);}
void scan(T...)(ref T args){auto input=readln.chomp.split;foreach(i,t;T)args[i]=input[i].to!t;}

//END OF TEMPLATE

void main(){
    ulong m,n;
    ulong[] a;
    scan(n,m);
    a=readarr!ulong;
    auto sum=a.csum;
    (a.filter!(x=>x.to!real>=sum.to!real/(4*m).to!real).array.length>=m?"Yes":"No").writeln;
}

auto csum(ulong[] a){ 
    ulong tmp;
    foreach(t;a)tmp+=t;
    return tmp;
}

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

int main()
{
  int n;
  cin>>n ;
  int p[n] ;
  for(int i=0;i<n;i++) cin>>p[i] ;
  
  int count=0 ;
  for(int i=1;i<=n-2;i++) if((p[i+1]>p[i]&&p[i-1]<p[i])||(p[i]>p[i+1]&&p[i-1]>p[i])) count++ ;
  
  cout<<count<<endl ;
  return 0 ;
}

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

L=[]

for i in range(N):
    S=list(map(int,input().split()))
    del S[0]
    L.append(S)
#print(L)

P=[i for i in range(m+1)]
size=[1 for i in range(m+1)]

def find(x):
    if P[x]==x:
        return x
    else:
        return find(P[x])
        
def union(y,z):
    Y=find(y)
    Z=find(z)
    if size[Y]>=size[Z]:
        size[Y]+=size[Z]
        P[Z]=P[Y]
    else:
        size[Z]+=size[Y]
        P[Y]=P[Z]
        
for i in range(len(L)):
    if len(L[i])>=2:
        for j in range(1,len(L[i])):
            if find(L[i][j-1])==find(L[i][j]):
                pass
            else:
                union(L[i][j-1],L[i][j])
#print(P)
F=[0 for i in range(m+1)]
for i in range(len(L)):
    for j in range(len(L[i])):
        F[L[i][j]]=1
#print(F)

cnt=0
for i in range(len(F)):
    if F[i]==1 and P[i]==i:
        cnt+=1
if cnt==1:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 29904
x=int(input())
li=[]
for b in range(1,40):
    for p in range(2,11):
        li+=[b**p]
li=sorted(li)
ans=0
f=0
for i in range(len(li)):
    if li[i]>x and f==0:
        ans=li[i-1]
        f=1
print(ans)
        
        
  
      

Measured memory_bytes: 3060
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        int N = scn.nextInt();
        ArrayList<Integer> D = new ArrayList<>();
        for(int i = 0;i<N;i++){
            D.add(scn.nextInt());
        }
        int health =0;
        int total = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i+1 ; j < N ; j++) {
                health = D.get(i) * D.get(j);
                total = total + health;
            }
        }
        System.out.println(total);
    }
}

Measured memory_bytes: 23636
#include <iostream>
#include <string>
#include <locale>

using namespace std;

int main(void){
	string str; getline(cin, str);

	for(int i = 0; i < str.length(); i ++){
		locale loc;
		cout << toupper(str[i], loc);
	}
	cout << endl;

	return 0;
}

Measured memory_bytes: 1172
#include<iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int main() {

	int N, A[100],minj;
	int count = 0;

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

	for (int i = 0; i < N-1 ; i++) {
		minj = i;
		for (int j = i; j < N; j++) {
			if (A[j] < A[minj])
				minj = j;
		}
			swap(A[i], A[minj]);
			if (i != minj) count++;
	}

	for (int i = 0; i < N; i++) {
		if (i != 0) cout << " ";
		cout << A[i];
	}
	putchar('\n');

	cout << count << endl;

	return 0;

}

Measured memory_bytes: 1164
#include <bits/stdc++.h>
#include <numeric>
typedef long long ll;
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;

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

    int N, A, B; cin >> N >> A >> B;
    string S; cin >> S;

    int passedAll = 0, passedB = 0;

    rep(i, 0, S.size()) {
        if (S[i] == 'a' and passedAll < A+B) { ++passedAll; cout << "Yes\n"; }
        else if (S[i] == 'b' and passedAll < A+B and passedB < B) { ++passedAll; ++passedB; cout << "Yes\n"; }
        else cout << "No\n";
    }
}

Measured memory_bytes: 848
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int W = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        int dist = 0;
        if(a+W < b){
            dist = b - (a+W);
        } else if(b+W < a){
            dist = a - (b+W);
        } else {
            dist = 0;
        }
        System.out.print(dist);
    }
}

Measured memory_bytes: 22996
#include<stdio.h>

#define INFTY 100000000000

int S[1000000];
int n;
int count=0;

void mergeSort(int,int);
void merge(int,int,int);

int main(){
  int i;

  scanf("%d",&n);

  for(i = 0;i < n;i++){
    scanf("%d",&S[i]);
  }

  mergeSort(0,n);

  for(i = 0;i < n-1;i++){
    printf("%d ",S[i]);
    //  printf("\n%d",i);
  }
  printf("%d\n",S[i]);

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

void mergeSort(int left,int right){
  int mid;

  if(left+1 < right){
    //  printf("ok\n");

    mid = (left+right)/2;
    // printf("1\n");
    mergeSort(left,mid);

    // printf("2\n");

    mergeSort(mid,right);
    merge(left,mid,right);
  }
}

void merge(int left,int mid,int right){

  int i, j, k;
  int n1,n2;
  int L[250001];
  int R[250001];

  n1 = mid - left;
  n2 = right - mid;

  for(i = 0;i <= n1-1;i++){
    // printf("%d\n",S[left + i]);
    L[i] = S[left + i];
  }
  for(i = 0;i <= n2-1;i++){
    R[i] = S[mid + i];
  }
  L[n1] = INFTY;
  R[n2] = INFTY;

  i = 0; 
  j = 0;

  for(k = left;k <= right-1;k++){
    count++;
    if(L[i] <= R[j]){
      // printf("ok\n");
     	S[k] = L[i]; 
	i = i + 1;
      }
    else{
      S[k] = R[j];
      j =j + 1;
    }
  }
}

Measured memory_bytes: 4504
H, W = map(int, input().split())
field = list(list(input()) for _ in range(H))

dp = list(list(float('INF') for _ in range(W)) for _ in range(H))
dp[0][0] = 1 if field[0][0] == '#' else 0

for x in range(W):
    for y in range(H):
        if y < H - 1:
            dp[y + 1][x] = min(dp[y + 1][x],
                               dp[y][x] + 1 if field[y + 1][x] == '#' and field[y][x] == '.' else dp[y][x])
        if x < W - 1:
            dp[y][x + 1] = min(dp[y][x + 1],
                               dp[y][x] + 1 if field[y][x + 1] == '#' and field[y][x] == '.' else dp[y][x])

print(dp[H - 1][W - 1])

Measured memory_bytes: 3444
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    int a, b, c, d;

    public static void main(String args[]) {
        new Main().run();
    }

    void run() {
        FastReader sc = new FastReader();
        a = sc.nextInt();
        b = sc.nextInt();
        c = sc.nextInt();
        d = sc.nextInt();
        solve();
    }

    void solve() {
        int left = a + b;
        int right = c + d;
        if (left > right) {
            System.out.println("Left");
        } else if (left < right) {
            System.out.println("Right");
        } else {
            System.out.println("Balanced");
        }
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

        long nextLong()
        {
            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
}


Measured memory_bytes: 21204
<?php
fscanf(STDIN, "%s %s", $a, $b);
$s = floor($a / 100);
$t = floor($b / 100);
$p = $s * 100 + $a[1] * 10 + $a[0];
$q = $t * 100 + $b[1] * 10 + $b[0];
if ($a > $p) $s++;
if ($b < $q) $t--;
echo $t - $s + 1;

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

int main()
{
    string s;
    cin >> s;
    string ans;
    int len = s.size();
    for (int i=0; i<len; i++)
    {
        if (s[i] == '0') ans += '0';
        else if (s[i] == '1') ans += '1';
        else {
            if (ans.size() != 0) ans.pop_back();
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
main = do
    [k,n] <- map read.words <$> getLine :: IO [Int]
    vs <- map read.words <$> getLine :: IO [Int]
    putStrLn.show $ answer k n vs

answer k n vs = k - maxDistance where
    maxDistance = foldl max (head vs+k-last vs).map (uncurry (flip (-))) $ zip vs (tail vs)


Measured memory_bytes: 106876
#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>;

struct UnionFind
{
    vector<int> par;
    UnionFind(int n) : par(n, -1){ }
    int root(int x){
        if(par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    bool issame(int x, int y){
        return root(x) == root(y);
    }
    bool merge(int x, int y){
        x = root(x); y = root(y);
        if(x == y) return false;
        if(par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    int size(int x){
        return -par[root(x)];
    }
};

int main() {
    int N, M; cin >> N >> M;
    int p[N];
    rep(i, N) { cin >> p[i]; p[i]--; }
    UnionFind uf(N);
    rep(i, M){
        int x, y; cin >> x >> y;
        x--; y--;
        uf.merge(x, y);
    }

    int ans = 0;
    rep(i, N) {
        if(uf.issame(i, p[i])) ans++;
    }
    cout << ans << endl;
    return 0;
}

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

namespace Atcoder
{
    class Program
    {
        private static string Read() { return Console.ReadLine(); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }

        private static void print(object obj) { Console.WriteLine(obj); }

        static void Main(string[] args)
        {
            var a = ReadInts();
            var b = a.ToList();
            b.Sort();
            int c = 0;
            c += b[1] - b[0];
            c += b[2] - b[1];
            print(c);
        }
    }
}

Measured memory_bytes: 13268
using System;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ').Select(y => int.Parse(y));
            var x = input.First();
            var a = input.Skip(1).First();

            if (x < a)
            {
                Console.WriteLine("0");
                return;
            }
            Console.WriteLine("10");
        }
    }
}


Measured memory_bytes: 11348
#include "bits/stdc++.h"
#define REP(i, n) for(int i = 0; i < int(n); i++)
#define FOR(i,n,m) for(int i = int(n); i < int(m); i++)
using namespace std;
typedef long long ll;

// スライド最小値 O(N)
// return[i] = min( v[i,i+k) )
template< typename T >
vector< T > slide_min(const vector< T > &v, int k)
{
    deque< int > deq;
    vector< T > ret;
    for (int i = 0; i < v.size(); i++) {
        while (!deq.empty() && v[deq.back()] >= v[i]) {
            deq.pop_back();
        }
        deq.push_back(i);
        if (i - k + 1 >= 0) {
            ret.emplace_back(v[deq.front()]);
            if (deq.front() == i - k + 1) deq.pop_front();
        }
    }
    return ret;
}

int main() {
    const ll LLINF = 1e18;
    int n, x; cin >> n >> x;
    vector<int> v(n << 1);
    REP(i, n) {
        cin >> v[n - 1 - i];
        v[n - 1 - i + n] = v[n - 1 - i];
    }
    ll ans = 1e18;
    FOR(k,1,n+1) {
        auto sm = slide_min(v, k);
        ll sum = 0;
        REP(i, n) sum += sm[i];
        ans = min(ans, sum + (ll)x * (k-1));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cstdio>

#include<vector>
#include<queue>
#include<set>
#include<map>
#include<string>

#include<algorithm>
#include<cmath>

using namespace std;
typedef long long ll;
template <class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return 1;} return 0;}
template <class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return 1;} return 0;}
const int INF = 1e9;

int N,M;
int D = 1e9 + 7;

int main() {
    cin >> N >> M;
    
    vector<int> dp(N+1);
    for (int i = 0; i < M; i++) {
        int a; cin >> a;
        dp[a] = -1;
    }
    
    dp[0] = 1;
    for (int i = 0; i < N; i++) {
        if (dp[i+1] != -1) {
            if (dp[i] != -1) {
                dp[i+1] = (dp[i+1] + dp[i]) % D;
            }
            if (i-1 >= 0 && dp[i-1] != -1) {
                dp[i+1] = (dp[i+1] + dp[i-1]) % D;
            }
        }
    }
    cout << dp[N] << endl;

}


Measured memory_bytes: 640
#include "bits/stdc++.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<int,int> pii;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define INTINF INT_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
template<class T> inline bool chmax(T &a, T b){if(a < b){a = b;return true;}return false;}
template<class T> inline bool chmin(T &a, T b){if(a > b){a = b;return true;}return false;}
/*----------------------------------------------------------------*/
// int MOD = 998244353;
int MOD = 1000000007;

/*----------------------------------------------------------------*/
signed main(){
	int x;
	cin >> x;
	int ans = x/500*1000;
	x %= 500;
	ans += x/5*5;
	cout << ans << endl;

	

	return 0;
}
/*----------------------------------------------------------------*/

// g++ -std=c++14 code1.cpp
// sudo pip3 install --upgrade online-judge-tools
// rm -r -f test;oj dl https://code-festival-2018-quala.contest.atcoder.jp/tasks/code_festival_2018_quala_c
// rm -r -f test;oj dl https://pakencamp-2019-day3.contest.atcoder.jp/tasks/pakencamp_2019_day3_c
// rm -r -f test;oj dl https://abc160.contest.atcoder.jp/tasks/abc160_a

Measured memory_bytes: 256
N,K = map(int,input().split())
X = list(map(int,input().split()))
min_time = 10**14
for i in range(N-K+1):
    l_edge = X[i]
    r_edge = X[i+K-1]
    route1 = abs(l_edge) + r_edge - l_edge
    route2 = abs(r_edge) + r_edge - l_edge
    time = min(route1,route2)
    if time < min_time:
        min_time = time
print(min_time)

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

#define lli long long int
#define REP(i,n) for(int i=0;i<n;i++)

using namespace std;

lli absL(lli a){
	if(a>=0)return a;
	else return -a;
}

int main(){
	lli n;
	vector<lli> a;
	cin>>n;
	REP(i,n){
		lli tmp;
		cin>>tmp;
		a.push_back(tmp);
	}

	lli now=0;
	lli cost=0;
		
	REP(i,n){
		cost += absL(a.at(i)-now);
		now = a.at(i);
	}
	cost+=absL(a.at(n-1));

	REP(i,n){
		lli x,y,z;
		if(i==0){
			x=0;
			y=a.at(0);
			z=a.at(1);
		}
		else if(i==n-1){
			x=a.at(n-2);
			y=a.at(n-1);
			z=0;
		}
		else{
			x=a.at(i-1);
			y=a.at(i);
			z=a.at(i+1);
		}
		lli xy = absL(x-y);
		lli yz = absL(z-y);
		lli xz = absL(x-z);
		cout<<cost - ((xy+yz)-xz)<<endl;
	}

	return 0;

}

Measured memory_bytes: 2164
#include <bits/stdc++.h>
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define IMAX 0x3f3f3f3f
#define LLMAX 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
typedef double db;
inline int read() {
  int x = 0, f = 1;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x * f;
}

ll a,b,n;

signed main() {
  a = read(), b = read(), n = read();
  printf("%lld\n", a * std::min((b - 1), n) / b);
  return 0;
}


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

for a in range(200):
    for b in range(-200, 1):
        if a**5-b**5==X:
            print(str(a) + " " + str(b))
            exit()

a = 0
b = 0

while True:
    cand = a**5-b**5
    if cand == X:
        print(str(a) + " " + str(b))
        exit()
    elif cand < X:
        a += 1
    else:
        b += 1

Measured memory_bytes: 64104