akhauriyash/Code-Regression huggingface dataset:
#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]

use itertools::Itertools;

const U_INF: usize = 1 << 60;
const I_INF: isize = 1 << 60;

fn main() {
    let mut sc = Scanner::new();
    let n = sc.next_usize();
    let mut a = Vec::with_capacity(n);
    for _ in 0..n {
        let ai = sc.next_usize();
        a.push(ai);
    }

    let mut now = 0;
    for i in 0..n {
        now = a[now] - 1;

        if now == 1 {
            println!("{}", i + 1);
            return;
        }
    }

    println!("{}", -1);
}

pub struct Scanner {
    buf: std::collections::VecDeque<String>,
}

impl Scanner {
    pub fn new() -> Self {
        Self {
            buf: std::collections::VecDeque::new(),
        }
    }

    fn scan_line(&mut self) {
        let mut flag = 0;
        while self.buf.is_empty() {
            let mut s = String::new();
            std::io::stdin().read_line(&mut s).unwrap();
            let mut iter = s.split_whitespace().peekable();
            if iter.peek().is_none() {
                if flag >= 5 {
                    panic!("There is no input!");
                }
                flag += 1;
                continue;
            }

            for si in iter {
                self.buf.push_back(si.to_string());
            }
        }
    }

    pub fn next<T: std::str::FromStr>(&mut self) -> T {
        self.scan_line();
        self.buf
            .pop_front()
            .unwrap()
            .parse()
            .unwrap_or_else(|_| panic!("Couldn't parse!"))
    }

    pub fn next_usize(&mut self) -> usize {
        self.next()
    }

    pub fn next_isize(&mut self) -> isize {
        self.next()
    }

    pub fn next_chars(&mut self) -> Vec<char> {
        self.next::<String>().chars().collect()
    }

    pub fn next_string(&mut self) -> String {
        self.next()
    }

    pub fn next_char(&mut self) -> char {
        self.next()
    }

    pub fn next_float(&mut self) -> f64 {
        self.next()
    }
}


Measured memory_bytes: 2832
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scanner = new Scanner(System.in);
		int a = scanner.nextInt();
		int b = scanner.nextInt();
		System.out.println((b-a)*(b-a+1)/2 -b);
	}

}

Measured memory_bytes: 21716
#include <iostream>
#include <cstring>
#include <climits>
#define MAXN 405

using namespace std;

int N;							//number of elements in set
int a[MAXN];					//given set
long long dp[MAXN][MAXN];	//dp table for minimum cost of merging elements from [i]to[j]
long long s[MAXN]; 		//prefix sum for efficient range query calculation
long long cost;				//dynamic cost for minimization

long long sum(int i,int j){
	if(i==j)
		return a[i];
	if(i==0)
		return s[j];
	return s[j]-s[i-1];
}


long long solve(int i,int j){
	if(i==j)
		dp[i][j] = 0;
	else if(dp[i][j]==0){
		dp[i][j] = INT64_MAX;
		for(int k=i;k<j;k++){
			solve(i,k);
			solve(k+1,j);
			cost = dp[i][k] + dp[k+1][j] + sum(i,k) + sum(k+1,j) ;
			if(dp[i][j]>cost)
				dp[i][j]  = cost;
		}
	}
	return dp[i][j];
}

int main(){
	cin>>N;
	memset(dp,0,sizeof(dp));
	memset(s,0,sizeof(s));
	for(int i=0;i<N;i++){
		cin>>a[i];
		s[i]=+a[i];
		if(i>0)
			s[i]+=s[i-1];
	}
	cout<<solve(0,N-1)<<endl;
}


Measured memory_bytes: 1536
def xorN(N):
    if N%4==1:
        return(1)
    elif N%4==2:
        return(N+1)
    elif N%4==3:
        return(0)
    else:
        return(N)

A,B=map(int,input().split())
print(xorN(A-1)^xorN(B))


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

using namespace std;

const int N=3010,MOD=1e9+7;

int n,m,ans;

int f[N][N][2];

int plu(int u,int v){
	return (u+v)%MOD;
}

int main(){
	scanf("%d%d",&n,&m);
	f[0][0][1]=1;
	for(int i=1;i<=n;i++){
		f[0][i][0]=1;
	}
	for(int i=0;i<m;i++){
		for(int j=0;j<=n;j++){
			for(int k=0;k<2;k++){
				if(j){
					f[i+1][j-1][k|(j==1)]=plu(f[i+1][j-1][k|(j==1)],f[i][j][k]);
					f[i+1][j][k|(j==1)]=plu(f[i+1][j][k|(j==1)],f[i][j][k]);
				}
				if(j!=n){
					f[i+1][j+1][k]=plu(f[i+1][j+1][k],f[i][j][k]);
					f[i+1][j][k]=plu(f[i+1][j][k],f[i][j][k]);
				}
			}
		}
	}
	for(int i=0;i<=n;i++){
		ans=plu(ans,f[m][i][1]);
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 70784
#include <bits/stdc++.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
#define rep(i,s,e) for (int64_t i=s; i<e; i++)
#define pi 3.14159265358979323846264338327950L
using namespace std;

int main() {
  int64_t X, Y;
  cin >> X >> Y;
  rep(i,1,70) {
    if (2*X<=Y) {
      X*=2;
    }
    else {
      cout << i << endl;
      break;
    }
  }
}


Measured memory_bytes: 3580
n, k = map(int, input().split())
s = [] 
mod = 998244353

for i in range(k):
    l, r = map(int, input().split())
    s.append([l, r])

dp = [0 for _ in range(n+1)]
dp[1] = 1
dpsum = [0 for _ in range(n+1)]
dpsum[1] = 1

for i in range(2,n+1):
    for l, r in s:
        li = max(i-r,1)
        ri = max(i-l,0)
        dp[i] += (dpsum[ri] - dpsum[li-1])%mod
    dpsum[i] = (dpsum[i-1] + dp[i])%mod

print(dp[n]%mod)

Measured memory_bytes: 27316
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long lo;
typedef pair< lo,lo > PII;
 
#define fi first
#define se second
#define int long long
#define mp make_pair
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
 
const lo inf = 200000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 3005;
const lo mod = 1000000007;
 
int n,m,b[li],a[li],k,flag,t,dp[li][li],c[li];
int cev;
string s,ss,s1;
vector<int> v;
 
main(void){
	fio();
	cin>>s>>ss;
	int n=(int)s.size();
	int m=(int)ss.size();
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(s[i]==ss[j])dp[i][j]=dp[i-1][j-1]+1;
			else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		}
	}
	int i=n-1;
	int j=m-1;
	while(i>=0 && j>=0){
		if(s[i]==ss[j]){s1+=s[i];i--;j--;continue;}
		if(dp[i-1][j]>=dp[i][j-1]){i--;}
		else j--;
	}
	reverse(s1.begin(),s1.end());
	cout<<s1<<endl;
	return 0;
}


