akhauriyash/Code-Regression huggingface dataset:
ans_list = []
def calclater(a, num_list):
    if a == "*":
        ans = 1
        for i in num_list:
            ans *= int(i)
    elif a == "+":
        ans = 0
        for i in num_list:
            ans += int(i)
    return str(ans)

while True:
    n = int(input())
    if not n:
        break
    s_list = [[] for i in range(100)]
    now = 0
    now_len = 0
    for i in range(n):
        s = input()
        if not i:
            s_list[0] = [s]
            now_len = len(s)
        else:
            if len(s) == now_len:
                s_list[now].append(s[-1])
            elif len(s) > now_len:
                now += 1
                s_list[now] = [s[-1]]
                now_len = len(s)
            elif len(s) < now_len:
                while len(s) < now_len:
                    s_list[now - 1][-1] = str(calclater(s_list[now - 1][-1], list(s_list[now])))
                    s_list[now] = []
                    now_len -= 1
                    now -= 1
                s_list[now].append(s[-1])

    for i in range(now - 1, -1, -1):
        s_list[i][-1] = str(calclater(s_list[i][-1], s_list[i + 1]))

    ans_list.append(s_list[0][0])

for i in ans_list:
    print(i)


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

int main(){
  int N,M;
  cin>>N>>M;
  vector<int> vec(N,0);
  for(int i=0;i<2*M;i++){
    int s;
    cin>>s;
    vec[s-1]++;
  }
  for(int i=0;i<N;i++)
    cout<<vec[i]<<endl;
}

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

#define INF 1 << 29
#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)

using namespace std;

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

void gen_sosuu(int sosuu[]){
  REP(i,100010){
    sosuu[i] = true;
  }
  sosuu[0] = false;
  sosuu[1] = false;
  sosuu[2] = true;
  FOR(i,2,sqrt(100000)+1){
    if(sosuu[i] == false) continue;
    for(int j = 2; i*j<=100000;j++){
      //printf("%d %d %d\n",i*j,i,j);
      sosuu[i*j] =false;
    }
  }
}

int n,a;

int main(){
  cin >> n>>a;
  if(n%500<=a) cout << "Yes"<<endl;
  else cout << "No" <<endl;
}


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

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

constexpr ll INF = 1e18;
constexpr ll MOD = 1e9 + 7;
constexpr double PI = 3.14159265358979323846;
constexpr int dx[] = {0, 0, 1, -1};
constexpr int dy[] = {1, -1, 0, 0};

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

    int n, l, a[112345];

    cin >> n >> l;
    REP(i, n)
    cin >> a[i];

    int p = -1;
    REP(i, n - 1)
    {
        if (a[i] + a[i + 1] >= l)
        {
            p = i;
        }
    }

    if (p == -1)
    {
        cout << "Impossible" << endl;
        return 0;
    }

    cout << "Possible" << endl;

    for (int i = 1; i < p + 1; i++)
        cout << i << endl;

    for (int i = n - 1; i >= p + 2; i--)
        cout << i << endl;

    cout << p + 1 << endl;

    return 0;
}

Measured memory_bytes: 1280
def partition(a)
  x = a[-1][0]
  i = 0 # 前方に持ってくるためのindex
  0.upto(a.size - 1) do | j |
    if a[j].class == Array
      aj = a[j][0]
    else
      aj = a[j]
    end
    if aj <= x
      a[i], a[j] = a[j], a[i]
      i += 1
    end
  end
end

n = gets.to_i
a = gets.split.map(&:to_i)
a[-1] = [a[-1]]
partition(a)
ans = ''
a.each{ | b | ans = "#{ans}#{b} "}
puts ans.rstrip



Measured memory_bytes: 207924
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-11;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

class Segment_Tree{
	private:
	int n;
	vi date;
	public:
	Segment_Tree(int n_){
		n=1;
		while(n<n_) n*=2;
		date=vi(2*n-1);
	}
	void Update(int k,int x){
		k+=n-1;
		date[k]+=x;
		while(k>0){
			k=(k-1)/2;
			date[k]=date[k*2+1]+date[k*2+2];
		}
	}
	int Query(int a,int b){
		a+=n-1;b+=n-1;
		int m=0;
		while(a<b){
			if(a%2==0) m+=date[a++];
			if(b%2==0) m+=date[--b];
			a/=2;b/=2;
		}
		return m;
	}
	int Open(int k){return date[k+n-1];}
};

int main(){
	int n;
	vl a,b;
	cin>>n;
	a=b=vl(n);
	for(auto &i:a) cin>>i;
	for(auto &i:b) cin>>i;
	for(int i=1;i<n;i++) a[i]+=a[i-1];
	vl c=a;
	sort(c.begin(),c.end());
	bool B=1;
	for(int i=0;i<n;i++) if(b[i]>c[i]-(i==0?0:c[i-1])) B=0;
	if(B==0) cout<<-1<<endl;
	else{
		map<ll,ll> mp;
		for(int i=0;i<n;i++) mp[c[i]]=i;
		for(int i=0;i<n;i++) a[i]=mp[a[i]];
		Segment_Tree st(n);
		ll res=0;
		for(int i=0;i<n;i++){
			res+=st.Query(a[i],n);
			st.Update(a[i],1);
		}
		cout<<res<<endl;
	}
}


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

using namespace std;

struct Paint {
  int v;
  int d;
  int c;
};

const int kMaxN = 1e5 + 11;

bool used[kMaxN][12];
vector <int> g[kMaxN];
int colors[kMaxN];
bool finalized[kMaxN];

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  int q;
  cin >> q;
  vector<Paint> paints(q);

  for (auto& p : paints) {
    cin >> p.v >> p.d >> p.c;
    p.v--;
  }

  std::reverse(paints.begin(), paints.end());

  for (const auto& cur : paints) {
    int from = cur.v;
    if (!used[from][cur.d]) {
      std::queue <pair<int, int>> bfs;
      bfs.emplace(from, cur.d);
      used[from][cur.d] = true;
      while (!bfs.empty()) {
        auto top = bfs.front();
        bfs.pop();
        if (!finalized[top.first]) {
          colors[top.first] = cur.c;
          finalized[top.first] = true;
        }
        if (top.second == 0) {
          continue;
        }

        for (auto to : g[top.first]) {
          if (!used[to][top.second - 1]) {
            bfs.emplace(to, top.second - 1);
            used[to][top.second - 1] = true;
          }
        }
      }
    }
  }

  for (int i = 0; i < n; i++) {
    cout << colors[i] << "\n";
  }
  cout << endl;

  return 0;
}

