akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<cstring>
#include<math.h>
#include<bitset>
#include<queue>
#include<set>
#include<iomanip>
#include<math.h>
#include<assert.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1LL << 60;
constexpr int INF = 1000000007;
const double INFD = 1e100;
const int mod = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

int main(){
  int N;
  cin >> N;
  string S,T;
  cin >> S >> T;
  string ans="";
  for(int i=0; i<N; i++){
    ans += S[i];
    ans += T[i];
  }
  cout << ans << endl;
  return 0;
}


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

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

int main(){
    int n;
    cin >> n;
    vector<int> vec(n);
    int len=0;
    rep(i,n) {
        cin >> vec[i];
    }

    rep(i,n){
        if(vec[i] == len+1){
            len++;
        }
    }
    if(len == 0)
        cout << -1 << endl;
    else 
        cout << n-len << endl;

    return 0;
}



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

using namespace std;

int main() {
	string s,a;

	cin >> s;

	for (int i = 0; i < s.size(); i++) {
		if (i % 2 == 0) {
			a = a + s[i];
		}
	}
	cout << a << endl;

	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <utility>
using namespace std;
using ll = long long;

int main(){
  int n, k; cin >> n >> k;
  
  cout << (n % k? 1: 0) << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {

    long long X, K, D;
    cin >> X >> K >> D;
    long long count = 0, result;

    if(X < 0){ // Xを正にする
        X *= -1;
    }
    count = X / D; // 0直前まで割った回数

    if(count > K){
        result = X - (D * K);
    }else{

        count = K - count;

        if(count % 2 == 0){
            result = X % D;
        }else{
            result = ((X % D) - D) * (-1);
        }
    }
    
    cout << result << endl;

}

Measured memory_bytes: 3616
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;


int main()
{
int N,M,a;
int x[5],ans=0,k;
for(int i=0;i<5;i++){
  cin>>x[i];
}
cin>>k;
if(x[4]-x[0]>k){
  cout<<":("<<endl;
}else{
  cout<<"Yay!"<<endl;
}


return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i<(int)(n); ++i)
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using Graph = vector<vector<int>>;  // int <=> ll
using P = pair<int, int>;  // int <=> ll
const int INFTY = 1e9+7;

int main() {
  int H, W, D; cin >> H >> W >> D;
  vector<P> place(H*W);
  rep(i,H) {
    rep(j,W) {
      int a; cin >> a; --a;
      place[a] = P(i,j);
    }
  }

  vi power(H*W);
  rep(i,H*W) {
    if (i<D) {
      power[i] = 0;
      continue;
    }
    int x, y, nx, ny;
    tie(x,y) = place[i-D];
    tie(nx,ny) = place[i];
    power[i] += power[i-D] + abs(nx-x) + abs(ny-y);
  }
  
  int Q; cin >> Q;
  rep(i,Q) {
    int L, R; cin >> L >> R; --L; --R;
    cout << power[R] - power[L] << endl;
  }
  return 0;
}


Measured memory_bytes: 2176
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
typedef long long ll;
int N;
ll a[100000],X;
int main(){
	cin>>N>>X;
	rep(i,N) cin>>a[i];
	ll ans=0;
	rep(i,N-1){
		if(a[i]+a[i+1]<=X) continue;
		if(a[i]>X){
			ans+=a[i+1]+a[i]-X;
			a[i+1]=0;
		}else{
			ll dis=a[i+1]+a[i]-X;
			ans+=dis;
			a[i+1]-=dis;
		}
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using ll = long long;
using namespace std;
 
int h, w;
int ma[80][80], mb[80][80], ch[80][80];
bool ans[80][80][16000];
 
int main(){
    cin >> h >> w;
    rep(i,h) rep(j,w) cin >> ma[i][j];
    rep(i,h) rep(j,w) cin >> mb[i][j];
    rep(i,h) rep(j,w) ch[i][j] = abs(ma[i][j]-mb[i][j]);
 
    ans[0][0][ch[0][0]] = true;
 
    rep(i,h) rep(j,w) rep(k,16000){
        if(ans[i][j][k]){
            if(i+1 < h){
                ans[i+1][j][k+ch[i+1][j]] = true;
                ans[i+1][j][abs(k-ch[i+1][j])] = true;
            }
            if(j+1 < w){
                ans[i][j+1][k+ch[i][j+1]] = true;
                ans[i][j+1][abs(k-ch[i][j+1])] = true;
            }
        }
    }
    rep(k,640000) if(ans[h-1][w-1][k]){
      cout << k << endl;
      return 0;
    }
}

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

int main() {
  int A , B , C , D;
  cin >> A >> B >> C >> D;
  
  if ( A + B > C + D ) {
    cout << "Left" << endl;
  }
  else if ( A + B < C + D ) {
    cout << "Right" << endl;
  }
  else {
    cout << "Balanced" << endl;
  }
}




Measured memory_bytes: 256
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int n = N%10;
		if(n == 3) {
			System.out.println("bon");
	
		}else if(n==0 || n == 1 || n==6 || n == 8){
			System.out.println("pon");
		}else {
			System.out.println("hon");
		}

	}
}



Measured memory_bytes: 35756
#include<stdio.h>
#include<stdlib.h>
#define ll long long
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}

ll a[100010];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		int t;
		scanf("%d",&t);
		a[t]=-1;
	}
	a[0]=1e9;
	for(int i=1;i<=n;i++){
		if(a[i]==-1)a[i]=0;
		else a[i]=a[i-1]+1;
	}
	sortdown(a+1,n);
	
	int q;
	scanf("%d",&q);
	while(q--){
		int t;
		scanf("%d",&t);
		t++;
		printf("%d\n",a[t]>=1e9?-1:a[t]+1);
	}
}