Measured memory_bytes: 74036
import math

N=int(input())
A=list(map(int,input().split()))
L=[0]*(N+1)
for i in range(N):
  L[i+1]=math.gcd(L[i],A[i])
R=[0]*(N+1)
for i in range(N-1,-1,-1):
  R[i]=math.gcd(R[i+1],A[i])
M=[]
for i in range(N):
  M.append(math.gcd(L[i],R[i+1]))
print(max(M))


Measured memory_bytes: 25088
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
using ll = long long;
int main(){ 
    ll n;
    cin>>n;
    if(n<10){
        cout<<n;
    }else if(n<100){
        cout<<9;
    }else if(n<1000){
        cout<<9+n-99;
    }else if(n<10000){
        cout<<909;
    }else if(n<100000){
        cout<<909+n-9999;
    }else{
        cout<<90909;
    }
    return 0;
}


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

int main(){
    int N; cin >> N;
    vector<int> vecA(N); for(int i=0; i<N; i++){ cin >> vecA[i]; }
    
    std::sort(vecA.begin(), vecA.end(), std::greater<int>());
    
    int Alice=0;
    int Bob  =0;
    for(int i=0; i<vecA.size(); i++){
        Alice += vecA[i++];
        Bob   += vecA[i  ];
    }
    
    cout << (Alice-Bob);
    
    return 0;
}

Measured memory_bytes: 256
def main():
    n,m = tuple([int(t)for t in input().split()])
    a = [int(t)for t in input().split()]

    e = [tuple([int(t)for t in input().split()])for _ in [0]*m]

    e.sort(key=lambda x:x[1])
    t = 0
    for _ in [0]*m:
        b,c = e.pop()
        t+=b
        for _ in [0]*b:
            a.append(c)
        if t>n:break
    
    a.sort(reverse = True)
    print(sum(a[:n]))
if __name__ == "__main__":
    main()


Measured memory_bytes: 93720
import sys
import bisect
N=int(input())
d=sorted(list(map(int,input().split())))
ans=0
for i in range(1,len(d)-1):
  for j in range(i+1,len(d)):
    v=(N-j)-(bisect.bisect_left(d,d[-i]-d[-j]+1))
    if v<=0:
      pass
    else:
      ans+=v
print(ans)

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

int n, m;
const int MAX = 55;
int A[MAX], B[MAX];
bool G[MAX][MAX], used[MAX];

void dfs(int now){
    used[now] = true;
    for(int i = 0; i < n; i++){
        if(!used[i] && G[now][i]){
            dfs(i);
        }
    }
}

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

    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> A[i] >> B[i];
        A[i]--; B[i]--;
        G[A[i]][B[i]] = true;
        G[B[i]][A[i]] = true;
    }

    int ans = 0;
    for(int i = 0; i < m; i++){
        G[A[i]][B[i]] = false;
        G[B[i]][A[i]] = false;

        for(int j = 0; j < n; j++){
            used[j] = false;
        }

        dfs(0);

        bool bridge = false;
        for(int j = 0; j < n; j++){
            if(used[j] == false) bridge = true; 
        }
        if(bridge) ans++;

        G[A[i]][B[i]] = true;
        G[B[i]][A[i]] = true;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define repr(e,x) for(auto& e:x)
using namespace std;
typedef long long ll;

int A,B;

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

    if(A<=8 && B<=8){
        cout<<"Yay!"<<endl;
    }else{
        cout<<":("<<endl;
    }
}

Measured memory_bytes: 256
def Partition(A,p,r): ## r = n-1 (A의 p~r번째(0 base)요소를 partition!)
    x = A[r][1]
    i = p-1
    for j in range(p,r):
        if (A[j][1] <= x):
            i += 1
            A[i], A[j] = A[j], A[i]
    A[r], A[i+1] = A[i+1], A[r]
    return i+1

def Quicksort(A, p, r):
    if (p < r):
        q = Partition(A,p,r)
        Quicksort(A,p,q-1)
        Quicksort(A,q+1,r)
n = int(input())
A = []
color = [[]for i in range(4)] #S H C D
for i in range(n):
    a,v = input().split()
    v = int(v)
    A.append((a,v))
copya = A[:]
Quicksort(A, 0, n-1)
Avdic = dict()
for a,v in A:
    if (v not in Avdic.keys()):
        Avdic[v] = [a]
    else:
        Avdic[v] += [a]
cvdic = dict()
for a,v in copya:
    if (v not in cvdic.keys()):
        cvdic[v] = [a]
    else:
        cvdic[v] += [a]
if (Avdic == cvdic):
    print('Stable')
else:
    print('Not stable')
for a in A:
    print(*a)


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