Measured memory_bytes: 12772
n, a, b = map(int, input().split())
MOD = 10**9 + 7

u = [1]
d = [1]
c = [1]
for i in range(1, b+1):
    u.append(u[-1] * (n-i+1) % MOD)
    d.append(d[-1] * i % MOD)
    # c.append(u[-1] // d[-1] % MOD)
    c.append(u[-1] * pow(d[-1], MOD-2, MOD) % MOD)

print((pow(2, n, MOD) - c[a] - c[b] - 1) % MOD)

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

int main() {
	string s; cin >> s;
	
	int ans = 0, cnt = 0;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T') {
			cnt++;
			ans = max(ans, cnt);
		}
		else cnt = 0;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
const ll INF=1e9+7;
const ll N = 100002;
string s,ans,A="(",B=")";
ll h=0,m=0,n;
stack<int> t;

int main(){
	cin>>n>>s;
	FOR(i,0,s.size()){
		if(s[i]=='('){
			t.push(1);
		}else{
			if(t.size()==0){
				m++;
			}else{
				t.pop();
			}
		}
	}
	h=t.size();
	FOR(i,0,m){
		ans+=A;
	}
	ans+=s;
	FOR(i,0,h){
		ans+=B;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    String s = in.readLine();
    int countZero = 0;
    for(int i=0; i<s.length(); i++) {
      if(s.charAt(i)=='0')
        countZero++;
    }
    System.out.println(countZero<s.length()-countZero?countZero*2:(s.length()-countZero)*2);
  }
}

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

int main(){
  int N;
  cin>>N;
  vector<long> vec(N);
  for(int i=0;i<N;i++)
    cin>>vec.at(i);
  sort(vec.begin(),vec.end());
  bool finished=false;
  for(int i=1;i<N;i++){
  	if(vec.at(i)==vec.at(i-1)){
      finished=true;
      break;
    }
  }
  if(finished==true)
    cout<<"NO"<<endl;
  else
    cout<<"YES"<<endl;
}

Measured memory_bytes: 1792
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.*;
 
public class Main {
 
    void solve() throws IOException {
        int N = ni();
        int K = ni();
        HashMap<Integer,Integer> count = new HashMap<>();
        for (int i = 0; i < N; i++) {
            int  a = ni();
            count.putIfAbsent(a, 0);
            count.put(a, count.get(a) + 1);
        }
        PriorityQueue<Integer> values = new PriorityQueue<>();
        for (Integer v : count.values()) {
            values.add(v);
        }
        long ans = 0;
        while(values.size()>K){
            ans += values.remove();
        }
        out.println(ans);
    }

    final int mod = 1000000007;
    final BigInteger MOD = BigInteger.valueOf(mod);

    int mul(int x, int y){
        int val = (int)((x * 1L * y) % mod);
        return val>=0 ? val : val+mod;
    }
    int add(int x, int y) {
        x += y;
        if(x < 0) x += mod;
        if(x>=mod) x -= mod;
        return x;
    }
    int sub(int x, int y){
        x = add(x,mod-y);
        if(x < 0) x += mod;
        if(x>=mod) x -= mod;
        return x;
    }
    String ns() throws IOException {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine(), " ");
        }
        return tok.nextToken();
    }
 
    int ni() throws IOException {
        return Integer.parseInt(ns());
    }
 
    long nl() throws IOException {
        return Long.parseLong(ns());
    }
 
    double nd() throws IOException {
        return Double.parseDouble(ns());
    }
 
    String[] nsa(int n) throws IOException {
        String[] res = new String[n];
        for (int i = 0; i < n; i++) {
            res[i] = ns();
        }
        return res;
    }
 
    int[] nia(int n) throws IOException {
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = ni();
        }
        return res;
    }
 
    long[] nla(int n) throws IOException {
        long[] res = new long[n];
        for (int i = 0; i < n; i++) {
            res[i] = nl();
        }
        return res;
    }
 
    static BufferedReader in;
    static PrintWriter out;
    static StringTokenizer tok;
 
    public static void main(String[] args) throws IOException {
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        tok = new StringTokenizer("");
        Main main = new Main();
        main.solve();
        out.close();
    }
}

Measured memory_bytes: 67400
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
using namespace std;
const int mod = 1000000007;
#define ll long long

int main()
{
	char s; cin >> s;
	if (s == 'a' || s == 'i' || s == 'u' || s == 'o' || s == 'e') {
		cout << "vowel" << endl;
	}
	else cout << "consonant" << endl;
}

Measured memory_bytes: 256
n = int(input())
*a, = sorted(map(int, input().split()))

ma = a[-1]

*b, = sorted((min(x, ma - x), x) for x in a[:-1])
_, r = b[-1]

print(ma, r)

"""
cmb(12,6) > cmb(12,5) > cmb(11,5)

cmb(n,r) = cmb(n-1,r) + cmb(n-1,r) > cmb(n-1,r)
rを決めたとき、nはできるだけ大きい方がよい=ma

cmb(ma,r)で最大となるもの
r=ma//2
"""


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

using namespace std;

int main(){
  int N;
  cin >> N;
  if( N%10 == 3){
    cout << "bon" << endl;
  }
  
  else if (N%10 == 0 || N%10 == 1 || N%10 == 6|| N%10 == 8){
    cout << "pon" << endl;
  }
  else{
    cout << "hon" << endl;
  }
  
}

Measured memory_bytes: 3548
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
long long n,m,r[200001]={0},B[200001],a,b,c,z=0;
vector<pair<int,int>> A[200001];
int search(int x){
    r[x]=1;
    for(auto i:A[x]){
        if(r[i.first]&&B[x]+i.second!=B[i.first]){z=1;return 0;}
        if(!r[i.first]) B[i.first]=B[x]+i.second,search(i.first);
    }
}
int main(){
    cin>>n>>m;
    rep(i,m)rep(j,3) cin>>a>>b>>c,A[a].push_back(make_pair(b,c)),A[b].push_back(make_pair(a,-c));
    B[1]=0;
    rep(i,n) search(i);
    if(z) cout<<"No";
    else cout<<"Yes";
}

Measured memory_bytes: 22492
from random import randint
import sys
input = sys.stdin.readline


def main(D, C, S):
    for _ in range(D):
        print(randint(1, 26))


