akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP0(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define RREP0(i, n) for (int i = (n)-1; i >= 0; --i)
#define REP1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define RREP1(i, n) for (int i = (n); i >= 1; --i)
#define pow10(n) int(1e##n + n)

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

const int INTINF = int(1e9) + 1;
const LL LLINF = LL(1e18) + 1;
long double eps = 1.0E-14;

void solve()
{
    int N;
    cin >> N;
    int excl = 0;
    int max_k = 0;
    REP1 (k, N)
    {
        LL sum = (k * LL(k + 1)) / 2;
        if (sum >= N)
        {
            excl = sum - N;
            max_k = k;
            break;
        }
    }

    REP1 (k, max_k)
    {
        if (k != excl)
        {
            std::cout << k << endl;
        }
    }
}

int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(20);
    solve();
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1e9 + 7;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class T>
istream& operator >> (istream& is, vector<T>& v)
{
	for (auto &i : v) is >> i;
	return is;
}
template<class T>
ostream& operator<<(ostream& os, vector<T>& v)
{
	const string delimiter = "\n";
	REP(i, v.size())
	{
		os << v[i];
		if (i != v.size() - 1) os << delimiter;
	}
	return os;
}
/*--------------------template--------------------*/

struct UnionFind
{
	vector<int> par;
	UnionFind(int n) :par(n, -1) {}
	int find(int x) { return par[x] < 0 ? x : par[x] = find(par[x]); }
	void unite(int x, int y)
	{
		x = find(x); y = find(y);
		if (x == y) return;
		if (par[y] < par[x]) swap(x, y);
		if (par[x] == par[y]) par[x]--;
		par[y] = x;
		if (find(x) != find(y)) par[find(y)] = x;
	}
	int count()
	{
		int cnt = 0;
		REP(i, par.size()) if (par[i] < 0) cnt++;
		return cnt;
	}
	bool same(int x, int y)
	{
		return find(x) == find(y);
	}
};

typedef ld Weight;
struct Edge
{
	int from, to; Weight cost; char c;
	bool operator < (const Edge& e) const { return cost < e.cost; }
	bool operator > (const Edge& e) const { return cost > e.cost; }
};
typedef vector<Edge> Edges;

const ld INF = 1e9;
const ld EPS = 1e-9;

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	int n, m, k;
	while (cin >> n >> m >> k, n)
	{
		Edges es;
		REP(i, m)
		{
			int a, b; ld c; char d;
			cin >> a >> b >> c >> d;
			a--; b--;
			es.emplace_back(Edge{ a, b, c, d });
		}
		int mn = INF, mx = -1;
		ld lb = -INF, ub = INF;
		REP(lp, 300)
		{
			ld mid = (ub + lb) / 2;
			Edges tmp;
			for (auto e : es)
			{
				if (e.c == 'A') e.cost += mid;
				tmp.push_back(e);
			}
			sort(ALL(tmp));
			UnionFind uf(n);
			ld cost = 0;
			int cnta = 0;
			for (auto e : tmp)
			{
				if (uf.same(e.from, e.to)) continue;
				if (e.c == 'A')
				{
					cnta++;
				}
				cost += e.cost;
				uf.unite(e.from, e.to);
			}

			chmax(mx, cnta);
			chmin(mn, cnta);
			if (lp == 299)
			{
				if (uf.count() != 1 || (mx < k || mn > k))
				{
					cout << -1 << endl;
				}
				else
				{
					cout << ll(cost - k * mid + EPS) << endl;
				}
			}
			else if (cnta > k)
			{
				lb = mid;
			}
			else
			{
				ub = mid;
			}
		}
	}
	return 0;
}


Measured memory_bytes: 3220
#include <stdio.h>

int main() {

    char a[7];

    scanf("%s", a);

    if(a[2] == a[3]) {
        if(a[4] == a[5]) {
            printf("Yes\n");
        }
        else {
            printf("No\n");
        }
    }
    else {
        printf("No\n");
    }

    return 0;
}

Measured memory_bytes: 128
using System;
using System.Collections.Generic;
using System.Linq;

namespace ABC136C
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            var H = Console.ReadLine().Split().Select(int.Parse).ToArray();

            bool ans = true;
            int min = H[0];
            for (int i = 0; i < N - 1; i++)
            {
                if (H[i + 1] < min)
                {
                    ans = false;
                    break;
                }
                min = Math.Max(min, H[i + 1] - 1);
            }

            if (ans) Console.WriteLine("Yes");
            else Console.WriteLine("No");
            Console.ReadKey();

        }
    }
}


Measured memory_bytes: 30172
#include<iostream>
using namespace std;
int main(){
    int a, b, c;
    cin >>a>>b>>c;
    if(a<=b&&b<=c) cout<< a <<" "<< b << " "<< c <<endl;
    else if(a<=c&&c<=b) cout<< a << " "<< c << " " << b <<endl;
    else if(b<=a&&a<=c) cout<< b << " " << a <<" " << c  <<endl;
    else if(b<=c&&c<=a) cout<< b << " " << c << " "<< a <<endl;
    else if(c<=b&&b<=a) cout<< c << " " << b << " "<< a <<endl;
    else if(c<=a&&a<=b) cout<< c << " " << a << " "<< b<<endl;
    
    return 0;
}


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

int main () {
    double a, b, C;
    cin >> a >> b >> C;
    C = C*acos(-1)/180;
    double S, L, h;
    S = 0.5*a*b*sin(C);
    L = a + b + sqrt(pow(a, 2)+pow(b, 2)-2*a*b*cos(C));
    h = 2*S / a;

    printf("%f\n", S);
    printf("%f\n", L);
    printf("%f\n", h);
    return 0;
}


Measured memory_bytes: 3500
#include <stdio.h>

int cnt=0,n;

int main() {
  int q,t;
  int i,j;
  scanf("%d", &n);
  int s[n];
  for (i=0;i<n;i++) {
    scanf("%d",&s[i]);
  }
  scanf("%d",&q);
  for (i=0;i<q;i++) {
    scanf("%d",&t);
    int left=0,right=n;
    int mid=(left+right)/2;

    while(left<right){
      mid=(left+right)/2;
      if(s[mid]==t){
        cnt++;
      //  printf("t=%d\n",t);
        break;
      }
      else if(t<s[mid])right=mid;
      else left=mid+1;
    }

  }

  printf("%d\n", cnt);

  return 0;
}