int main() {
  string s;
  cin >> s;
  rep(i, s.length()) {
    if (i%2 == 0 && s[i] == 'L') {
      cout << "No";
      return 0;
    } else if (i%2 == 1 && s[i] == 'R') {
      cout << "No";
      return 0;
    }
  }
  cout << "Yes";
  return 0;
}

Measured memory_bytes: 256
/*** 𝕒𝕜𝕤𝕙𝕒𝕪𝕜𝕦𝕞𝕒𝕣𝟡𝟡 ***/

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
template<typename T> using id_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update> ;
 
#define f(i,x,n) for(i=x;i<n;i++)
#define fr(i,x,n) for(i=x;i>=n;i--)
#define pu push_back           
#define pp pop_back
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define SP(x) fixed<<setprecision(x)
#define IOS() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
const long long MOD=1e9+7;
const long double PI = acos(-1);
const long long INF=INT_MAX;
const long long LINF=LLONG_MAX;
const long long N=2e5+1;
 
typedef int ll;
typedef long double ld;

void test_case()
{
    string s;
    cin>>s;
    if(s[1]=='R')
        cout<<"ABC\n";
    else
        cout<<"ARC\n";

   
}

int32_t main()
{
    IOS(); 
    int tc=1;
    // cin>>tc;
    while(tc--)
        test_case();
    return 0;
}

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

int main() {
    int n, m;
    while (cin >> n >> m, n) {
        vector<int> a(n);
        for (int& ai: a) cin >> ai;
        int ans = -1;
        for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) {
            if (a[i] + a[j] <= m) ans = max(ans, a[i] + a[j]);
        }
        if (ans == -1) cout << "NONE" << endl;
        else cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 3012
# C
H, W = map(int, input().split())
 
res = min(H, W)
# split H
for h in range(H // 3, H // 3 + 2):
    w = W // 2
    s1 = h*W
    s2 = (H-h)*w
    s3 = (H-h)*(W-w)
    res = min(res, max(s1,s2,s3) - min(s1,s2,s3))
# split W
for w in range(W // 3, W // 3 + 2):
    h = H // 2
    s1 = w*H
    s2 = (W-w)*h
    s3 = (W-w)*(H-h)
    res = min(res, max(s1,s2,s3) - min(s1,s2,s3))
    
# 3
if H % 3 == 0 or W % 3 == 0:
    res = 0
print(res)



Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
main(){
  int a,b,c,t;
  while(cin>>a>>b>>c,a!=-1){
  t=2*3600-a*3600-b*60-c;
  printf("%02d:%02d:%02d\n",t/3600,(t%3600)/60,t%60);
  t*=3;
  printf("%02d:%02d:%02d\n",t/3600,(t%3600)/60,t%60);
  }
}

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

int main() {
	int n, h, w;
	long int a[1001], b[1001];
	cin >> n >> h >> w;
	int j = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
		if (a[i] >= h && b[i] >= w)j++;
	}
	cout << j << endl;

}

Measured memory_bytes: 256
/* ---------- STL Libraries ---------- */

// IO library
#include <cstdio>
#include <fstream>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>
#include <cmath>
#include <numeric>
#include <random>

// container library
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>

/* ---------- Namespace ---------- */

using namespace std;

/* ---------- Type Abbreviation ---------- */

template <typename T>
using PQ = priority_queue<T>;
template <typename T>
using GPQ = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;

#define fst first
#define snd second
#define mp make_pair
#define mt make_tuple

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


/* ---------- conversion ---------- */

#define INT(c) static_cast<int>(c)
#define CHAR(n) static_cast<char>(n)
#define LL(n) static_cast<ll>(n)
#define DOUBLE(n) static_cast<double>(n)

/* ---------- container ---------- */

#define ALL(v) (v).begin(), (v).end()
#define SIZE(v) (LL((v).size()))

#define FIND(v, k) (v).find(k) != (v).end()
#define VFIND(v, k) find(ALL(v), k) != (v).end()

#define gsort(b, e) sort(b, e, greater<decltype(*b)>())

/* ----------- debug ---------- */

template <class T>
ostream& operator<<(ostream& os, vector<T> v) {
	os << "[";
	for (auto vv : v)
		os << vv << ",";
	return os << "]";
}

template <class T>
ostream& operator<<(ostream& os, set<T> v) {
	os << "[";
	for (auto vv : v)
		os << vv << ",";
	return os << "]";
}

template <class L, class R>
ostream& operator<<(ostream& os, pair<L, R> p) {
	return os << "(" << p.fst << "," << p.snd << ")";
}

/* ---------- Constants ---------- */

// const ll MOD = 1e9 + 7;
// const int INF = 1 << 25;
// const ll INF = 1LL << 50;
// const double PI = acos(-1);
// const double EPS = 1e-10;
// mt19937 mert(LL(time(0)));

/* ---------- Short Functions ---------- */

template <typename T>
T sq(T a) {
	return a * a;
}

template <typename T>
T gcd(T a, T b) {
	if (a > b) return gcd(b, a);
	return a == 0 ? b : gcd(b % a, a);
}

template <typename T, typename U>
T mypow(T b, U n) {
	if (n == 0) return 1;
	if (n == 1) return b /* % MOD */;
	if (n % 2 == 0) {
		return mypow(b * b /* % MOD */, n / 2);
	}
	else {
		return mypow(b, n - 1) * b /* % MOD */;
	}
}

ll pcnt(ll b) {
	return __builtin_popcountll(b);
}



// const ll dx[4] = {0, -1, 1, 0};
// const ll dy[4] = {-1, 0, 0, 1};
// const ll dx[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
// const ll dy[8] = {-1, -1, -1, 0, 0, 1, 1, 1};

/* v-v-v-v-v-v-v-v-v Main Part v-v-v-v-v-v-v-v-v */

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll N;
	cin >> N;
	const string march = "MARCH";
	ll cnt[5] = {};
	REP(i, N) {
		string S;
		cin >> S;
		REP(j, 5) {
			if (S[0] == march[j]) cnt[j]++;
		}
	}
	ll ans = 0;
	REP(i, 3) {
		FOR(j, i + 1, 4) {
			FOR(k, j + 1, 5) {
				ans += cnt[i] * cnt[j] * cnt[k];
			}
		}
	}
	cout << ans << endl;
	return 0;
}

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

using namespace std;
#define all(a)a.begin(),a.end()
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod = int(1e9)+7;
using V = vector<int>;
using P = pair<int,int>;

int main()
{
    int n;cin >>n;
    V l(n);rep(i,n)cin >>l[i];
    sort(all(l));
    int x=0;rep(i,n-1)x+=l[i];
    if(x>l[n-1])puts("Yes");
    else puts("No");
    return 0;
}


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

using namespace std;

const int M=26;

int arr[404];
int n;
int c[26];
int s[404][26];
int las[26];

long long calc()
{
	for(int i=0;i<M;i++) las[i]=0;
	long long ans=0;
	for(int i=0;i<n;i++)
	{
		las[arr[i]-1]=i+1;
		ans+=s[i][arr[i]-1];
		for(int j=0;j<M;j++)
			ans-=c[j]*(i+1-las[j]);
		//cout << ans << endl;
	}
	return ans;
}

int main()
{
	//auto start = std::chrono::system_clock::now();
	mt19937 rng(12342);
	cin >> n;
	for(int i=0;i<M;i++) cin >> c[i];
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<M;j++) cin >> s[i][j];
	}
	for(int i=0;i<n;i++)
	{
		/*int ans=0;
		for(int j=0;j<26;j++)
			if(s[i][j]>s[i][ans]) ans=j;*/
		arr[i]=i%26+1;
	}
	//std::chrono::duration<double> elp=std::chrono::system_clock::now()-start;
	int t=1000;
	long long curs=calc();
	while(t--)
	{
		int x=uniform_int_distribution<int>(0, n-1)(rng);
		int y=uniform_int_distribution<int>(0, M-1)(rng);
		int oldx=arr[x];
		arr[x]=y+1;
		if(calc()<curs)
		{
			arr[x]=oldx;
		}
	}
	for(int i=0;i<n;i++)
		cout << arr[i] << endl;
}