if __name__ == '__main__':
    D = int(input())
    C = [int(i) for i in input().split()]
    S = [[int(i) for i in input().split()] for j in range(D)]
    main(D, C, S)


Measured memory_bytes: 77944
#include <iostream>
#include <string>
#include <algorithm>
#include <utility>
#include <iomanip>
#include <functional>
#include <queue>
#include <stack>
#include <map>
#include <vector>
#include <cmath>
#include <cctype>
#include <cstdio>
#define ll long long
#define INF 1000000000000000001
#define MOD 1000000007
using namespace std;

ll power(ll x, ll n){
    if(n==0){
        return 1;
    }else{
        ll temp = power(x,n/2);
        temp *= temp;
        temp %= MOD;
        if(n%2==1){
            return (x*temp)%MOD;
        }else{
            return temp;
        }
        
    }
}


ll kaijo[1000000];
ll kaijo_gyaku[1000000];

ll combi(ll a, ll b){
    ll temp = kaijo_gyaku[b]*kaijo_gyaku[a-b];
    temp %= MOD;
    temp *= kaijo[a];
    temp %= MOD;
    return temp;
}

int main(){
    ll N,A,B,C;
    cin >> N >> A >> B >> C;


    kaijo[0]=1;
    kaijo_gyaku[0]=1;
    for(ll i=1; i<1000000; i++){
        kaijo[i] = kaijo[i-1]*i;
        kaijo[i]%=MOD;
    }
    
    for(int i=0; i<1000000; i++){
        kaijo_gyaku[i] = power(kaijo[i],MOD-2);
    }
    

    ll p1 = (power(A+B,MOD-2)*A)%MOD;
    ll p2 = (power(A+B,MOD-2)*B)%MOD;
    

    ll onetime=(100*power(A+B,MOD-2))%MOD;
    
    ll ans = 0;
    
    
    for(ll i=0; i<N; i++){
        ll temp = (power(p1,N)*power(p2,i))%MOD;
        temp *= combi(N+i-1,i);
        temp  %= MOD;
        temp *= N+i;
        temp %= MOD;
        
        ans += temp;
        ans%=MOD;
        
        temp = (power(p2,N)*power(p1,i))%MOD;
        temp *= combi(N+i-1,i);
        temp %= MOD;
        temp *= N+i;
        temp %=MOD;
        
        ans += temp;
        ans%=MOD;
    }
    
    ans *= onetime;
    ans %=MOD;
    cout<<ans<<endl;

    return 0;
}





Measured memory_bytes: 15872
#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define COUT(x) cout<<(x)<<"\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define REP(i, n) for(int i=0;i<n;i++)
#define YES(x) cout<<(x?"YES":"NO")<<"\n"
#define Yes(x) cout<<(x?"Yes":"No")<<"\n"
#define dump(x) cout<<#x<<" = "<<(x)<<"\n"
#define endl "\n"
using G = vector<vector<int>>;
using M = map<int,int>;
using P = pair<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int,vector<int>,greater<int>>;
using V = vector<int>;
using ll = long long;
using edge = struct { int to; int cost; };
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int main() {
  IOS;
  int n; cin >> n;
  vector<int> a(n),b(n);
  M m;
  REP(i,n) {
    int a,b;
    cin >> a >> b;
    m[b] += a;
  }
  int sum = 0;
  for (auto x = m.begin(); x != m.end(); x++) {
    int k = x->first;
    int v = x->second;
    sum += v;
    if (k < sum) {
      COUT("No");
      return 0;
    }
  }
  COUT("Yes");
  return 0;
}


Measured memory_bytes: 14192
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    a = IR(n)
    if a[0] != 0:
        print(-1)
        return
    ans = 0
    tmp = 0
    for i in a:
        if tmp + 1 == i:
            tmp += 1
            continue
        if tmp >= i:
            ans += tmp
            tmp = i
        else:
            print(-1)
            return
    print(ans + tmp)
    return


#main
if __name__ == '__main__':
    solve()


Measured memory_bytes: 52060
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
const ll inf = numeric_limits<ll>::max()/3;
const ll mod = 1e9+7;

const int MAX_N = 100010;

int uf[MAX_N];
ll sz[MAX_N];

void init(int n){
  for(int i = 0;i < n;++i){
    uf[i] = -1;
    sz[i] = 1;
  }
}

int find(int n){
  if(uf[n] < 0){
    return n;
  }else{
    return uf[n] = find(uf[n]);
  }
}

bool same(int a,int b){
  return find(a) == find(b);
}

ll unite(int a,int b){
  int pa = find(a);
  int pb = find(b);
  
  if(pa == pb) return 0LL;

  ll merged = sz[pa] * sz[pb];
  if(uf[pa] < uf[pb]){
    uf[pb] = pa;
    sz[pa] += sz[pb];
  }else if(uf[pa] > uf[pb]){
    uf[pa] = pb;
    sz[pb] += sz[pa];
  }else{
    uf[pb] = pa;
    --uf[pa];
    sz[pa] += sz[pb];
  }
  return merged;
}

int main(void) {
  int n,m;
  cin >> n >> m;
  init(n);
  vector< P > q;
  for(int i = 0;i < m;++i){
    int a,b;
    cin >> a >> b;
    q.push_back(P(a,b));
  }
  reverse(q.begin(),q.end());
  vector< ll > delta;
  for(int i = 0;i < m;++i){
    delta.push_back(unite(q[i].first,q[i].second));
  }
  reverse(delta.begin(),delta.end());
  ll now = 0;
  for(int i = 0;i < m;++i) {
    now += delta[i];
    cout << now << endl;
  }
  return 0;
}