Measured memory_bytes: 2144
#include <bits/stdc++.h>
using namespace std;
int64_t zero = 0;

int main() {
  int N;
  cin >> N;
  vector<int> V(N), C(N);
  for(int i = 0; i < N; i++) {
    cin >> V.at(i);
  }
  for(int i = 0; i < N; i++) {
    cin >> C.at(i);
  }
  int ans = 0;
  for(int i = 0; i < N; i++) {
    ans += max(0, V.at(i) - C.at(i));
  }
  cout << ans << endl;
}

Measured memory_bytes: 3612
mod = 10 ** 9 + 7

n = int(input())
t = tuple(map(int, input().split()))
a = tuple(map(int, input().split()))

ans = 1
for i in range(1, n - 1):
    x = t[i] if t[i] > t[i - 1] else 1
    y = a[i] if a[i] > a[i + 1] else 1
    ans = ans * max(0, min(t[i], a[i]) - max(x, y) + 1) % mod

print(ans if a[0] == t[-1] else 0)


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

int main() {
  int n;
  cin >> n;
  int s = 0, tmp = n;

  while (tmp > 0) {
    s += tmp % 10;
    tmp /= 10;
  }
  cout << (n % s == 0 ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
cin = open(0).read().split('\n')

n = int(cin[0])
a = list(map(int, cin[1].split(' ')))
q = int(cin[2])
m = list(map(int, cin[3].split(' ')))

tmp = []
for i in range(2**n):
    ret = 0
    for j in range(n):
        if (i>>j) & 1:
            ret += a[j]
    tmp.append(ret)

for mi in m:
    if mi in tmp:
        print('yes')
    else:
        print('no')


Measured memory_bytes: 43076
#include<bits/stdc++.h>
    #define ll  long long
    #define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    #define rep(i,a,b)  for(ll i=a;i<b;i++)
    #define pb push_back
    #define Max(x,y,z) max(x,max(y,z))
    #define f first
    #define s second
    #define lbd lower_bound
    #define sz(x)       (ll)x.size()
    #define pi 3.1415926536
    #define mod 1000000007
    using namespace std;
    /*void bfs(ll s, vector<vector<ll>> &adj)
    {
     dis[s]=0;B
     vis[s]=1;
     queue<ll> q;
     q.push(s);
     while(!q.empty())
     {
       ll x=q.front();
       q.pop();
       for(auto to:adj[x])
       {
           if(!vis[to])
           {dis[to]=dis[x]+1;q.push(to); vis[to]=1;}
       }
     }
    }*/
    void solve()
    {
        ll n,m,k,res=0,l=0,r=0,sum=0,z,sum1=0,cnt1=0,h,res1,c,x,y;
        cin>>n;
        ll ar[n][3];
        rep(i,0,n)
        rep(j,0,3) cin>>ar[i][j];
        ll dp[n][3];
        dp[0][0]=ar[0][0];
        dp[0][1]=ar[0][1];
        dp[0][2]=ar[0][2];
        if(n>1){
        rep(i,1,n)
        {
            dp[i][0]=max(dp[i-1][1],dp[i-1][2])+ar[i][0];
            dp[i][1]=max(dp[i-1][2],dp[i-1][0])+ar[i][1];
            dp[i][2]=max(dp[i-1][0],dp[i-1][1])+ar[i][2];
        }
        }
        cout<<Max(dp[n-1][0],dp[n-1][1],dp[n-1][2]);

        
    }
    int main()
    {   
        /*#ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
        #endif*/

        speed_up
        ll t;
        //cin>>t;
        t=1;
        while(t--)
            solve();
    }

Measured memory_bytes: 4992
/*****And nothing else matters!******/

#include<bits/stdc++.h>
using namespace std;

#define pi 3.1415926535
#define endl "\n"
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define ll long long
#define llu unsigned long long
#define setbits(x) __builtin_popcountll(x)
#define pb push_back
#define mp make_pair
#define sz(x) (int)x.size()
#define tc int test_case; cin >> test_case; while(test_case--)
#define f(i,a,n) for(int i = a ; i < n ; i++)
#define rf(i,n,a) for(int i = n-1 ; i >= a ; i--)
#define F first
#define S second
#define all(c) (c).begin(),(c).end()
#define get(a,n) f(i,0,n) cin >> a[i];
#define show(a,n) f(i,0,n) cout << a[i] << " "; cout << endl;
#define sp(x) fixed << setprecision(10) << x
#define fast ios:: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define trace(x) cerr << '>' << #x << ':' << (x) << "\n"
#define trace2(x,y) cerr<< '>' << #x << ':' << (x) << " | " << #y << ':' << (y) << "\n"
#define trace3(a,b,c) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define trace4(a,b,c,d) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"

typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<pii,int> ppi;
typedef vector<pii> vpi;
typedef map<int,int> mii;
typedef map<ll,ll> mll;

const int inf = 1e9;
const ll inf64 = 1e18;
const int mod = inf + 7;
const int N = 2e5 + 10;

int main()
{
    fast;
    int n;
    cin >> n;
    string s;
    cin >> s;
    int r = count(all(s),'R');
    int g = count(all(s),'G');
    int b = count(all(s),'B');

    ll ans = 1ll * r * g * b;

    f(i,0,n-2)
    {
        f(j,i+1,n-1)
        {
            int k = 2 * j - i;
            if(k < n and s[i] != s[j] and s[j] != s[k] and s[i] != s[k])
                ans--;
        }
    }
    cout << ans;
}


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

typedef long long ll;

ll gcd( ll x, ll y );
ll lcm( ll x, ll y );

int main()
{
    ll x, y;

    scanf("%lld %lld", &x, &y );

    printf("%lld\n", gcd( x, y ) );

    return 0;
}

ll gcd( ll x, ll y )
{
    if ( y == 0 ) return x;
    return gcd( y, x % y );
}

ll lcm( ll x, ll y )
{
    return x / gcd( x, y ) * y;
}




Measured memory_bytes: 3216
mod = 10**9 + 7
def main():
  n = int(input())
  ans_every = 1
  ans_0 = 1
  ans_0_9 =  1
  for i in range(n):
    ans_every *= 10
    ans_every %= mod
    
    ans_0 *= 9
    ans_0 %= mod
    
    ans_0_9 *= 8
    ans_0_9 %= mod
  print((ans_every-(ans_0*2 -ans_0_9))%mod)
  
if __name__ == "__main__":
  main()

Measured memory_bytes: 9176
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }

typedef long long ll;

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

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const int INF = 1e9;
const ll INFLL = 1e18;
const ll MOD = 1e9+7;

const double PI = acos(-1.0);
bool isprime(int v) {
    if (v == 1) return false;
    for (int i = 2; 1LL * i*i <= v; i++) if (v%i == 0) return false;
    return true;
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int N;
    cin>>N;
    vector<int> prime;
    for(int i = 2; i < 55555; i++){
        if(isprime(i)){
            prime.push_back(i);
        }
    }
    vector<int> ans;
    rep(i,(int)prime.size()){
        if(prime[i]%5 == 1){
            ans.push_back(prime[i]);
        }
        if((int)ans.size() == N)break;
    }
    rep(i,N)cout<<ans[i]<<endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#include<stdio.h>
#include<vector>
#pragma GCC optimize(2)
typedef long long ll;
typedef unsigned long long ull;
const int mod=1000;
const int maxn=1e5+5;
const ll INF=100000000000005;
using namespace std;
ll n,m,p;
ll qpow(ll a,ll b){ll ans=1;while(b){if(b&1) ans=(ans*a)%mod;b/=2;a=(a*a)%mod;}return ans;}
ll dp[maxn];
ll num[maxn];
int q[maxn];
int main()
{

    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++) dp[i]=INF;
    for(int i=1;i<=n;i++) scanf("%lld",&num[i]);
    dp[1]=0;dp[2]=abs(num[2]-num[1]);
    for(int i=3;i<=n;i++)
    {
        for(int k=i-m;k<i;k++)
        {
            if(k>=1) dp[i]=min(dp[i],dp[k]+abs(num[i]-num[k]));
        }
    }
    printf("%lld\n",dp[n]);
    return 0;
}
/***
10 4
40 10 20 70 80 10 20 70 80 60
***/


Measured memory_bytes: 1792
l = input()
MOD = 10**9 + 7
dp = [[0]*2 for i in range(len(l)+1)]
dp[0][0] = 1

for i in range(len(l)):
    # is_smaller = 0 -> is_smaller = 0
    if l[i] == "1":
        dp[i+1][0] += 2*dp[i][0] # (0, 1), (1, 0)の2通り
    elif l[i] == "0":
        dp[i+1][0] += dp[i][0] # (0, 0)の1通り
    
    # is_smaller = 0 -> is_smaller = 1
    if l[i] == "1":
        dp[i+1][1] += dp[i][0] # (0, 0)の1通り

    # is_smaller = 1 -> is_smaller = 1
    dp[i+1][1] += 3*dp[i][1] # (1, 0), (1, 0), (1, 1)の3通り
    
    dp[i+1][0] %= MOD
    dp[i+1][1] %= MOD

print((dp[len(l)][0] + dp[len(l)][1]) % MOD)


Measured memory_bytes: 54364
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(ll i=0;i<n;i++)
#define Graph vector<vector<ll>>
#define INF (1ll<<60)
#define mod 1000000007

//abc157e simple string queries
int main(){
    ll n,q;
    string s;
    cin>>n>>s>>q;
    vector<set<ll>> cnt(26);

    rep(i,26) cnt[i].insert(INF);
    rep(i,s.size()){
        cnt[s[i]-'a'].insert(i);
    }

    rep(i,q){
        ll query;cin>>query;
        if(query==1){
            ll iq;
            char cq;
            cin>>iq>>cq;iq--;
            cnt[s[iq]-'a'].erase(iq);//log(|s|)
            cnt[cq-'a'].insert(iq);
            s[iq]=cq;
        }else if(query==2){
            ll lq,rq;cin>>lq>>rq;//左と右
            lq--;rq--;
            
            ll output=0;
            rep(j,26){//26*log(|s|)
                ll ins=*cnt[j].lower_bound(lq);//文字j+'a'について、lq<= <=rqの中に入っているか確かめる。いっているなら種類に++
                if(ins<=rq) output++; 
            }

            cout<<output<<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 27232
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using db = double;
using pii = pair < int, int >;
using pll = pair < ll, ll >;
const int N = 2e5 + 10;
const ll inf = 1e15 + 42;
#define endl "\n"
const ll mod = 1000000007;
 
void testCase() {
    ll k, n;
    cin >> k >> n;
    ll arr[n+4];
    for (int i=1; i<=n; i++)
        cin >> arr[i];
    vector <ll> val;
    for (int i=2; i<=n; i++) {
        val.push_back (arr[i]-arr[i-1]);
    }
    val.push_back (k-arr[n]+arr[1]);
    ll ans = 0;
    for (int i=0; i<val.size(); i++) {
        //cout << val[i] << "..";
        ans += val[i];
    }
    //cout << ans << endl;
    ll fans = ans;
    for (int i=0; i<val.size(); i++) {
        fans = min (fans, ans-val[i]);
    }
    cout << fans << endl;
}
 
int main() {
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    testCase();
    return 0;
}

Measured memory_bytes: 4084
#include <iostream>
#include <string>
#include <stdlib.h>

#define MAX 100000
#define MOD 1000000007
using namespace std;

typedef long long int ll;

ll DP[MAX+1][13]={};

int main(void){
  string str;
  cin >> str;
  //最後の文字だけ処理
  char c = str[str.size()-1];
  if(c == '?'){
    for(int i=0;i<10;i++){
      DP[1][i] = 1;
    }
  }else{
    int num = atoi(&c);
    DP[1][num] = 1;
  }
  // ここからDP
  int digit = 10;
  for(int n=2;n<=str.size();n++){
    char ch = str[str.size()-n];
    if(ch != '?'){
      int num = ch - '0';
      //cout << num << endl;
      int plus = (num*digit)%13;
      for(int i=0;i<13;i++){
        DP[n][(i+plus)%13] = DP[n-1][i];
      }
    }else{
      // ch = ?
      for(int i=0;i<10;i++){
        int num = (i*digit)%13;
        for(int j=0;j<13;j++){
          DP[n][(num+j)%13] = (DP[n][(num+j)%13] + DP[n-1][j])%MOD;
          //cout << "(ij)" << num << " " << (num+j)%13 << " " << DP[n][(num+j)%13] << endl;
        }
      }
    }
    digit = (10*digit)%13;
  }
  cout << DP[str.size()][5] << endl;
  return 0;
}


Measured memory_bytes: 10624
/*
    Problem 6
    https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d
*/
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
void solve1() {
    int N; string S;
    cin >> N >> S;
    int ans = 0;
    // 000 ~ 999までがSに含まれるか全探索
    // O(10^3 * 3 * 10^4) = O(3 * 10^7)
    for (int i = 0; i < 1000; i++) {
        vector<int> v{i / 100, (i / 10) % 10, i % 10};
        int t = 0;
        for (int s = 0; s < N; s++) {
            if (S[s] == ('0' + v[t])) t++;
            if (t >= 3) {
                ans++;
                break;
            }
        }
    }
    cout << ans << '\n';
}

void solve2() {
    int N; string S;
    cin >> N >> S;
    // dp[len][num]
    // len : 何文字で
    // num : numができるか
    // ex)
    // dp[2][2] => 02
    // dp[3][2] => 002
    vector<vector<bool>> dp(4, vector<bool>(1000));
    for (int pos = 0; pos < N; pos++) {
        int cur = S[pos] - '0';
        // dp[2][num] => dp[3][num*10 + cur]
        for (int num = 0; num < 100; num++) if (dp[2][num]) dp[3][cur + num * 10] = true;
        // dp[1][num] => dp[2][num*10 + cur]
        for (int num = 0; num < 10; num++) if (dp[1][num]) dp[2][cur + num * 10] = true;
        // dp[1][cur]
        dp[1][cur] = true;
    }
    int ans = accumulate(dp[3].begin(), dp[3].end(), 0);
    cout << ans << '\n';
}
/* main */
int main(){
    // solve1();
    solve2();
}

Measured memory_bytes: 3684
#include <stdio.h>          // printf(), scanf()
#include <string.h>         // strlen(), strncmp()

int skip[256];

int
search(const char* text, const char* key, int ix, int m, int n)
{
	int p = ix + n - 1;
	while (p < m)
	{
		if (text[p] == key[n - 1] && strncmp(&text[p - n + 1], key, n) == 0)
			return p - n + 1;

		p += skip[(int)text[p]];
	}

	return -1;
}

void
calc_skip(const char* key, int n)
{
	int i;

	for (i = 0; i < 256; ++i)
		skip[i] = n;

	for (i = 0; i < n - 1; ++i)
		skip[(int)key[i]] = n - 1 - i;
}

int
main(int argc, char** argv)
{
	char t[1000001];
	char p[10001];
	int m, n;
	int i;

	scanf("%s %s", t, p);
	m = strlen(t);
	n = strlen(p);

	calc_skip(p, n);
	i = search(t, p, 0, m, n);
	while (i != -1)
	{
		printf("%d\n", i);
		i = search(t, p, i + 1, m, n);
	}

	return 0;
}

Measured memory_bytes: 1548
#include <cstdio>
#include <cstring>
int main(){
    int N,M;
    scanf("%d%d",&N,&M);
    int as[1145],cs[1145];
    memset(cs,0,sizeof(cs));
    for(int i=0;i<N;i++){
        scanf("%d",&as[i]);
    }
    for(int i=0;i<M;i++){
        int b;
        scanf("%d",&b);
        for(int j=0;j<N;j++){
            if(as[j]<=b){
                cs[j]++;
                break;
            }
        }
    }
    int ma=0,mat;
    for(int i=0;i<N;i++){
        if(cs[i]>ma){
            ma=cs[i];
            mat=i;
        }
    }
    printf("%d\n",mat+1);
}

Measured memory_bytes: 1016
#include <iostream>
using namespace std;
int main(void){
    int N, M, cost=0;
    cin >> N >> M;
    
    int A[M], B[M];
    int max_loss=0, max_loss_num=-1;
    for(int i=0; i<M; i++){
        cin >> A[i] >> B[i];
        if(A[i] < N){
            if(B[i]-A[i] > max_loss){
                max_loss = B[i]-A[i];
                max_loss_num = i;
            }
        }
    }
    
    if(max_loss_num == -1){
        cout << 0 << endl;
    }
    else{
        for(int i=0; i<M; i++){
            if(i!=max_loss_num){
                if(A[i]<N){
                    cost += N-A[i];
                }
            }
        }
        cout << cost << endl;
    }
    
    return 0;
}



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

struct Card { char suit, value; };

void bubble(struct Card A[], int N) {
    for ( int i = 0; i < N; i++ ) {
      for ( int j = N - 1; j >= i; j-- ) {   
        if ( A[j].value < A[j-1].value ) {
            Card t = A[j]; A[j] = A[j-1]; A[j-1] = t;
        }
      }
    }
}
void selection(struct Card A[], int N) {
    for ( int i = 0; i < N; i++ ) {
        int minj = i;
        for ( int j = i; j < N; j++ ) {
            if ( A[j].value < A[minj].value ) minj = j;
        }
        Card t = A[i]; A[i] = A[minj]; A[minj] = t;
    }
}

void print(struct Card A[], int N) {
    for ( int i = 0; i < N; i++ ) {
        if ( i > 0 ) cout << " ";
        cout << A[i].suit << A[i].value;
    }
    cout << endl;
}

// バブルソートと選択ソートの結果を比較
bool isStable(struct Card C1[], struct Card C2[], int N) {
    for ( int i = 0; i < N; i++ ) {
        if ( C1[i].suit != C2[i].suit ) return false;
    }
    return true;
}

int main() {
    Card C1[100], C2[100];
    int N;
    char ch;

    cin >> N;
    for ( int i = 0; i < N; i++ ) {
        cin >> C1[i].suit >> C1[i].value;
    }

    for ( int i = 0; i < N; i++ ) C2[i] = C1[i];

    bubble(C1, N);
    selection(C2, N);

    print(C1, N);
    cout << "Stable" << endl;
    print(C2, N);
    if ( isStable(C1, C2, N) ) {
        cout << "Stable" << endl;
    } else {
        cout << "Not stable" << endl;
    }

    return 0;
}


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

int main(){
  int n;
  cin >> n;
  vector<int> vec(2*n);
  for(int i=0;i<2*n;i++){
    cin >> vec.at(i);
  }
  sort(vec.begin(),vec.end());
  int sum=0;
  for(int i=0;i<n;i++){
    sum = sum + vec.at(2*i);
  }
  cout << sum << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
  while(true){
    int x,y,s;
    cin>>x>>y>>s;
    if(x==0&&y==0&&s==0){
      break;
    }
    int tmax=-1;
    for(int a=1;a<=s-1;a++){
      int ax = a*(100+x)/100;
      int ay = a*(100+y)/100;

      for(int b=1;b<=s-1;b++){
        int bx=b*(100+x)/100;
        int by=b*(100+y)/100;
        if(ax+bx==s){
          tmax=max(tmax,ay+by);
        }
        else if (ax+bx>s) {
          break;
        }
      }
    }
    cout<<tmax<<endl;
  }
  return 0;
}



Measured memory_bytes: 3088
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_C main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
// functions

#endif


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

    int N;  cin >> N;
    vi t(N), x(N), y(N);
    REP(i, N) cin >> t[i] >> x[i] >> y[i];

    string ans = "Yes";
    int dist = x[0] + y[0];
    int dt = t[0];
    if (dist > dt || dist % 2 != dt % 2) ans = "No";
    FOR(i,1,N) {
        dist = abs(x[i] - x[i - 1]) + abs(y[i] - y[i - 1]);
        dt = t[i] - t[i - 1];
        if (dist > dt || dist%2 != dt%2) {
            ans = "No";
            break;
        }
    }

    cout << ans << endl;

    return 0;
}

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

int main()
{
	int N,a;
	int ans=0;
	
	cin >> N;
	for(int i=0;i<N;i++)
	{
		cin >> a;
		while(a%2==0)
		{
			a/=2;
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int i,j,k;
  int n,m;
  while(cin>>n>>m,n||m){
    int a[100];
    for(i=0;i<n;++i)
      cin>>a[i];
    int re=0,rt=0;
    for(j=0;j<n-m+1;++j){
      int pi=1,mn=1<<30,mx=-1;
      for(k=0;k<m;++k){
	pi*=a[j+k];
	mn=min(mn,a[j+k]);
      }
      for(k=0;k<j;++k)
	mx=max(mx,a[k]);
      for(k=j+m;k<n;++k)
	mx=max(mx,a[k]);
      re=max(re,pi);
      rt=max(rt,mx<0?pi:pi/mn*mx);
    }
    if(re>rt)
      cout<<"NO GAME"<<endl;
    else
      cout<<rt-re<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
using System;
using System.Linq;
using System.Text;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var a = Encoding.ASCII.GetBytes(Console.ReadLine()).OrderBy(x => x).ToArray();
            var b = Encoding.ASCII.GetBytes(Console.ReadLine()).OrderByDescending(x => x).ToArray();

            var aString = Encoding.ASCII.GetString(a);
            var bString = Encoding.ASCII.GetString(b);

            if(String.Compare(aString, bString) < 0)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
}


Measured memory_bytes: 13536
#include <bits/stdc++.h>
#include <math.h>
#define ALL(a)    a.begin(), a.end()
using namespace std;

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

if(a == 0)cout <<1;

if(b == 0)cout <<2;

if(c == 0)cout <<3;

if(d == 0)cout <<4;

if(e == 0)cout <<5;

}

Measured memory_bytes: 3620
///not today

#include<bits/stdc++.h>
using namespace std;

#define SZ(x) (int)(x).size()
#define pb push_back
#define ll long long
#define xmax(x, y) (x) = max((x), (y))
#define xmin(x, y) (x) = min((x), (y))
#define F first
#define S second
#define pii pair<int, int>
#define pll pair<long long, long long>
#define int long long
#define pipii pair<int, pair<int, int> >
#define pf push_front

const int maxn = 5000* 100 + 5;
int a[maxn];
vector <int> v;

int32_t main(){
    string s;
    cin >>s;
    for(int i = 0; i < SZ(s); i ++){
        if(i == SZ(s) - 1 and s[i] == '>')
            v.pb(SZ(s));
        else if((i == 0 and s[i] == '<') or (i > 0 and s[i] == '<' and s[i - 1] == '>'))
            v.pb(i);
    }
    for(int i = 0; i < SZ(v); i ++){
        int x = v[i];
        for(int j = x + 1; j < SZ(s) + 1 and s[j - 1] == '<'; j ++){
            xmax(a[j], a[j - 1] + 1);
        }
        for(int j = x - 1; j >= 0 and s[j] == '>'; j --){
            xmax(a[j], a[j + 1] + 1);
        }
    }
    int sum = 0;
    for(int i = 0; i < SZ(s) + 1; i ++)
        sum += a[i];
    cout <<sum <<endl;
    return false;
}



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

int main(void) {
  string S;
  cin >> S;

  int a,b,c,z;
  int tmp;
  int min = 753;

  for (int i = 0; i <= S.size() - 3; i++) {
    a = S[i] - '0';
    b = S[i+1] - '0';
    c = S[i+2] - '0';
    z = 100*a + 10*b +c;

    if (z > 753) {
      tmp = z - 753;
    } else {
      tmp = 753 - z;
    }

    if (tmp < min) {
      min = tmp;
    }
  }

  cout << min << endl;

  return 0;
}

Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10**7)
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
printn = lambda x: print('\n'.join(x))

s = input()
for x in ['ABC', 'ARC']:
    if s != x:
        print(x)


Measured memory_bytes: 9056
use std::io::*;
use std::str::FromStr;

fn main() {
    let stdin = stdin();
    let mut lock = stdin.lock();
    let mut str1 = String::new();
    lock.read_line(&mut str1).unwrap();
    let vec: Vec<_> = str1.trim().split_whitespace().map(|x|
    u32::from_str(x).unwrap()).collect();
    let ab = vec[0] + vec[1];
    let cd = vec[2] + vec[3];
    if ab < cd {
        println!("Right");
    } else if ab == cd {
        println!("Balanced");
    } else {
        println!("Left");
    }
}

Measured memory_bytes: 4352
use proconio::input;

use proconio::marker::{Chars, Usize1};
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused)]
const ALPHA_SMALL: [char; 26] = [
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's',
    't', 'u', 'v', 'w', 'x', 'y', 'z',
];
#[allow(unused)]
const ALPHA: [char; 26] = [
    'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S',
    'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
];
fn main() {
    input!(N: usize, K: i64);
    input!(P: [Usize1; N]);
    input!(C: [i64; N]);
    let mut ans = std::i64::MIN;

    let p = parse(&P, &C);
    for g in &p {
        let L = g.len();
        let cs = calc(g, K);
        let sum = cs[L - 1];
        let m = K as usize % L;
        let n = K / L as i64;
        if sum <= 0 {
            for &cost in &cs {
                ans = max(ans, cost);
            }
        } else {
            for i in 0..=m {
                if i == 0 {
                    ans = max(ans, sum * n);
                } else {
                    ans = max(ans, sum * n + cs[i - 1]);
                }
            }
            if n > 0 {
                for i in 0..L {
                    if i == 0 {
                        ans = max(ans, sum * (n - 1));
                    } else {
                        ans = max(ans, sum * (n - 1) + cs[i - 1]);
                    }
                }
            }
        }
    }

    println!("{}", ans);
    //println!("{:?}", p);
}

fn calc(g: &Vec<(usize, i64)>, K: i64) -> Vec<i64> {
    let mut ret = vec![std::i64::MIN; g.len()];
    let L = g.len();
    for start in 0..L {
        let mut cost = 0;
        for pos in 0..L {
            cost += g[(start + pos) % L].1;
            ret[pos] = max(ret[pos], cost);
        }
    }

    ret
}

//単一視点から目的のノードまでの最短距離、ただし全ての辺の重みが等しいグラフに限る
fn parse(g: &Vec<usize>, cost: &Vec<i64>) -> Vec<Vec<(usize, i64)>> {
    let N = g.len();
    let mut ret = Vec::new();
    let mut visit = vec![false; N];

    for start in 0..N {
        if visit[start] {
            continue;
        }
        let mut now = start;
        let mut h = Vec::new();
        while !visit[now] {
            visit[now] = true;
            h.push((now, cost[g[now]]));
            now = g[now];
        }

        ret.push(h);
    }

    ret
}


Measured memory_bytes: 2432
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> v(n);
    vector<int> c(n);

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

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

    int sum = 0;

    for (int i = 0; i < n; i++) {
        if (v[i] - c[i] > 0) {
            sum += (v[i] - c[i]);
        }
    }

    cout << sum;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))
