akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,a;
  a=0;
  cin>>N;
  vector<int> vec(N);
  for(int i=0;i<N;i++)
    cin>>vec.at(i);
  sort(vec.begin(),vec.end());
  reverse(vec.begin(),vec.end());
  for(int i=0;i<N;i++){
    if(i == i/2*2)
      a +=vec.at(i);
    else
      a -=vec.at(i);
  }
  cout<<a<<endl;
}

Measured memory_bytes: 256
fn get_line() -> String {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().to_string()
}

fn reads<T>() -> Vec<T>
    where
        T: std::str::FromStr,
        <T as std::str::FromStr>::Err: std::fmt::Debug {
    get_line().split(' ').map(|x| x.parse().unwrap()).collect()
}

fn readln<T>() -> T
    where
        T: std::str::FromStr,
        <T as std::str::FromStr>::Err: std::fmt::Debug {
    get_line().parse().unwrap()
}

fn main() {
    let nab = reads();
    let mut hs: Vec<usize> = vec![];

    for _ in 0..nab[0] {
        hs.push(readln());
    }

    hs.sort();

    let mut upper = hs[nab[0] - 1];
    let mut under = 0;
    let mut prev_upper = 0;

    while upper > under {
        let ulimit = nab[2] * upper;
        let add = nab[1] - nab[2];

        let mut c = 0;
        for i in 0..nab[0] {
            c = i;
            if hs[i] > ulimit {
                break;
            }
        }


        let mut d = 0;

        if hs[c] > ulimit {
            for i in c..nab[0] {
                let h = hs[i] - ulimit;

                let m = h % add;
                d += h / add + if m == 0 {0} else {1};
            }
        }

        if d == upper {
            break;
        }

        let m = (upper + under) % 2;

        if d > upper {

            under = upper;
            upper = prev_upper;
        }
        else {
            prev_upper = upper;
            upper = (upper + under) / 2;

            if m > 0 {
                upper += 1;
            }

            if prev_upper == upper {
                break;
            }
        }
    }

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


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const int64_t LINF=8931145141919364364,LMOD=998244353;
// const int dy[]={0,-1,0,1,1,-1,-1,1};
// const int dx[]={1,0,-1,0,1,1,-1,-1};

int main() {
	int h, a; cin >> h >> a;
	cout << (h + a - 1) / a << '\n';
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int i,n;
	int p1,p2,p3;
	int ans=0;
	
	scanf("%d%d%d",&n,&p1,&p2);
	
	for(i=0;i<n-2;i++){
		scanf("%d",&p3);
		if(p1>p2 && p2>p3)
			ans++;
		else if(p1<p2 && p2<p3)
			ans++;
		p1=p2;
		p2=p3;
	}
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef pair < int , int > Pi;
bool data[5001][5001];
bool isOK(int x,int y){
  return (x < 0 || x > 5000 || y < 0 || y > 5000) ? false : data[x][y];
}
int main(){
  int n;
  Pi p[3000];
  while(cin >> n , n){
    fill_n( *data, 5001 * 5001 , false);
    for(int i = 0 ; i < n ; i++ ){
      cin >> p[i].first >> p[i].second;
      data[p[i].first][p[i].second] = true;
    }
    int ret = 0;
    for(int i = 0 ; i < n ; i++ ){
      for(int j = 0 ; j < i ; j++ ){
        int x = p[j].first - p[i].first;
        int y = p[j].second - p[i].second;
        if((isOK(p[i].first + y,p[i].second - x) & isOK(p[j].first + y,p[j].second - x))
          |(isOK(p[i].first - y,p[i].second + x) & isOK(p[j].first - y,p[j].second + x)))
          ret = max( ret, x * x + y * y);
      }
    }
    cout << ret << endl;
  }
}

Measured memory_bytes: 25604
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <fstream>
#include <cmath>
#include <random>
#include <complex>
#include <functional>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)
using namespace std;
typedef vector<ll> vec;
typedef vector<vec> mat;

const ll inf = 1LL << 60;

template<class T> inline void chmin(T& a, T b) {
    if (a > b) {
        a = b;
    }
}
template<class T> inline void chmax(T& a, T b) {
    if (a < b) {
        a = b;
    }
}

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

    ll N;
    cin >> N;
    vector<string> s(N);
    vec t(N);
    Rep (i, N) {
        cin >> s[i] >> t[i];
    }

    string X;
    cin >> X;
    ll ans = 0;
    bool asleep = false;
    Rep (i, N) {
        if (asleep) {
            ans += t[i];
        }

        if (s[i] == X) {
            asleep = true;
        }
    }

    cout << ans << endl;
}

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

//template
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(a);i>(b);i--)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll;
const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;
string to_str(ll x){string res; while(x)res+=('0'+(x%10)),x/=10; reverse(ALL(res)); return res;}
template<class T> inline bool chmax(T& a,T b){ if(a<b){a=b;return 1;}return 0; }
template<class T> inline bool chmin(T& a,T b){ if(a>b){a=b;return 1;}return 0; }
//template end

string RSP="rsp";
vector<int> a[100010];

int main(){
    int n,k; scanf("%d%d",&n,&k);
    int adds[3]; rep(i,0,3)scanf("%d",&adds[i]);
    string s; cin>>s;
    rep(i,0,n){
        a[i%k].push_back(RSP.find(s[i]));
    }
    ll res=0;
    rep(rem,0,k){
        vector<ll> dp[3];
        rep(i,0,3)dp[i].resize(a[rem].size()+1,0);
        rep(i,0,a[rem].size())rep(j,0,3){
            rep(nxt,0,3)if(j!=nxt){
                int add=(nxt==(a[rem][i]+2)%3?adds[nxt]:0);
                chmax(dp[nxt][i+1],dp[j][i]+add);
            }
        }
        ll add=0;
        rep(i,0,3)chmax(add,dp[i][a[rem].size()]);
        res+=add;
    }
    printf("%lld\n",res);
    return 0;
}