Measured memory_bytes: 3012
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
const Int MOD = 1000000007;
const Int MAX = 200000;
array<Int, MAX> fac, finv, inv;
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    COMinit();
    int N; cin >> N;
    vector<Int> X(N); for (auto &x : X) cin >> x;
    vector<Int> A(N + 1);
    for (int i = 1; i <= N; i++) {
        A[i] = (A[i - 1] + inv[i]) % MOD;
    }
    Int ans = 0;
    for (int i = 0; i < N - 1; i++) {
        ans = (ans + (X[i + 1] - X[i]) * A[i + 1]) % MOD;
    }
    cout << ans * fac[N - 1] % MOD << endl;
    return 0;
}

Measured memory_bytes: 6528
#[allow(unused_imports)]
use std::cmp;
use std::io::Write;

// Input macro from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
  (source = $s:expr, $($r:tt)*) => {
    let mut iter = $s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
  ($($r:tt)*) => {
    let 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:tt ]) => {{
    let len = read_value!($iter, usize);
    (0..len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
  }};

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

fn main() {
  let out = std::io::stdout();
  let mut out = std::io::BufWriter::new(out.lock());
  macro_rules! puts {
    ($($format:tt)*) => (write!(out,$($format)*).unwrap());
  }
  input! {
    x: usize,
    y: usize,
    a: usize,
    b: usize,
    c: usize,
    p: [i64; a],
    q: [i64; b],
    r: [i64; c],
  }
  let mut p = p;
  p.sort();
  let mut q = q;
  q.sort();
  let mut i = a - x;
  let mut j = b - y;
  use std::collections::BinaryHeap;
  let mut h: BinaryHeap<_> = r.into_iter().collect();
  let mut sum_clear = 0;
  while let Some(clear) = h.pop() {
    if i == a && j == b {
      break;
    }
    if j == b || p[i] < q[j] {
      if clear > p[i] {
        i += 1;
        sum_clear += clear;
      } else {
        break;
      }
    } else {
      if clear > q[j] {
        j += 1;
        sum_clear += clear;
      } else {
        break;
      }
    }
  }
  let mut sum = 0;
  for ii in i .. a {
    sum += p[ii];
  }
  for jj in j .. b {
    sum += q[jj];
  }

  puts!("{}\n", sum + sum_clear);
}


Measured memory_bytes: 12408
#include <cstdio>
#include <cstring>
#include <algorithm>
int test;
int c[11][4][5];
int res=20;

void push(int v){
	int vv=0;
	/*
	for(int i=0;i<5;i++){
		for(int j=0;j<4;j++){
			printf("%d%c",c[v][j][i],j==3?'\n':' ');
		}
	}
	printf("\n");
	*/
	for(int i=0;i<20;i++){
		if(c[v][i%4][i/4]!=0){
			c[v][vv%4][vv/4]=c[v][i%4][i/4];
			if(vv!=i){
				c[v][i%4][i/4]=0;
			}
			vv++;
		}
	}
	/*
	for(int i=0;i<5;i++){
		for(int j=0;j<4;j++){
			printf("%d%c",c[v][j][i],j==3?'\n':' ');
		}
	}
	*/
}

void dfs(int t){
	res=std::min(res,20-t*2);
	if(res==0)return;
	for(int i=0;i<5;i++){
		for(int j=0;j<4;j++){
			if(c[t][j][i]==0)continue;
			for(int k=-1;k<=1;k++){
				for(int l=-1;l<=1;l++){
					if(k==0 && l==0)continue;
					int py=i+k,px=j+l;
					if(px>=0 && px<4 && py>=0 && py<5){
						if(c[t][j][i]==c[t][px][py]){
							memset(c[t+1],0,sizeof(c[t+1]));
							for(int m=0;m<5;m++){
								for(int n=0;n<4;n++){
									if((j==n && i==m) || (px==n && py==m))continue;
									c[t+1][n][m]=c[t][n][m];
								}
							}
							push(t+1);
							dfs(t+1);
							//printf("%d %d\n",j+i*4,px+py*4);
						}
					}
				}
			}
		}
	}
}

int main(void){
	scanf("%d",&test);
	for(int ddd=0;ddd<test;ddd++){
		for(int i=0;i<5;i++){
			for(int j=0;j<4;j++){
				scanf("%d",&c[0][j][i]);
			}
		}
		res=20;
		dfs(0);
		printf("%d\n",res);
	}
	return 0;
}

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

typedef long long ll;
typedef unsigned long long int ull;
#define endl "\n"
#define pb push_back
#define sq(a) (a)*(a)
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugv(v) cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;
#define MOD 1000000007
#define PI 3.141592653589793238
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);

ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

ll exp(ll x,ll n,ll mod)
{
    ll result=1;
    while(n)
    {
        if(n & 1)
            result=(result * x)%mod;
        x=(x*x)%mod;
        n=n>>1;
    }
    return result;
}

const ll M=1e9+7;
const ll N=1e6+1;
vector<ll> fact(3e6);
vector<ll> invfact(3e6);

void factset(ll n)
{
	fact[0]=1LL;
	invfact[0]=1LL;

	for(ll i=1;i<=n;i++)
	{
		fact[i]=((fact[i-1])%M*(i%M))%M;

		invfact[i]=((invfact[i-1]%M)*(exp(i,M-2,M)%M))%M;
	}

}