sum = 0
res = [0,0]
for change in range(2):
  sum = 0
  for i in range(n):
    if i % 2 == change:
      if sum + a[i] < 0: # -だったら
        #temp = -1 - sum - a[i]
        temp = 1 - sum - a[i]
        res[change] += temp
        sum += temp
      elif sum + a[i] == 0:
        sum += 1
        res[change] += 1
    else:
      if sum + a[i] > 0:
        #temp = 1 - sum - a[i]
        temp = -1 - sum - a[i]
        res[change] -= temp
        sum += temp
      elif sum + a[i] == 0:
        sum -= 1
        res[change] += 1
    sum += a[i]
print(min(res[0],res[1]))

Measured memory_bytes: 14468
n = int(input())
a = [int(input()) for _ in range(n)]
if a[0] != 0:
  print(-1)
  exit(0)
cnt = 0
cur = 0
for i in range(n-1,-1,-1):
  if cur > a[i]:
    print(-1)
    exit(0)
  if cur < a[i]:
    cur = a[i]
    cnt += a[i]
  if cur > 0:
    cur -= 1
print(cnt)

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

using namespace std;

#define N 2005
const int mod = 1000000007;
#define add(x, y) (x + y >= mod ? x + y - mod : x + y)
#define dec(x, y) (x < y ? x - y + mod : x - y)