Measured memory_bytes: 4212
#include "bits/stdc++.h"
using namespace std;
struct valt{
	long long p0, p1, sum1, mdiff;
	valt(){
		p0 = 0;
		p1 = 0;
		sum1 = 0;
		mdiff = 0;
	}
	valt(long long a, long long b){
		p0 = a; p1 = b;
		sum1 = p1;
		mdiff = p1 - p0;
	}
	valt operator + (valt other){
		valt ans;
		ans.sum1 = sum1 + other.sum1;
		ans.mdiff = max(mdiff, other.mdiff);
		return ans;
	}
};
const int delta = 2;
struct tree{
	long long values[delta];
	long long sum1;
	void add(valt a){
		sum1 += a.sum1;
		for(int e = 0; e < delta; e++){
			if(a.mdiff > values[e]){
				for(int f = delta-1; f > e; f--){
					values[f] = values[f-1];
				}
				values[e] = a.mdiff;
				break;
			}
		}
	}
	void rem(valt a){
		sum1 -= a.sum1;
		for(int e = 0; e < delta; e++){
			if(a.mdiff == values[e]){
				for(int f = e; f < delta-1; f++){
					values[f] = values[f+1];
				}
				break;
			}
		}
	}
	valt getFull(){
		valt ans;
		ans.sum1 = sum1;
		ans.mdiff = values[0];
		return ans;
	}
};
const int maxn = 100100;
vector<int> tr[maxn];
tree mtree[maxn];
char s[maxn];
int ty[maxn], ms[maxn];
long long d[2][maxn];
void add(int cur, valt val){
	mtree[cur].add(val);
}
void rem(int cur, valt val){
	mtree[cur].rem(val);
}
void calc(int cur, int par, int sons){
	int ru = par != -1;
	int letdown = max(sons - 1, 0);
	valt incur = mtree[cur].getFull();
	d[0][cur] = sons + letdown + incur.sum1 - incur.mdiff + ((ty[cur] + letdown + ru)%2);
	d[1][cur] = 2 * sons + incur.sum1 + ((ty[cur] + sons + ru)%2);
}
void solve(int cur, int par){
	int sons = 0;
	for(int nxt : tr[cur]){
		if(nxt == par) {
			continue;
		}
		solve(nxt, cur);
		valt pnxt = valt(d[0][nxt], d[1][nxt]);
		add(cur, pnxt);
		sons++;
	}
	ms[cur] = sons;
	calc(cur, par, sons);
}
void fix(int cur, int par){
	if(par != -1){
		valt before = valt(d[0][cur], d[1][cur]);

		rem(par, before);
		calc(par, cur, tr[par].size() - 1);

		add(cur, valt(d[0][par], d[1][par]));
		calc(cur, -1, tr[cur].size());

		add(par, before);

		calc(par, -1, tr[par].size());
	}
	for(int nxt : tr[cur]){
		if(nxt == par) continue;
		fix(nxt, cur);
	}
}
int deg[maxn];
set<int> pk[maxn], stl;
int main(){
	int n;
	scanf("%d", &n);
	for(int e = 0; e < n - 1; e++){
		int x, y; scanf("%d %d", &x, &y); x--; y--;
		pk[x].insert(y);
		pk[y].insert(x);
		deg[x]++; deg[y]++;
	}
	scanf("%s", s);
	for(int e = 0; e < n; e++) ty[e] = s[e] == 'W';
	queue<int> q;
	for(int e = 0; e < n; e++) stl.insert(e);
	for(int e = 0; e < n; e++) if(deg[e] == 1 && ty[e] == 0) q.push(e);
	while(!q.empty()){
		int u = q.front(); q.pop();
		stl.erase(u);
		for(int v : pk[u]){
			deg[v]--;
			pk[v].erase(u);
			if(deg[v] == 1 && ty[v] == 0) q.push(v);
		}
		pk[u].clear();
	}
	if(stl.empty()){
		cout << 0 << endl;
		return 0;
	}
	int rt = *(stl.begin());
	for(int v : stl){
		for(int u : pk[v]){
			tr[v].push_back(u);
		}
	}
	solve(rt, -1);
	fix(rt, -1);
	long long ans = 1ll<<60;
	for(int v : stl) ans = min(ans, d[0][v]);
	cout << ans << endl;
    return 0;
}


Measured memory_bytes: 38016
#include <stdio.h>
#include <string.h>

int main()
{
	char str[101];
	scanf("%s", str);
	int length = strlen(str);
	int count = 0;
	
	for(int i = 0; i < length / 2; i++){
		if(str[i] != str[length - i - 1]){
			count = count + 1;
		}
	}
	
	printf("%d\n", count);
	
	return 0;
}

Measured memory_bytes: 128
def euc(a,b):
  if b>a:
    return euc(b,a)
  res = a%b
  if res==0:
    return b
  else:
    return euc(b,res)

B,C = map(lambda x: int(x),input().split())
print(int(B*C/euc(B,C)))

Measured memory_bytes: 3060
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
f = [0]*n
g = [0]*n
for i in range(n):
  f[i] = a[i] ^ a[(i+1)%n]
  g[i] = b[i] ^ b[(i+1)%n]

def KMP(S, W):
    ls, lw = len(S), len(W)
    m, i = 0, 0
    T = _KMP_table(W)
    res = list()
    while m + i < ls:
        if W[i] == S[m + i]:
            i += 1
            if i == lw:
                res.append(m)
                m += i - T[i]
                if i > 0:
                    i = T[i]
        else:
            m += i - T[i]
            if i > 0:
                i = T[i]
    return res


def _KMP_table(W):
    W += ['$']
    lw = len(W)
    T = [0] * lw
    T[0] = -1
    i, j = 2, 0
    while i < lw:
        if W[i - 1] == W[j]:
            T[i] = j + 1
            i += 1
            j += 1
        elif j > 0:
            j = T[j]
        else:
            T[i] = 0
            i += 1
    return T
res = KMP(f*2, g)
for x in res:
  if x < n:
    print(x, a[x]^b[0])

Measured memory_bytes: 41404
import numpy as np 
import sys 

readline = sys.stdin.readline

N, K = map(int, readline().split())
A = list(map(int, readline().split()))

# 愚直にやると計算量O(K)でTLEになる
# 同じ街にいったら操作打ち切りで配列を完結させる

# Teleport順の配列を作る
teleport = {1: True}
next_town = 1
roop_exist = False
for i in range(K):
    next_town = A[next_town - 1] # next_townがintで与えられる
    try: # 辞書を使用してO[1]で判定する
        teleport[next_town]
        dupulicate_town = next_town
        # 辞書をリストに変換
        teleport = list(teleport.keys())
        dupulicate_index = teleport.index(dupulicate_town)
        dupulicate_list = teleport[dupulicate_index:]
        roop_exist = True
        break
    except KeyError:
        teleport[next_town] = True


# 最後の処理の前にリストに変換してしまう
if not roop_exist:
    teleport = list(teleport.keys())

if len(teleport) - 1 == K:
    print(teleport[-1])
else: # ループに入る場合
    consumption = len(teleport) - 1
    roop_num = K - consumption
    roop_index = roop_num % len(dupulicate_list)
    if roop_index == 0:
        print(dupulicate_list[-1])
    else:
        print(dupulicate_list[roop_index - 1])