Measured memory_bytes: 3684
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
#define first_more_idx(ve, num) upper_bound(all(ve), num)-ve.begin() // idx = first_more_idx(ve,num); if(idx = ve.size()) , then not exist
#define first_lessequal_idx(ve, num) lower_bound(all(ve), num)-ve.begin()
#define pq_pair_tB priority_queue <pair<ll,ll>, vector<pair<ll,ll> > , greater<pair<ll,ll> > >
#define pq_pair_ts priority_queue <pair<ll,ll> > // only sort first param
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}
ll power(ll x, ll n){if(n == 0) return 1;return  (n%2)? x*power(x, n-1)%MOD : power(x*x%MOD, n/2);}

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};
map<ll, bool> flg;

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

    ll N;
    cin >> N;


    UnionFind UF(200001);


    rep(i, N){
        ll a,b ;
        cin >> a >> b ;
        b += 100000;
        flg[a] = true;
        flg[b] = true;
        UF.unite(a,b);
    }
    vector<ll> idx;
    map<ll,vector<ll> > itm;
    rep(i, 200001){
        if(i == 0) continue;
        ll rt = UF.root(i);
        idx.pb(rt);
        itm[rt].pb(i);
    }

    rmsame(idx);


    ll ans  = 0;
    rep(i, idx.size()){
        if(flg[idx[i]] == false)continue;
        ll x = 0;
        ll y = 0;
        rep(j, itm[idx[i]].size()){
            if(itm[idx[i]][j] <= 100000) x ++;
            else y ++;
        }
        ans += x*y;
    }

    cout << ans - N << endl;
    //cout << fixed << setprecision(16) << ans << endl;
    return 0;
}


Measured memory_bytes: 36976
#include <stdio.h>
#define MAX 1000000
int n,Matrix[100][100],distance[100];
char color[100];



void Dijkstra_init(){
  int i;
  for(i=0;i<n;i++){
    distance[i]=MAX;
    color[i]='w';
  }
  distance[0]=0;
  color[0]='g';
}

void Dijkstra_print(){
  int vertex=0;
  while(vertex<n){
    if(distance[vertex]!=MAX)
      printf("%d %d\n",vertex,distance[vertex]);
    else
      printf("%d %d\n",vertex,-1);
    vertex++;
  }
}

void Dijkstra(){
  int minimum,i,j,vertex;

  Dijkstra_init();

  while(1){
    minimum=MAX;
    vertex=-1;
    //search for minimum of next vertex's distance
    for(i=0;i<n;i++){
      if(minimum>distance[i] && color[i]!='b'){
	vertex=i;
	minimum=distance[i];
      }
    }//finish first-for-loop

    if(vertex==-1)
      break;
    
    color[vertex]='b';
    for(i=0;i<n;i++){
      if(color[i]!='b' && Matrix[vertex][i]!=MAX){
	if(distance[i]>distance[vertex]+Matrix[vertex][i]){
	  distance[i]=distance[vertex]+Matrix[vertex][i];
	  color[i]='g';
	}
      }

    }//finish second-for-loop

  }//finish while loop

  Dijkstra_print();
}

void Initialization(){
  int i,j;
  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
      Matrix[i][j]=MAX;
}

int main(){
  //dis_dest -> distance of destination
  //degree -> outgoing degree from vertex
  int i,j,vertex,degree,destination,dis_dest;
  scanf("%d",&n);

  Initialization();
  
  for(i=0;i<n;i++){
    scanf("%d%d",&vertex,&degree);
    for(j=0;j<degree;j++){
      scanf("%d%d",&destination,&dis_dest);
      Matrix[vertex][destination]=dis_dest;
    }
  }

  Dijkstra();

  return 0;
}