int Pow(int x, int k)
{
	int ans = 1, base = x;
	while(k)
	{
		if(k & 1) ans = 1ll * ans * base % mod;
		base = 1ll * base * base % mod;
		k >>= 1;
	}
	return ans;
}

int n, k, f[N][N], pw[N * N], inv[N * N];

int C(int x, int y)
{
	return 1ll * pw[y] * inv[y - x] % mod * inv[x] % mod;
}

int main()
{
	scanf("%d%d", &n, &k);
	pw[0] = inv[0] = 1;
	for(int i = 1; i <= n * k; i++) pw[i] = 1ll * pw[i - 1] * i % mod, inv[i] = Pow(pw[i], mod - 2);
	if(k == 1) {cout << 1 << endl; return 0;}
	f[0][0] = 1;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 0; j <= i; j++)
		{
			f[i][j] = add(f[i - 1][j], (1ll * f[i][j - 1] * (n - j + 1) % mod * C(k - 2, n * k - i - (j - 1) * (k - 1) - 1) % mod));
		}
	}
	printf("%d\n", f[n][n]);
	return 0;
}

Measured memory_bytes: 47360
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF ((1LL<<62)-(1LL<<31))
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define bit(n,m)(((n)>>(m))&1)
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}
ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;}
//#define MOD 998244353
#define MOD 1000000007
#define invp(a,p)pom(a,p-2,p)