Measured memory_bytes: 50776
p = 1000000007
n, m = (int(x) for x in input().split())
seq = [1 for i in range(n+1)]
for i in range(m):
    a = int(input())
    seq[a] = 0
ans = 1
for i in range(2,n+1):
    if seq[i] == 0:
        continue
    seq[i] = (seq[i-1] + seq[i-2]) % p
print(seq[-1])

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

int main(){ 
  string s;
  cin >> s;
  int n = sz(s);
  string s1, s2;
  if (n % 2 == 0) {
    s1 = s.substr(0,n/2);
    s2 = s.substr(n/2,n/2);
  } else {
    s1 = s.substr(0,n/2);
    s2 = s.substr((n+1)/2,n/2);
  }
  reverse(s2.begin(), s2.end());
  int res = 0;
  for (int i = 0; i < n/2; i++) {
    if (s1[i] != s2[i]) res++;
  }
  cout << res << endl;
  return 0;
} 

Measured memory_bytes: 256
n,q = map(int,input().split())
s = input()
count = 0
index = [0 for i in range(n)]
for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        count += 1
    index[i+1] = count
L = []
R = []
for i in range(q):
    l,r = map(int,input().split())
    L.append(l)
    R.append(r)
for i in range(q):
    print(index[R[i]-1]-index[L[i]-1])

Measured memory_bytes: 14372
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define leading zero str.erase(0, min(str.find_first_not_of('0'), str.size()-1));
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
string text="abcdefghijklmnopqrstuvwxyz";
const int maxn=1e6+7;
//        .--------------.
//        | Try First One|
//        '--------------'
//                |     .--------------.
//                |     |              |
//                V     V              |
//              .--------------.       |
//              |      AC.     |<---.  |
//              '--------------'    |  |
//              (True)|  |(False)   |  |
//           .--------'  |          |  |
//           |           V          |  |
//           |  .--------------.    |  |
//           |  |   Try Again  |----'  |
//           |  '--------------'       |
//           |                         |
//           |  .--------------.       |
//           '->| Try Next One |-------'
//              '--------------'
ll bin_pow(ll a,ll b,ll m)
{
    ll res=1;
    a%=m;
    while(b>0)
    {
        if(b&1)
            res=res*a%m;
        b>>=1;
        a=a*a%m;
    }
    return res;
}
bool miller_rabin(ll d,ll n)
{
    ll a=2+rand()%(n-4);
    ll x=bin_pow(a,d,n);
    if(x==1 || x==n-1)
        return true;
    while(d!=n-1)
    {
        x=(x*x)%n;
        d*=2;
        if(x==1)
            return false;
        if(x==n-1)
            return true;
    }
    return false;
}
bool prime(ll n,ll k)
{
    if(n==1 || n==4)
        return false;
    if(n<=3)
        return true;
    ll d=n-1;
    while(d%2==0)
        d/=2;
    for(int i=0; i<k; i++)
    {
        if(!miller_rabin(d,n))
            return false;
    }
    return true;
}
int n;
string s;
ll ans = 0;