Measured memory_bytes: 2112
<?php
  fscanf(STDIN,"%d %d",$n,$k);
  $sunk = [];
  for($i=1; $i<=$n; $i++){
    $sunk[$i] = 0;
  }
  for($i=0; $i<$k; $i++){
    $d = trim(fgets(STDIN));
    $a = explode(" ",trim(fgets(STDIN)));
    for($j=0; $j<$d; $j++){
      $sunk[$a[$j]]++;
    }
  }
  $count=0;
  for($i=1; $i<=$n; $i++){
    if($sunk[$i] <= 0){
      $count++;
    }
  }
  echo $count."\n";
  

Measured memory_bytes: 16160
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import defaultdict

H,W = map(int,readline().split())
A = [line.rstrip().decode('utf-8') for line in readlines()]

source = 0
sink = H+W+1

graph = [defaultdict(int) for _ in range(H+W+2)]

INF = 10 ** 18
for h in range(1,H+1):
    for w,ox in enumerate(A[h-1],1):
        if ox == 'x':
            continue
        elif ox == 'o':
            graph[h][H+w] = 1
            graph[H+w][h] = 1
        elif ox == 'S':
            graph[source][h] = INF
            graph[h][source] = INF
            graph[source][H+w] = INF
            graph[H+w][source] = INF
        elif ox == 'T':
            graph[sink][h] = INF
            graph[h][sink] = INF
            graph[sink][H+w] = INF
            graph[H+w][sink] = INF


class Dinic():
    def __init__(self,graph,V,source,sink):
        self.graph = graph
        self.sink = sink
        self.source = source
        self.V = V
#        self.compress()
        self.N = len(V)
    
    def compress(self):
        self.N = len(self.V)
        v_to_i = {x:i for i,x in enumerate(self.V)}
        self.sink = v_to_i[self.sink]
        self.source = v_to_i[self.source]
        g = [dict() for _ in range(self.N)]
        for v,e in self.graph.items():
            vn = v_to_i[v]
            g[vn] = {v_to_i[w]:c for w,c in e.items()}
        self.graph = g
        
    def bfs(self):
        level = [0]*self.N
        q = [self.source]
        level[self.source] = 1
        d = 1
        while q:
            if level[self.sink]:
                break
            qq = []
            d += 1
            for v in q:
                for w,cap in self.graph[v].items():
                    if cap == 0:
                        continue
                    if level[w]:
                        continue
                    level[w] = d
                    qq.append(w)
            q = qq
        self.level = level
        
    def dfs(self,v,f):
        if v == self.sink:
            return f
        for w,cap in self.itr[v]:
            if cap == 0 or self.level[w] != self.level[v] + 1:
                continue
            d = self.dfs(w,min(f,cap))
            if d:
                self.graph[v][w] -= d
                self.graph[w][v] += d
                return d
        return 0
    
    def max_flow(self):
        INF = 10**18
        flow = 0
        while True:
            self.bfs()
            if self.level[self.sink] == 0:
                break
            self.itr = [iter(e.items()) for e in self.graph]
            while True:
                f = self.dfs(self.source,INF)
                if f == 0:
                    break
                flow += f
        return flow

answer = Dinic(graph=graph,V=list(range(H+W+2)),source=0,sink=H+W+1).max_flow()
if answer >= INF:
    answer = -1
print(answer)

Measured memory_bytes: 4724
#include <bits/stdc++.h>
#ifdef BUG
    #include "debug.hpp"
#else
    #define DEBUG(var)
#endif

using namespace std;
template< class T1, class T2 > inline istream &
operator>>( istream & fin, pair< T1, T2 > & pr )
{ fin >> pr.first >> pr.second; return fin; }
template< class T0, class T1, class T2 > inline istream &
operator>>( istream & fin, tuple< T0, T1, T2 > & t )
{ fin >> get<0>(t) >> get<1>(t) >> get<2>(t); return fin; }
template< class T > inline istream &
operator>>( istream & fin, vector< T > & a ) {
for(auto & u: a) fin >> u; return fin; }
template<class T, size_t n> inline istream &
operator>>( istream & fin, array<T, n> & a ) {
for(auto & u: a) fin >> u; return fin; }
template<class FwdIter> inline auto
dump(FwdIter first, FwdIter last, const char * dlm = " ") -> void {
typedef typename iterator_traits<FwdIter>::value_type value_type;
copy(first, last, ostream_iterator<value_type>(cout, dlm)); }
template<typename T> vector<T> & operator--(vector<T> & a)
{ for(auto & i: a) --i; return a; }
/* @@@ ----------------------------------- */



int main(const int argc, char * argv [])
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  vector<int64_t> a(3);
  cin >> a;

  for(size_t i = 0; ; ++i)
  {
    if((a[0] & 1) || (a[1] & 1) || (a[2] & 1))
    {
      cout << i;
      return 0;
    }
    if(a[0] == a[1] && a[0] == a[2])
    {
      cout << -1;
      return 0;
    }

    a = vector<int64_t>({(a[1] + a[2]) / 2, (a[0] + a[2]) / 2, (a[0] + a[1]) / 2});
    DEBUG(a);
  }

  cout << -1;

  return EXIT_SUCCESS;
}



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner stdIn = new Scanner(System.in);
		int K = stdIn.nextInt();
		int ans = -1;
		int amari = 7 % K;
		
		for(int i = 1; i <= K; i ++) {
			if(amari == 0) {
				ans = i;
				break;
			}else {
				amari = (amari * 10 + 7) % K;
			}
		}
		
		System.out.println(ans);
	}
}