ll a[5],ans;
int main(){
	rep(i,0,5)scanf("%lld",a+i);
	ll ans=0;
	rep(i,0,5)ans+=(a[i]+9)/10*10;
	ll M=0;
	rep(i,0,5)M=max(M,(a[i]+9)/10*10-a[i]);
	printf("%lld",ans-M);
}

Measured memory_bytes: 128
#include <iostream>

using namespace std;

int tax(int a,int b){
    for(int i=1;i<=1009;i++){
      if(int(i*0.1)!=0&&int(i*0.08)==a&&int(i*0.1)==b){
        return i;
      }
    }
    return -1;
}
int main(void){
  int a,b;
  cin >> a >> b;
  cout<<tax(a,b);
  return 0;
  
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>
#include <stack>
#include <cstdint>



#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = (int)(n-1); i >= 0; i--)
#define repi(i,a,b) for(int i=(ll)(a);i<(ll)(b);i++)
#define rrepi(i,a,b) for(int i=(ll)(b);i>=(ll)(a);i--)

#define all(x) (x).begin(),(x).end()

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

typedef long long ll;

using namespace std;


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll a,b,c;cin>>a>>b>>c;
  if(a+b+c>21){
    cout<<"bust"<<endl;
  }
  else {
    cout<<"win"<<endl;
  }

  return 0;

}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>