Measured memory_bytes: 5624
h, n = map(int, input().split())
s = []
for _ in range(n):
    D = list(map(int, input().split()))
    s.append(D)

dp = [[10**10 for i in range(h+1)] for j in range(n+1)]
dp[0][0] = 0

for i in range(n):
    dmg=s[i][0]
    mp=s[i][1]
    for j in range(h+1):
        dp[i+1][j] = min(dp[i+1][j],dp[i][j])
        dp[i+1][min(j+dmg,h)] = min(dp[i+1][min(j+dmg,h)], dp[i+1][j]+mp)

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

Measured memory_bytes: 125276
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
	int a,b;
	double f;
	cin >> a >> b;
	f=1.0*a/b;
	cout << a/b << " " << a%b << " ";
	printf("%.5f\n",f);
	return  0;
}

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

typedef long long int ll;
#define T int t,q; scanf("%d",&t); for(q=1;q<=t;q++)

int main(){
	ll a;
	cin >> a;
	a=a%10;
	if(a==2 or a==4 or a==5 or a==7 or a==9)cout << "hon"<< endl;
	else if(a==3)cout << "bon" << endl;
	else cout << "pon" << endl;
	
	return 0;
}

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

N, M = MAP()
A = LIST()

print(-1 if N < sum(A) else N - sum(A))

Measured memory_bytes: 10880
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef unsigned long long ULL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int main() {
  string r, a;

  while(1) {
    cin >> r >> a;
    if(r[0] == '0' && a[0] == '0') break;
    int hit = 0, blow = 0;
    
    REP(i, 4) {
      if(r[i] == a[i]) {
	hit++;
	continue;
      }
      REP(j, 4) {
	if(r[i] == a[j]) blow++;
      }
    }
    cout << hit << ' ' << blow << endl;
  }  
}

Measured memory_bytes: 1176
class mod_comb_k():
  def __init__(self, MAX_N = 10**6, mod = 10**9+7):
    self.fact = [1]
    self.fact_inv = [0] * (MAX_N + 4)
    self.mod = mod
    for i in range(MAX_N + 3):
      self.fact.append(self.fact[-1] * (i + 1) % self.mod)
    self.fact_inv[-1] = pow(self.fact[-1], self.mod - 2, self.mod)
    for i in range(MAX_N + 2, -1, -1):
      self.fact_inv[i] = self.fact_inv[i + 1] * (i + 1) % self.mod
  def comb(self, n, k):
    if n < k:return 0
    else:return self.fact[n] * self.fact_inv[k] % self.mod * self.fact_inv[n - k] % self.mod
c=mod_comb_k()
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
ans=0
mod=10**9+7
for i,j in enumerate(a,1):
  ans-=j*c.comb(n-i,k-1)
  ans%=mod
for i,j in enumerate(a[::-1],1):
  ans+=j*c.comb(n-i,k-1)
  ans%=mod
print(ans)

Measured memory_bytes: 165180
while 1:
    list = [input().split()]
    m = int(list[0][0])
    f = int(list[0][1])
    r = int(list[0][2])
    if m == -1 and f == -1 and r == -1 :
        break
    elif m == -1 or f == -1 :
        print("F")
    elif m + f >= 80 :
        print("A")
    elif 65 <= m + f and m + f < 80 :
        print("B")
    elif 50 <= m + f and m + f < 65 :
        print("C")
    elif 30 <= m + f and m + f < 50 and 50 <= r :
        print("C")
    elif 30 <= m + f and m + f < 50 and r < 50 :
        print("D")
    elif m + f < 30 :
        print("F")

Measured memory_bytes: 7668
from collections import deque

N = int(input())
dist = {}
graph = [[] for i in range(N)]

for i in range(1, N):
    u, v, w = map(int, input().split())
    graph[u-1].append(v-1)
    graph[v-1].append(u-1)
    dist[(u-1, v-1)] = w


q = deque()
q.append(0)

color = [-1] * N
color[0] = 0

while q:
    now = q.popleft()

    for adj in graph[now]:
        if color[adj] == -1:
            if now < adj:
                color[adj] = color[now] + dist[(now, adj)]
            else:
                color[adj] = color[now] + dist[(adj, now)]

            q.append(adj)


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


Measured memory_bytes: 52684
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long u_ll;
typedef pair<int, int> pair_;
 
const int INF = 1001001001;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
int k;
 
int gcd(int a, int b){
    if(b == 0) return a;
 
    return gcd(b, a%b);
}
 