int32_t main()
{
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    IOS

    ll k;
    cin>>k;
    string s;
    cin>>s;
    ll n=s.length();
    factset(n+k);

   ll ans=0,x=1;
   for(int i=0;i<=k;i++)
   {
   		ans=(ans+(((fact[n+k]*invfact[n+k-i])%M*invfact[i])%M*x)%M)%M;
   		x=(x*25)%M;
   }

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

Measured memory_bytes: 51144
#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define RREP(i,a,b) for(int i=(a);i>=(b);i--)
typedef long long ll; typedef long double ld;
using namespace std;
const int INF=1e9, MOD=1e9+7, around[]={0,1,1,-1,-1,0,-1,1,0,0};
const ld PI=abs(acos(-1));
int a,b,c;

int main(){
	cin >> a >> b >> c;
	
	cout << (a<=c and c<=b?"Yes":"No") << endl;
	return 0;
}
 


Measured memory_bytes: 256
#include <cstdio>
#define CITY_MAX_CNT 64

int main() {
    int N = 0, M = 0;
    scanf("%d %d", &N, &M);
    int adjList[CITY_MAX_CNT] = {0};

    for (int i = 0; i < M; i++) {
        int a = 0, b = 0;
        scanf("%d %d", &a, &b);
        adjList[a]++;
        adjList[b]++;
    }

    for (int i = 1; i <= N; i++) {
        printf("%d\n", adjList[i]);
    }
    return 0;
}


Measured memory_bytes: 128
#include<iostream>
using namespace std;
int main() {
	int n, m;
	cin >> n >> m;
	int k[101][101];
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			cin >> k[i][j];
		}
	}
	for (int i = 0; i < n; i++){
		int sum = 0;
		for (int j = 0; j < m; j++){
			sum += k[i][j];
		}
		k[i][m] = sum;
	}
	for (int i = 0; i < m; i++) {
		int sum = 0;
		for (int j = 0; j < n; j++) {
			sum += k[j][i];
		}
		k[n][i] = sum;
	}
	int sum = 0;
	for (int i = 0; i < n; i++){
		sum += k[i][m];
	}
	k[n][m] = sum;
	for (int i = 0; i < n + 1; i++){
		for (int j = 0; j < m + 1; j++){
			cout << k[i][j];
			if (j == m)
				cout << endl;
			else cout << ' ';
		}
	}
	return 0;
}

Measured memory_bytes: 3092
import java.util.*;
//import java.math.BigInteger;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String str = sc.next();
        char[] c = str.toCharArray();
        int K = sc.nextInt();
        //int[] p = new int[N];
        //a[0] = Character.getNumericValue(str.charAt(0));
        //boolean test = false;
        
        for(int i=0; i<N; i++){
            if(c[K-1] != c[i]){
                c[i] = '*';
            }
            //System.out.println(count);
        }
        for(int i=0; i<N; i++){
            System.out.print(c[i]);
        }
        System.out.println("");
    }
}


Measured memory_bytes: 35972
#include <iostream>
#include <algorithm>
using namespace std;
static const int MAX=200000;
int main()
{
    int n,R[MAX];
    cin>>n;
    for (int i = 0; i < n; ++i) {
        cin>>R[i];
    }
    int maxv=R[1]-R[0];
    int minv=R[0];
    for (int i = 1; i < n; ++i) {
        maxv = max(maxv, R[i] - minv);
        minv = min(minv, R[i]);
    }
    cout<<maxv<<endl;

}


Measured memory_bytes: 3872
#include<iostream>
#include<algorithm>
#include<vector>
#include<climits>
#include<array>
using namespace std;

static const int MAX = 100;
static const long long INFTY = (1LL<<32);

int n;
long long d[MAX][MAX];
int e, u, v, c;
int R[100000];

void floyd() {
  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      if (d[i][k] == INFTY) continue;
      for (int j = 0; j < n; j++) {
        if (d[k][j] == INFTY) continue;
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
      }
    }
  }
}

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

  for ( int i = 0; i < n; i++){
    for (int j = 0; j < n; j++) {
      d[i][j] = ( (i == j) ? 0 : INFTY);
    }
  }

  for (int i = 0; i < e; i++) {
    cin >> u >> v >> c;
    d[u][v] = c;
  }

  floyd();

  bool negative = false;
  for ( int i = 0; i < n; i++) {
    if (d[i][i] < 0) {
      negative = true;
    }
  }

  if (negative) {
    cout << "NEGATIVE CYCLE" << endl;
  } else {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (j) cout << " ";
        if (d[i][j] == INFTY) {
          cout << "INF";
        }else{
          cout << d[i][j];
        }
      }
      cout << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 3188
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
 
using namespace std;
 