#define ll long long
#define LINF LLONG_MAX

using namespace std;

int main() {
  ll N;
  cin >> N;
  vector<ll> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  sort(A.begin(), A.end(), greater<ll>());

  vector<ll> mxfirst, mnfirst;
  if (N % 2 == 0) {
    mxfirst.push_back(1);
    mxfirst.push_back(-1);
    mnfirst.push_back(1);
    mnfirst.push_back(-1);
    for (int i = 0; i < (N - 2) / 2; i++) {
      mxfirst.push_back(2);
      mnfirst.push_back(2);
    }
    for (int i = 0; i < (N - 2) / 2; i++) {
      mxfirst.push_back(-2);
      mnfirst.push_back(-2);
    }
  } else {
    mxfirst.push_back(1);
    mxfirst.push_back(1);
    mnfirst.push_back(-1);
    mnfirst.push_back(-1);
    for (int i = 0; i < (N - 2) / 2; i++) {
      mxfirst.push_back(2);
      mnfirst.push_back(-2);
    }
    for (int i = 0; i < ((N - 2) / 2) + 1; i++) {
      mxfirst.push_back(-2);
      mnfirst.push_back(2);
    }
  }
  sort(mxfirst.begin(), mxfirst.end(), greater<ll>());
  sort(mnfirst.begin(), mnfirst.end(), greater<ll>());
  ll res1 = 0, res2 = 0;

  for (int i = 0; i < N; i++) {
    res1 += mxfirst[i] * A[i];
    res2 += mnfirst[i] * A[i];
  }

  ll ans = max(res1, res2);
  cout << ans << endl;
}