Measured memory_bytes: 35724
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for(int i=0;i<n;i++)
#define MOD 1000000007
typedef long long ll;
template <class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}else{return 0;}}
template <class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}else{return 0;}}
template <class T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template <class T> inline T LCM(T a,T b){return a*b/GCD(a,b);}


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

  int dp[3001][3001];
  
  for(int i=1;i<s.size()+1;i++){
    for(int j=1;j<t.size()+1;j++){
      dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
      if(s[i-1]==t[j-1]){
        if(dp[i-1][j-1]+1>dp[i][j]){
          dp[i][j]=dp[i-1][j-1]+1;
        }
      }
    }
  }
  string ans="";
  int ss=s.size(),tt=t.size();
  while(ss && tt){
    if(s[ss-1]==t[tt-1]){
      
      ans=s[ss-1]+ans;
      ss--;tt--;
    }else{
      if(dp[ss-1][tt]>dp[ss][tt-1]){
        ss--;
      }else{
        tt--;
      }
    }
  }
  cout << ans << endl;
  
}


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

#define ll long long
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define debug(x) cerr<<#x<<": "<<x<<'\n'

using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

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

template<class T=int>
T in(){T x;cin>>x;return (x);}
template<class T>
void print(T& x){cout<<x<<'\n';}

const int MOD =(int)1e9+7;
const int MAX =510000;

ll fac[MAX],finv[MAX],inv[MAX];
void COMint(){
    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;
    }
}
ll COM(int n,int k){
    if(n<k) return 0;
    if(n<0||k<0)return 0;
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}

ll gcd(ll a,ll b){
    if(b==0)return a;
    if(a>b){
        swap(a,b);
    }
    return gcd(a,b%a);
}
ll lcm(ll a,ll b){
    ll g;g=gcd(a,b);
    return a*b/g;
}
bool is_753(ll n){
    int d;
    d=to_string(n).size();
    bool flg_7;flg_7=false;
    bool flg_5;flg_5=false;
    bool flg_3;flg_3=false;
    REP(i,d){
        if(to_string(n)[i]-'0'==7){
            flg_7=true;
        }else if(to_string(n)[i]-'0'==5){
            flg_5=true;
        }else if(to_string(n)[i]-'0'==3){
            flg_3=true;
        }else{
            return false;
        }
    }
    if(flg_3&&flg_5&&flg_7){
        return true;
    }else{
        return false;
    }
}
int ans;
void dfs(ll k,ll N){
    if(k<=N){
        if(is_753(k)){
            ans++;
        }
        dfs(k*10+7,N);
        dfs(k*10+5,N);
        dfs(k*10+3,N);
    }
}
int main() {
    //COMint();
    ll N=in();
    ans=0;
    dfs(0,N);
    print(ans);
}

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

#define fi first
#define se second
#define FO(x, n) for (int x = 0; x < n; ++x)
#define FOR(x, a, b) for (int x = a; x < b; ++x)
#define RFO(x, n) for (int x = n - 1; x >= 0; --x)
#define RFOR(x, a, b) for (int x = b - 1; x >= a; --x)
#define FOR_ITER(x, a) for(auto x = a.begin(); x != a.end(); ++x)



using namespace std;
typedef unsigned char byte;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<string, string> pss;
typedef pair<ll, ll> pll;
inline bool feq(const double& a, const double& b) { return fabs(a - b) < 1e-10; }

using namespace std;


int main(){
//    int n, l;
//    cin >> n >> k;
//    vector<bool> dislike(10, false);
//
//    FOR(i, 0, k) {
//        int t;
//        cin >> t;
//        dislike[t] = true;
//    }

    char a, b, c;
    cin >> a ;//>> b >> c;

    cout << (a=='a'||a=='e' ||a=='i'||a=='o'||a=='u'? "vowel":"consonant") << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h> 
using namespace std; 
typedef long long ll;
int main(){
	ll a,b,n,x;
	cin>>a>>b>>n;
	if(n<b)cout<<a*n/b-a*(n/b);
	else x=n/b*b-1,cout<<a*x/b-a*(x/b);
	return 0;
}

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

struct Node{
  Node () :   //constracter
    parent (-1),
    id(-1),
    depth(0)
  {}

  int id;
  int depth;
  int parent;
  std::vector<Node*>children; //stack,pointa
};

int FindRoot(Node* nodes, int n){
  for(int i=0; i<n; i++){
    if(nodes[i].parent == -1){
      return i;
    }
  }
  return n-1;
}

void ComputeDepth(Node*nodes, int idx, int depth){
  nodes[idx].depth = depth;
  for(int i=0; i<nodes[idx].children.size(); i++){
    ComputeDepth(nodes, nodes[idx].children[i]->id, depth+1);
  }
}

int main(){
  //input
  int n;
  std::cin >> n;
  Node nodes[n];
  for(int i=0; i<n; ++i){
    int id, num_children;
    std::cin >> id >> num_children;
    nodes[id].id = id;
    for(int j=0; j<num_children; ++j){
      int c;
      std::cin >> c;
      nodes[id].children.push_back(&nodes[c]);//pointa
      nodes[c].parent = id;
    }
  }

  //compute depth
  int root = FindRoot(nodes, n);
  ComputeDepth(nodes, root, 0);

  for(int i=0; i<n; i++){
    std::cout << "node " << nodes[i].id;
    std::cout << ": parent = " << nodes[i].parent;
    std::cout << ", depth = " << nodes[i].depth << ", ";

    if(nodes[i]. parent == -1){ std::cout << "root, ["; }
    else if(nodes[i].children.size() != 0){ std::cout << "internal node, ["; }
    else { std::cout <<"leaf, ["; }

    for(int j=0; j<nodes[i].children.size(); j++){
      std::cout <<nodes[i].children[j]->id;
      if(j != nodes[i].children.size() -1 ){
        std::cout << ", ";
      }
    }
    std::cout << "]" <<std::endl;
  }
  return 0;
}



Measured memory_bytes: 8232
#include<iostream>

int main(){
    int a[5],i,j,n;
    
    for(i=0;i<5;i++){
        std::cin>>a[i];
         }
    for(i=0;i<5;i++){
        for(j=i+1;j<5;j++){
            if(a[i]<a[j]){
            n=a[i];
            a[i]=a[j];
            a[j]=n;
            	     }
                 }
            }
            
    for(i=0;i<4;i++){
    std::cout<<a[i]<<" ";
    }
    std::cout<<a[4]<<std::endl;
                
return 0;
}   

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#include <numeric>
#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c).begin(), (c).end(), greater<int>())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG true
#define LL long long
#define Num 1000000007
// sort(a.begin(), a.end(), std::greater<int>());
using namespace std;

struct data{
    int y,m,d;
};

int main(){
    int n;
    cin>>n;
    data start;
    start.y=1000;
    start.m=1;
    start.d=1;
    vector<data> hoge;
    rep(i,n){
        data a;
        cin>>a.y>>a.m>>a.d;
        hoge.push_back(a);
    }
    rep(i,hoge.size()){
        data a;
        int ans=0;
        a.y=hoge[i].y-1;
        a.m=hoge[i].m-1;
        a.d=hoge[i].d-1;
        ans+=a.y/3*20*10;
        ans+=(a.y-a.y/3)*(19*5+20*5);
        if(hoge[i].y%3==0){
            ans+=a.m*20;
            
        }
        else{
            ans+=a.m/2*19;
            ans+=(a.m-a.m/2)*20;
        }
        ans+=a.d;
        cout<<196470-ans<<endl;
    }
    return 0;
}


Measured memory_bytes: 3004
#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define WHATIS(x) cout << #x << " is " << x << endl;
#define ERROR(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x

using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<II, ll> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cout << *it << " = " << a << endl;
    err(++it, args...);
}