void solve(ll x,ll y){
    if(x==n+1){
        ans += y;
        return;
    }
    ll cur = 0;
    for(ll i=x;i<=n;i++){
        cur = (10*cur) + (s[i]-'0');
        solve(i+1,y+cur);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin>>n;
    ll a[n+2];
    for(int i=0;i<n;i++)cin>>a[i];
    ll sum=0;
    ll cnt=0;
    ll ans=1<<18;
    for(int i=0;i<n;i++){
        sum+=a[i];
        if(i%2==0){
            if(sum<=0){
                cnt+=abs(sum)+1;
                sum=1;
            }
        }
        else{
            if(sum>=0){
                cnt+=abs(sum)+1;
                sum=-1;
            }
        }
    }
    sum=0;
    ll cnt1=0;
    for(int i=0;i<n;i++){
        sum+=a[i];
        if(i%2==0){
            if(sum>=0){
                cnt1+=abs(sum)+1;
                sum=-1;
            }
        }
        else{
            if(sum<=0){
                cnt1+=abs(sum)+1;
                sum=1;
            }
        }
    }
    cout<<min(cnt,cnt1)<<endl;
}


Measured memory_bytes: 1024
import java.io.*;
import java.util.Scanner;


public class Main {

	private static Scanner sc;
	private static Printer pr;

	private static void solve() {
		char[] s = sc.next().toCharArray();

		int[] cnt = new int[26];
		cnt[s[0] - 'A']++;
		cnt[s[1] - 'A']++;
		cnt[s[2] - 'A']++;
		cnt[s[3] - 'A']++;

		for (int i = 0; i < 26; i++) {
			if (cnt[i] != 0 && cnt[i] != 2) {
				pr.println("No");
				return;
			}
		}
		
		pr.println("Yes");
	}

	// ---------------------------------------------------
	public static void main(String[] args) {
		sc = new Scanner(System.in);
		pr = new Printer(System.out);
			
		solve();
			
		pr.close();
		sc.close();
	}

	static class Printer extends PrintWriter {
		Printer(OutputStream out) {
			super(out);
		}
	}
}


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

#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

using ll = long long;
using P = pair<int, int>;

int main() {
  int n;
  cin >> n;
  vector<int> l(n);
  rep(i, n) cin >> l[i];
  sort(l.begin(), l.end());
  int result = 0;
  for (int i = 0; i < n - 2; ++i) {
    int a = l[i];
    for (int j = i + 1; j < n - 1; ++j) {
      int b = l[j];
      for (int k = j + 1; k < n; k++) {
        int c = l[k];
        if ((a < b + c) && (b < c + a) && (c < a + b)) {
          result++;
        }
      }
    }
  }
  cout << result << endl;

  return 0;
}


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

class Main {
	static BufferedReader jvin = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter jvout = new PrintWriter(System.out);
	
	static int MOD = (int)1E9+7;
	
	public static void main(String[] args) throws IOException {
		Main instance = new Main();
		instance.passStaticVar();
	}

	long fact(int n) {
		long res = 1;
		for (int i = 1; i <= n; ++i)
			res = (res*i)%MOD;
		return res;
	}

	public void passStaticVar() throws IOException {
		String[] t = jvin.readLine().split(" ");
		int N = Integer.parseInt(t[0]), M = Integer.parseInt(t[1]);
		long fN = fact(N), fM = fact(M), res = 0;
		if (N == M) 
			res = (fN*fM*2)%MOD;
		else if (N == M+1 || M == N+1)
			res = (fN*fM)%MOD;
		jvout.println(res);
		jvout.flush();
	}
}


Measured memory_bytes: 21204
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string.h>
#include <cstdio>
#include <tuple>
using namespace std; using ll = long long; using ld = long double;  using pll = pair<ll, ll>;
using vl = vector<ll>; using vll = vector<vl>; using vpll = vector<pll>;
using vs = vector<string>; using tll = tuple<ll, ll, ll>; using vtll = vector<tll>;
const ld PI = 3.1415926535897932;
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define rep1(n) for(ll i=0;i<n;++i)
#define rep2(i,n) for(ll i=0;i<n;++i)
#define rep3(i,a,b) for(ll i=a;i<b;++i)
#define rep4(i,a,b,c) for(ll i=a;i<b;i+=c)
#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define mp make_pair
#define mt make_tuple
void in() {}
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail>
void debug_out(Head h, Tail... t) {
	cerr << " " << h;
	if (sizeof...(t) > 0) cerr << " :";
	debug_out(t...);
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> vec) {
	for (size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
	return os;
}
ll ctoi(char c) {
	switch (c) {
	case '0': return 0; case '1': return 1; case '2': return 2;
	case '3': return 3; case '4': return 4; case '5': return 5;
	case '6': return 6; case '7': return 7; case '8': return 8;
	case '9': return 9;  default: return 0;
	}
}
bool pairCompare(const pll firstElof, pll secondElof)
{
	return firstElof.first > secondElof.first;
}
//**Snippetリスト**//
//rep, vin, all, iteLoop, bitSearch, bitList, nod//
//gcdlcm, isPrime, eratos, primeFactorize, Npow, combination, divisor, modinv,  digitDP//
//dfs, bfs, dijkstra, WarshallFloyd, BellmanFord, UnionFind, Kruskal ,RMQ, LCA//
ll i, j, k, l; ll N, M, K, H, W, L, X, Y, Z, R, Q;
ll MOD = 1000000007; ll INF = 1LL << 60; ll ans = 0; ll z = 0, o = 1;
vl flag; vll path; vl D;
//***********//
ll nod(ll F) { return log10(F); }

int main() {
	cin >> N;
	vl A(N);
	ans = 1;
	for (i = 0; i < N; i++) {
		cin >> A[i];
	}
	sort(A.begin(), A.end());
	for (i = 0; i < N; i++) {
		if (nod(ans) + nod(A[i]) >= 18 && 1000000000000000000/ans!=A[i]) {
			cout << -1;
			exit(0);
		}
		else if (nod(ans) + nod(A[i]) == 17 && ans * A[i] > 1000000000000000000) {
			cout << -1;
			exit(0);
		}
		ans *= A[i];
	}
	cout << ans;
}

Measured memory_bytes: 4708
#include<string>
#include<string.h>
#include<map>
#include<set>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdio> 
using namespace std;
int main(){
   int x;
   cin>>x;
   int a[x+5];
   for(int i=0;i<x;i++)
   cin>>a[i];
   sort(a,a+x);
   cout<<a[x-1]-a[0];
   system("pause");
   return 0;
}

Measured memory_bytes: 504
from collections import Counter
import bisect

def main():
    n = int(input())
    A = list(map(int,input().split()))

    A.sort()
    counter = Counter(A)
    ch = [True] * n

    beki = []
    c = 1
    for _ in range(31):
        beki.append(c)
        c *= 2

    # print(counter)
    ans = 0
    for i in range(n-1,-1,-1):
        a = A[i]
        j = bisect.bisect_right(beki,a)
        t = beki[j] - a
        # print(t,a)
        if t == a:
            m = counter[a]//2
        elif t < a:
            m = min(counter[a],counter[t])

        counter[a] -= m
        counter[t] -= m
        ans += m
    print(ans)

main()

Measured memory_bytes: 55996
N,K = [int(s) for s in input().split()]
temp = 0
if K % 2 == 0 :
  a = int(N//K)
  b = 0
  temp = int(K/2)
  while True:
    if temp > N:
      break
    b += 1
    temp += K
  print(a**3+b**3)
else:
  a = int(N//K)
  print(a**3)

Measured memory_bytes: 3064
def build_combination(n, mod):
    def cmb(n, r):
        if r < 0 or n < r:
            return 0
        return (((invs[r] * invs[n - r]) % mod) * fact[n]) % mod

    fact = [1] * (n + 1)
    for x in range(2, n + 1):
        fact[x] = x * fact[x - 1] % mod

    invs = [1] * (n + 1)
    invs[n] = pow(fact[n], mod - 2, mod)
    for x in range(n - 1, 0, -1):
        invs[x] = invs[x + 1] * (x + 1) % mod

    return cmb


def find(a):
    """重複する数値のindexのペアを返す"""
    n = len(a)
    checked = [-1] * (n + 1)
    for i, x in enumerate(a):
        if checked[x] != -1:
            return checked[x], i
        else:
            checked[x] = i
    raise ValueError


def main():
    mod = 10 ** 9 + 7

    n = int(input())
    *a, = map(int, input().split())

    cmb = build_combination(n + 1, mod)

    li, ri = find(a)

    for k in range(1, n + 2):
        ret = (cmb(n + 1, k) - cmb(n + 1 - (ri - li + 1), k - 1)) % mod  # mod忘れ
        print(ret)
        # for j in range(k + 1):
        #     ret -= cmb(li, j) * cmb(n - ri, k - j - 1)
        # PxQxRのPRからk-1個とる
        # PRの取り方の総和を求めるより、区間PRに含まれる総個数からk-1個選ぶ方法を考える


if __name__ == '__main__':
    main()


Measured memory_bytes: 19428
N = int(input())
p = [True] * 55555

p[0] = False
p[1] = False
for i in range(2, int(55555**0.5)):
    for j in range(i*2, 55555, i):
        if j % i == 0:
            p[j] = False

p = [str(i) for i, f in enumerate(p) if f == True and i % 5 == 1][:N]
print(" ".join(p))

Measured memory_bytes: 3444
#include <stdio.h>
#include <stdlib.h>
int main()
{
 int n,i;
 int *a;
 scanf("%d",&n);
 a=(int*)malloc(sizeof(int)*n);
 for(i=0;i<n;i++)
  scanf("%d",&a[i]);
 for(i=n-1;i>0;i--)
  printf("%d ",a[i]);
 printf("%d\n",a[0]);
 return 0;
}


Measured memory_bytes: 2100
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T> bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}
template<class T> T div_floor(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>0 ? (a-1)/b+1 : a/b;
}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod * mod;
constexpr int MAX = 100010;

int n;
tuple<lint, int, int> p[MAX*2];
lint sum = 0;
int cnt[4] = {0, 0, 0, 0}, state[MAX];

void add(int i){
    lint x; int k, v;
    tie(x, k, v) = p[i];
    --cnt[state[v]];
    state[v] ^= 1<<k;
    ++cnt[state[v]];
    sum += x;
}

void del(int i){
    lint x; int k, v;
    tie(x, k, v) = p[i];
    --cnt[state[v]];
    state[v] ^= 1<<k;
    ++cnt[state[v]];
    sum -= x;
}

int main(){
    scanf("%d", &n);
    rep(i, n){
        lint a, b;
        scanf("%lld%lld", &a, &b);
        p[i*2] = make_tuple(a, 0, i);
        p[i*2+1] = make_tuple(b, 1, i);
    }
    sort(p, p+2*n);

    memset(state, 0, sizeof(state));
    cnt[0] = n;
    rep(i, n) add(i);

    if(cnt[0] || cnt[1] == n || cnt[2] == n) printf("%lld\n", sum);
    else{
        del(n-1); add(n);
        if(cnt[0] || cnt[1] == n || cnt[2] == n) printf("%lld\n", sum);
        else{
            lint ans = INF;
            del(n); add(n+1);
            chmin(ans, sum);
            del(n-2); del(n+1); add(n-1); add(n);
            chmin(ans, sum);
            printf("%lld\n", ans);
        }
    }
}

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

using namespace std;

int main(){
    int N;
    long long int ans=0;
    cin >> N;
    vector<long long int> A(N+1),B(N);
    for(int i=0;i<=N;i++){
        cin >> A[i];
    }
    for(int i=0;i<N;i++){
        cin >> B[i];
    }

    for(int i=0;i<N;i++){
        if((A[i]+A[i+1])<=B[i]){
            ans += A[i] + A[i+1];
            A[i+1] = 0;
        }

        if(A[i]<=B[i] && (A[i]+A[i+1])>B[i]){
            ans += B[i];
            A[i+1] -= (B[i] - A[i]);
        }

        if(B[i]<A[i]){
            ans += B[i];
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 1792
# Union Find
#0オリジン以下注意

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
    
def unite(x, y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きい方がx
        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y] #ここで集合の個数を更新している
        par[y] = x
        return True
    
#xとyが同じ集合に含まれているかどうかを判定(同じ集合にあればTrue)
def same(x, y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#初期化
#根なら-size, 子なら親の頂点
n, m = map(int, input().split())
par = [-1]*n
for i in range(m):
    a, b = map(int, input().split())
    unite(a-1, b-1)
M = 0
for i in range(n):
    M = max(M, size(i))
print(M)

################以下にコードを書く
######2次元配列が与えられたら１次元に直す必要あり

Measured memory_bytes: 77580
N,S=list(map(int, input().split())) 
tele=list(map(int, input().split())) 
for i in range(N):
    tele[i]-=1
loop=[0]*N
order=[]
now=0
cnt=0
while loop[now]!=1:
    loop[now]=1
    order.append(now)
    cnt+=1
    now=tele[now]

looptime=0
i=0
for i in range(cnt):
    if order[i]==now:
        looptime=cnt-i
        break
mod=(S-i)%looptime
if S-i<0:
    print(order[S]+1)
else:
    if (mod+i==len(order)):
        print(order[i]+1)
    else:
        print(order[mod+i]+1)

Measured memory_bytes: 95256
N, M, P = map(int, input().split())

ABC = []
for _ in range(M):
    a, b, c = map(int, input().split())
    ABC.append((a - 1, b - 1, P - c))

inf = float("inf")
d = [inf] * N
d[0] = 0

# Bellman-Ford
for i in range(N):
    for a, b, c in ABC:
        if d[b] <= d[a] + c:
            continue
        d[b] = d[a] + c
ans = d[N - 1]
for i in range(N):
    for a, b, c in ABC:
        if d[b] <= d[a] + c:
            continue
        d[b] = -inf
if ans != d[N - 1]:
    print(-1)
else:
    print(max(0, -d[N - 1]))


Measured memory_bytes: 48444
// https://atcoder.jp/contests/dp/tasks/dp_d

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define mod 1000000007
#define gcd __gcd
#define inf INT_MAX
#define INF LLONG_MAX
#define minf INT_MIN
#define MINF LLONG_MIN
#define pb push_back
#define all(v) v.begin(),v.end()
#define print(v) for(auto x:v) cout<<x<<" "; cout<<"\n";
#define printn(v) for(auto x:v) cout<<x<<"\n";
#define F first
#define S second
#define mp make_pair

ll dp[101][100001];
vector<int>wt, val;

ll knapsack(int n, int w) {
	if (n == 0 || w == 0) return 0;

	if (dp[n][w] != -1) return dp[n][w];

	if (wt[n] > w) return dp[n][w] = knapsack(n - 1, w);
	else return  dp[n][w] = max(val[n] + knapsack(n - 1, w - wt[n]), knapsack(n - 1, w));
}

int32_t main() {
	fastio;
	int n, w;
	cin >> n >> w;
	memset(dp, -1, sizeof dp);
	wt.resize(n + 1, 0);
	val.resize(n + 1, 0);
	for (int i = 1; i <= n; i++) cin >> wt[i] >> val[i];
	cout << knapsack(n, w) << endl;
}

Measured memory_bytes: 82484
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
#define repr(i, n) for (int i = (int)n - 1; i >= 0; --i)
#define ALL(a) (a).begin(), (a).end()
const ll mod = 1e9 + 7;

int r, s, p;

int chage(char c) {
  if (c == 's')
    return r;
  else if (c == 'p')
    return s;
  else
    return p;
}

int main() {
  int n, k;
  ll ans = 0;
  string t;
  cin >> n >> k >> r >> s >> p >> t;
  rep(i, k) {
    int j = i;
    char c = 'a';
    while (j < t.length()) {
      if (c != t[j]) {
        ans += chage(t[j]);
        c = t[j];
      } else {
        c = 'a';
      }
      j += k;
    }
  }
  cout << ans << endl;
  return 0;
}

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



int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
#ifdef LOCAL
	std::ifstream in("in");
	std::cin.rdbuf(in.rdbuf());
#endif

	string s;
	while(cin >> s, s != "#"){
		if(s == "north"){
			cout << 0 << endl;
			continue;
		}
		if(s == "west"){
			cout << 90 << endl;
			continue;
		}
		vector<char> d;
		for(int i = 0; i < s.size(); i++){
			if(s[i] == 'n' || s[i] == 'w'){
				d.push_back(s[i]);
			}
		}

		int n = d.size();
		ll sum = 0, q = 1LL << (n - 1);
		for(int i = 0; i < d.size() - 1; i++){
			ll x = 90 << i;
			if(d[i] == 'n') sum -= x;
			else sum += x;
		}
		if(d.back() == 'w') sum += 90LL * q;

		while(sum % 2 == 0 && q % 2 == 0){
			sum /= 2;
			q /= 2;
		}
		if(q == 1) cout << sum << endl;
		else cout << sum << "/" << q << endl;
	}

}

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

using namespace std;

int main(void)
{
	string s[3];
	for(int i=1;i<=3;i++)
		cin >> s[i-1];
	
	cout << (s[0][s[0].size()-1]==s[1][0] and s[1][s[1].size()-1]==s[2][0] ? "YES" : "NO") << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define vc vector<int>
#define um unordered_map<int,int>
#define ll long long 
#define rep(i,a,b) for(__typeof(a) i=a; i<b; i++)
#define si(a) a.size()
#define all(a) a.begin(),a.end()
#define ss(a) a.second
#define ff(a) a.first
#define M 1000000
#define pb push_back
#define repit(i,a) for(auto i=a.begin(); i!=a.end(); i++)
#define take(arr,n) for(int i=1;i<n+1;i++)cin>>arr[i]
#define out(arr,n) for(int i=0;i<n;i++)cout<<arr[i]<<' '
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define reprev(i,b,a) for(__typeof(b) i=b; i>=a; i--)
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL)
#define doublearray vector<vector<int>>
using namespace std;
ll max(ll a, ll b){ return a>b?a:b; }
ll min(ll a, ll b){ return a<b?a:b; }
ll gcd(ll a, ll b){
    if(b==0) return a;
    return gcd(b,a%b);
}
ll lcm(ll a, ll b){
    return (a*b)/gcd(a,b);
}
int main(){
  int n; cin>>n;
  cout<<(ll)ceil(n/1000.0)*1000-n<<endl;
}
  
  
  
  
  
  

Measured memory_bytes: 3708
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, e) for (int i = (int)(s); i <= (int)(e); i++)
#define printYesNo(is_ok) puts(is_ok ? "Yes" : "No");
#define SORT(v) sort(v.begin(), v.end());
#define RSORT(v) sort(v.rbegin(), v.rend());
#define REVERSE(v) reverse(v.begin(), v.end());

template <typename T>
void printlnVector(T v)
{
  rep(i, v.size())
  {
    cout << v[i] << endl;
  }
}

template <typename T>
void printVector(T v)
{
  rep(i, v.size())
  {
    cout << v[i] << " ";
  }
  cout << endl;
}

int main()
{
  string S;
  cin >> S;
  vector<string> kouho = {"AKIHABARA", "KIHABARA", "AKIHBARA", "KIHBARA", 
                          "AKIHABRA", "KIHABRA", "AKIHBRA", "KIHBRA", 
                          "AKIHABAR", "KIHABAR", "AKIHBAR", "KIHBAR", 
                          "AKIHABR", "KIHABR", "AKIHBR", "KIHBR"};
  bool is_ok = false;
  rep(i, kouho.size())
  {
    if(S == kouho[i])
      is_ok = true;
  }
  if(is_ok)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
  return 0;
}

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

int main(){
  int N, K;
  cin >> N >> K;
  char S[N+1];
  cin >> S;
  K--;
  if (S[K] == 'A') S[K] = 'a';
  else if (S[K] == 'B') S[K] = 'b';
  else if (S[K] == 'C') S[K] = 'c';
  cout << S;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int a,c,b,x,ans=0;
int main()
{
	cin>>a>>b>>c>>x;
//	cout<<a%c<<endl;
	for(int i=0;i<=a;i++)
	{
		for(int j=0;j<=b;j++)
		{
			for(int l=0;l<=c;l++)
			{
				if(500*i+100*j+50*l==x)ans++;
			}
			
		}
		
	}
	cout<<ans<<endl;
}

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

using ll = long long;
using P = pair<int, int>;

const int INF = 1e9;
const int MOD = 1e9 + 7;

// 4近傍、8近傍
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int main() {
  int N;
  cin >> N;
  int a[N];
  for (int i = 0; i < N; i++) cin >> a[i];

  sort(a, a + N);
  double ans = (a[0] + a[1]) / 2.0;
  for (int i = 2; i < N; i++) {
    ans = (ans + a[i]) / 2.0;
  }

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


Measured memory_bytes: 256
n = int(input())
h = [int(x) for x in input().split()]

dp = [float('inf')]*n

dp[0] = 0
for i in range(1,n):
    dp[i] = min(dp[i],dp[i-1]+abs(h[i]-h[i-1]))
    if i > 1:
        dp[i] = min(dp[i],dp[i-2] + abs(h[i] - h[i-2]))
print(dp[n-1])

Measured memory_bytes: 13800
package main

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

const (
	initialBufSize = 100000
	maxBufSize     = 10000000
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wt = bufio.NewWriter(os.Stdout)
)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, _ := strconv.Atoi(next())
	return i
}

func nextInts(n int) []int {
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i] = nextInt()
	}
	return slice
}

func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(next(), 64)
	return f
}

func nextFloat64s(n int) []float64 {
	slice := make([]float64, n)
	for i := 0; i < n; i++ {
		slice[i] = nextFloat64()
	}
	return slice
}

func putf(format string, a ...interface{}) {
	fmt.Fprintf(wt, format, a...)
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}

func min(nums ...int) int {
	ret := nums[0]
	for _, v := range nums {
		if v < ret {
			ret = v
		}
	}
	return ret
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, initialBufSize), maxBufSize)
	defer wt.Flush()

	n, a, b := nextInt(), nextInt(), nextInt()

	puts(min(a*n, b))
}


Measured memory_bytes: 640