Measured memory_bytes: 2804
import collections as c
n,m=map(int,input().split())
print(['POSSIBLE','IMPOSSIBLE'][not [1 for c in c.Counter([[a,b][a==1] for a,b in [[i,j] for i,j in [list(map(int,input().split())) for _ in range(m)] if i==1 or j==n]]).values() if c>1]])

Measured memory_bytes: 60240
import heapq

N, M = map(int, input().split())

data = []
for _ in range(N):
    data.append(list(map(int, input().split())))

score = [] 
scores = []
for i in range(-1, 2, 2):
    for j in range(-1, 2, 2):
        for k in range(-1, 2, 2):
            for info in data:
                heapq.heappush(score, -(i*info[0] + j*info[1] + k*info[2]))
            scores.append(-sum([heapq.heappop(score) for _ in range(M)]))
            score.clear()

print(max(scores))

                

Measured memory_bytes: 3416
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<limits.h>

#define rep(i,begin,end) for(int i=begin; i<end; i++)
#define revrep(i, begin, end) for(int i=begin; i>end; i--)
#define lld long long int

typedef struct node node;
typedef struct edge{
    lld len;
    node* target;
    struct edge* next;
}edge;
typedef struct node{
    lld value;
    edge* fst;
    edge* lst;
}node;
void init(node* p){
    p->value = 0;
    p->fst = NULL;
    p->lst = NULL;
}
void add(node* p, node* target, lld len){
    if(p->fst == NULL){
        p->fst = (edge*)malloc(sizeof(edge));
        p->lst = p->fst;
    }else{
        p->lst->next = (edge*)malloc(sizeof(edge));
        p->lst = p->lst->next;
    }
    p->lst->target = target;
    p->lst->len = len;
    p->lst->next = NULL;
}

void func(node* p, node* pre){
    edge* q = p->fst;
    while(q != NULL){
        if(q->target != pre){
            q->target->value = p->value + q->len;
            func(q->target, p);
        }
        q = q->next;
    }
    return;
}

int main(){
    int n;
    scanf("%d", &n);
    node t[n+1];
    rep(i, 1, n+1){
        init(&t[i]);
    }
    rep(i, 0, n-1){
        int a, b;
        lld c;
        scanf("%d %d %lld", &a, &b, &c);
        add(&t[a], &t[b], c);
        add(&t[b], &t[a], c);
    }
    int q, k;
    scanf("%d %d", &q, &k);
    func(&t[k], &t[k]);
    lld ans[q];
    rep(i, 0, q){
        int x, y;
        scanf("%d %d", &x, &y);
        ans[i] = t[x].value + t[y].value;
    }
    rep(i, 0, q){
        printf("%lld\n", ans[i]);
    }

    return 0;
}

Measured memory_bytes: 13440
#include<bits/stdc++.h>
//Problem Code

#define TC int t; cin>>t; while(t--)
#define MOD 1000000007
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define MEM(a, b) memset(a, (b), sizeof(a))
#define FOR(i, st, en, in) for (int i=st ; i<en ; i+=in)
#define RFOR(i, st, en, in) for (int i=st ; i>=en ; i-=in)
#define REP(i, n) FOR(i, 0, n, 1)
#define RREP(i, n) RFOR(i, n-1, 0, 1)
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define sz(a) int(a.size())
#define SORT(c) sort(all(c))
#define RSORT(c) sort(rall(c))

using namespace std;
using ull = unsigned long long int;
using ll = long long;
using pii = pair<int,int>;

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

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

ll bs(ll s,ll e,ll a[],ll v){
    ll m =(s+e)/2;
    if(v>a[m]) return bs(m+1,e,a,v);
    else if(v<a[m]) return bs(s,m-1,a,v);
    return m;
}

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

void testingio(){
    freopen("input.txt","r",stdin); //redirects standard input
    freopen("output.txt","w",stdout); //redirects standard output   
}

int main(){
    // testingio();
    fastio();
    int n; cin>>n;
    ull sum=0,x;
    for(int i=0;i<n;i++){
        cin>>x;
        sum+=x;  
    }
    cout<<sum-n<<"\n";
    return 0;
}