const ll MODBASE = 1000000007LL;
const int MAXN = 2010;
const int MAXM = 35;
const int MAXK = 510;
const int MAXQ = 200010;

int n;
ll dp[55][2];
string s[2];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n;
    cin >> s[0] >> s[1];
    s[0] = " " + s[0];
    s[1] = " " + s[1];
    dp[0][0] = 1;
    FOR(i,1,n) {
        if (s[0][i] == s[1][i])  {
            if (i == 1) dp[i][0] = 3;
            else {
                dp[i][0] = dp[i-1][0] * 2 % MODBASE;
                dp[i][0] = (dp[i][0] + dp[i-1][1]) % MODBASE;
            }
            dp[i][1] = 0;
        }
        else {
            if (s[0][i] == s[0][i-1]) {
                dp[i][0] = 0;
                if (i == 2) dp[i][1] = 6;
                else {
                    dp[i][1] = dp[i-2][0] * 2 % MODBASE;
                    dp[i][1] = (dp[i][1] + dp[i-2][1] * 3 % MODBASE) % MODBASE;
                }
            }
        }
        //cout << dp[i][0] << ' ' << dp[i][1] << endl;
    }
    cout << (dp[n][0] + dp[n][1]) % MODBASE;
    return 0;
}

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

bool IsReversible(string s) {
    string r = s;
    reverse(r.begin(), r.end());
    return s == r;
}