int main(){
  int N,M; cin>>N>>M;
  vector<pair<unsigned long,int>> v;
  for(int i=0;i<N;i++){
    int a, b; cin>>a>>b;
    v.push_back(make_pair(a,b));
  }
  sort(v.begin(), v.end());
  
  int c=0;
  unsigned long ans=0;
  while(M>0){
    int d = v[c].second;
    ans += min(M,d)*v[c].first;
    M -= min(M,d);
    c++;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 2420
#include <stdio.h>
#include <algorithm>
using namespace std;

int num[200001]; 

bool cmp(int a, int b)
{
	return a>b;
}
int main()
{
	int n, k, a;
	scanf("%d%d", &n, &k);
	int m = 0;
	for(int i=0;i<n;i++)
	{
		scanf("%d", &a);
		num[a]++;
		if(a>m)
			m = a;
	}
	sort(num, num+m+1, cmp);
	int sum = 0;
	for(int i=0;i<k;i++)
	{
		sum += num[i]; 
	}
	printf("%d\n", n-sum);
	return 0;
}

Measured memory_bytes: 896
#include <stdio.h>
#define N 200005
typedef long long ll;
int n,a[N];
int main() {
	int sum=0;ll ans=0;
	scanf("%d",&n);
	for(int i=0;i<n;++i) scanf("%d",a+i);
	for(int i=0,j=0;i<n;++i) {
		while(j<n&&!(a[j]&sum)) sum|=a[j++];
		ans+=j-i;
		sum-=a[i];
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 1024
use std::cmp::{max, min};
use std::collections::{HashMap, HashSet, VecDeque};
use std::io::{stdin, Read};
use std::str::FromStr;

// https://qiita.com/tubo28/items/e6076e9040da57368845
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

#[allow(dead_code)]
fn main() {
    let h = read::<usize>();
    let w = read::<usize>();
    let mut s = (0..h)
        .map(|_| read::<String>().chars().collect::<Vec<_>>())
        .collect::<Vec<_>>();
    let mut q = VecDeque::new();
    q.push_front((0, 0, 0));
    let mut ans = 0;
    while let Some((i, j, c)) = q.pop_front() {
        if s[i][j] == '#' {
            continue;
        }

        if (i, j) == (h - 1, w - 1) {
            ans = c;
            let sharps: usize = s
                .iter()
                .map(|a| a.iter().filter(|&x| *x == '#').count())
                .sum();

            println!("{}", h * w - (ans + 1) - sharps);
            return;
        }

        if s[i][j] == '_' {
            continue;
        }

        s[i][j] = '_';

        if i > 0 {
            q.push_back((i - 1, j, c + 1))
        }
        if j > 0 {
            q.push_back((i, j - 1, c + 1))
        }
        if i < h - 1 {
            q.push_back((i + 1, j, c + 1))
        }
        if j < w - 1 {
            q.push_back((i, j + 1, c + 1))
        }
    }
    println!("-1")
}


Measured memory_bytes: 4352
from scipy.sparse.csgraph import connected_components, bellman_ford, NegativeCycleError
from scipy.sparse import csr_matrix

N, M = map(int, input().split())
frm, to, length = [], [], []
for _ in range(M):
    a, b, c = map(int, input().split())
    frm.append(a - 1)
    to.append(b - 1)
    length.append(-c)

# N-1→0の辺を追加してから卿連結判定⇒ゴールにたどり着けない閉路を除外
connect_check = csr_matrix(([1] * (M + 1), (frm + [N - 1], to + [0])), shape=(N, N))
_, labels = connected_components(connect_check, connection='strong')
label_num = labels[0]
frm_c, to_c, length_c = [], [], []
for i in range(M):
    if labels[frm[i]] == labels[to[i]] == label_num:
        frm_c.append(frm[i])
        to_c.append(to[i])
        length_c.append(length[i])

matr = csr_matrix((length_c, (frm_c, to_c)), shape=(N, N))

try:
    ans = -int(bellman_ford(matr, indices=0)[N - 1])
    print(ans)
except NegativeCycleError:
    print('inf')


Measured memory_bytes: 38340
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,a[200005],total,psum;
ll m(ll x, ll y){
  ll res=0;
  x%=1000000007;
  while(y){
    if(y%2) res=(res+x)%1000000007;
    x=(x*2)%1000000007;
    y/=2;
  }
  return res;
}
int main(){
  cin>>n;
  for(ll i=1;i<=n;i++){
    cin>>a[i];
    total+=m(psum,a[i]);
    total%=1000000007;
    psum+=a[i];
    psum%=1000000007;
  }
  cout<<total;
  return 0;
}

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

ll mod = 1000000007;


struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};

struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}



int main(){
  int n, m; cin >> n >> m;
  mint ans, ps = m - n + 1, p;
  if(n % 2 == 0){
    ans = 1;
    p = -ps;
  }
  else{
    ans = -1;
    p = ps;
  }
  combination c(n+5);

  for(int i = 1; i <= n; i++){

    //cout << "c : " << c(n, i) << ", p : " << p << endl;
    ans += p * c(n, i);
    if(i < n) p *= -(ps + i);
  }
  ans *= p;
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 10932
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val x :: xs = List.fill(sc.nextInt())(sc.nextInt())
  val (_, _, max) = xs.foldLeft((x, 0, 0)) {
    case ((step, count, max), next) if next <= step =>
      (next, count + 1, max.max(count + 1))
    case ((_, _, max), next) =>
      (next, 0, max)
  }
  println(max)
}

Measured memory_bytes: 62740
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
const int M = 1e7;
int si[] = {-1, 0, 1, 0};
int sj[] = {0, -1, 0, 1};

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

  int ans = M;
  for(int a = 1; a < n; a++){
    int b = n-a;
    int k = 0;
    string x = to_string(a);
    rep(i,x.size()) k += (int)x[i] - (int)'0';
    string y = to_string(b);
    rep(i,y.size()) k += (int)y[i] - (int)'0';
    ans = min(k,ans);
  }

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


Measured memory_bytes: 3656
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long int ll;
int main(){
  int n;
  cin >> n;
  ll a[n],ans=0,sum[n+1],cnt=1,k;
  sum[0]=0;
  for(int i=1;i<n+1;i++)  {
    cin >> a[i];
    sum[i]=a[i]+sum[i-1];
  }
  sort(sum,sum+n+1);
  for(int i=0;i<n+1;i++){
    if(cnt==1) k=sum[i];
    if(i!=n){
      if(k==sum[i+1]) cnt++;
      if(k!=sum[i+1]) {
        ans+=((cnt*(cnt-1))/2);
        cnt=1;
      }
    }
    else{
      ans+=((cnt*(cnt-1))/2);
    }
  }
    cout <<ans <<endl;
}


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

X = INT()
ans = X//500*1000
X = X%500
ans += X//5*5

print(ans)


Measured memory_bytes: 5784
#include<bits/stdc++.h>
#define N 10
using namespace std;
int n,m,d[N],ans;
map<char,int> c;
set<char> ish;
bool used[N];
bool q[N];
string s;
int p[N];


void func(int x){
  if(x==m){
    int f=0,sum=0;
    for(int i=0;i<m;i++){
      if(!d[i]&&q[i])f=1;
      sum+=p[i]*d[i];
    }
    if(f)return;
    if(!sum)ans++;
    return;
  }
  for(int i=0;i<10;i++){
    if(used[i])continue;
    d[x]=i;
    used[i]=true;
    func(x+1);
    used[i]=false;
  }
}

int main(){
  while(1){
    cin>>n;
    if(!n)break;
    for(int i=0;i<n;i++){
      cin>>s;
      for(int j=s.size()-1,k=1;j>=0;j--,k*=10){
	if(!j&&s.size()!=1)ish.insert(s[j]);
	if(c.find(s[j])==c.end())
	  if(i!=n-1)c[s[j]]=k;
	  else c[s[j]]=-k;
	else
	  if(i!=n-1)c[s[j]]+=k;
	  else c[s[j]]-=k;
      }
    }
    memset(q,0,sizeof(q));
    map<char,int>::iterator ite;
    int k=0;
    for(ite=c.begin();ite!=c.end();ite++,k++){
      p[k]=(*ite).second;
      if(ish.find((*ite).first)!=ish.end())
	q[k]=true;
    }
    m=c.size();
    ans=0;
    func(0);
    cout<<ans<<endl;
    ish.clear();
    c.clear();
  }
  return 0;
}

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

int main(){

	int N;
	cin >> N;
	int written[200][3];
	int score[200];

	for(int i = 0; i < N; i++){
		cin >> written[i][0] >> written[i][1] >> written[i][2];
		score[i] = 0;
	}
	
	for(int game = 0; game < 3; game++){
		for(int i = 0; i < N; i++){
			bool UNI = true;
			for(int j = 0; j < N; j++){
				if(i == j) continue;
				if(written[i][game] == written[j][game]){
					UNI = false;
				}
			}
			if(UNI)score[i] += written[i][game];
		}
	}

	
	for(int i = 0; i < N; i++){
		cout << score[i] << endl;
	}

	return 0;
}


Measured memory_bytes: 3080
#include<bits/stdc++.h>
using namespace std;
int main() {
	int N, M;
	cin >> N >> M;
	vector<int> vec(N);
	for (int j = 0; j < M; j++){
		int a, b;
		cin >> a >> b;
        vec.at(a-1)++;
		vec.at(b-1)++;
		}
	for (int i = 0; i < N; i++)
		cout << vec.at(i) << endl;
	return 0;
}


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

public class Main {
    public static void main(String[] args) {
        FastScanner scanner = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i <n; i++) {
            arr[i] = scanner.nextInt();
        }
        int prev = arr[0];
        int cur = 0;
        int best = 0;
        for(int i  = 1; i < n; i++) {
            if (arr[i] <= prev) cur++;
            else {
                cur = 0;
            }
            best = Math.max(best, cur);
            prev = arr[i];
        }
        out.println(best);
        out.flush();
    }
    
    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        
        public FastScanner(Reader in) {
            br = new BufferedReader(in);
        }
        
        public FastScanner() {
            this(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 readNextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}


Measured memory_bytes: 38240
#include<bits/stdc++.h>
using namespace std;
 
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return
#define lb(v,n) lower_bound(v.begin(),v.end(),n)
#define ub(v,n) upper_bound(v.begin(),v.end(),n)
#define mae(v) max_element(v.begin(),v.end())
#define mie(v) min_element(v.begin(),v.end())
#define INF 0x7FFFFFFF
#define mod 1000000007
#define fir first
#define sec second
typedef long long ll;
////////////////////////////////////////////////////////////

int main(){
	int x,y;
	cin >> x >> y;
	cout << x + y/2 << endl;
	ret 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct node{
	unsigned int key;
	struct node *next;
	struct node *prev;
};

typedef struct node * NodePointer;

NodePointer nil;

NodePointer listSearch( int key )
{
	NodePointer cur = nil->next;
	while( cur != nil && cur->key != key ) {
		cur = cur->next;
	}
	return cur;
}

void init( )
{
	nil = malloc( sizeof(struct node) );
	nil->next = nil;
	nil->prev = nil;
}

void printList( )
{
	NodePointer cur = nil->next;
	int isf = 1;
	while(1) {
		if( cur == nil ) { break; }
		if( isf == 0) { printf(" "); }
		printf( "%d", cur->key );
		cur = cur->next;
		isf = 0;
	}
	printf("\n");
}

void deleteNode( NodePointer t )
{
	t->prev->next = t->next;
	t->next->prev = t->prev;
	free( t );
}

void deleteFirst( )
{
	NodePointer t = nil->next;
	if( t == nil ) return;
	deleteNode( t );
}

void deleteLast( )
{
	NodePointer t = nil->prev;
	if( t == nil ) return;
	deleteNode( t );
}

void delete( int key )
{
	NodePointer t = listSearch( key );
	if( t == nil ) return;
	deleteNode( t );
}

void insert( int key )
{
	NodePointer x;
	x = malloc( sizeof(struct node) );
	x->key = key;
	x->next = nil->next;
	x->next->prev = x;
	x->prev = nil;
	nil->next = x;
}


int main( int argc, char *argv[] ) 
{
	int key, n, i;
	char com[20];
	
	scanf( "%d", &n );
	init( );
	for( i = 0; i < n; i++ ) {
		scanf( "%s", com );
		if( com[0] == 'i' ) {
			scanf( "%d", &key );
			insert( key ); 
		} else if( com[0] == 'd' ) {
			if( 6 < strlen( com )  ) {
				if( com[6] == 'F' ) { 
					deleteFirst( );
				} else if( com[6] == 'L' ) {
					deleteLast( );
				}
			} else {
				scanf( "%d", &key );
				delete( key );
			}
		}
	}
	printList( );
	
    return 0;
}

Measured memory_bytes: 31788
#include <iostream>
#include <iomanip>
#include <ios> 
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <bitset>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define sz(c) ((int)(c).size())

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
const ll MOD=1e9+7;
const int MAX=1e5+5;

ll extgcd(ll a,ll b,ll& x, ll& y){
	ll d=a;
	if(b!=0){
		d = extgcd(b, a%b, y, x);
		y -= (a/b) * x;
	}
	else{
		x = 1; y = 0;
	}
	return d;
}
ll mod_inv(ll a,ll m){
	ll x,y;
	extgcd(a,m,x,y);
	return (m+x%m)%m;
}

ll fc[2*MAX];

ll cb(int a,int b){
	return (((fc[a]*mod_inv(fc[b],MOD))%MOD)*mod_inv(fc[a-b],MOD))%MOD;
}
//(a,b)から(c,d)へ行く
ll rect(int a,int b,int c,int d){
	return cb(a-c+d-b,a-c);
}

int main(){
	fc[0]=1;
	rep1(i,2*MAX-1)fc[i]=(i*fc[i-1])%MOD;
	
	int H,W,A,B;
	cin>>H>>W>>A>>B;
	ll ans=0;
	int p=A,q=B;
	while(p<H && q<W){
		ll k=(rect(H-1,0,p,q)*rect(p,q,0,W-1))%MOD;
		ans=(ans+k)%MOD;
		p++;q++;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 1792
import math
log2 = math.log2
ceil = math.ceil
read = input
n,k = map(int, read().split())
ans = 0.0
for i in range(1, n+1):
    if i >= k:
        ans += 1
    else :
        ans += 0.5 ** ceil(log2(k/i))
ans /= n
print('%.12f'%ans)

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

using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;

void AGC039A()
{
	string S;
	cin >> S;
	ll K;
	cin >> K;
	int N = S.size();

	bool isSingle = true;
	for (int i = 1; i < N; ++i)
	{
		if (S[i] != S[0])
		{
			isSingle = false;
			break;
		}
	}
	if (isSingle)
	{
		cout << N * K / 2 << endl;
		return;
	}

	bool update = false;
	ll ct = 0;
	for (int i = 1; i < N; ++i)
	{
		if (!update && S[i] == S[i - 1])
		{
			++ct;
			update = true;
		}
		else
			update = false;
	}
	ll ct2 = ct;
	if (!update && S.back() == S.front())
	{
		++ct2;
		update = true;
	}
	else
		update = false;
	for (int i = 1; i < N; ++i)
	{
		if (!update && S[i] == S[i - 1])
		{
			++ct2;
			update = true;
		}
		else
			update = false;
	}
	cout << ct + (ct2 - ct) * (K - 1) << endl;
}

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

Measured memory_bytes: 256
use std::cmp;
use std::io;

fn main() {
    let n = read_one::<usize>();
    let an = read::<isize>();
    let mut dp = vec![vec![0isize; 2]; n + 1];
    dp[0][1] = -1_000_000_000;
    for i in 0..n {
        dp[i + 1][0] = cmp::max(dp[i][0] + an[i], dp[i][1] - an[i]);
        dp[i + 1][1] = cmp::max(dp[i][0] - an[i], dp[i][1] + an[i]);
    }

    println!("{}", dp[n][0]);
}

#[allow(dead_code)]
fn read<T>() -> Vec<T>
where
    T: std::str::FromStr,
    T::Err: std::fmt::Debug,
{
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.split_whitespace()
        .map(|s| s.trim().parse().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_one<T>() -> T
where
    T: std::str::FromStr,
    T::Err: std::fmt::Debug,
{
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().unwrap()
}

Measured memory_bytes: 10492
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
const int mod = 1e9+7;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
struct UnionFind{
    vector<int> d;
    UnionFind(int n) : d(n,-1) {}
    //根なら、-サイズを格納それ以外は、親を格納
    int find(int x){
        if(d[x] < 0) return x;
        return d[x] = find(d[x]); //経路縮約
    }
    bool unite(int x,int y){
        //二つ頂点を持ってくる
        x = find(x);
        y = find(y);
        if(x == y) return false;//根が一致するなら何もしない
        if(d[x] > d[y]) swap(x,y);
        //ex:d[x]=-5,d[y]=-2
        //小さい方が、大きい方に引っ付く
        d[x] += d[y];//この場合、yがxにくっつく
        d[y] = x;
        return true;
    }
    bool same(int x,int y) {return find(x) == find(y);}
    int size(int x) {return -d[find(x)];}
};
int main(){
    cout << fixed << setprecision(10);
    ll n,m;
    cin >> n >> m;
    vector<int> a(m),b(m);
    rep(i,m) cin >> a[i] >> b[i];
    rep(i,m){
        a[i]--; b[i]--;
    }
    UnionFind uf(n);
    vector<ll> ans;
    ll now = n*(n-1)/2;
    rep(i,m){
        ans.push_back(now);
        int aa = a[m-i-1], bb = b[m-i-1];
        if(uf.same(aa,bb)){
            continue;
        }
        ll sa = uf.size(aa)*uf.size(bb);
        now -= sa;
        uf.unite(aa,bb);
    }
    reverse(ans.begin(),ans.end());
    for(auto u : ans) cout << u << endl;
    return 0;
}

Measured memory_bytes: 3444
n, k = map(int, input().split())
a = list(map(int, input().split()))

visited_l = [1]
visited_s = set([1])

now = 1

if k <= n:
    for i in range(k):
        now = a[now - 1]
    print(now)
else:
    for i in range(n):
        now = a[now - 1]
        if now in visited_s:
            break
        else:
            visited_l.append(now)
            visited_s.add(now)

    l = visited_l.index(now)
    loop = i - l + 1

    res = (k - len(visited_l)) % loop

    print(visited_l[l + res])

Measured memory_bytes: 32336
#include <iostream>
#include <string>
#include <queue>
#include <algorithm>

using namespace std;

int main() {

	int x[4], y[4], dx ,dy;
	bool a = false, b = false;

	cin >> x[0] >> y[0] >> x[1] >> y[1];

	dx = x[1] - x[0];
	dy = y[1] - y[0];

	if (dx > 0) a = true;
	if (dy > 0) b = true;

	dx = abs(dx);
	dy = abs(dy);


	if (a && b) {
		x[2] = x[1] - dy, x[3] = x[2] - dx, y[2] = y[1] + dx, y[3] = y[2] - dy;
	}
	else if(a && !b) {
		x[2] = x[1] + dy, x[3] = x[2] - dx, y[2] = y[1] + dx, y[3] = y[2] + dy;
	}
	else if (!a && b) {
		x[2] = x[1] - dy, x[3] = x[2] + dx, y[2] = y[1] - dx, y[3] = y[2] - dy;
	}
	else if (!a && !b) {
		x[2] = x[1] + dy, x[3] = x[2] + dx, y[2] = y[1] - dx, y[3] = y[2] + dy;
	}

	cout << x[2] << " " << y[2] << " " << x[3] << " " << y[3];

	return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const int INF = 1001001001;

int main(){
  int n; cin >> n;
  vector<int> assign(n,-1);
  vector<vector<int>> to(n,vector<int>(0));
  for(int i=0;i<n-1;i++){
    int a,b;
    cin >> a >> b;
    a--; b--;
    to.at(a).push_back(b);
    to.at(b).push_back(a);
  }
  vector<int> c(n,0);
  for(int i=0;i<n;i++) cin >> c.at(i);
  sort(c.rbegin(),c.rend());
  assign.at(0) = c.at(0);
  queue<int> q;
  q.push(0);
  ll j = 1;
  while(q.size()){
    int x = q.front();
    q.pop();
    for(auto y:to.at(x)){
      if(assign.at(y)!=-1) continue;
      assign.at(y) = c.at(j); j++;
      q.push(y);
    }
  }
  ll m = 0;
  for(int i=1;i<n;i++){
    m += c.at(i);
  }
  cout << m << endl;
  for(int i=0;i<n;i++){
    cout << assign.at(i) << " ";
  }
}

Measured memory_bytes: 1024
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return set([i for i in range(n + 1) if is_prime[i]])
sosuu = primes(10**6)
N=int(input())
for i in range(N,10**6):
 if i in sosuu:
  print(i)
  break

Measured memory_bytes: 16564
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>
#include<queue>

using namespace std;

#define INF 1000000007

vector<int> dist1;
vector<int> dist2;
vector<vector<int>> to;
vector<bool> done;

void dfs1(int id,int d)
{
	dist1[id]=d;
	done[id]=true;
	for(int i=0;i<to[id].size();i++)
	{
		int nx=to[id][i];
		if(done[nx])continue;
		dfs1(nx,d+1);
	}
}

void dfs2(int id,int d)
{
	//cout << id << " : " << d << endl;
	dist2[id]=d;
	done[id]=true;
	for(int i=0;i<to[id].size();i++)
	{
		int nx=to[id][i];
		if(dist1[nx]<=d+1)continue;
		if(done[nx])continue;
		dfs2(nx,d+1);
	}
} 

int main()
{
	int n,u,v;
	cin >> n >> u >> v;
	u--;v--;

	to=vector<vector<int>>(n);
	dist1=vector<int>(n,INF);
	dist2=vector<int>(n,INF);
	for(int i=0;i<n-1;i++)
	{
		int a,b;
		cin >> a >> b;
		a--;b--;
		to[a].push_back(b);
		to[b].push_back(a);
	}

	dist1[v]=0;
	done=vector<bool>(n,false);
	dfs1(v,0);

	dist2[u]=0;
	done=vector<bool>(n,false);
	dfs2(u,0);

	int ans=0;
	int id=0;
	for(int i=0;i<n;i++)
	{
		//cout << dist1[i] << " " << dist2[i] << endl;
		if(dist1[i]>=ans and dist2[i]!=INF)
		{
			ans=dist1[i];
			id=i;
		}
	}
	//cout << dist1[id]-1 << endl;
	cout << ans-1 << endl;




}


Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
#define LL long long
#define INF 0x3f3f3f3f

const int MAXN = 1e5 + 5;
const LL MOD = 1e9 + 7;

int c[4][4];

int main()
{
#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
#endif

    for(int i = 1; i <= 3; i++)
    {
        for(int j = 1; j <= 3; j++)
        {
            scanf("%d", &c[i][j]);
        }
    }
    int flag = 0;
    for(int a1 = 0; a1 <= 100; a1++)
    {
        int b1 = c[1][1] - a1;
        int a2 = c[2][1] - b1;
        int a3 = c[3][1] - b1;
        int b2 = c[1][2] - a1;
        int b3 = c[1][3] - a1;
        if(a2 + b2 == c[2][2] && a2 + b3 == c[2][3]
                && a3 + b2 == c[3][2] && a3 + b3 == c[3][3])
        {
            flag = 1;
            break;
        }
    }

    if(flag)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}
/*
a1+b1 a1+b2 a1+b3
a2+b1 a2+b2 a2+b3
a3+b1 a3+b2 a3+b3
*/

Measured memory_bytes: 256
from sys import stdin
n = int(stdin.readline().rstrip())
arr = stdin.readline().rstrip().split()
pre_num = int(arr.pop(0))
cnt = 0
max_cnt = 0
for i in arr:
  current_num = int(i)
  if pre_num >= current_num:
    cnt += 1
  else:
    if max_cnt < cnt:
      max_cnt = cnt
    cnt = 0
  pre_num = current_num
if max_cnt < cnt:
  max_cnt = cnt
print(max_cnt)


Measured memory_bytes: 11128
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using vi = vector<i64>;
using vvi = vector<vi>;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

class BIT {
    int n, N;
    vi data;

    i64 sum(int i) {
        i64 s = 0;
        while (i > 0) {
            s += data[i];
            i -= i & -i;
        }
        return s;
    }

    // assuming elements are all positive
    int lower_bound(i64 w) {
        if (w <= 0) return -1;
        int x = 0;
        for (int k = N; k > 0; k >>= 1) {
            if (x + k <= n && data[x + k] < w) {
                w -= data[x + k];
                x += k;
            }
        }
        return x;
    }

    int upper_bound(i64 w) {
        if (w <= 0) return -1;
        int x = 0;
        for (int k = N; k > 0; k >>= 1) {
            if (x + k <= n && data[x + k] <= w) {
                w -= data[x + k];
                x += k;
            }
        }
        return x;
    }

public:
    BIT(int n) : n(n) {
        data = vi(n + 1);
        N = 1;
        while (N <= n) N <<= 1;
        N >>= 1;
    }

    void add(int i, i64 x) {
        i++;
        while (i <= n) {
            data[i] += x;
            i += i & -i;
        }
    }

    // [l, r)
    i64 sum(int l, int r) {
        return sum(r) - sum(l);
    }

    // sum([a, k]) >= xとなる最小のk
    int lower_bound(int a, i64 x) {
        return max(a, lower_bound(x + sum(0, a)));
    }

    // sum([a, k]) > xとなる最小のk
    int upper_bound(int a, i64 x) {
        return max(a, upper_bound(x + sum(0, a)));
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout.setf(ios::fixed);
    cout.precision(10);
    int n, q;
    cin >> n >> q;
    BIT bit(n + 1);
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        bit.add(i, a);
    }
    bit.add(n, 1e17);
    while (q--) {
        i64 x;
        cin >> x;
        i64 ret = 0;
        for (int i = 0; i < n; i++) {
            ret += bit.upper_bound(i, x) - i;
        }
        cout << ret << endl;
    }
}


Measured memory_bytes: 3568
#!/usr/bin/env python3
import sys
import math
import decimal
import itertools
from itertools import product
from functools import reduce
def input():
    return sys.stdin.readline()[:-1]
def sort_zip(a:list, b:list):
    z = zip(a, b)
    z = sorted(z)
    a, b = zip(*z)
    a = list(a)
    b = list(b)
    return a, b

def main():
    H, W, K = map(int, input().split())
    c = []
    for i in range(H):
        c.append(input())

    ans = 0
    for i in product([0, 1], repeat=H):
        for j in product([0, 1], repeat=W):
            black = 0
            for h in range(H):
                for w in range(W):
                    if i[h] == 1 and j[w] == 1 and c[h][w] == '#':
                        black += 1
            if black == K:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 78936
use std::fs;
use std::io::{stdin, Read};

macro_rules! parse {
    ($it: ident) => {
        $it.next().unwrap().parse().unwrap()
    };
    ($it: ident,2) => {
        (parse!($it), parse!($it))
    };
    ($it: ident,3) => {
        (parse!($it), parse!($it), parse!($it))
    };
    ($it: ident,4) => {
        (parse!($it), parse!($it), parse!($it), parse!($it))
    };
    ($it: ident, $n: expr) => {
        (&mut $it).take($n).map(|e| e.parse().unwrap()).collect();
    };
}

fn solve(s: &str) {
    let mut it = s.split_whitespace();
    let n = parse!(it);
    let a: Vec<isize> = parse!(it, n);
    let s = a.iter().filter(|&&x| x < 0).count() % 2;
    let mut pa = a
        .iter()
        .map(|&x| if x >= 0 { x } else { -x })
        .collect::<Vec<_>>();
    pa.sort();
    let sum = pa.iter().sum::<isize>();
    if s == 0 || a.contains(&0) {
        println!("{}", sum);
    } else {
        println!("{}", sum - 2 * pa[0]);
    }
}

fn test() {
    let mut f = fs::File::open("foo.txt").unwrap();
    let mut s = String::new();
    f.read_to_string(&mut s).unwrap();
    solve(&s);
}

fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    solve(&s);
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_main() {
        test();
    }
    #[test]
    fn test_input() {
        let s = "
        ";
        solve(s);
    }
}


Measured memory_bytes: 8444
#include <bits/stdc++.h>
using namespace std;
#define EPS 1e-8  
struct Point{
	double x,y;
};


double cross(Point a, Point b) {
	return a.x*b.y - a.y*b.x;
}

double dot(Point a,Point b){
  return a.x*b.x+a.y*b.y;
}

int contains(vector<Point> g,Point p){
  int n=g.size();
  bool x=false;
  for(int i=0;i<n;i++){
  	Point a,b;
	a.x=g[i].x-p.x;
	a.y=g[i].y-p.y;
	b.x=g[(i+1)%n].x-p.x;
	b.y=g[(i+1)%n].y-p.y;
    if(fabs(cross(a,b)) < EPS && dot(a,b) < EPS) return 1;
    if(a.y>b.y) swap(a,b);
    if(a.y < EPS && EPS < b.y && cross(a,b) > EPS ) x = !x;
  }
  return (x?2:0);
}

int main(){
	int n;
	cin>>n;
	vector<Point> p(n);
	for(int i=0;i<n;i++) {
		cin>>p[i].x>>p[i].y;
	}
	int q;
	cin>>q;
	while(q--){
		Point r;
		cin>>r.x>>r.y;
		cout<<contains(p,r)<<endl;
	}
}


Measured memory_bytes: 3260
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
# mod = 10 ** 9 + 7
mod = 998244353 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def functional(N):
    F = [1] * (N + 1)
    for i in range(N):
        F[i + 1] = (i + 1) * F[i] % mod
    return F


def inv(a):
    return pow(a, mod - 2, mod)


def C(F, a, b):
    return F[a] * inv(F[a - b]) * inv(F[b]) % mod 


def main():
    N, M, K = read_values()
    F = functional(N)

    res = 0
    for k in range(K + 1):
        res += M * pow(M - 1, N - 1 - k, mod) * C(F, N - 1, k) % mod
        res %= mod

    print(res % mod)


if __name__ == "__main__":
    main()



Measured memory_bytes: 77512
#include <iostream>
#include<sstream>
#include<vector>
#include<iterator>
using namespace std;

int main(void)
{
	long long N, T;
	cin >> N >> T;

	long long left, right;
	left = 0;
	right = T;
	long long ret = 0;
	for(int i=0; i<N; i++)
	{
		long long t;
		cin >> t;

		if(t < right)
			right = t + T;
		else
		{
			ret += right - left;
			left = t;
			right = left + T;
		}
	}
	ret += right - left;

	cout << ret << endl;

	return 0;
}


Measured memory_bytes: 256