akhauriyash/Code-Regression huggingface dataset:
N,K = map(int,input().split())
A = list(map(int, input().split()))


#一回あたりのループを計算（何回で戻ってくるか）
#ループの箇所を見つける
trace = [0]*N
loop_start = 0
loop_before = 0
cnt = 0
all_cnt = 0

if K > N:
    loop = 0
    now = 0
    while(1):
        # print(trace)
        trace[now] += 1
        if trace[now] == 3:
            break
        if trace[now] == 2:
            cnt += 1
            loop += 1 
            if cnt == 1: 
                loop_start = now
                loop_before = all_cnt
        now = A[now]-1
        all_cnt += 1

    loop_before = loop_before - loop 

    # print(loop)
    # print(loop_start)
    # print(loop_before)
    # print(loop)
    min_K = (K-1-loop_before) % loop
    # print(min_K)
    # print(loop_before)
    now = 0
    for i in range(loop_before):
        now = A[now]-1
    for i in range(min_K):
        now = A[now]-1
    print(A[now])

if K <= N:
    now = 0
    for i in range(K-1):
        now = A[now]-1
    print(A[now])


# print(K % 3)

# print(now+1)




    

Measured memory_bytes: 32392
#include <bits/stdc++.h>
using namespace std;
vector<int> a[100001];
long long f[100001][2];
long long ff(int x,int prev,int color)
{
	int ans=1,flag=1,i;
	if(f[x][color]!=-1)
		return f[x][color];
	for(i=0;i<a[x].size();i++)
	{
		if(a[x][i]==prev)
			continue;
		flag=0;
		if(color==1)
			ans=ans*ff(a[x][i],x,0)%1000000007;
		else
			ans=ans*(ff(a[x][i],x,1)%1000000007+ff(a[x][i],x,0)%1000000007)%1000000007;
	}
	f[x][color]=ans;
	if(flag)
		f[x][color]=1;
	return f[x][color];
}
int main()
{
	int n,i,u,v;
	scanf("%d",&n);
	for(i=0;i<n-1;i++)
	{
		scanf("%d %d",&u, &v);
		a[u].push_back(v);
		a[v].push_back(u);
	}
	for(i=0;i<100001;i++)
		f[i][1]=f[i][0]=-1;
	printf("%d",(ff(1,-1,0)%1000000007+ff(1,-1,1)%1000000007)%1000000007);
	return 0;
}

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

void print( const vector<pair<int, int>>& a, char sep = ' ' ) {
	size_t n = a.size();

	for( size_t i = 0; i < n; ++i ) {
		cout << a.at( i ).first;

		if( i < n-1 ) { cout << sep; }
	}

	cout << endl;
}

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

	int N, Q;
	cin >> N >> Q;

	vector<pair<int, int>> tr( N, {0, -1} );
	for( int i = 0; i < N-1; ++i ) {
		int a, b;
		cin >> a >> b;

		tr.at( b-1 ).second = a-1;
	}

	for( int i = 0; i < Q; ++i ) {
		int p, x;
		cin >> p >> x;

		tr.at( p-1 ).first += x;
	}

	for( int i = 1; i < N; ++i ) {
		tr.at(i).first += tr.at( tr.at( i ).second ).first;
	}

	print( tr );
}


Measured memory_bytes: 3968
//Author:- Kishan Panchal


#include<bits/stdc++.h>
using namespace std;
    #define ll long long 
 
    #define f first
    #define s second
    #define pb push_back
    #define FAST ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);srand(time(NULL));
    #define all(v) v.begin(),v.end()
    #define M 1000000007
    #define pii pair<int,int>
    #define pll pair<ll,ll>
    #define vll vector<ll>
    #define For(i,a,b) for(ll i=a;i<b;i++)

class component{
    public:
    	ll min3(ll a,ll b,ll c)
		{
			return min(a,min(c,b));
		}
		ll mod(ll a,ll n)
		{
			return (a%n+n)%n;
		}
		template <class T>
		void print(T a)
		{
			
			//cout << "Ans: ";
			cout << a << endl;
		}
		//friend class Ans;
};


class Ans : component {
	public:
	    ll n;
		ll ans;
		Ans()
		{
			ans=0;
		}
		void solve()
		{
            
          string s;
          cin>>s;
          int n=0;
          For (i,0,s.size())
          {
            n+=s[i]-'0';
          }
          if (n%9==0)
          {
            cout << "Yes" <<endl;
          }
          else
          {
            cout << "No" <<endl;
          }
            
          
           
		}
		
};



    int main()
    {
    	int t;
    	//cin>>t;
         t=1;
    	
    	for (int i=1;i<=t;i++)
    	{
    	     Ans a;   
             //cout << "Case #"<<i<<": ";/// stack memory 
    		a.solve();
    		//delete(&a);
		}
	}