int main() {
    string S;
    cin >> S;
    int N = S.size();
    string S_half1 = S.substr(0, (N-1)/2);
    string S_half2 = S.substr((N+1)/2, N-1);
    if(IsReversible(S) && IsReversible(S_half1) && IsReversible(S_half2))
        cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define int long long
using P = pair<int,int>;
//#########################################
const int INF = 1e18;

signed main(){
	int n,k;cin >> n >> k;
	vector<int> p(n),c(n);
	rep(i,n){
		cin >> p[i];
		p[i]--;
	}
	rep(i,n)cin >> c[i];
	int ret = -INF;
	rep(a,n){
		int tmp = 0;
		int len = 0;
		int round = 0;
		for(int b = a; len == 0||b != a;b = p[b],len++)round += c[b];
		for(int b = a,move = 1;move ==1 || b != a ;b = p[b],move++){
			// a--b
			tmp += c[b];
			int cur = tmp + max(0ll,max(0ll,((k-move))/len)*round);	
			if(move <= k)ret = max(ret,cur);
			// trace(a,b,cur,len,round);
			// int rest = max(0ll,k-move);
			// if(rest){
			// 	rest/= len;
			// 	rest *= round;
			// }
			// int cur = tmp + rest;
			
		}

	
	}
	cout << ret << endl;

	return 0;
}

Measured memory_bytes: 3696
from collections import*
e=eval
I=9**9
(h,w),(s,t),(f,g)=e('map(int,input().split()),'*3)
m=e('input(),'*h)
d=e('[I]*w,'*h)
q=deque([(s-1,t-1,1)])
while q:
 y,x,c=q.popleft()
 if d[y][x]>c:
  d[y][x]=c
  for i in range(y-2,y+3):
   for j in range(x-2,x+3):
    if h>i>-1<j<w<I==d[i][j]!=m[i][j]>'#':
     if abs(y-i)+abs(x-j)<2:q.appendleft((i,j,c))
     else:q.append((i,j,c+1))
print(d[f-1][g-1]%I-1)

Measured memory_bytes: 226812
#include<bits/stdc++.h>
#define maxn 100010
using namespace std;
int n;
long long ans,x;
long long a[maxn];
int main()
{
    scanf("%d%lld",&n,&x);
    for(int i=1;i<=n;i++){scanf("%lld",&a[i]);ans+=a[i];}
    if(x==0){
    	printf("%lld",ans);
    	return 0;
	}
	ans=0;
    if(a[1]>x){
        ans += a[1]-x;
        a[1]=x;
    }
    for(int i=2;i<=n;i++)
     if(a[i-1] + a[i] >x)ans += a[i-1] +a[i] -x,a[i]=x-a[i-1];
    printf("%lld",ans);
   return 0;
}

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

namespace Contest.cs
{
	class Program
	{
		static void Main(string[] args)
		{
			ReadStr();
			var S = ReadInt();
			ReadStr();
			var T = ReadInt();
			var Con = new int[S.Length + T.Length + 1];
			int ans = 0;
			T.CopyTo(Con, 0);
			S.CopyTo(Con, T.Length);
			for(var i = 0;i < T.Length; i++)
			{
				Con[Con.Length - 1] = Con[i];
				var target = Con[i];
				int j = T.Length;
				while (true)
				{
					if (Con[j] == target) break;
					j++;
				}
				if (j != Con.Length - 1) ans++;
			}
			Console.WriteLine(ans);
		}

		static string[] ReadStr()
		{
			return Console.ReadLine().Split(' ').ToArray();

		}

		static int[] ReadInt()
		{
			return Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
		}
	}
}


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

const long long mod = 998244353;
const int maxn = 3e5 + 100;
long long fac[maxn],inv[maxn];

long long q_pow(long long x,long long n)
{
    long long res = 1;
    while(n > 0)
    {
        if(n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

void inti()
{
    int i;
    fac[0] = 1;
    for(i = 1;i < maxn;i++)
    {
        fac[i] = (fac[i - 1] * i) % mod;
    }
    inv[maxn - 1] = q_pow(fac[maxn - 1],mod - 2);
    for(i = maxn - 2;i >= 0;i--)
    {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
}

long long C(int n,int m)
{
    if(n < m) return 0;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}

int main()
{
    long long n,a,b,k,A,B,ans;
    inti();
    scanf("%lld%lld%lld%lld",&n,&A,&B,&k);
    ans = 0;
    for(a = 0; a <= n; a++)
    {
        if(k - A * a < 0) continue;
        if((k - A * a) % B) continue;
        b = (k - A * a) / B;
        if(b > n) continue;
        ans = (ans + C(n,a) * C(n,b) + mod) % mod;
    }
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PLL = pair<LL,LL>;
#define MP make_pair


void cnt(PLL cp, vector<LL>& res, set<PLL>& ps){
  int c = 0;
  for(int dx=-1;dx<=1;++dx)
	for(int dy=-1;dy<=1;++dy)
	  if(ps.count(MP(cp.first+dx, cp.second+dy)))
		++c;
  res[c]++;
}

int main(){
  LL H, W, N; cin >> H >> W >> N;
  set<PLL> ps;
  vector<PLL> evs;
  for(int i=0;i<N;++i){
	PLL p; cin >> p.second >> p.first;
	ps.insert(p);
	for(LL x=max(1LL,p.first-2);x<=min(W,p.first+2);++x)
	  for(LL y=max(1LL,p.second-2);y<=min(H,p.second+2);++y)
		evs.emplace_back(x, y);
  }
  sort(begin(evs), end(evs));
  evs.erase(unique(begin(evs), end(evs)), end(evs));

  vector<LL> ans(10, 0);
  for(auto&& p: evs){
	if(p.first-1 <= 0 || p.first+1 > W) continue;
	if(p.second-1 <= 0 || p.second+1 > H) continue;
	cnt(p, ans, ps);
  }
  LL sum = 0;
  for(int i=0;i<10;++i)
	sum += ans[i];
  ans[0] += (H-2)*(W-2) - sum;

  for(int i=0;i<10;++i)
	cout << ans[i] << endl;

  return 0;
}


Measured memory_bytes: 71136
N, x = list(map(int,input().split()))
a = list(map(int,input().split()))
result = 0

for i in range(N-1):
  n = a[i] + a[i+1] - x
  if n > 0:
    result += n
    a[i+1] -= n
    if a[i+1] < 0:
      a[i+1] = 0

print(result)

Measured memory_bytes: 14132
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
const int maxn = 2e6+100;
using namespace std;
typedef long long ll;
ll a[maxn];
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    int flag=0;
    for(int i=0;i<n;i++){
    	cin>>a[i];
    	if(a[i]==0){
    		flag=1;
		}
	}
	if(flag){
		cout<<0;
		return 0;
	}
	ll ans=1;
	for(int i=0;i<n;i++){
		ans*=a[i];
	}
	if(ans>1000000000000000000){
		cout<<-1;
		return 0;
	}
    ans=1;
	for(int i=0;i<n;i++){
		int b=0,c=0;
		ll cnt=ans;
		while(cnt>=10){
			cnt/=10;
			b++;
		}
		cnt*=a[i];
		while(cnt>=10){
			cnt/=10;
			c++;
		}
		if(b+c>18||(b+c==18&&cnt!=1)){
			cout<<-1;
			return 0;
		}
		else ans=ans*a[i];
		if(ans>1000000000000000000){
			cout<<-1;
			return 0;
		}
	}
	cout<<ans;
	return 0;
}

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

int main()
{
	int h,w,k;
	cin >> h >> w >> k;

	vector<vector<char>> c(h,vector<char>(w));
	for (int i=0;i<h;++i)
	{
		for (int j=0;j<w;++j)
		{
			cin >> c[i][j];
		}
	}

	int hmask_max=1<<h;
	int wmask_max=1<<w;
	int count=0;
	for (int hmask=0;hmask<hmask_max;++hmask)
	{
		for (int wmask=0;wmask<wmask_max;++wmask)
		{
			int b=0;
			for (int i=0;i<h;++i)
			{
				if ((hmask&(1<<i))!=0)
				{
					continue;
				}
				for (int j=0;j<w;++j)
				{
					if ((wmask&(1<<j))!=0)
					{
						continue;
					}
					if (c[i][j]=='#')
					{
						++b;
					}
				}
			}
			if (b==k)
			{
				++count;
			}
		}
	}
	cout << count << endl;
}








Measured memory_bytes: 3628