int main(){

    int n;
    cin >> n;
    double ans=0.0;
    for(int i = 1;i <=n; i++){
        if(i%2==1) ans+=1.0;
    }

    ans = ans / n;

    cout << fixed << setprecision(6) << ans;
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int A,B,C,X,ans=0;
    scanf("%d%d%d%d",&A,&B,&C,&X);
    for(int i=0;i<=A;i++){
        for(int j=0;j<=B;j++){
            for(int k=0;k<=C;k++){
                if(i*500+j*100+k*50==X){
                    ans+=1;
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
} 


Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
using namespace std;
int main(){
	string s,t;
	cin>>s>>t;
	int n=(int)s.size();
	bool ans=false;
	for(int i=0;i<n;i++){
		bool f=true;
		for(int j=0;j<n;j++){
			if(s[(i+j)%n]!=t[j])f=false;
		}
		ans|=f;
	}
	if(ans)cout<<"Yes"<<endl;else cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef  long long int ll;
typedef  long double ld;
#define sync ios_base::sync_with_stdio(false); cin.tie(NULL) 
#define input(arr,n) for(ll i1=0;i1<n;i1++ )cin>>arr[i1]
#define mod 1000000007
#define F first
#define S second 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
//recursions\
#pragma comment(linker, "/stack:200000000")
//loops\
#pragma GCC optimize("unroll-loops")
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>//s.order_of_key(val) *s.find_by_order(ind)
using namespace std;
const int N = 1e6+5;
int main()
{
	sync;
	ll x;
	cin >> x;
	cout << (x  >= 30 ? "Yes" :"No");
}

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


string s,SS;

void dfs(int a,string S,int sum){
	if(a==4){
		if(sum==7){
			SS=S;
		}
		return;
	}
	
	dfs(a+1,S+"-"+s[a],sum-(s[a]-'0'));
	dfs(a+1,S+"+"+s[a],sum+(s[a]-'0'));
}

int main(){
	int a;
	string s2;
	cin >> s;
	
	a=s[0]-'0';
	s2=s[0];
	dfs(1,s2,a);
	
	cout << SS << "=7" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)

int N, M;
constexpr int Nmax = 400;
bitset<Nmax> isDead;
int status[Nmax][Nmax];

int main()
{
    cin >> N >> M;
    memset(status, 0, sizeof(status));
    REP(_, M)
    {
        int x, y;
        cin >> x >> y;
        x--; y--;
        if (isDead[x] || isDead[y] || status[x][y])
        {
            isDead.set(x);
            isDead.set(y);
            REP(i, N) status[x][i] = status[i][x] = status[y][i] = status[i][y] = 1;
        }
        else
        {
            status[x][y] = status[y][x] = 1;
            REP(i, N)
            {
                if (status[x][i]) status[y][i] = status[i][y] = 1;
                else if (status[y][i]) status[x][i] = status[i][x] = 1;
            }
        }
    }
    int ans = 0;
    REP(i, N) REP(j, i) ans += 1 - status[i][j];
    cout << ans << endl;
}


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

struct RollingHash {
    static const int base1 = 1007, base2 = 2009;
    static const int mod1 = 1000000007, mod2 = 1000000009;
    vector<long long> hash1, hash2, power1, power2;

    // construct
    RollingHash(const vector<long long> &S) {
        int n = (int)S.size();
        hash1.assign(n+1, 0);
        hash2.assign(n+1, 0);
        power1.assign(n+1, 1);
        power2.assign(n+1, 1);
        for (int i = 0; i < n; ++i) {
            hash1[i+1] = (hash1[i] * base1 + S[i]) % mod1;
            hash2[i+1] = (hash2[i] * base2 + S[i]) % mod2;
            power1[i+1] = (power1[i] * base1) % mod1;
            power2[i+1] = (power2[i] * base2) % mod2;
        }
    }
    
    // get hash of S[left:right]
    inline pair<long long, long long> get(int l, int r) const {
        long long res1 = hash1[r] - hash1[l] * power1[r-l] % mod1;
        if (res1 < 0) res1 += mod1;
        long long res2 = hash2[r] - hash2[l] * power2[r-l] % mod2;
        if (res2 < 0) res2 += mod2;
        return {res1, res2};
    }

    // get lcp of S[a:] and S[b:]
    inline int getLCP(int a, int b) const {
        int len = min((int)hash1.size()-a, (int)hash1.size()-b);
        int low = 0, high = len;
        while (high - low > 1) {
            int mid = (low + high) >> 1;
            if (get(a, a+mid) != get(b, b+mid)) high = mid;
            else low = mid;
        }
        return low;
    }

    // get lcp of S[a:] and T[b:]
    inline int getLCP(const RollingHash &T, int a, int b) const {
        int len = min((int)hash1.size()-a, (int)hash1.size()-b);
        int low = 0, high = len;
        while (high - low > 1) {
            int mid = (low + high) >> 1;
            if (get(a, a+mid) != T.get(b, b+mid)) high = mid;
            else low = mid;
        }
        return low;
    }
};


int N;
vector<long long> a, b;

void solve() {
    vector<long long> da(N*2), db(N*2);
    for (int i = 0; i < N*2; ++i) {
        int j = i % N;
        int k = (i + 1) % N;
        da[i] = a[j] ^ a[k];
        db[i] = b[j] ^ b[k];
    }

    RollingHash A(da), B(db);
    for (int k = 0; k < N; ++k) {
        int len = A.getLCP(B, k, 0);
        if (len >= N) {
            cout << k << " " << (a[k] ^ b[0]) << endl;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    while (cin >> N) {
        a.resize(N); b.resize(N);
        for (int i = 0; i < N; ++i) cin >> a[i];
        for (int i = 0; i < N; ++i) cin >> b[i];
        solve();
    }
}

Measured memory_bytes: 37888
#include<vector>
#include<queue>
#include<functional>
#include<algorithm>
#include<set>
#include<iostream>

using namespace std;

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

const int MX = 1<<19;
const int MM = 1000000007;

int vst[MX], cnt[MX];

int main()
{
	int N, M;
	scanf("%d%d", &N, &M);
	for(int i = 1; i <= N; i++) cnt[i] = 1;
	vst[1] = 1;
	for(int i = 1; i <= M; i++){
		int a, b;
		scanf("%d%d", &a, &b);
		if( vst[a] ) vst[b] = 1;
		if( cnt[a] == 1 ) vst[a] = 0;
		cnt[a]--; cnt[b]++;
	}
	int ans = 0;
	for(int i = 1; i <= N; i++){
		ans += vst[i];
	}
	printf("%d\n", ans);
}


Measured memory_bytes: 2688
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main(){
    int N, M;
    cin >> N >> M;
    ll A, B, C;
    vector<ll> vec;

    for(int i=0;i<N;i++){
        cin >> A;
        vec.push_back(A);
    }
    pair<ll, ll> p[100000];
    for(int i=0;i<M;i++){
        cin >> B >> C;
        p[i] = make_pair(C, B); // 整数値，枚数
    }

    // 降順ソート（整数値）
    sort(p, p + M, greater<pair<ll, ll>>());
    // N枚まで加える
    ll num = 0;
    for(int i=0;num<N;i++){
        //vector<ll> tmp(p[i].first, p[i].second);
        //vec.insert(vec.end(), tmp.begin(), tmp.end()); 
        for(int j=0;j<p[i].second;j++)
            vec.push_back(p[i].first);
        num += p[i].second;
    }

    // 降順ソート
    sort(vec.begin(), vec.end(), greater<ll>());
    ll ans = 0;
    for(int i=0;i<N;i++){
        ans += vec[i];
    }

    cout << ans << endl;

}

Measured memory_bytes: 68320
import sys

INPUT = lambda: sys.stdin.readline().rstrip()
MAP = lambda: map(int, INPUT().split())

sys.setrecursionlimit(10 ** 9)


def main():
    A, B, K = MAP()

    cnt = 0
    for i in range(A-1, -1, -1):
        if A%(i+1) == 0 and B%(i+1) == 0: cnt += 1
        if cnt == K:
            print(i+1)
            sys.exit()


if __name__ == '__main__':
    main()

Measured memory_bytes: 38384
N, K = map(int,input().split())
A = list(map(int,input().split()))
X = [-1 for j in range(N)]
X[0] = 0
Y = [0]
i = 0
Num = 0
MM = 0
for k in range(1,N):
  i = A[i]-1
  if k == K:
    MM = 1
    P = i
    break
  elif X[i] != -1:
    Num = X[i]
    break
  else:
    X[i] = k
    Y.append(i)
Y = Y[Num:]
B = (K-Num)%len(Y)
if MM == 1:
  print(P+1)
else:
  print(Y[B]+1)

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
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 main():
    rr = []

    while True:
        n,k,s = LI()
        if n == 0 and k == 0 and s == 0:
            break
        d = collections.defaultdict(int)
        d[(0,0)] = 1
        for i in range(1,n+1):
            for kk,vv in list(d.items()):
                if kk[0] == k or kk[1] + i > s:
                    continue
                d[(kk[0]+1,kk[1]+i)] += vv

        rr.append(d[(k,s)])

    return '\n'.join(map(str, rr))


print(main())




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

ll gcd(ll a, ll b){
    while(b != 0){
        ll tmp = b;
        b = a % b;
        a = tmp;
    }
    return a;
}

int main(){
    int n;
    cin >> n;
    vector<ll> monster(n);
    for(int i=0;i<n;i++) cin >> monster.at(i);
    ll g = gcd(monster.at(0),monster.at(1));
    for(int i=2;i<n;i++){
        g = gcd(g,monster.at(i));
    }
    cout << g << endl;
}

Measured memory_bytes: 4044
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int n,m,l,a,b; //n*mの行列がA、m*lの行列がB
    cin >> n >> m >> l;
    int A[n][m];
    int B[m][l];
    
    for(int i = 0; i<n;i++){  //Aに要素を入れる
        
        for(int j = 0;j < m;j++){
            cin >> a;
            A[i][j] = a;
            
        }
    }
    
    for(int k = 0; k < m;k++){   //Bに要素を入れる。
        for(int x = 0;x<l; x++){
            cin >> b;
            B[k][x] = b;
        }
    }
    
    for(int i = 0;i<n; i++){
        for(int j = 0; j < l; j++){
            long long c = 0;
            for(int k = 0; k < m;k++){
                c += A[i][k] * B[k][j];
                //cout << c << " ";
            
            }
            if(j == 0) cout << c;
            else cout << " " << c;
            //cout << endl;
            
        }
        cout << endl;
    }
    
}


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

const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

int main(){
    int n;
    cin >> n;
    vi a(n);
    rep(i, n) cin >> a[i];
    vll b(n+1);
    rep(i, n) b[i+1] = b[i] + a[i];
    VSORT(b);
    ll ans = 0;
    int cnt = 1;
    rep(i, n+1) {
        if (i<n && b[i]==b[i+1]) ++cnt;
        else {
            ans += (ll)cnt * (cnt-1) / 2;
            cnt = 1;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 5624
/******************************************
* AUTHOR : RAJAGOPALAN *
* NICK : ARNO *
* INSTITUTION : VIT *
******************************************/
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define alli(a, n, k) (a+k),(a+n+k)
#define FP(i, a, b, k) for(__typeof(a) i = a;i < b;i += k)
#define FS(i, a, b, k) for(__typeof(a) i = a;i > b;i -= k)
#define IT(it, a) for(__typeof(a.begin()) it = a.begin();it != a.end(); ++it)
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define eps 1e-6
#define pi 3.141592653589793
using namespace std;
using namespace __gnu_pbds;

template<class T> inline T gcd(T x, T y) { if (!y) return x; return gcd(y, x%y);}
typedef vector<int> VII;
typedef vector<ll> VLL;
typedef pair<int, int> PII;
typedef vector< pair<int, int> > VPII;
typedef vector< pair<int, PII > > VPPI;
const int MOD = 1e9 + 7;
const int INF = 1e9;

inline ll modulo(ll a, ll m)
{
    return (a % m + m) % m;
}

inline ll modInverse(ll a, ll m)
{
    assert(__gcd(a, m) == 1);
    ll m0 = m;
    ll y = 0, x = 1;

    if (m == 1)
        return 0;

    while (a > 1)
    {
        ll q = a / m;
        ll t = m;

        m = a % m, a = t;
        t = y;

        y = x - q * y;
        x = t;
    }

    if (x < 0)
        x += m0;

    return x;
}

inline ll modPow(ll x, ll y, ll m)
{ //x^y % m
    if (y == 0)
        return 1LL;
    else if (y == 1)
        return x;
    else
    {
        ll ans = modPow(x, y / 2, m) % m;
        if (y & 1)
        {
            return (((ans * ans) % m) * x) % m;
        }
        else
        {
            return (ans * ans) % m;
        }
    }
}

int main(int argc, char* argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    set<int> s;
    for(int i=0;i<3;++i)
    {
        int x;
        cin>>x;
        s.insert(x);
    }
    if(s.size()==2)cout<<"Yes";
    else cout<<"No";
    return 0;
}

Measured memory_bytes: 256
import core.bitop;
import std.algorithm;
import std.ascii;
import std.bigint;
import std.conv;
import std.functional;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.random;
import std.typecons;
import std.container;

ulong MOD = 1_000_000_007;
ulong INF = 1_000_000_000_000;
alias sread = () => readln.chomp();
alias TOWN = Tuple!(long, "x", long, "y");

void main()
{
    auto week = ["SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"];
    auto s = sread();
    foreach(i; iota(week.length))
    {
        if(s == week[i])
        {
            (7 - i).writeln();
        }
    }

}

T lread(T = long)()
{
    return readln.chomp.to!T();
}

T[] aryread(T = long)()
{
    return readln.split.to!(T[])();
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}

long product_MOD(long n)
{
    long p_MOD = 1;
    while (n > 0)
    {
        p_MOD *= n--;
        p_MOD %= MOD;
    }
    return p_MOD;
}


Measured memory_bytes: 256
#include<iostream>
#include<map>
#include<algorithm>
#include <iomanip>
#include <cmath>
#include <sstream>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <vector>
#include <bitset>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <cstring>

#define INF 1050000000
#define MOD 1000000007

int n, a, b, c;
int l[10];

using namespace std;

int dfs(int depth, int x, int y, int z) {
	if (depth == n) {
		if (x == 0 || y == 0 || z == 0) {//答えから除外する。無に魔法は使えない。
			return 1e9;
		}
		return abs(x - a) + abs(y - b) + abs(z - c) - 30;
	}

	int mu = dfs(depth + 1, x, y, z);
	int entyou = dfs(depth + 1, x + l[depth], y, z)+10;
	int tansyuku = dfs(depth + 1, x, y + l[depth], z)+10;
	int gousei = dfs(depth + 1, x, y, z + l[depth])+10;

	return min({ mu,entyou,tansyuku,gousei });

}


int main() {
	cin >> n >> a >> b >> c;

	for (int i = 0; i < n; i++) {
		cin >> l[i];
	}

	cout << dfs(0, 0, 0, 0) << endl;








}

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

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;


int main() {
    ios_base::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    int ans = 1;
    for (int i = 0; i < n; ++i) {
        int r = ans*2, w = ans+k;
        ans = min(r,w);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
/**
 *    author:  tourist
 *    created: 25.11.2017 13:17:25       
**/
#include <bits/stdc++.h>

using namespace std;

string to_string(string s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

const int md = (int) 1e9 + 7;

inline void add(int &a, int b) {
  a += b;
  if (a >= md) a -= md;
}

inline void sub(int &a, int b) {
  a -= b;
  if (a < 0) a += md;
}

inline int mul(int a, int b) {
#if !defined(_WIN32) || defined(_WIN64)
  return (int) ((long long) a * b % md);
#endif
  unsigned long long x = (long long) a * b;
  unsigned xh = (unsigned) (x >> 32), xl = (unsigned) x, d, m;
  asm(
    "divl %4; \n\t"
    : "=a" (d), "=d" (m)
    : "d" (xh), "a" (xl), "r" (md)
  );
  return m;
}

inline int power(int a, long long b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) {
      res = mul(res, a);
    }
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}

inline int inv(int a) {
  a %= md;
  if (a < 0) a += md;
  int b = md, u = 0, v = 1;
  while (a) {
    int t = b / a;
    b -= t * a; swap(a, b);
    u -= t * v; swap(u, v);
  }
  assert(b == 1);
  if (u < 0) u += md;
  return u;
}

const int N = 111;

int f[N][N * N];

int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  int total = mul(power(k + 1, n), mul(n * k, inv(2)));
  f[n][0] = 1;
  for (int i = n; i >= 1; i--) {
    for (int j = 0; j < N * N; j++) {
      int ft = f[i][j];
      if (ft == 0) {
        continue;
      }
      debug(i, j, ft);
      for (int at = 0; at <= k; at++) {
        int nj = j;
        if (at <= i) {
          int to_next = i - at;
          int have = j;
          if (have >= to_next) {
            nj++;
            have -= to_next;
            nj += have / i;
          }
        }
        add(f[i - 1][nj], ft);
      }
    }
  }
  for (int j = 0; j < N * N; j++) {
    if (f[0][j] > 0) {
      debug(0, j, f[0][j]);
    }
    sub(total, mul(j, f[0][j]));
  }
  printf("%d\n", total);
  return 0;
}


Measured memory_bytes: 2560
n = int(input())
aa, bb, cc = [], [], []
hs = []
for i in range(n):
  a, b, c = map(int, input().split())
  hs.append({})
  hs[i]['a'] = a
  hs[i]['b'] = b
  hs[i]['c'] = c

dp = []
dp.append({})
for x in 'abc':
  dp[0][x] = 0

for i in range(1, n+1):
  dp.append({})
  for current in 'abc':
    vals = []
    for before in 'abc':
      if current == before:
        continue
      vals.append(dp[i-1][before] + hs[i-1][current])
    dp[i][current] = max(vals)

print(max(dp[n].values()))


Measured memory_bytes: 83140
#include <stdio.h>
#include <stdlib.h>

int N, M;
int ec[114514];
int* es[114514];

void ae(int f, int t) {
	es[f] = realloc(es[f], sizeof(*es[f]) * (ec[f] + 1));
	if (es[f] == NULL) exit(2);
	es[f][ec[f]++] = t;
}

int sansyo[114514];

int next_count[2];
int next_buffer[2][114514];

int answer[114514];

int main(void) {
	int i;
	int phase;
	if (scanf("%d%d", &N, &M) != 2) return 1;
	for (i = 1; i <= N - 1 + M; i++) {
		int A, B;
		if (scanf("%d%d", &A, &B) != 2) return 1;
		ae(A, B);
		sansyo[B]++;
	}
	next_count[0] = 0;
	for (i = 1; i <= N; i++) {
		if (sansyo[i] == 0) next_buffer[0][next_count[0]++] = i;
	}

	phase = 0;
	while (next_count[phase] > 0) {
		next_count[1 - phase] = 0;
		for (i = 0; i < next_count[phase]; i++) {
			int target = next_buffer[phase][i];
			int j;
			for (j = 0; j < ec[target]; j++) {
				if (--sansyo[es[target][j]] == 0) {
					answer[es[target][j]] = target;
					next_buffer[1 - phase][next_count[1 - phase]++] = es[target][j];
				}
			}
		}
		phase = 1 - phase;
	}
	for (i = 1; i <= N; i++) {
		printf("%d\n", answer[i]);
	}
	return 0;
}

/*

一番上(根)はどこからも参照されてない
→ そこからの参照を消せば、次の階層がどこからも参照されなくなるはず
→ 繰り返す

*/


Measured memory_bytes: 6756
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import math
[n,k]=i2()
d=[]
for i in range(n):
 d.append(i2())
eps=10**(-6)
def check(t):
 for x1,y1,c1 in d:
  for x2,y2,c2 in d:
   if x1==x2 and y1==y2:
      continue
   aa=2*(x1-x2)
   bb=2*(y1-y2)
   cc=t**2*(1/c2**2-1/c1**2)+x1**2-x2**2+y1**2-y2**2
   if aa==0:
      continue
   ss=bb**2/aa**2+1
   tt=bb/aa*(x1-cc/aa)-y1
   uu=(x1-cc/aa)**2+y1**2-(t/c1)**2
   if tt**2-ss*uu<0 or ss==0:
      continue
   Y1=-tt-math.sqrt(tt**2-ss*uu)
   Y1/=ss
   X1=(cc-bb*Y1)/aa
   count=0
   for x,y,c in d:
    if c*math.sqrt((X1-x)**2+(Y1-y)**2)<=t+eps:
      count+=1
   if count>=k:
    return True
   Y2=-tt+math.sqrt(tt**2-ss*uu)
   Y2/=ss
   X2=(cc-bb*Y2)/aa
   count=0
   for x,y,c in d:
    if c*math.sqrt((X2-x)**2+(Y2-y)**2)<=t+eps:
      count+=1
   if count>=k:
    return True
 for X,Y,C in d:
   count=0
   for x,y,c in d:
    if c*math.sqrt((X-x)**2+(Y-y)**2)<=t+eps:
      count+=1
   if count>=k:
    return True
 return False

low=0
high=100*3000

while high-low>eps:
  mid=(low+high)/2
  if check(mid):
     high=mid
  else:
     low=mid
print(high)

Measured memory_bytes: 51932
from collections import defaultdict


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N = read_int()
    G = defaultdict(list)
    for _ in range(N-1):
        a, b, c = read_ints()
        G[a].append((b, c))
        G[b].append((a, c))
    Q, K = read_ints()

    dist = [0]*(N+1)
    stack = [(None, 0, K)]
    while stack:
        parent, base_d, node = stack.pop()
        for child, d in G[node]:
            if child != parent:
                dist[child] = base_d+d
                stack.append((node, base_d+d, child))

    for _ in range(Q):
        x, y = read_ints()
        print(dist[x]+dist[y])


if __name__ == '__main__':
    solve()


Measured memory_bytes: 124644
#include <iostream>
#include <string>
using namespace std;
int main(){
  int N;
  float x[10],sum=0.0;
  string u[10];
  cin >> N ;
  for (int i=0;i<N;i++){
    cin >> x[i];
    cin >> u[i];
  }
  for (int i=0;i<N;i++){
    if (u[i] == "JPY"){
      sum += float(x[i]);
    }else{
      sum += 380000.0*x[i];
    }
  }
  cout << sum <<endl;
}


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

int mod = 1000000007;

int main()
{
    int N, tmp, ans = 0;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> tmp;
        ans += (tmp - 1);
    }
    cout << ans;
}

Measured memory_bytes: 256
import qualified Data.Vector.Unboxed as V
import Data.Vector.Unboxed ((!))
import qualified Data.Vector.Unboxed.Mutable as VM
import Data.List
import Control.Monad
import Data.IORef

coordN :: Int -> (Int, Int) -> Int
coordN n (x,y) = x*n+y

main :: IO ()
main = do
  [n,m,q] <- map read . words <$> getLine
  let cd = coordN n
  vecm <- VM.replicate (n*n) 0 :: IO (VM.IOVector Int)
  replicateM_ m $ do
    [x,y] <- map read . words <$> getLine
    VM.modify vecm (+1) $ cd (x-1,y-1)
  forM_ [1..n-1] $ \x -> do
    let slice0 = VM.slice ((x-1)*n) n vecm
        slice1 = VM.slice (x*n) n vecm
    forM_ [0..n-1] $ \y -> do
      val <- VM.read slice0 y
      VM.modify slice1 (val+) y
  forM_ [0..n-1] $ \x -> do
    let slice = VM.slice (x*n) n vecm
    forM_ [1..n-1] $ \y -> do
      val <- VM.read slice (y-1)
      VM.modify slice (val+) y
  vec <- V.unsafeFreeze vecm :: IO (V.Vector Int)
  replicateM_ q $ do
    [x,y] <- map read . words <$> getLine
    putStrLn $ show $ query vec n (x-1) (y-1)

query :: V.Vector Int -> Int -> Int -> Int -> Int
query vec n x y =
  vec ! cd (y,y) - chk (vec ! cd (x-1,y)) - chk (vec ! cd (y,x-1))
  + chk (vec ! cd (x-1,x-1))
 where
   cd = coordN n
   chk = if x <= 0 then const 0 else id

Measured memory_bytes: 3836
#include <iostream>
#include <sstream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>

using namespace std;

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


#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
#define dump(x) cout << #x << " = " << (x) << endl

int main() {
	int N;
  cin>>N;
	vector<double> A(N, 0);
	double mult = 1;
	double sum = 0;
	rep(i, N) {
		cin >> A[i];
		A[i] /= 1000.0;
		mult *= A[i];
	}

	rep(i, N) {
		sum += mult / A[i];
	}
	double ans = mult /sum*1000;
	cout << ans << endl;
	return 0;


}

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

typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;
#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev
#define dump(x)  cout << #x << " = " << (x) << endl;	//debug
#define SZ(x) ((int)(x).size())
#define REP(i, n) for(ll i = 0; i < (n); i++)
#define REPR(i, n) for (ll i = (n); i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define RFOR(i, a, b) for (ll i = (a); i >= (b); i--)
#define ps(s) cout << #s << endl;
#define pv(v) cout << (v) << endl;
#define pvd(v) cout << setprecision(16) << res << endl;
#define ALL(a)  (a).begin(),(a).end()
#define RANGE(a, l, r)  (a).begin()+(l),(a).begin()+(r)

int main() {
	int n;
	cin >> n;
	set<int> st;
	FOR(i, 1, n) {
		int a;
		cin >> a;
		if (st.find(a) == st.end()) {
			st.insert(a);
		}
		else {
			ps(NO);
			return(0);
		}
	}
	ps(YES);
	return(0);
}

Measured memory_bytes: 9600
from collections import defaultdict

M = 998244353
B = pow(10, 18, M)
N = int(input())

def geometric_mod(a, r, m, n):
  x = a
  for i in range(n):
    yield x
    x = (x*r)%m

BB = list(geometric_mod(1, B, M, N+2))

def ext_euc(a, b):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, b
  while z1 != 1:
    d, m = divmod(z2,z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1, y1

def inv_mod(a, b, m):
  x, y = ext_euc(a, m)
  return (x * b % m)

def mex(s):
  for i in range(N+1):
    if i not in s:
      return i

def calc_grundy(e):
  g = {}
  sum_g = defaultdict(int)
  sum_g[0] = inv_mod(B-1, pow(B, N+1, M)-B, M)
  for i in range(N, 0, -1):
    if i not in e:
      continue
    m = mex({g.get(j, 0) for j in e[i]})
    if m:
      g[i] = m
      sum_g[g[i]] = (sum_g[g[i]] + BB[i]) % M
      sum_g[0]  = (sum_g[0] - BB[i]) % M

  return sum_g

def read_edge():
  M = int(input())
  e = defaultdict(set)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].add(b)
  return e

def solve(N, edge):
  sum_g = list(map(calc_grundy, edge))
  ret = 0
  for gx, sx in sum_g[0].items():
    for gy, sy in sum_g[1].items():
      gz = gx^gy
      sz = sum_g[2][gz]
      if sz:
        ret = (ret + sx*sy*sz) % M
  return ret


edge = [read_edge() for i in range(3)]

print(solve(N, edge))

Measured memory_bytes: 77536
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;

int n,k,ans = 0;

int ec = 0,to[800005],nxt[800005],hed[400005] = {0};
void add_edge(int f,int t){
	++ ec; to[ec] = t; nxt[ec] = hed[f]; hed[f] = ec;
}

int dsv[400005] = {0},fa[400005] = {0};
int dsu[400005] = {0},vis[400005] = {0};
int lis[400005],lcn = 0;

void dfs1(int u,int f){
	dsv[u] = dsv[f] + 1;
	fa[u] = f;
	for(int i = hed[u];i;i = nxt[i]){
		int v = to[i];
		if(v == f) continue;
		dfs1(v,u);
	}
}

void dfs2(int u,int f){
	vis[u] = 1;
	for(int i = hed[u];i;i = nxt[i]){
		int v = to[i];
		if(v == f) continue;
		dfs2(v,u);
	}
}

int main(){
	int u,v,a,b;
	cin >> n >> u >> v;
	for(int i = 1;i < n;i ++){
		cin >> a >> b;
		add_edge(a,b);
		add_edge(b,a);
	}
	dfs1(v,0);
	
	while(u != v){
		lis[++ lcn] = u;
		u = fa[u];
	}lis[++ lcn] = u;
	int vv = lis[lcn >> 1];
//	for(int i = 1;i <= lcn;i ++) cout << lis[i] << (i == lcn ? '\n' : ' '); cout << vv << endl; 
	
	int ffa = fa[vv]; dfs2(vv,ffa);
	for(int i = 1;i <= n;i ++) if(vis[i]) ans = max(ans,dsv[i]);
	cout << ans - 2 << endl;
	return 0;
}

Measured memory_bytes: 11520
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include<queue>
#include<set>
#include<climits>
using namespace std;

int main()
{
  long long n, M = 0, A = 0, R = 0, C = 0, H = 0, result = 0;
  long long march[5];
  string s;
  cin >> n;
  
  for (int i = 0; i < n; i++)
  {
    cin >> s;
    if(s[0] == 'M')
    M++;
    if(s[0] == 'A')
    A++;
    if(s[0] == 'R')
    R++;
    if(s[0] == 'C')
    C++;
    if(s[0] == 'H')
    H++;
  }
  
  march[0] = M;
  march[1] = A;
  march[2] = R;
  march[3] = C;
  march[4] = H;
  
  for (int i = 0; i < 5; i++)
  {
    for (int j = i + 1; j < 5; j++)
    {
      for (int k = j + 1; k < 5; k++)
      {
        long long tmp = march[i] * march[j] * march[k];
        result += tmp;
      }
    }
  }
  
  cout << result << endl;
  
}

Measured memory_bytes: 384
program abc145e
type data
  integer::A,B
end type
integer N,T
type(data),allocatable::menu(:)
integer,allocatable::DP1(:,:),DP2(:,:)
integer ans
read*,N,T
allocate(DP1(0:N+1,0:T),DP2(0:N+1,0:T))
allocate(menu(N))
do i=1,N
    read*,menu(i)%A,menu(i)%B
end do

DP1=0;DP2=0
do i = 1,N
	do j = 0,T
    	if (j >= menu(i)%A)then
        	dp1(i+1,j) = max(dp1(i,J-menu(i)%A) +menu(i)%B, dp1(i,j))
        else
            dp1(i+1,j) = dp1(i,j)
        endif
    end do
end do
do i = N,1,-1
	do j = 0,T
    	if (j >= menu(i)%A)then
        	dp2(i-1,j) = max(dp2(i,J-menu(i)%A) +menu(i)%B, dp2(i,j))
        else
            dp2(i-1,j) = dp2(i,j)
        endif
    end do
end do
ans=0
do j=1,N
  do i=0,T-1
    ans=max(ans,DP1(j,i)+DP2(j,T-1-i)+menu(j)%B)
  end do
end do
print"(i0)",ans
end program

Measured memory_bytes: 70656
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
fn main(){
    let n:usize  =read();
    let mut an = vec![];
    for _ in 0..n{
        an.push(read::<i64>());
    }
    an.sort();
    let mut bn:Vec<i64> = (0..n).map(|x| {
        if n % 2 == 0{
            even(x,n-1)
        } else {
            odd(x,n-1)
        }
    }).collect();
    let mut cn:Vec<i64> = (0..n).map(|x| {
        if n % 2 == 0{
            even_1(x,n-1)
        } else {
            odd_1(x,n-1)
        }
    }).collect();
    bn.sort();
    cn.sort();
    let  up:Vec<i64> = an.iter().zip(bn.into_iter()).map(|(a,b)| {a*b}).collect();
    let down:Vec<i64> = an.iter().zip(cn.into_iter()).map(|(a,b)| {a*b}).collect();
    // println!("{:?}",up );
    // println!("{:?}",down );
    let ans = std::cmp::max(up.into_iter().sum::<i64>(),down.into_iter().sum::<i64>());
    println!("{}", ans);
}
fn odd(x:usize,upper:usize)->i64{
        if x == 0 || x == upper{
            1
        } else if x % 2 == 0 {
            2
        } else {
            -2
        }
}
fn odd_1(x:usize,upper:usize)->i64{
        if x == 0 || x == upper{
            -1
        } else if x % 2 == 0 {
            -2
        } else {
            2
        }
}
fn even(x:usize,upper:usize)->i64{
    if x == 0 {
        1
    } else if x == upper {
        -1
    } else if x % 2 == 0{
        2
    } else {
        -2 
    }
}
fn even_1(x:usize,upper:usize)->i64{
    if x == 0 {
        -1
    } else if x == upper {
        1
    } else if x % 2 == 0{
        -2
    } else {
        2 
    }
}

Measured memory_bytes: 9884
while 1:
	n = input()
	if n == 0: break
	item = {}
	for i in range(n):
		name,cost = raw_input().split()
		item[name] = int(cost)
	for i in range(input()):
		recipe = raw_input().split()
		cost = sum(item[name] if name in item else 0 for name in recipe[2:])
		item[recipe[0]] = min(cost, item[recipe[0]])
	print item[raw_input()]

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

int main(){
    string S;
    cin >> S;
    int n = (int)S.size();
    vector<string> words;
    words = {"dream", "dreamer", "erase", "eraser"};
    while (n > 0) {
        bool check = true;
        for (string word : words) {
            int m = (int)word.size();
            check = true;
            for (int i = 0; i < m; i++) {
                if (S[n-m+i] != word[i]) {
                    check = false;
                    break;
                }
            }
            if (check) {
                n -= m;
                break;
            }
        }
        if (!check) {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}

Measured memory_bytes: 512
def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    elif b == 1:
        return 1
    return gcd(b, a % b)

if __name__ == "__main__":
    N = int(input())
    li = input().split()
    g = int(li[0])
    for i in range(N):
        g = gcd(g, int(li[i]))
    print(g)

Measured memory_bytes: 12140
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

int main() {
	int n;
	for(;n=in();){
		int a,b,i,res=-1;
		for(i=0;i<12;i++){
			a=in();b=in();
			n-=a-b;
			if(n<=0)if(res==-1)res=i+1;
		}
		if(res!=-1)cout<<res<<endl;
		else cout<<"NA\n";
	}
}

Measured memory_bytes: 0