Measured memory_bytes: 256
//#include <tourist>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = 1e9;
const ll LINF = ll(1e18);
const int MOD = 1000000007;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define rep(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define debug(v)          \
    cout << #v << ":";    \
    for (auto x : v)      \
    {                     \
        cout << x << ' '; \
    }                     \
    cout << endl;
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;
}
//cout<<fixed<<setprecision(15);有効数字15桁
//-std=c++14
//-std=gnu++17
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
  	int x,a,b;
    cin >> x>>a>>b;
    x-=a;
  	cout<<x%b<<"\n";
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Atc_0037
{
    class Program
    {
        static void Main(string[] args)
        {
            double a = 0.08;
            double b = 0.10;

            var s = Console.ReadLine();

            int A = int.Parse(s.Split(' ')[0]);
            int B = int.Parse(s.Split(' ')[1]);

            for (int i = 0; i < 1010; i++)
            {
                if ((int)(i * a) == A && (int)(i * b) == B)
                {
                    Console.WriteLine(i);
                    return;
                }
            }

            Console.WriteLine(-1);

        }
    }
}


Measured memory_bytes: 27504
import math
a,b,h,m = map(int,input().split())


h_x = a*math.cos(math.radians(90-(h*60+m)/2))
h_y = a*math.sin(math.radians(90-(h*60+m)/2))


t_x = b*math.cos(math.radians(90-(m*6)))
t_y = b*math.sin(math.radians(90-(m*6)))

#print(90-(m*60),t_x,t_y)

print((abs(h_x-t_x)**2+abs(h_y-t_y)**2)**0.5)

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

#define endl '\n'
#define ff first
#define ss second
#define pb pushback

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

void solve() {
	const string yes = "Yes", no = "No";
	int n;
	cin >> n;
	for (int i = 1; i < 10; i++) {
		for (int j = i; j < 10; j++) {
			if (i * j == n) {
				cout << yes;
				return;
			}
		}
	}
	cout << no;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef LOCAL
		ifstream in("in");
		cin.rdbuf(in.rdbuf());
	#endif
	solve();
}

Measured memory_bytes: 256
N = int(input())
*A, = map(int, input().split())
for i in range(N):
    R = ["node %d: key = %d," % (i+1, A[i])]
    l = 2*i+1; r = 2*i+2
    if i:
        R.append("parent key = %d," % A[(i-1)//2])
    if l < N:
        R.append("left key = %d," % A[l])
    if r < N:
        R.append("right key = %d," % A[r])
    print(*R, "")



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

int intlog(double base, double x)
{
    return ceil((log(x) / log(base)));
}

int main()
{
    int n, k;
    cin >> n >> k;
    int res = 0;
    while(n>0)
    {
        n/=k;
        res++;
    }
    cout<<res;
    return 0;
}

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

int main() {
	int a[3];
	for(int i=0;i<3;i++){
		cin>>a[i];
	}
	sort(a,a+3);
	if(a[0]+a[1]==a[2]){
		cout<<"Yes";
	}
	else{
		cout<<"No";
	}
	// your code goes here
	return 0;
}

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


int main() {
    int N;
    cin >> N;
    int cnt_4 = 0, cnt_2 = 0;
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        if (a % 4 == 0) cnt_4++;
        else if (a % 2 == 0) cnt_2++;
    }

    if (cnt_4 + (cnt_2 / 2) >= N / 2) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define P(x) cout << x << endl
#define D(x) P(#x << ": " << x)
#define F(i,n) for (int i=0; i<(int)(n); i++)
#define DEC(i,n) for (int i=(int)(n); --i>=0;)
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
const int N=100000;

vector<int> adj[N];
int col[N];

bool bipa(int u, int c) {
    if (col[u]) return col[u] == c;
    col[u] = c;
    bool ok=true;
    for (int v : adj[u])
        if (!bipa(v, 3-c))
            ok=false;
    return ok;
}

signed main() {
    int n,m; cin>>n>>m;
    F(i,m) {
        int a,b; cin>>a>>b;
        a--, b--;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    int alone=0, bip=0, other=0;
    F(i,n) if (!col[i]) {
        if (adj[i].empty()) {
            col[i] = 1;
            alone++;
        } else if (bipa(i, 1))
            bip++;
        else
            other++;
    }
    int res = n*n - (n-alone)*(n-alone);
    res += (other+bip)*(other+bip) + bip*bip;
    P(res);
}

Measured memory_bytes: 12416
#include <iostream>
#include <map>

using namespace std;

int main()
{
#if 1
	int a[101] = {0};
	int v;

	// 数え上げ
	while (cin >> v) {
		a[v]++;
	}

	// 最大値を求める
	int max = 0;

#if 0
	// autoが使えるとき
	for (auto x : a) {
		if (x > max) {
			max = x;
		}
	}
#else
	for (int i = 1; i <= 100; i++) {
		if (a[i] > max) {
			max = a[i];
		}
	}
#endif

	// 最大値になった数（添え字）を表示
	for (int i = 1; i <= 100; i++) {
		if (a[i] == max) {
			cout << i << endl;
		}
	}

#else
	map<int, int> a;
	int v;

	while (cin >> v) {
		a[v]++;
	}

	// 最大値を求める
	int max = 0;
	for ( auto x : a ) {
		if (x.second > max) {
			max = x.second;
		}
	}

	// 最大値を取る値を出力
	vector<int> answer;
	for ( auto x : a ) {
		if ( x.second == max) {
			answer.push_back(x.first);
		}
	}

	// 並べ替え
	sort(answer.begin(), answer.end());
	for ( auto x : answer ) {
		cout << x << endl;
	}

#endif

	return 0;
}



Measured memory_bytes: 3008
#include <iostream>
#include <set>
#include <vector>

using namespace std;

#define loop(i,a,b) for(int i=(a); i<(int)(b); i++)
#define rep(i,b) loop(i,0,b)

typedef set<vector<int>> sv;

int main(){
    int n;
    while(cin>>n,n){
        sv prev; prev.insert(vector<int>(1,1));
        rep(i,n-1){
            sv next;
            for(auto v:prev){
                rep(i,v.size()){
                    if(i==0||v[i-1]>v[i]){
                        v[i]++;
                        next.insert(v);
                        v[i]--;
                    }
                }
                v.push_back(1);
                next.insert(v);
            }
            swap(prev,next);
        }
        for(auto v=prev.rbegin(); v!=prev.rend(); ++v){
            rep(i,v->size()-1) cout<<(*v)[i]<<" ";
            cout<<v->back()<<endl;
        }
    }
}

Measured memory_bytes: 2152