Measured memory_bytes: 3736
#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <bitset>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define Rep(i,a) for(int i = 0; i < (a); i++)
#define rep(i,a,b) for(int i = (a); i <= (b); i++)//(a)!
#define dep(i,a,b) for(int i = (a); i >= (b); i--)
#define ab(a) ((a) > 0 ? (a) : -(a))
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back(a)
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
int main() {
	int n; scanf("%d",&n);
	LL sa = 1, sb = 1;
	rep(i,1,n) {
		int a, b; scanf("%d%d",&a,&b);
		LL ta = (sa + (a - (sa % a == 0 ? a : sa % a))) / a, tb = (sb + (b - (sb % b == 0 ? b : sb % b)) ) / b;
		LL t = max(ta, tb);
		sa = t * a, sb = t * b;
	}	
	cout <<sa + sb<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
using namespace std;
int main(){
	int i,d,s=0;
	string s1;
	getline(cin,s1);
	for(i=0;i<s1.length();i++){
		if(s1[i]=='C')	
		{
			s=s+1;
			d=i;
			break;
		}
	}
	for(i=d;i<s1.length();i++){
		if(s1[i]=='F')	
		{
			s=s+1;
			break;
		}
	}
	if(s==2){
		cout<<"Yes"<<endl;
	}
	else
	{
		cout<<"No"<<endl;
	}
	return 0;
}

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

int main() {
	int N, l, r;
	cin >> N;
	int sum = 0;
	for (int i = 0;i < N;i ++) {
		cin >> l >> r;
		sum += r - l + 1;
	}
	cout << sum;
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり

まず、l_iからr_iまでに座る人数はl_i-r_i+1人である
端がある時の植木算を間違えないようにね、ちゃんと+1するように
で、同じ席に複数の人が座ることがないみたいなので、普通に上の計算式で総和すれば良い
*/

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

    void solve(set<string> &s, vector<int> &x)
    {
        char id = 'a';
        int pp = -2;
        vector<char> mp(30, 0);
        for (int i = 0; i < x.size(); i++)
        {
            if (x[i] == -1)
            {
                x[i] = pp--;
                mp[x[i] + 10] = id++;
                continue;
            }
            if ('a' <= mp[x[i] + 10] && mp[x[i] + 10] <= 'z') continue;
            else mp[x[i] + 10] = id++;
        }
        string t = "";
        for (int i = 0; i < x.size(); i++) t += mp[x[i] + 10];
        s.insert(t);
    }

    void dfs(set<string> &s, vector<int> &x, int n)
    {
        int cnt = 0;
        for (int i = 0; i < x.size(); i++)
        {
            cnt += x[i];
            if (x[i] == 0)
            {
                if (i == 0)
                {
                    for (int j = 1; j < n; j++)
                    {
                        if (j * x.size() > n) break;
                        x[i] = j;
                        dfs(s, x, n);
                    }
                    x[i] = 0;
                    return ;
                }
                for (int j = x[i - 1]; j < n; j++)
                {
                    if (cnt + j * (x.size() - i) > n) break;
                    x[i] = j;
                    dfs(s, x, n);
                }
                x[i] = 0;
                return ;
            }
        }
        if (cnt != n) return ;
        vector<int> y;
        for (int i = 0; i < x.size(); i++)
        {
            if (x[i] == 1)
            {
                y.push_back(-1);
                continue;
            }
            for (int j = 0; j < x[i]; j++) y.push_back(i);
        }
        sort(y.begin(), y.end());
        do {
            solve(s, y);
        } while (next_permutation(y.begin(), y.end()));
    }

    int main()
    {
        int n;
        cin >> n;
        set<string> s;
        string t = "";
        for (int i = 0; i < n; i++) t += "a";
        s.insert(t);
        t = "";
        for (int i = 0; i < n; i++) t += ('a' + i);
        s.insert(t);
        for (int i = 2; i <= n - 1; i++)
        {
            vector<int> x(i, 0);
            dfs(s, x, n);
        }
        auto ptr = s.begin();
        while (ptr != s.end()) cout << *(ptr++) << endl;
    }

Measured memory_bytes: 14208
#include<bits/stdc++.h>
#include<iomanip>
#include<numeric>

using namespace std;
using ll = long long;
constexpr int mo = 1e9+7;
constexpr int mo2 = 998244353;
constexpr int  mod = mo;
constexpr int inf = 1<<30;
int main(){
    string s,t;
    cin>>s>>t;
    map<char,vector<int>> m;
    for(int i=0;i<(int)s.size();++i){
        m[s[i]].push_back(i);
    }
    for(auto c : t){
        if(m.count(c) == 0){
            cout << -1 << endl;
            return 0;
        }
    }
    ll ret = 0ll;
    int n = (int)t.size();
    int slen = (int)s.size();
    ret += m[t[0]][0]+1;
    int cur = m[t[0]][0];
    for(int i=1;i<n;++i){
        auto it = upper_bound(m[t[i]].begin(),m[t[i]].end(),cur);
        if(it == m[t[i]].end()){
            ret += (slen-1)-cur+(m[t[i]][0]+1);
            cur = m[t[i]][0];
            continue;
        }
        ret += *it - cur;
        cur = *it;
    }
    cout << ret << endl;
    
    return 0;
}



Measured memory_bytes: 1216
from collections import deque
N, M = map(int, input().split())
G = dict()
for i in range(N):
    G[i+1] = []
color_list = [0] * N

close = False

for _ in range(M):
    A, B = map(int, input().split())
    G[A].append(B)
    G[B].append(A)
    

# color
color_list[0] = 1
for q in G[1]:
    color_list[q-1] = -1

que = deque(G[1])

while len(que) > 0:
    p = que.popleft()
    for q in G[p]:
        if color_list[q-1] == 0:
            color_list[q-1] = - color_list[p-1]
            que.append(q)
        elif color_list[q-1] == color_list[p-1]:
            close = True
            break

if close == True:
    print(N*(N-1) // 2 - M)
else:
    print(color_list.count(1)*color_list.count(-1) - M)

Measured memory_bytes: 30948
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<bitset>
#include<math.h>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int N=100000+100;
const db pi=acos(-1.0);
#define lowbit(x) ((x)&(-x))
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define go(u,i) for (register int i=head[u],v=sq[i].to;i;i=sq[i].nxt,v=sq[i].to)
#define fir first
#define sec second
#define mkp make_pair
#define pb push_back
#define maxd 998244353
#define eps 1e-8
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

inline ll readll()
{
    ll x=0;int f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

map<string,int> f,g;

int calcf(string);int calcg(string);

int calcg(string s)
{
    if (g[s]) return g[s];
    int n=s.size(),ans=0;
    rep(d,1,n-1)
    {
        if (n%d) continue;
        string t="";
        rep(i,0,d-1)
        {
            int ch=1;
            for (int j=i;j<n;j+=d) ch&=(s[j]-'0');
            t=t+(char)(ch+'0');
        }
        ans=(ans+calcf(t))%maxd;
    }
    g[s]=ans;return ans;
}

int calcf(string s)
{
    if (f[s]) return f[s];
    int n=s.size(),ans=0;
    rep(i,1,n)
        ans=(ans+1ll*calcg(s.substr(0,i))*calcf(s.substr(i,n))%maxd)%maxd;
    f[s]=ans;return ans;
}

int main()
{
    string s;
    cin >> s;
    f[""]=1;
    g[""]=1;g["0"]=1;g["1"]=2;
    printf("%d",calcf(s));
    return 0;
}

Measured memory_bytes: 12928
package main

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

func main() {
  sc := bufio.NewScanner(os.Stdin)
  sc.Scan()
  strArr := strings.Split(sc.Text(), " ")
  A, _ := strconv.Atoi(strArr[0])
  B, _ := strconv.Atoi(strArr[1])
  if -1 <= A-B && A-B <= 1 {
    fmt.Println("Brown")
  } else {
    fmt.Println("Alice")
  }
}


Measured memory_bytes: 640
<?php
    function S($n){
        $r = 0;
        $m = $n;
        while($m > 0){
            $r += $m % 10;
            $m /= 10;
        }
        return $r;
    }
    fscanf(STDIN, "%d", $n);
    if($n % S($n) ==0){
        echo("Yes\n");
    }else{
        echo ("No\n");
    }
?>

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

int main(){
    int a, b, c, d, e;
    int k;

    cin >> a >> b >> c >> d >> e >> k;

    if((e - a) > k){
        cout << ":(" << endl;
    }else{
        cout << "Yay!" << endl;
    }

    return 0;
}



Measured memory_bytes: 256
# -*- coding: utf-8 -*-

from sys import stdin
    
def calc(ryokans):
    ans = 0
    _max = -1

    for x in ryokans:
        if x >= _max:
            ans += 1
            _max = x

    return ans

def main():
    n = stdin.readline().rstrip()
    ryokans = [int(x) for x in stdin.readline().rstrip().split()]
    ans = calc(ryokans)
    print(ans)
    
if __name__=='__main__':
    main()

Measured memory_bytes: 3060
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <fstream>

using namespace std;


ifstream in("input.txt");
ofstream out("output.txt");


template<typename T1, typename T2>inline void chkmin(T1& x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1& x, T2 y) { if (x < y) x = y; }
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define PI 3.14159265358979323846

typedef unsigned long long ll;

const int maxn = 3e5 + 228;

int n, k;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    int cnt = 0;
    while (n > 0) {
        n /= k;
        cnt++;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
package main

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

var (
        qset []int
        nline int
)

func main(){
        fmt.Scan(&nline)

        qset= make([]int, nline)

        for i := 0; i < nline; i++ {
                qset[i] = i
        }

        // exec Unite set, manipulate query set
        execUniteData()
}

func execUniteData(){
        scanner := bufio.NewScanner(os.Stdin)

        for scanner.Scan(){
                lineArgs := strings.Fields(scanner.Text())
                if len(lineArgs) == 3 {
                        setquery(lineArgs)
                }
        }
}

func setquery(args []string){
        w, _ := strconv.Atoi(args[0])
        x, _ := strconv.Atoi(args[1])
        y, _ := strconv.Atoi(args[2])
        x,y = numCompare(qset[x],qset[y])

        if w == 0 { // manipulate query set
                for i:=0;i<nline;i++ {
                        if qset[i] == y {
                                qset[i] = x
                        }
                }
        }else{ // print
                if qset[x]==qset[y]{
                        fmt.Println(1)
                }else{
                        fmt.Println(0)
                }
        }
}

func numCompare(a int, b int)(int,int){
        if a>b {
                return b, a
        }else{
                return a, b
        }
}


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

#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define ll long long
#define ii pair<int,int>
#define vi vector<int>
#define vll vector<ll>
#define vii vector<ii>

using namespace std;

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,k;
	ll ans=0;
	cin>>n>>k;
	vi vs(n);
	for(int &x:vs) cin>>x;
	sort(vs.rbegin(),vs.rend());
	for(int i=0;i<n;++i){
		if(k>0)
			--k;
		else
			ans+=vs[i];
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <math.h>
int main(void)
{
    int a,b,C;
    double rad;
    long double S,L,h,c;
    double PI=acos(-1);
    
    scanf("%d %d %d",&a,&b,&C);
    
    rad=C*PI/180;
    
    S=a*b*sin(rad)*0.5;
    c=sqrt(a*a+b*b-2*a*b*cos(rad));
    L=a+b+c;
    h=S*2/a;
    
    printf("%Lf\n%Lf\n%Lf\n",S,L,h);

    
    return 0;
}




Measured memory_bytes: 2076
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random,resource

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    x = LI()

    return 15 - sum(x)


print(main())




Measured memory_bytes: 10996
//To compile : type "$     g++ test.cpp -std=c++14 -I .    "
#include <atcoder/all>
#include <bits/stdc++.h>
//#include <chrono>
//#pragma GCC optimize("Ofast")
using namespace std;
using namespace atcoder;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,Q,K,A,B;
string S;
typedef pair<ll, ll> P;
const ll INF = (1LL<<60);

int main() {
	cin>>N>>Q;
	fenwick_tree<ll> fw(N);
	rep(i,N){
		cin>>A;
		fw.add(i, A);
	}
	rep(_, Q){
		int t, u, v;
		cin>>t>>u>>v;
		if(t == 0){
			fw.add(u, v);
		}else{
			cout<<fw.sum(u, v)<<endl;
		}
	}
}

Measured memory_bytes: 8224
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
    
using namespace std;    
typedef long long ll;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

int main(){

    string s;
    cin >> s;

    string t;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == '0') t.push_back('0');
        if(s[i] == '1') t.push_back('1');
        if(s[i] == 'B'){
            if(t.size() > 0){
                t.erase(t.end()-1);
            }
        }

    }
    cout << t << endl;
}


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

inline int read(){
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}

inline void write(int x){
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
}

inline void writeln(int x){
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
     puts("");
}

int main(){
    int x=read();
    writeln(360/(__gcd(x,360)));
    
    return 0;
}

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

int main () {
  map <string,int> memo;
  int N;
  cin >> N;
  for (int i = 0; i < N; i++){
    string s;
    cin >> s;
    memo[s] += 1;
  }
  int max = 0;
  for (auto p: memo) {
    auto v = p.second;
    if (max < v) max = v;
  }
  for (auto p: memo){
    auto v = p.second;
    auto k = p.first;
    if (max == v) cout << k << endl;
  }
}

Measured memory_bytes: 25216
#include <bits/stdc++.h>
using namespace std;
#define pi 2*asin(1.0)
 
int main() {

int N,K;
int Ans=0;
cin>>N>>K;

vector<int> p(N);

for(int i=0;i<N;i++){

cin>>p.at(i);

}

sort(p.begin(),p.end());

for(int i=0;i<K;i++){

Ans=Ans+p.at(i);

}
  cout<<Ans<<endl;
}

Measured memory_bytes: 3596
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<map>
using namespace std;

int main() {
	int a, b, c;
	while (cin>>a>>b>>c, a | b | c) {
		map<int, int>e;
		for (int d = 0; d < a; d++) {
			int f;
			cin >> f;
			e[20000-f]++;
		}
		auto i = e.end();
		i--;
		int g = 0;
		int p = 0, q = 0;
		for (auto h = e.begin();h!=i; h++) {
			g += (*h).second;
			if (g < b)continue;
			else if (g > c)break;
			auto j = h;
			j++;
			if ((*j).first - (*h).first >= p) { p = (*j).first - (*h).first; q = g; }
		}
		cout << q << endl;
	}
}

Measured memory_bytes: 3116
n, m = map(int, input().split())
edges = []
for i in range(m):
    a, b, c = map(int, input().split())
    a-=1; b-=1
    edges.append((a, b, -c))

dist = [float('inf')]*n
dist[0] = 0
for i in range(n-1):
    # n-1回ループすることで、到達できるすべての頂点の更新ができる
    for st, en , score in edges:
        if dist[st] == float('inf'): continue
        if dist[en] > dist[st] + score:
            dist[en] = dist[st] + score

negative = [False] * n

for loop in range(n):
    # n回目以降のループで更新された頂点は負閉路を含む
    # それをn回繰り返して更新された頂点は、負閉路の影響を受けている
    for e in edges:
        st, en, score = e
        if dist[st] == float('inf'): continue
        if dist[en] > dist[st] + score:
            dist[en] = dist[st] + score
            negative[en] = True
        if negative[st]:
            negative[en] = True

if negative[n-1]:
    print('inf')
else:
    print(-dist[n-1])

Measured memory_bytes: 9360
def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n=n0()
s=s2(n)

ac=0
tle=0
wa=0
re=0
for a in s:
    if a=="AC":
        ac+=1
    elif a=="TLE":
        tle+=1
    elif a=="WA":
        wa+=1
    else:
        re+=1
print(f"AC x {ac}")
print(f"WA x {wa}")
print(f"TLE x {tle}")
print(f"RE x {re}")

Measured memory_bytes: 16348
n=input()
n=str(n)

hon=['2','4','5','7','9']
pon=['0','1','6','8']
bon=['3']

for num in hon:
    if num==n[len(n)-1]:
        print("hon")

for num in pon:
    if num==n[len(n)-1]:
        print("pon")

for num in bon:
    if num==n[len(n)-1]:
        print("bon")


Measured memory_bytes: 9068
#include<stdio.h>
#include<math.h>
int main(){
    int N;
    int a[10];
    int i;
    int odd[10]={0};
    int serial=1;
    int total=0;
    scanf("%d",&N);
    for(i=0;i<N;i++){
        scanf("%d",&a[i]);
        if(a[i]%2!=0)
            odd[i]+=1;
        if ((a[i]+1)%2!=0)
            odd[i]+=1;
        if ((a[i]-1)%2!=0)
            odd[i]+=1;
    }
    for (i=0;i<N;i++){
        serial=serial*odd[i];
    }
    total = pow(3,N)-serial;
    printf("%d\n",total);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define rep(i, s, n) for (int i = s; i < n; i++)
#define rrep(i, s, n) for (int i = (n)-1; i >= (s); i--)
#define all(a) a.begin(),a.end()
const long long MOD = 1e9+7, INF = 1e18;
template<class T>inline bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}

int H,W;

int check(int si,int h,int sj,int w,vector<vector<int>>&v){
	int ma = -INF,mi = INF;
	rep(i,si,h+1){
		rep(j,sj,w+1){
			if(i==si||j==sj||i==h||j==w)chmin(mi,v[i][j]);
			else chmax(ma,v[i][j]);
		}
	}
	if(ma>=mi)return 0;
	int ret = 0;
	rep(i,si+1,h){
		rep(j,sj+1,w){
			ret += mi - v[i][j];
		}
	}
	return ret;
}

signed main(){
	vector<int>ans;
	while(cin>>H>>W,H||W){
		vector<vector<int>>v(H,vector<int>(W,0));
		rep(i,0,H){
			rep(j,0,W){
				cin>>v[i][j];
			}
		}
		int ma = 0;
		rep(i,0,H){
			rep(j,i+2,H){
				rep(k,0,W){
					rep(l,k+2,W){
						chmax(ma,check(i,j,k,l,v));
					}
				}
			}
		}
		ans.push_back(ma);
	}
	for(auto e:ans){
		cout<<e<<endl;
	}
}


Measured memory_bytes: 3076
#include <bits/stdc++.h>
#include <boost/numeric/ublas/lu.hpp>
#include <boost/numeric/ublas/matrix.hpp>
#include <boost/numeric/ublas/vector.hpp>
using namespace std;
using namespace boost::numeric;

void Main()
{
    /*
    a + b = x
    2a + 4b = y

    Ax=b

    A=[[1, 1], [2, 4]]
    b=[x, y]
    z=[a, b]
    */

    int x, y;
    cin >> x >> y;

    ublas::matrix<double> A(2,2);
    ublas::vector<double> b(2);
    A(0,0)=1; A(0,1)=1;
    A(1,0)=2; A(1,1)=4;
    b(0)=x; b(1)=y;
   
    ublas::permutation_matrix<> PM(A.size1());
    ublas::lu_factorize(A, PM);
    ublas::lu_substitute(A, PM, b);

    if(b(0)>=0 && b(1)>=0
        && abs(b(0)-round(b(0))) < 1e-5 
        && abs(b(1)-round(b(1))) < 1e-5){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

int main(int argc, char **argv)
{
    Main();
    return 0;
}


Measured memory_bytes: 3668
import java.util.*;
public class Main {
public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
  	int N = sc.nextInt();
  	int K = sc.nextInt();
  	String num = "";
  	while(N>0){
		num = num + N%K;
      	N = (int) N/K;
      	//System.out.println("N:" + N);
      	//System.out.println("num:" + num);
    }

	System.out.println(num.length());
}
}

Measured memory_bytes: 23124
use proconio::*;

fn main() {
    input!{
        n: usize,
        m: usize,
        k: usize,
        a: [usize; n],
        b: [usize; m],
    }

    let mut a_cnt = 0;
    let mut a_sum = 0;
    for aa in a.iter() {
        if a_sum + aa <= k {
            a_cnt += 1;
            a_sum += aa;
        }
        else {
            break;
        }
    }

    let mut ans = a_cnt;
    let mut b_sum = 0;
    for i in 0..b.len() {
        b_sum += b[i];
        if b_sum > k {
            break;
        }
        while b_sum + a_sum > k {
            a_sum -= a[a_cnt-1];
            a_cnt -= 1;
        }

        ans = ans.max(a_cnt + i + 1);
    }

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


Measured memory_bytes: 9344
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define REPL(i,m,n) for(ll i=(ll)(m); i<(ll)(n); i++)
#define repl(i,n) REPL(i,0,n)
#define all(v) v.begin(), v.end()
template<class t, class u>
ostream& operator<<(ostream& os, const pair<t, u>& p) {
  return os << "{" << p.first << ", " << p.second << "}";
}
template<class t> ostream& operator<<(ostream& os, const vector<t>& v) {
  os << "{";
  rep(i, v.size()) { if(i) os << ", "; os << v[i]; }
  return os << "}";
}
// template<class t> ostream& operator<<(ostream& os, const set<t>& se) {
//   os << "{";
//   auto itr = se.begin();
//   rep(i, se.size()) { if(i) os << ", "; os << *itr; itr++; }
//   return os << "}";
// }
// template<class t, class u>
// ostream& operator<<(ostream& os, const map<t, u>& mp) {
//   os << "{";
//   auto itr = mp.begin();
//   rep(i, mp.size()) { if(i) os << ", "; os << *itr; itr++; }
//   return os << "}";
// }
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main() {
  int N;
  cin >> N;
  vector<ll> A(N), B(N+1);
  ll sum = 0;
  rep(i, N) {
    cin >> A[i];
    B[i+1] = A[i] + B[i];
    sum += A[i];
  }
  ll mn = longinf;
  rep(i, N+1) {
    ll m = min(B[i], sum-B[i]);
    ll M = sum - m;
    if(M-m < mn) mn = M-m;
  }
  cout << mn << endl;
  return 0;
}



Measured memory_bytes: 3328
import java.util.*;
import java.io.*;
import java.awt.Point;
import java.math.BigInteger;

public class Main {

	public static void main(String[] args) throws Exception {
		FastIO sc = new FastIO(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		
		int N = sc.nextInt();
		
		double[] p = new double[N];
		for(int i =0; i < N; i++) p[i] = Double.parseDouble(sc.next());
		
		double dp[][] = new double[N+1][6005];
		dp[0][3002] = 1;
		
		for(int i = 0; i < N; i++) {
			for(int j = 1; j < 6004; j++) {
				dp[i+1][j+1] += dp[i][j]*p[i];
				dp[i+1][j-1] += dp[i][j]*(1-p[i]);
			}
		}
		
		double tot = 0;
		for(int i = 3003; i < 6005; i++) tot += dp[N][i];
		
		pw.println(tot);
		pw.close();

	}

	static class FastIO {

		//Is your Fast I/O being bad?

		InputStream dis;
		byte[] buffer = new byte[1 << 17];
		int pointer = 0;

		public FastIO(String fileName) throws Exception {
			dis = new FileInputStream(fileName);
		}

		public FastIO(InputStream is) throws Exception {
			dis = is;
		}

		int nextInt() throws Exception {
			int ret = 0;

			byte b;
			do {
				b = nextByte();
			} while (b <= ' ');
			boolean negative = false;
			if (b == '-') {
				negative = true;
				b = nextByte();
			}
			while (b >= '0' && b <= '9') {
				ret = 10 * ret + b - '0';
				b = nextByte();
			}

			return (negative) ? -ret : ret;
		}

		long nextLong() throws Exception {
			long ret = 0;

			byte b;
			do {
				b = nextByte();
			} while (b <= ' ');
			boolean negative = false;
			if (b == '-') {
				negative = true;
				b = nextByte();
			}
			while (b >= '0' && b <= '9') {
				ret = 10 * ret + b - '0';
				b = nextByte();
			}

			return (negative) ? -ret : ret;
		}

		byte nextByte() throws Exception {
			if (pointer == buffer.length) {
				dis.read(buffer, 0, buffer.length);
				pointer = 0;
			}
			return buffer[pointer++];
		}

		String next() throws Exception {
			StringBuffer ret = new StringBuffer();

			byte b;
			do {
				b = nextByte();
			} while (b <= ' ');
			while (b > ' ') {
				ret.appendCodePoint(b);
				b = nextByte();
			}

			return ret.toString();
		}

	}
}


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

constexpr long long MOD = 1'000'000'007;

class binomial_coefficients {
	long long MAX_VAL;
	vector<long long> fac, mmi;

public:

	binomial_coefficients(){
	}
	
	binomial_coefficients(long long num){
		init(num);
	}
	
	~binomial_coefficients(){
		
	}
	
	void init(long long num){
		MAX_VAL = num+1; 
		fac.resize(MAX_VAL);
		mmi.resize(MAX_VAL);
		
		factorial_mod();
		modular_multiplicatibe_inverse();
	}
	
	void factorial_mod(){
		 fac[0] = 1;
		for(long long i = 1; i < MAX_VAL; fac[i] %= MOD, i++)
			fac[i] = fac[i - 1] * (i % MOD);
	}
	
	long long power(long long x, long long n){
		long long ans = 1;
		for(;n;n >>= 1, x *= x, ans %= MOD, x %= MOD)
			if(n&1)ans*=x;
		return ans % MOD;
	}
	
	void exgcd(long long a, long long b, long long &x, long long &y){
		if(b == 0){
			x = 1;
			y = 0;
			return ;
		}
		exgcd(b, a % b, y, x);
		y -= a / b * x;
	}
	
	void modular_multiplicatibe_inverse(){
		long long x, y;  
		exgcd(fac[MAX_VAL - 1], MOD, x, y);
		mmi[MAX_VAL-1] = x;
		// mmi[MAX_VAL-1] = power(fac[MAX_VAL-1], MOD-2);
		for(long long i = MAX_VAL - 2; i >= 0; mmi[i]%=MOD, i--)
			mmi[i] = mmi[i + 1] * ((i + 1) % MOD);
	}
	
	long long combination(long long n, long long r){
		return n < r ? 0 :fac[n] * (mmi[r] * mmi[n-r] % MOD) % MOD;
	}
};

int main(){
	long long n, k, ans = 0;
	
	cin>>n>>k;
	
	
	binomial_coefficients BC(n);
	
	for(int i = 0; i < n && i <= k; i++){
		ans += BC.combination(n, i) * BC.combination(n-1, i);
		ans %= MOD;
	}
	
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 3328
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.io.PrintWriter
import java.lang.StringBuilder
import java.util.*

fun PrintWriter.solve(sc: FastScanner) {
    val n = sc.nextInt()
    val m = sc.nextInt()
    val s = sc.nextLine()
    var lst = mutableListOf<Int>()
    var i = n
    while (i != 0) {
        var ni = Math.max(0, i - m)
        var ok = false
        for (j in 0 until m) {
            if (s[ni] == '0') {
                ok = true
                lst.add(i - ni)
                i = ni
                break
            }
            ni++
        }
        if (!ok) {
            println(-1)
            return
        }
    }
    lst.reverse()
    println(lst.joinToString(" "))
}

fun main(args: Array<String>) {
    val writer = PrintWriter(System.out, false)
    writer.solve(FastScanner(System.`in`))
    writer.flush()
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}


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

int main(){
    int n,k,c;
    cin>>n>>k>>c;
    string s;
    cin>>s;
    vector<pii> left(n+1);
    vector<int> right(n+2,0);

    left[0]=make_pair(0,0);
    int cnt=0;
    int r=0;
    REP(i,n){
        if(s[i-1]=='o'&&i>r){
            cnt++;r=i+c;
        }
        left[i]=make_pair(cnt,r);
    }
    cnt=0;
    int l=n+1;
    rep(i,n){
        if(s[n-i-1]=='o'&& l>n-i){
            cnt++;
            l=n-i-c;
        }
        right[n-i]=cnt;
    }

    REP(i,n){
        if(s[i-1]=='o'){
            int mx=left[i-1].first+right[min(n+1,max(left[i-1].second,i)+1)];
            if(mx<k){
                cout<<i<<endl;
            }
        }
    }

}

Measured memory_bytes: 4228
#include<stdio.h>
#define P(type,x) fprintf(stdout,"%"#type"\n",x)
#define S(type,x) fscanf(stdin,"%"#type,&x)
#define MAX(a,b) a>b?a:b
int main() {
	int a[5000] = {},
		b[5000] = {},
		n, m, i, j;
	S(d, n), S(d, m);
	for (i = 0; i < n; i++)S(d, a[i]);
	for (i = 0; i < m; i++)S(d, b[i]);
	int c = 0;
	for (i = 0; i < m - c; i++) {
		int cur = i, d = 0;
		for (j = 0; j < n; j++)
			if (a[j] == b[cur])cur++, d++;
		c = MAX(c, d);
	}
	P(d, c);
	return 0;
}

Measured memory_bytes: 648
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;

deque<char> que;
int main()
{
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i++)
    {
        que.push_back(s[i]);
    }

    int Q;
    cin >> Q;
    bool rev = false;
    for (int i = 0; i < Q; i++)
    {
        int t;
        cin >> t;
        if (t == 1)
        {
            rev = !rev;
        }
        else
        {
            int f;
            char c;
            cin >> f >> c;
            if ((f == 1) ^ rev)
            {
                que.push_front(c);
            }
            else
            {
                que.push_back(c);
            }
            
        }
        
    }

    if (!rev)
    {
        for (deque<char>::iterator it = que.begin(); it != que.end(); it++)
        {
            cout << *it;
        }

    }
    else
    {
        for (deque<char>::reverse_iterator it = que.rbegin(); it != que.rend(); it++)
        {
            cout << *it;
        }
    }
    
    // system("pause");
}

Measured memory_bytes: 960
input_number = int(input())
int_list = list(map(int, input().split()))

check = 10 ** 18
ans = int_list[0]
for i in int_list[1:]:
    ans = ans * i

    if ans > check:
        ans = -1
        break

for i in int_list:
    if i == 0:
        ans = 0
        break

print(ans)


Measured memory_bytes: 21528
// #include <boost/multiprecision/cpp_int.hpp> 
// using namespace boost::multiprecision; 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define f first
#define s second
#define pb push_back
#define REP(i,a,b) for(long long int i=a ; i<b ; i++)
#define mp make_pair
#define INF 1000000000000000000
#define mod 1000000007
#define pi pair<ll,ll>
#define pd pair<ld,ld>
#define vi vector<ll>
#define vd vector<ld>
#define vvi vector<vi>
#define vvd vector<vd>
#define vpi vector<pi>
#define vpd vector<pd>
#define us unordered_set<ll>
#define um unordered_map<ll,ll>
#define sortA(a) sort(a.begin(),a.end())
#define sortD(a) sort(a.begin(),a.end(),greater<ll>())
#define all(a) a.begin(),a.end()
#define N 100005


#include <ext/pb_ds/assoc_container.hpp> 
using namespace __gnu_pbds; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> new_data_set; 
#define in insert
#define fbo find_by_order
#define ook order_of_key


void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

ll powmod(ll x,ll y)
{
	if(x==0)
		return 0;
	if(y==0 || x==1)
		return 1;
	if(y%2==0)
		return powmod((x*x)%mod,y/2)%mod;
	return (x*powmod(x,y-1)%mod)%mod;
}
void print1D(vi a)
{
	for(ll i=0;i<a.size();++i)
	{
		cout<<a[i]<<" ";
	}
	cout<<endl;
}
void print2D(vector<vi> a)
{
	for(ll i=0;i<a.size();++i)
	{
		for(ll j=0;j<a[i].size();++j)
		{
			cout<<a[i][j]<<" ";
		}
		cout<<endl;
	}
}
void solve()
{
	ll n,w;
	cin>>n>>w;
	vvi a(n+1,vi(2));
	for(ll i=1;i<=n;++i)
	{
		cin>>a[i][0]>>a[i][1];
	}
	vvi dp(n+1,vi(w+1));
	ll ans=0;
	for(ll i=1;i<=n;++i)
	{
		for(ll j=1;j<=w;++j)
		{
			dp[i][j]=dp[i-1][j];
			if((j-a[i][0])>=0)
			{
				dp[i][j]=max(dp[i][j],dp[i-1][j-a[i][0]]+a[i][1]);
			}
			ans=max(ans,dp[i][j]);
		}
	}
	cout<<ans<<endl;
}
int main()
{
	ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
	ll t=1;
	// cin>>t;
	while(t--)
	{
		solve();
	}
}


Measured memory_bytes: 80256
#include<iostream>
#include<math.h>
#include<string>
#include<algorithm>
#include<unordered_map>
#include<stack>
#include<vector>
using namespace std;
int main(){
    int N;
    cin >> N;
    string S;
    cin >>S;
    int ans = 0;
    for(int i = 1;i < S.length();i++){
        if(S[i] != S[i-1])ans++;
    }
    cout << ans + 1;
}


Measured memory_bytes: 512
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

int main() {
    int a, b, k;
    cin >> a >> b >> k;
    bool f = true;
    while (k--){
        if (f){
            a = a / 2 * 2;
            a /= 2;
            b += a;
        }else{
            b = b / 2 * 2;
            b /= 2;
            a += b;
        }
        f ^= 1;
    }
    cout << a << " " << b << endl;
    return 0;
}


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

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,x,y,br=0;
    cin >> n >> x >> y;
    vector<int> v(n,0);
    for (int i=1;i<=n-1;i++)
        for (int j=i+1;j<=n;j++)
        {
            br=0;
            br=min(j-i,abs(i-x)+abs(j-y)+1);
            v[br]++;
        }
    for (int i=1;i<=n-1;i++)
        cout << v[i] << '\n';
}


Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace D
{
    public class Program
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var nm = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();
            var briges = new Brige[nm[1]];
            var answers = new long[nm[1]];
            answers[answers.Length - 1] = ((long)nm[0] * ((long)nm[0] - 1)) / 2;
            for (var i = 0; i < briges.Length; i++)
            {
                var ab = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();
                briges[i] = new Brige { A = ab[0] - 1, B = ab[1] - 1 };
            }

            var unionFind = new UnionFind(nm[0]);
            for (var i = answers.Length - 1; i >= 1; i--)
            {
                var a = briges[i].A;
                var b = briges[i].B;
                if (unionFind.IsSame(a, b))
                {
                    answers[i - 1] = answers[i];
                }
                else
                {
                    answers[i - 1] = answers[i] - (long)unionFind.Size(a) * (long)unionFind.Size(b);
                    unionFind.Union(a, b);
                }
            }
            foreach (var count in answers)
            {
                Console.WriteLine(count);
            }

        }

        public struct Brige
        {
            public int A;
            public int B;
        }

        public class UnionFind
        {
            private int[] _parents;
            private int[] _counts;

            public UnionFind(int length)
            {
                _parents = Enumerable.Range(0, length).ToArray();
                _counts = Enumerable.Repeat(1, length).ToArray();
            }

            public int Find(int x)
            {
                if (_parents[x] == x) return x;
                return _parents[x] = Find(_parents[x]);
            }

            public bool Union(int x, int y)
            {
                var rootX = Find(x);
                var rootY = Find(y);
                if (rootX == rootY) return false;

                if (_counts[rootX] < _counts[rootY])
                {
                    var tmp = rootX;
                    rootX = rootY;
                    rootY = tmp;
                }
                _counts[rootX] += _counts[rootY];
                _parents[rootY] = rootX;
                return true;
            }

            public int Size(int x)
            {
                return _counts[Find(x)];
            }

            public bool IsSame(int x, int y)
            {
                return Find(x) == Find(y);
            }
        }
    }
}


Measured memory_bytes: 20788
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=610;
int n,x,y,cnt;
int fix[N];
ll dp[N][N],pd[N][N],ans;

void upd(ll &a,ll b) {
	a=(a+b)%mod;
}
int main() {
	scanf("%d",&n);
	for (int i=1;i<=n;i++) {
		scanf("%d%d",&x,&y);
		if (x==-1&&y==-1) {
			cnt++;
		} else if (x!=-1&&y!=-1) {
			fix[min(x,y)]=2;
			fix[max(x,y)]=2;
		} else {
			fix[x+y+1]=1;
		}
	}
	dp[0][0]=1;
	for (int i=2*n;i>=1;i--) {
		for (int j=0;j<=n;j++) for (int k=0;k<=2*n;k++) {
			pd[j][k]=dp[j][k];
			dp[j][k]=0;
		}
		// 剩j对x? k个没用的数值
		if (fix[i]==2) {
			for (int j=0;j<=n;j++) for (int k=0;k<=2*n;k++) {
				dp[j][k]=pd[j][k];
			}
		} else if (fix[i]==1) {
			for (int j=0;j<=n;j++) for (int k=0;k<=2*n;k++) {
				upd(dp[j+1][k],pd[j][k]);
				if (k>0) upd(dp[j][k-1],pd[j][k]);
			}
		} else {
			for (int j=0;j<=n;j++) for (int k=0;k<=2*n;k++) {
				upd(dp[j][k+1],pd[j][k]);
				if (j>0) upd(dp[j-1][k],pd[j][k]*j);
				if (k>0) upd(dp[j][k-1],pd[j][k]);
			}	
		}
/*		for (int j=0;j<=n;j++) for (int k=0;k<=2*n;k++) if (dp[j][k]) {
			printf("%d %d %d %lld\n",i,j,k,dp[j][k]);
		}*/
	}
	ll fac=1;
	for (int i=1;i<=cnt;i++) fac=fac*i%mod;
	upd(ans,dp[0][0]*fac);
	printf("%lld\n",ans);
}

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

typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007;

int main(){
    
    int N;cin>>N;
    priority_queue<ll> Q1,Q2;
    ll sum1=0,sum2=0;
    vector<ll> S(N*3),T1(3*N,0),T2(3*N,0);
    for(int i=0;i<3*N;i++){
        cin>>S[i];
    }
    for(int i=0;i<N;i++){
        sum1+=S[i];
        Q1.push(-S[i]);
    }
    T1[N-1]=sum1;
    for(int i=N;i<2*N;i++){
        Q1.push(-S[i]);
        T1[i]=T1[i-1]+S[i]+Q1.top();
        Q1.pop();
    }
    for(int i=3*N-1;i>=2*N;i--){
        sum2+=S[i];
        Q2.push(S[i]);
    }
    T2[2*N]=sum2;
    for(int i=2*N-1;i>=N;i--){
        Q2.push(S[i]);
        T2[i]=T2[i+1]+S[i]-Q2.top();
        Q2.pop();
    }
    ll ans=T1[N-1]-T2[N];
    for(int i=N-1;i<=2*N-1;i++){
        ans=max(ans,T1[i]-T2[i+1]);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 9588
#include<bits/stdc++.h>
using namespace std;
int main(){
  cin.tie(NULL);
  ios::sync_with_stdio(false);
  char n[5];
  int sum=0;
  cin>>n[0]>>n[1]>>n[2];
  for(int i=0;i<3;i++){
    if(n[i]=='o') sum++;
  }
  cout<<700+sum*100<<'\n';
  return 0;
}


Measured memory_bytes: 256
s=input()
n=len(s)
l=[[0,0] for i in range(n+1)]
ri,le=0,0
for i in range(n):
    l[i][0]=le
    l[-1-i][1]=ri
    if "<"==s[i]:le+=1
    else:le=0
    if ">"==s[-1-i]:
        ri+=1
    else:ri=0

l[n][0]=le
l[0][1]=ri
print(sum(max(a,s) for a,s in l))

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

using namespace std;

#define debug(x) cout << #x << "::" << x << endl;
#define debug2(x, y) cout << #x << "::" << x << " " << #y << "::" << y << endl;
#define debug3(x, y, z) cout << #x << "::" << x << " " << #y << "::" << y <<" "<< #z << "::" << z << endl;

#define For(i, a, b) for (int i = a; i < b; i++)

typedef long long ll;
const ll mod = 1e9 + 7;
const int MAX = 1e5 + 5;
typedef pair<int, int> pii;

void add(ll &a, ll b)
{
    a = (a + b) % mod;
    if (a < 0) a += mod;
}

ll mul(ll &a,ll b){
    return (a*b)%mod;
}
vector<int> g[MAX],visited(MAX);
ll dp[MAX][2];


pii dfs(int root,int parent) {

    //int black = dp[parent][0];
    //int white = dp[parent][1];
    
    ll allWhite = 1;
    ll smthBlack = 0;
    
    for(auto child : g[root]){
       if(child == parent) continue;
        pii value = dfs(child,root);
        ll memoWhite = allWhite;
        allWhite = mul(allWhite,value.second);
        smthBlack = (mul(memoWhite,value.first) + mul(smthBlack,value.first+value.second))%mod;
    }

   return {allWhite,(allWhite + smthBlack)%mod};
}


int main() {

    int n;
    cin>>n;
    For(i,0,n-1){
        
        int x,y;
        cin>>x>>y;
        
        g[x].push_back(y);
        g[y].push_back(x);

    }

    auto ans = dfs(1,0);
    cout<<(ans.first + ans.second)%mod<<endl;
    return 0;

}

Measured memory_bytes: 13056
import itertools
import math

n = int(input())
m = [list(map(int, input().split())) for i in range(n)]
l = 0


def f(a, b):
    return ((a[0] - b[0])**2 + (a[1] - b[1])**2)**0.5


for i in itertools.permutations(m, n):
    for j in range(n-1):
        l += f(i[j], i[j+1])

print(l / math.factorial(n))

Measured memory_bytes: 3188