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

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

    long long c1 = a[1] + a[0] / 2 * 2 + a[3] / 2 * 2 + a[4] / 2 * 2;

    long long c2 = a[1];
    if (1 <= a[0] && 1 <= a[3] && 1 <= a[4]) {
        c2 += 3;
        a[0]--;
        a[3]--;
        a[4]--;
    }   
    c2 += a[0] / 2 * 2 + a[3] / 2 * 2 + a[4] / 2 * 2;

    cout << max(c1, c2) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
vector<vector<int>>G(100100,vector<int>());
vector<bool>used(100100,false);
void dfs(int v){
   for(auto nx:G[v]){
      if(used[nx])continue;
      used[nx]=true;
      dfs(nx);
   }
   return;
}
int main()
{
  int N,M;
  cin >> N >> M;
  rep(i,M){
     int x,y,z;cin >> x >> y >> z;
     x--;y--;
     G[x].push_back(y);
     G[y].push_back(x);
  }
  int ans=0;
  for(int i=0;i<N;i++){
     if(!used[i]){
        ans++;
        used[i]=true;
        dfs(i);
     }
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 8832
#include <bits/stdc++.h>
using namespace std;
using pi = pair <int, int>;
using ll = long long;
const ll mod = 1e9 + 7;
const int N = 2e5 + 10;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int a, b;
    cin >> a >> b;
    cout << 6 - a - b;
}


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

int main(){
    int h, w; cin >> h >> w;
    vector<vector<char>> c(2*h, vector<char>(w));

    for(int y = 0; y < h * 2; y+=2){
        for(int x = 0; x < w; x++){
            cin >> c.at(y).at(x);
            c.at(y+1).at(x) = c.at(y).at(x);
        }
    }

    for(int y = 0; y < h * 2; y++){
        for(int x = 0; x < w; x++){
            cout << c.at(y).at(x);
        }
        cout << endl;
    }
}

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

int main(){
  string s;
  cin >> s;
  int n = sz(s);

  if(s[n-1]=='s') s += "es";
  else s += "s";
  cout << s << endl;
}


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

using namespace std;
typedef long long ll;

vector<int> w[4];
ll dp[4][101];

int main(void) {
    int N, W, wtmp, w1, v;
    scanf("%d%d", &N, &W);
    scanf("%d%d", &w1, &v);
    w[0].emplace_back(v);
    for(int i=0; i<N-1; i++) {
        scanf("%d%d", &wtmp, &v);
        w[wtmp-w1].emplace_back(v);
    }

    for(int i=0; i<4; i++) {
        dp[i][0] = 0;
        sort(w[i].begin(), w[i].end(), greater<int>() );
        for(int j=1; j<=w[i].size(); j++) {
            dp[i][j] = dp[i][j-1] + w[i][j-1];
        }
    }

    ll ans = 0;
    for(int i=0; i<=w[0].size(); i++) for(int j=0; j<=w[1].size(); j++)
        for(int k=0; k<=w[2].size(); k++) for(int l=0; l<=w[3].size(); l++) {
            ll weight = 1LL * (i+j+k+l)*w1 + j + 2*k + 3*l;
            if(weight > W) continue;
            ans = max(ans, dp[0][i]+dp[1][j]+dp[2][k]+dp[3][l]);
    }

    printf("%lld\n", ans);
    return 0;
}

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

struct LowestCommonAncestor {
    size_t n;
    size_t size() const { return n; }
    vector<int> color, parent, depth, topDepth, goUp, visited;
    vector<vector<int>> g;
    LowestCommonAncestor(size_t n_) : n(n_), g(n) {}
    void addEdge(int u, int v){
        g[u].push_back(v); g[v].push_back(u);
    }
    void decomp(int root = 0, int B = 500){
        parent.assign(n, -1); depth.assign(n, 0);
        topDepth.assign(n, 0); goUp.assign(n, -1); visited.assign(n, false);
        vector<int> tord;
        vector<int> q(n+1); int l = 0, r = 0;
        q[r++] = root;
        while(l != r){
            int v = q[l++]; visited[v] = true;
            tord.push_back(v);
            for(int c : g[v]){
                if(!visited[c]){ parent[c] = v; depth[c] = depth[v] + 1; q[r++] = c; }
            }
        }
        swap(color, visited); // ?????¢????????±??????
        color.assign(n, 0);
        int c = 0;
        for(int u : tord){
            if(color[u]) continue;
            c++;
            l = 0, r = 0;
            q[r++] = u;
            for(int i = 0; i < B && l != r; i++){
                int v = q[l++];
                color[v] = c; goUp[v] = parent[u]; topDepth[v] = depth[u];
                for(int c : g[v]) if(!color[c]) q[r++] = c;
            }
        }
    }
    int solve(int u, int v){
        // for(int i = 0; i < n; i++) cout << parent[i] << " ";
        // cout << endl;
        while(color[u] != color[v]){
            if(topDepth[u] > topDepth[v]) u = goUp[u];
            else v = goUp[v];
        }
        // cout << depth[u] << " " << depth[v] << endl;
        while(depth[u] > depth[v]){
            assert(depth[u] == depth[parent[u]]+1);
            u = parent[u];
            // cout << depth[u] << " " << depth[v] << endl;
        }
        while(depth[u] < depth[v]){
            assert(depth[v] == depth[parent[v]]+1);
            v = parent[v];
            // cout << depth[u] << " " << depth[v] << endl;
        }
        assert(depth[u] == depth[v]);
        while(u != v) u = parent[u], v = parent[v];
        return u;
    }
};

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

int main(){
    int n;
    cin >> n;
    LowestCommonAncestor g(n);
    rep(i,n){
        int k;
        cin >> k;
        rep(j,k){
            int c;
            cin >> c;
            g.addEdge(i,c);
        }
    }
    g.decomp(0);
    int q;
    cin >> q;
    rep(i,q){
        int u,v;
        cin >> u >> v;
        cout << g.solve(u,v) << endl;
    }
}

Measured memory_bytes: 10028
#include <stdio.h>

int main(void){
  char c;
  scanf("%c",&c);
  if(c=='a') printf("vowel\n");
  else if(c=='i') printf("vowel\n");
  else if(c=='u') printf("vowel\n");
  else if(c=='e') printf("vowel\n");
  else if(c=='o') printf("vowel\n");
  else printf("consonant\n");
  return(0);
}


Measured memory_bytes: 128
import java.util.*;


public class Main {
    static Scanner input = new Scanner(System.in);

    static public void solve() {
        int c1x = input.nextInt();
        int c1y = input.nextInt();
        int c1r = input.nextInt();
       
        int c2x = input.nextInt();
        int c2y = input.nextInt();
        int c2r = input.nextInt();

        input.close();

        double x = (double) c1x - c2x;
        double y = (double) c1y - c2y;
        double l12 = Math.sqrt(x * x + y * y);
        double plus = (double) c1r + c2r;
        double minus = (double) c1r - c2r;
        if (minus < 0) minus = - minus;

        if (l12 > plus) {
            System.out.println("4");
        }
        if (l12 == plus) {
            System.out.println("3");
        }
        if (l12 < plus && l12 > minus) {
            System.out.println("2");
        }
        if (l12 == minus) {
            System.out.println("1");
        }
        if (l12 < minus) {
            System.out.println("0");
        }
    }

    public static void main(String[] args) {
        solve();
    }
}


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

int main(){
    string s,t;
    cin >> s >> t;
    long long int answer = 0;
    long long int before = -1,after = 0;;

    for(int i=0;i<t.size();i++){
        if(s.find(t[i])==string::npos){
            cout << -1 << endl;
            return 0;
        }
        if(before == s.size()-1) before = -1;
        if(s.find(t[i],before+1) != string::npos) after = s.find(t[i],before+1);
        else after = s.find(t[i]);
        if(before < after) answer += after - before;
        else if(before == after) answer += s.size();
        else answer += s.size() - before + after;

       // cout << "before:" << before << " " << "after:" << after << " " << "answe:" << answer << endl;
        before = after;

    }
    cout << answer << endl;
    return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
const ll inf = 1LL << 50;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////

int main() {
	ll N, T; cin >> N >> T;
	vector<int>V;
	for (int i = 0; i < N; ++i) {
		ll t; cin >> t;
		V.push_back(t);
	}
	sort(V.begin(), V.end());
	ll sum = 0;
	ll now = 0;
	for (int i = 1; i <= N; ++i) {
		if (i == N) {
			sum += T;
			break;
		}
		if (now + T <= V[i]) {
			sum += T;
			now = V[i];
		}
		else {
			sum += V[i] - now;
			now = V[i];
		}
	}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 1400
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#include<cmath>
#include<cstdint>

#define INF 1e9
#define LINF 1e19
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)
     
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<ll, ll>;
     
const ll MOD = 1e9 + 7;
const ll zer = 0;

int main(){
    int n;
    cin >> n;
    vector<ll> a(n), b(n);
    ll sa = 0, sb = 0;
    rep(i, n){
      cin >> a[i];
      sa += a[i];
    }
    rep(i, n){
      cin >> b[i];
      sb += b[i];
    }
    if(sa < sb){
      cout << -1 << endl;
      return 0;
    }

    vector<ll> dif(n);
    rep(i, n)dif[i] = a[i] - b[i];
    sort(ALL(dif), greater<ll>());
    vector<ll> q;
    ll sum = 0;
    rep(i, n){
      if(dif[i] >= 0){
        q.push_back(dif[i]);
      }
      sum += dif[i];
    }
    sort(ALL(q));
    ll res = 0;
    rep(i, (int)q.size()){
      if(sum >= q[i]){
        res++;
        sum -= q[i];
      }
    }
    cout << n - res << endl;
}





Measured memory_bytes: 6440
import Control.Monad
import Data.List

comb :: Int -> [a] -> [[a]]
comb 0 xs = [[]]
comb _ [] = []
comb n (x:xs) = [x:y | y <- comb (n-1) xs] ++ comb n xs

main = do
    n <- readLn :: IO Int
    ds <- map read . words <$> getLine :: IO [Int]
    print $ sum [product xy | xy <- (comb 2 ds)]

Measured memory_bytes: 4248
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
int n,m;
string s;
vector<string>v;
cin>>n>>m;
for(int i=0;i<n;i++)
{
    cin>>s;
    v.push_back(s);
}
for(int i=0;i<n;i++)
{
     cout<<v[i]<<endl;
    cout<<v[i]<<endl;
}
return 0;
}


Measured memory_bytes: 3600
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;

namespace AtCoder
{
	public class Program
	{
		static void Main()
		{
			var nm = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
			int n = nm[0];
			int m = nm[1];
			var ab = new Tuple<int, int>[m];
			for (int i = 0; i < m; i++) {
				var temp = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
				ab[i] = new Tuple<int, int>(temp[0] - 1, temp[1] - 1);
			}

			int ans = 0;
			for (int i = 0; i < m; i++) {
				ans += Check(n, m, ab, i);
			}

			Console.WriteLine(ans);
		}

		static int Check(int n, int m, Tuple<int, int>[] edges, int target)
		{
			var to = new List<int>[n];
			for (int i = 0; i < n; i++) {
				to[i] = new List<int>();
			}

			for (int i = 0; i < m; i++) {
				if (i == target) {
					continue;
				}

				to[edges[i].Item1].Add(edges[i].Item2);
				to[edges[i].Item2].Add(edges[i].Item1);
			}

			var done = new bool[n];
			var q = new Queue<int>();
			q.Enqueue(0);
			while (q.Count > 0) {
				int cur = q.Dequeue();
				if (done[cur]) {
					continue;
				}

				done[cur] = true;
				foreach (var next in to[cur]) {
					q.Enqueue(next);
				}
			}

			for (int i = 0; i < n; i++) {
				if (done[i] == false) {
					return 1;
				}
			}

			return 0;
		}
	}
}

Measured memory_bytes: 13524
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;

int main(){
    int N;
    cin >> N;
    int max = 55555;
    int p[max+1];
    
    for(int i = 2; i <= sqrt(max); i++){
        if(p[i] == 0){
            for(int j = 2*i; j <= max; j+=i){
                p[j] = 1;
            }
        }
    }

    /*cnt cnt[5];
    for(int i = 0; i < 5; i++){
        cnt[i] = 0;
    }
    for(int i = 7; i < max+1; i++){
        if(p[i] == 0){
            cnt[i%5]++;
        }
    }
    for(int i = 0; i < 5; i++)
        cout << cnt[i] << " "; */
    
    int cnt = 0;
    int idx = 7;
    while(cnt < N){
        if(p[idx] == 0 && idx%5 == 1){
            cout << idx << " ";
            cnt++;
        } 
        idx++;       
    }
}

Measured memory_bytes: 512
#include "bits/stdc++.h"
using namespace std;

int main() {

	int N;
	cin >> N;

	vector<int64_t> a(3 * N);
	for (int i = 0;i < 3 * N;i++)
		cin >> a.at(i);

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

	int64_t ans = 0;
	for (int i = 0;i < N;i++)
		ans += a.at(3 * N - 2 - 2 * i);

	cout << ans;
	
	}

Measured memory_bytes: 2560
#include<stdio.h>
#include<stdlib.h>
#define PI 3.141592653589

int main()
{
  int a,b,ans;
  char op;
  while(1)
    {
      scanf("%d %c %d",&a,&op,&b);
      if(op == '+')
	{
	  ans = a + b;
	}
      else if(op == '-')
	{
	  ans = a - b;
	}
      else if(op == '*')
	{
	  ans = a * b;
	}
      else if(op == '/')
	{
	  ans = a / b;
	}
      else
	{
	  break; 
	}
      printf("%d\n",ans);
    }
  return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int,int>
#define ff first
#define ss second
#define boost ios::sync_with_stdio(false);cin.tie(nullptr)
#define endl "\n"
#include "string"

int32_t main(){
	boost;
	int n;
	cin >> n;
	cout << (n >= 30ll ? "Yes" : "No") << endl;		
}


Measured memory_bytes: 3648
#include<stdio.h>

#define MAX_N 1000000

int main(void){

    long int K,N,A[MAX_N],i,ans,reduce_way = 0,longest_way = 0,tmp;

    scanf("%ld %ld",&K,&N);
    for(i = 0;i < N;i++){
        scanf("%ld",&A[i]);
        if(i > 0){
            tmp = A[i] - A[i-1];
            if(tmp > longest_way){
                longest_way = tmp;
                reduce_way = i;
            }
        }
    }

    tmp = K - A[N-1] + A[0];
    if(tmp > longest_way){
        longest_way = tmp;
        reduce_way = 0;
    }

    if(reduce_way == 0){
        ans = A[N-1] - A[0];
    }else{
        ans = K - longest_way;
    }

    printf("%ld\n",ans);
    return 0;
}

Measured memory_bytes: 3584
#include <stdio.h> 
 
int main() {
  int x,i,n;
 
  scanf("%d",&n);
   
  for(i=1; i<=n; i++) {
    x = i;
     
    if(x %3 == 0) {
      printf(" %d",i);
    }
    else if(x % 10 == 3) {
      printf(" %d",i);
    } 
    else { 
      while(x != 0) {
    x /=10;
    if(x % 10 == 3) {
      printf(" %d",i);
      break;
    }
      }
    }
     
  }
  printf("\n");
  return 0;
}


Measured memory_bytes: 2052
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
      Scanner in = new Scanner(System.in);

      int N = in.nextInt();
      long ans[] = new long[87];

      ans[0] = 2;
      ans[1] = 1;

      for(int cnt = 2; cnt <= N; cnt++) {
          ans[cnt] = ans[cnt-1] + ans[cnt-2];
      }

      System.out.println(ans[N]);

    }
}


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

#define ll long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define debug3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define debugB(x, y) cerr<<#x<<": "<<bitset<y>(x) << endl;
#define line() cerr << "---------------" << endl;

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

template<typename T>
void printA(vector<T> &printArray, char between = ' ') {
   int paSize = printArray.size();
   for (int i = 0; i < paSize; i++) { cerr << printArray[i] << between;}
   if (between != '\n') {cerr << endl;}
}

// ------------------------------------------------------------------------------------------

int W, H;
char B[30][30];

int dfs(int y, int x) {
   int ret = 1;
   B[y][x] = '#';
   rep (i, 4) {
      int nx = x + dx[i], ny = y + dy[i];
      if (nx < 0 || nx >= W || ny < 0 || ny >= H || B[ny][nx] == '#') continue;
      ret += dfs(ny, nx);
   }
   return ret;
}

void solve() {
   rep (i, H) {
      cin >> B[i];
   }
   rep (i, H) {
      rep (j, W) {
         if (B[i][j] == '@') {
            cout << dfs(i, j) << endl;
            return;
         }
      }
   }
}

int main() {
   while (1) {
      cin >> W >> H;
      if (H*W == 0) break;
      solve();
   }

   return 0;
}


Measured memory_bytes: 3016
#include <bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define Mod 1000000007
#define ll long long
#define dd double
#define pb push_back
#define ff first
#define ss second
#define Mp make_pair
#define INF (ll)(1e17+5)
#define NN (ll)(1e6+5)
int mod(string s,int a) 
{ 
    int ans=0; 
    for (int i=0;i<s.length();i++) 
         ans=(ans*10+(int)s[i]-'0')%a; 
    return ans; 
}
ll min(ll x,ll y){if(x<y) return x;return y;}
ll max(ll x,ll y){if(x>y) return x;return y;}
ll power(ll x,unsigned ll y) 
{ 
    if (y==0) 
        return 1; 
    else if (y%2==0) 
        return power(x,y/2)*power(x,y/2); 
    else
        return x*power(x,y/2)*power(x,y/2); 
}
ll hcf(ll a,ll b) 
{ 
    if(b==0) 
        return a; 
    return hcf(b,a%b);  
}
int main()
{
   fio;
   /*#ifndef ONLINE_JUDGE 
    	freopen("input.txt", "r", stdin); 
    	freopen("output.txt", "w", stdout); 
    	freopen("error.txt", "w", stderr); 
   #endif*/
   ll TT=1;
   //cin>>TT;
   while(TT--)
   {    
       ll n,i,ans=0;
       cin>>n;
       vector <ll> v(n);
       map <ll,ll> mp;
       for(i=0;i<n;i++)
       {
           cin>>v[i];
           mp[v[i]]++;
       } 
       for(auto it:mp)
       {
           if(it.ss>1)
           {
               ans+=it.ss*(it.ss-1)/2;
           }
       }
       //cout<<ans<<"\n";
       for(i=0;i<n;i++)
       {
           if(mp[v[i]]>1)
           {
               ll x;
               x=ans-mp[v[i]]*(mp[v[i]]-1)/2;
               if(mp[v[i]]-1>1)
               {
                   x+=(mp[v[i]]-1)*(mp[v[i]]-2)/2;
               }
               cout<<x<<"\n";
           }
           else
            cout<<ans<<"\n";
       }
   }
}

Measured memory_bytes: 11136
def main():
  x,n = [int(i) for i in input().split()]
  table = list(map(int, input().split()))
  
  for i in range(101):
    if x - i not in table:
      print(x-i)
      exit()
    elif x + i not in table:
      print(x+i)
      exit()
    	
if __name__ == "__main__":
  main()

Measured memory_bytes: 9168
#include <stdio.h>

int main(void)
{
	char s[2],t[2];
	int i=0;
	scanf("%d%d",&s[0],&s[1]);
	for(i;i <= 1;i++)
	{
		if(s[i]==2)
			{t[i]=0;}
		else if(s[i]==4 || s[i]==6 || s[i]==9 || s[i]==11)
			{t[i]=1;}
		else
			{t[i]=2;}
	}
	if(t[0]==t[1])
		{printf("Yes");}
	else
		{printf("No");}
	return 0;
}


Measured memory_bytes: 128
n, m = map(int, input().split())
no = 0
l = []
ans = []

cityNo = 0

beforeKen = 0

for i in range(m):
    p, y = map(int, input().split())
    l.append([p, y, no])
    no += 1

l.sort()

for j in l:
    if j[0] == beforeKen:
        cityNo += 1
    else:
        cityNo = 1

    ans.append([j[2], str(j[0]).zfill(6) + str(cityNo).zfill(6)])
    beforeKen = j[0]

ans.sort()

for k in ans:
    print(k[1])


Measured memory_bytes: 41016
#include<bits/stdc++.h>
using namespace std;
int n,d,p,ans;

int main(){
  cin>>n>>d;
  while(n--){
    cin>>p;
    ans+=max(0,p-d);
  }
  if(!ans)cout<<"kusoge"<<endl;
  else cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#define ll long long
#define rep(i, s, n) for(int i = s; i < n; i++)
using namespace std;

int main() {
    int h, a; 
    cin >> h >> a;
    int b = 0;
    if(h%a != 0) {
        b = 1;
    }
    cout << h/a + b << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.util.stream.Collectors;

public class Main {

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int N=scanner.nextInt();
        int M=scanner.nextInt();
        long[] Acc=new long[N+1];

        for(int i=1;i<Acc.length;i++){
            Acc[i]=Acc[i-1]+scanner.nextInt();
        }
        Map<Long,Long> map=new HashMap<>();
        for(int i=0;i<Acc.length;i++){
            map.put(Acc[i]%M,map.getOrDefault(Acc[i]%M,0l)+1);
        }
        long result=0;
        for(Long key:map.keySet()){
            long num=map.get(key);
            result+=(num*(num-1))/2;
        }
        System.out.println(result);
    }


}


Measured memory_bytes: 62400
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define repb(i, n) for (int i = (int)n; i >= 0; i--)
#define reps(i, m, n) for (int i = (int)m; i < (int)n; i++)
#define repsb(i, m, n) for (int i = (int)m; i >= (int)n; i--)
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define pb(a) push_back(a)
#define INF 999999999
#define ll long long int
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; }
int dy[] = {0, 0, 1, -1, 0};
int dx[] = {1, -1, 0, 0, 0};
using namespace std;

int main(int argc, char const *argv[])
{
    ll dp[100100];
    int n,k;
    cin >> n>>k;
    vector<int> h(n);
    rep(i, n)
    {
        cin >> h[i];
    }
    rep(i,100100){
        dp[i] = INF;
    }
    dp[0] = 0;
    rep(i, n)
    {
        rep(j,k){
            chmin(dp[i + 1 + j], dp[i] + abs(h[i] - h[i + j + 1]));
        }
    }
    cout << dp[n - 1] << endl;
    return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;++i)



int main(){
  ll n;
  cin >> n;
  ll a[200100]={0};
  rep(i,n)cin >> a[i];
  //syakutori
  ll right=0;
  ll res=0,ans=0;
  ll buc[50]={0};
  bool flag=true;

  rep(left,n){
    flag=true;
    /*
    cout << "1:" << endl;
    rep(i,10)cout << buc[i] << " ";
    cout << endl;
*/
    while(right<n){
      rep(i,30){
        //if被りが出たら
        if(a[right]&(buc[i]<<i)){
          flag=false;
        }
      }
      if(flag){
        rep(i,30){
          if(a[right]&(1ll<<i))buc[i]++;
        }
        right++;
      }
      else break;
    }

    if(left==right)right++;
    ans+=(right-left);
    rep(i,30){
      if(a[left]&(1ll<<i))buc[i]--;
    }

  //  cout << "left:" << left <<  " right:" << right << endl;
  }
  cout << ans << endl;
}


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



int main(){
	string s;
	cin >> s;
	if(s.size()<3){
		cout << "No" << endl;
		return 0;
	}
	
	if(s[0]=='Y'&&s[1]=='A'&&s[2]=='K'&&s[3]=='I') cout << "Yes" << endl;
	else cout << "No" << endl;
	
	return 0;
}

Measured memory_bytes: 256
n=97,t,s;
int c(int i,int j,int k){printf("< %d %d %d ",i,j,k);}
int a(int i,int j,int k){printf("+ %d %d %d ",i,j,k);}
int b(int i,int j,int k){a(i,j,98);c(n,98,99);a(k,99,k);}
int m(int i,int l,int j,int p,int k){for(t=0;t<l+p-1;++t){if(t)a(k,k,k);for(s=0;s<=t;++s)if(s<p&&s+l>t)b(i+t-s,j+s,k);}}
int d(int x,int i,int l,int j){for(t=0;t<l;++t){if(t)a(j+t-1,j+t-1,j+t);a(j+t,n,j+t);for(s=t;s+1<l;++s)a(j+s,j+s,j+s+1);c(j+l-1,x,i+t);a(j+t-1,j+t-1,j+t);a(j+t,i+t,j+t);}}
main(){puts("3930");a(0,1,n);c(2,n,n);a(0,n,3);a(1,n,4);d(3,5,30,36);d(4,36,30,67);m(5,30,36,30,2);}

Measured memory_bytes: 1596
#include <stdio.h>

int main(void){
    int a,last,t;
    last=10;
    t=0;
    for(int i=0; i<5; i++){
        scanf("%d",&a);
        
        if(a%10){
            if(a%10<last)
                last=a%10;
            t++;
        }
        t+=a/10;
    }
    printf("%d",t*10+last-10);
}


Measured memory_bytes: 128
#include <atcoder/all>
#include <cstdio>

using namespace std;
using namespace atcoder;

int main()
{
    int n, q;
    scanf("%d %d", &n, &q);
    dsu d(n);
    for (int i = 0; i < q; i++)
    {
        int t, u, v;
        scanf("%d %d %d", &t, &u, &v);
        if (t == 0)
        {
            d.merge(u, v);
        }
        else
        {
            if (d.same(u, v))
            {
                printf("1\n");
            }
            else
            {
                printf("0\n");
            }
        }
    }
    return 0;
}


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

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int a,b,c; cin>>a>>b>>c;
	if (a<=c&&c<=b) cout<<"Yes\n";
	else cout<<"No"<<endl;
	return 0;
}


Measured memory_bytes: 256
/* Great things never come from comfort zones,
"whatever the mind of a man can conceive and believe,it can achieve." */
 
#include <bits/stdc++.h>
#define ll long long
#define scf(n) scanf("%d",&n)
#define lscf(n) scanf("%lld",&n)
#define lpri(n) printf("%lld ",n)
#define pri(n) printf("%d ",(int)n)
#define prin(n) printf("%d\n",(int)n)
#define lprin(n) printf("%lld\n",n)
#define rep(i,ini,n) for(int i=ini;i<(int)n;i++)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define inf INT_MAX
#define ninf INT_MIN
#define gcd __gcd
#define bitcount(n) __builtin_popcount(n)
using namespace std;
const ll mod =1e9+7;
const int N = 1e6+7;

int main()
{
       
			int n,a=0,b=0,ans=0;
			scf(n);

			string x,s;
			cin>>x;
			
			rep(i,0,n)
			(x[i]=='E')?s.pb('A'):s.pb('B');
			
			
			rep(i,0,n)
			{	
				if(s[i]=='A')
				a++;
			}

			ans=a;

			rep(i,0,n)
			{
				if(s[i]=='A')
				a--;

				else 
				b++;

				ans=min(ans,a+b);
			}

			prin(ans);

		}



Measured memory_bytes: 4308
const input=require('fs').readFileSync('/dev/stdin', 'utf8').split(/[\s]/);const nin=()=>{const r = input[0];input.shift();return Number(r)};const nrin=(n)=>{const a:number[]=[];rep(n,()=>a.push(nin()));return a};const sin=()=>{const r = input[0];input.shift();return String(r)};const out=(...a)=>{console.log(...a)};const floor=(a)=>{return Math.floor(a)};const abs=(a)=>{return Math.abs(a)};const min=(...a)=>{return Math.min(...a)};const max=(...a)=>{return Math.max(...a)};const rep=(n, callback)=>{for(let i = 0;i < n; i++){callback()}};const strrep=(s, i, v)=>{return s.slice(0, i)+v+s.slice(i+1);};const permutation=({result=[],pre=[],post,n=post.length})=>{if(n>0){post.forEach((_,i)=>{const rest=[...post];const elem=rest.splice(i, 1);permutation({result, pre: [...pre,...elem],post:rest,n:n-1})})}else{result.push(pre)}return result}

const main = ()=>{
  let[a,b]=nrin(2);
  out(a/b);
}
main();

Measured memory_bytes: 7500
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define st string
#define ve(i) vector<i>
#define repi(i, m, n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i, n) repi(i, 0, n)
#define each(i, n) for(auto&& i: n)

int main() {
  st S;
  cin >> S;
  int a = 0;
  if(S == "SUN") {
    a = 7;
  }
  else if(S == "MON") {
    a = 6;
  }
  else if(S == "TUE") {
    a = 5;
  }
  else if(S == "WED") {
    a = 4;
  }
  else if(S == "THU") {
    a = 3;
  }
  else if(S == "FRI") {
    a = 2;
  }
  else if(S == "SAT") {
    a = 1;
  }
  cout << a << endl;
}  

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
int main(){
  ll n,m;
  cin >> n >> m;
  vector<pair<ll,ll>> a(m);
  for(int i = 0;i < m;i++){
    ll ina,inb;
    cin >> ina >> inb;
    a[i] = make_pair(inb,ina);
  }
  sort(a.begin(),a.end());
  ll mae = 0;
  ll res = 0;
  for(int i = 0;i < m;i++){
    if(mae >= a[i].second)continue;
    else{
      mae = a[i].first - 1;
      res++;
    }
    //cout << i << " " << mae << endl;
  }
  cout << res << endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <array>
#include <tuple>
#include <string>
#include <algorithm>
#include <functional> // greater など
#include <cmath>      // abs など
#include <numeric>    // accumulate, gcd など
#include <cassert>    // assert
#include <stdexcept>
#include <bitset>
using namespace std;

// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
// typedef int128_t ll;
// typedef cpp_int ll;

// GCC, 配列のアクセスなど
#define _GLIBCXX_DEBUG
// Clang, 配列のアクセスなど
#define _LIBCPP_DEBUG 0

// #define NDEBUG 1
// debug用出力 https://trap.jp/post/998/
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T)
{
    cerr << H << " ";
    debug_out(T...);
}
#ifdef NDEBUG
#define debug(...)
#else
#define debug(...) debug_out(__VA_ARGS__)
#endif

//////////////// //////////////// //////////////// //////////////// ////////////////
//////////////// //////////////// //////////////// //////////////// ////////////////

// constexpr inline ll mod = 1'000'000'007;
// constexpr int max_n = 200'000 + 5;

int main()
{
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << setprecision(15); // 浮動小数の表示の精度

    int k,a,b; cin>>k>>a>>b;
    if ((a + k - 1) / k * k <= b) {
        cout << "OK" << endl;
    } else {
        cout << "NG" << endl;
    }

    return 0;
}


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

using namespace std;

int tim = 0;
vector<vector<int>> to;
vector<bool> reached;
vector<int> d;
vector<int> f;



void dfs(int point);

int main()
{
    int n;
    cin >> n;
    to.resize(n+1);
    for(int i = 1; i <= n; i++){
        int m;
        cin >> m;
        cin >> m;
        to[i].resize(m);
        for(int j = 0; j < m; j++){
            cin >> to[i][j];
        }
    }
    
    reached.resize(n+1);
    d.resize(n+1);
    f.resize(n+1);

    for(int i = 1; i <=n; i++){
        if(!reached[i]){
            dfs(i);
        }
    }

    for(int i = 1; i <= n; i++){
        cout << i << " " << d[i] << " " << f[i] << endl;
    }

    return 0;
}

void dfs(int point)
{
    tim++;
    reached[point] = true;
    d[point] = tim;

    for(int i = 0; i < to[point].size(); i++){
        if(!reached[to[point][i]]){
            dfs(to[point][i]);
        }
    }
    tim++;
    f[point] = tim;    

}

Measured memory_bytes: 1204
#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long int
#define ar array
#define mp make_pair
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int m, n;
	cin>>n>>m;
	int a[n][n];
	memset(a,0x3f,sizeof(a));
	set<array <int,3> >s;
	for(int i = 0;i <n; i++)
		a[i][i]=0;

	for(int i = 0,j,k,c ;i<m;i++)
	{
		cin>>j>>k>>c ,--j, --k;
		a[j][k]= c;
		a[k][j]= c;
		s.insert({j,k,c});
	}

    int ans=m;
	for(int k = 0; k<n;k++)
		for(int i = 0;i <n; i++)
			for(int j = 0; j<n; j++)
				a[i][j] = min(a[i][j],a[i][k]+a[k][j]);


	for(auto it:s)
	{
		for(int i = 0;i<n;i++)
			if(a[i][it[0]]+it[2]==a[i][it[1]])
			{
				ans--;
				break;
			}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
int a[10],i,sum=0,max=0,k;
int main()
{
	for (i=1;i<=3;i++)
	{
		scanf("%d",&a[i]);
		if (a[i]>max) max=a[i];
		sum+=a[i];
	}
	scanf("%d",&k);
	printf("%d",sum+max*((1<<k)-1));
	return 0;
}

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

int main(){
    int x, ans = 8;
    cin >> x;
    
    if (x <= 599) {
        ans = 8;
    } else if (x <= 799) {
        ans = 7;
    } else if (x <= 999) {
        ans = 6;
    } else if (x <= 1199) {
        ans = 5;
    } else if (x <= 1399) {
        ans = 4;
    } else if (x <= 1599) {
        ans = 3;
    } else if (x <= 1799) {
        ans = 2;
    } else {
        ans = 1;
    }
    
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 3632
# 最大値の最小値、ちょうどn/2臭い
# あとは帳尻合わせが効きそう
# 14とかだと7+4+2+1 （7+5+2でも7+4+3でもいい
# かと思いきや 1+2+3+4+5で15いくので, 5+4+3+2でよかった
# 10^7なので毎回足してもどうせ間に合う。これで答えの集合のうち最大値は確定
# あとはそれでnを引いて0になるまで -> これだと間に合わない

n = int(input())
ans = []
cur = 0

while cur != n:
    tmp = 0
    for i in range(1, n + 1 - cur):
        if i + tmp >= n - cur:
            tmp = i
            break
        tmp += i
    ans.append(tmp)
    cur += tmp
    # print("tmp = {}, cur = {}".format(tmp, cur))
# print(ans)
for a in ans:
    print(a)


Measured memory_bytes: 43740
from sys import stdin as s
from math import sqrt as sq
lx=[]
ly=[]
c=0
n=int(s.readline())
for i in range(n):
  x,y=map(int,s.readline().split())
  lx.append(x)
  ly.append(y)
for i in range(n):
  for j in range(i+1,n):
    c+=sq((lx[i]-lx[j])**2+(ly[i]-ly[j])**2)
print(c*2/n)


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

#define pi 3.141592654
#define fix(n) cout << fixed << setprecision(n)

#define rep(i,a,b) for(int i=a;i<b;i++)
#define ren(i,a,b) for(int i=a;i>=b;i--)

#define si(d)  scanf("%d",&d)
#define sll(d) scanf("%lld",&d)
#define pin(d) printf("%d\n",d)
#define pln(d) printf("%lld\n",d)
#define nl     printf("\n")

#define ll long long
#define ull unsigned long long

#define mp make_pair
#define pb push_back
#define fi first
#define se second

#define vi vector<int>
#define pii pair<int,int> 
#define piii pair<pair<int,int>,int> 

#define chalne_de continue
int mod=1000000007;
const int N = 1005;
#define inf 1e15
ll gcd(ll a , ll b)
{
    if ( b == 0)
    return a;
    return gcd( b, a % b);
}
//vector<pii> v[N];
ll dist[N][N];
int n;
void floyd()
{
    rep(k,1,n+1)
    {
        rep(i,1,n+1)
        {
            rep(j,1,n+1)
            dist[i][j] = max(dist[i][j],dist[i][k]+dist[k][j]);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    int m;
    cin >> n >> m;
    rep(i,1,n+1)
    {
        rep(j,1,n+1)
        if ( i == j)
            dist[i][j] = 0;
        else
        dist[i][j] = -inf;
    }
    rep(i,0,m)
    {
        ll x,y,c;
        cin >> x >> y >> c;
        //v[x].pb({y,c});
        dist[x][y] = c;
    }
    floyd();
    if ( dist[1][1]>0)
        cout << "inf";
    else
        cout << dist[1][n] ;

    return 0;
}


Measured memory_bytes: 8064
n=int(input())
a=list(map(int,input().split()))
x=0
y=0
z=0
for i in range(n):
    if a[i]%4==0:
        x+=1
    elif a[i]%2==0:
        y+=1
    else:
        z+=1
if y==0:
    if z<=x+1:
        print("Yes")
    else:
        print("No")
else:
    if z<=x:
        print("Yes")
    else:
        print("No")



Measured memory_bytes: 14252
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n , m;
	cin>>n>>m;
	if(n <= 0 && m >= 0)
	{
		cout<<"Zero";
		return 0;
	}
	if(n > 0 &&m > 0 || (abs(n - m) + 1) % 2  == 0)
	{
		cout<<"Positive";
	}else
	{
		cout<<"Negative";
	}
}

Measured memory_bytes: 256
#include <stdio.h>
int main(){
int p[100];
int n,q;
q=0;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&q);p[i]=q;
}
for(int k=(n-1);k>=0;k--){
printf("%d",p[k]);
if(k>(0))printf(" ");
}
printf("\n");
return 0;
}

Measured memory_bytes: 1028
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <climits>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define ALL(A)		(A).begin(),(A).end()
#define DUMP(A)    cout<<#A<<"="<<(A)<< endl
#define SIZE(A)    (int)((A).size())
using namespace std;
typedef long long ll;

int getnum(string s,int cake){
    if(s[0]=='C') return atoi(s.substr(1).c_str())-1;
    else if(s[0]=='H') return cake;
    else if(s[0]=='D') return cake+1;
    else return cake+1+atoi(s.substr(1).c_str());
}
int main(){
    int m,n,k,d;
    for(;;){
        scanf("%d%d%d%d",&m,&n,&k,&d);
        if(m==0&&n==0&&k==0&&d==0) break;
        int cals[6];
        for(int i=0;i<m;i++){
            cin>>cals[i];
        }
        pair<pair<int,int>,int> ps[512];
        for(int i=0;i<d;i++){
            string a,b;
            int d;
            cin>>a>>b>>d;
            ps[i*2]=make_pair(make_pair(getnum(a,m),getnum(b,m)),d);
            ps[i*2+1]=make_pair(make_pair(getnum(b,m),getnum(a,m)),d);
        }
        int cakepat=1<<m,vnum=m+n+2;
        int ds[108][64];
        const int INF=10000000;
        for(int ix=0;ix<vnum;ix++){
            for(int i=0;i<cakepat;i++){
                ds[ix][i]=INF;
            }
        }
        ds[m][0]=0;
        for(;;){
            bool isc=false;
            for(int i=0;i<d*2;i++){
                for(int j=0;j<cakepat;j++){
                    int fromnum=ps[i].first.first,tonum=ps[i].first.second,d=ps[i].second;
                    if(tonum<m){
                        if(j&(1<<tonum)) continue;
                        else{
                            if(ds[tonum][j|(1<<tonum)] > ds[fromnum][j]+d*k-cals[tonum]){
                                ds[tonum][j|(1<<tonum)] = ds[fromnum][j]+d*k-cals[tonum];
                                isc=true;
                            }
                        }
                    }else{
                        if(ds[tonum][j]>ds[fromnum][j]+d*k){
                            ds[tonum][j]=ds[fromnum][j]+d*k;
                            isc=true;
                        }
                    }
                }
            }
            if(!isc) break;
        }
        int mind=INF;
        for(int i=0;i<cakepat;i++){
            mind=min(mind,ds[m+1][i]);
        }
        printf("%d\n",mind);
    }
}

Measured memory_bytes: 0
#!/usr/bin/env python3

import sys

DEBUG = False

def read(t):
    return t(sys.stdin.readline().rstrip())


def read_list(t, sep = " "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]


def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return


def main():
    x = read(int)

    m = 100
    i = 0
    while m < x:
        m = int(m * 1.01)
        i += 1
    print(i)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9192
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second

int n, m;
vector<pp> edge[200010];

int S, T;

ll d[2][200010];
ll w[2][200010];
ll rw[2][200010];
bool re[2][200010];

priority_queue<pair<ll,int>> pq;
int order[100010];

const ll mod = 1'000'000'007, inf = 1ll<<60;

void Work(int S, ll *d, ll *w, ll *rw, bool *re){
	int T=::S+::T-S;
	for(int i=1; i<=n; ++i) d[i]=inf; d[S]=0; pq.emplace(0, S); w[S] = 1;
	int on = 0;
	while(pq.size()){
		int p; ll md; tie(md, p)=pq.top(); pq.pop();
		if(md != -d[p]) continue;
		order[on++] = p;
		for(auto tmp:edge[p]){
			int y, e; tie(y, e) = tmp;
			if(d[y]>e-md){
				d[y]=e-md;
				w[y]=w[p];
				pq.emplace(-d[y], y);
			} else if(d[y]==e-md){
				(w[y]+=w[p]) %= mod;
			}
		}
	}
	rw[T]=1; re[T]=1;
	for(int i=on-1; 0<=i; --i){
		int p=order[i];
		if(!re[p]) continue;
		for(auto tmp:edge[p]){
			int q, e; tie(q, e) = tmp;
			if(d[q] == d[p]-e){
				(rw[q] += rw[p]) %= mod;
				re[q]=1;
			}
		}
	}
}

bool intersect(ll a, ll b, ll c, ll d){
	return min(b, d)-max(a, c)>=1;
}

int main()
{
	read(n, m, S, T);
	for(int i=1; i<=m; ++i){
		int a, b, c; read(a, b, c);
		edge[a].eb(b, c); edge[b].eb(a, c);
	}
	Work(S, d[0], w[0], rw[0], re[0]);
	Work(T, d[1], w[1], rw[1], re[1]);
	
	ll ans = 0;
	
	for(int i=1; i<=n; ++i){
		for(auto tmp:edge[i]){
			int j, e;
			tie(j, e) = tmp;
			if(d[0][j]==d[0][i]+e && re[0][i] && re[0][j] &&
			   d[1][i]==d[1][j]+e && re[1][i] && re[1][j]){
				if(intersect(d[0][i], d[0][j], d[1][j], d[1][i])){
					(ans += w[0][i] * w[1][j] % mod * rw[0][j] % mod * rw[1][i] % mod) %= mod;
				}
			}
		}
		if(d[0][i] == d[1][i]){
			(ans += w[0][i] * w[1][i] % mod * rw[0][i] % mod * rw[1][i] % mod) %= mod;
		}
	}
	
	printf("%lld\n", ((w[0][T]*w[1][S]%mod-ans)%mod+mod)%mod);
	return 0;
}


Measured memory_bytes: 21496
#include <stdio.h>
#define MAX 100000
#define NIL -1
 
struct Node{
  int parent;
  int left;
  int right;
};

struct Node T[MAX];

void Pre(int);
void In(int);
void Post(int);
 
int main()
{
  int n, k, root, node, child;
  int i, j;
 
  scanf("%d", &n);

  for(i=0; i<n; i++){
    T[i].parent = NIL;
    T[i].left = NIL;
    T[i].right = NIL;
 }
  
 for(i=0; i<n; i++){
   scanf("%d", &node);
   for(j=0; j<2; j++){
     scanf("%d", &child);
     if(child != NIL){
       T[child].parent = node;
       if(j==0) T[node].left = child;
       else T[node].right = child;
     }
   }
 }

 for(i=0; i<n; i++){
   if(T[i].parent == NIL) root = i;
 }

 printf("Preorder\n");
 Pre(root);
 printf("\n");
 printf("Inorder\n");
 In(root);
 printf("\n");
 printf("Postorder\n");
 Post(root);
 printf("\n");

 return 0;
}

void Pre(int root)
{
  printf(" %d", root);
  if(T[root].left != NIL) Pre(T[root].left);
  if(T[root].right != NIL) Pre(T[root].right);
}
 
void In(int root)
{
  if(T[root].left != NIL) In(T[root].left);
  printf(" %d", root);
  if(T[root].right != NIL) In(T[root].right);
}
 
void Post(int root)
{
  if(T[root].left != NIL) Post(T[root].left);
  if(T[root].right != NIL) Post(T[root].right);
  printf(" %d", root);
}

Measured memory_bytes: 616
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

ll mul1[2001], mul2[2001];
constexpr int mod = 1000000007;
struct mint {
  long long x;
  constexpr mint(long long x = 0) : x((x % mod + mod) % mod) {}
  constexpr mint operator-() const { return mint(-x); }
  constexpr mint &operator+=(const mint &a) {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  constexpr mint &operator-=(const mint &a) {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  constexpr mint &operator*=(const mint &a) {
    (x *= a.x) %= mod;
    return *this;
  }
  constexpr mint operator+(const mint &a) const {
    mint res(*this);
    return res += a;
  }
  constexpr mint operator-(const mint &a) const {
    mint res(*this);
    return res -= a;
  }
  constexpr mint operator*(const mint &a) const {
    mint res(*this);
    return res *= a;
  }
  constexpr mint pow(long long t) const {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

  constexpr mint inv() const { return pow(mod - 2); }
  constexpr mint &operator/=(const mint &a) { return (*this) *= a.inv(); }
  constexpr mint operator/(const mint &a) const {
    mint res(*this);
    return res /= a;
  }
};
ostream &operator<<(ostream &os, const mint &m) {
  os << m.x;
  return os;
}

void comb(ll n, ll r, bool type) {
  mint res = 1;
  for (int i = 1; i <= r; i++) {
    res *= n;
    res /= i;
    if (type)
      mul1[i] = res.x;
    else
      mul2[i] = res.x;
    n--;
  }
}

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

  int n, k;
  cin >> n >> k;
  int red = n - k;

  mul1[0] = 1;
  comb(k - 1, k - 1, true);
  comb(red + 1, red + 1, false);

  rep(i, 1, k + 1) {
    mint ans = (mul1[i - 1] * mul2[i]);
    cout << ans.x << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 
int main() {
ll N;
  cin>>N;
  ll ans=1;
  for(ll i=1;i<=N;i++) {
ans*=i;
    ans%=1000000007;
  }
  
  cout<<ans<<endl;
}
  
  
  
  
  


Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n;
	vector<int> a(3);
	cin >> n;
	int dp[3][n];
	int ans = 0;
	for (int i{}; i < 3; i++) {
		cin >> a[i];
		dp[i][0] = a[i];
		ans = max(ans, a[i]);
	}
	
//	n--;
	for (int i{1}; i < n; i++) {
		for (auto &x : a) {
			cin >> x;
		}
		dp[0][i] = max(dp[1][i - 1], dp[2][i - 1]) + a[0];
		dp[1][i] = max(dp[0][i - 1], dp[2][i - 1]) + a[1];
		dp[2][i] = max(dp[0][i - 1], dp[1][i - 1]) + a[2];
	}
	cout << max(max(dp[0][n - 1], dp[1][n - 1]), max(dp[0][n - 1], dp[2][n - 1]));
}


Measured memory_bytes: 4796
/*
author: Apoorv Singh
*/

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

typedef vector <long long> vi;
typedef pair <long long, long long> pii;
#define pb push_back   
#define all(c) c.begin(), c.end()
#define FOR(i, a, b) for (long long i = a; i < b; ++i)
#define FORR(i, a, b) for (long long i = a; i > b; --i)
#define um unordered_map
#define F first
#define S second
#define int long long
#define inf LLONG_MAX
#define endl "\n"
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _CRT_SECURE_NO_WARNINGS

#define TRACE
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

template <class X>
void printarr(X arr[], int n)
{
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << endl;
}
template <typename X> ostream& operator << (ostream& x,const vector<X>& v){ for (X a : v) x << a << ' '; return x;} 
template <typename X, typename Y> ostream& operator << (ostream& x, const vector< pair<X, Y> >& v) {for (pair <X, Y> it : v) x << it.first << ' ' << it.second << endl; return x;} 
template <typename T, typename S> ostream& operator << (ostream& os, const map<T, S>& v) { for (pair <T, S> it : v) os << it.first << " => " << it.second << endl; return os; }

double pi = 3.14159265358979323846264338327950288419716939937510582097494459230;
int modulo = 1e9 + 7;

int fpow(int a, int n)
{
    int ans = 1;
    while (n)
    {
        if (n&1)
            ans = (ans * a)%modulo;
        a = (a*a)%modulo;
        n = n >> 1;
    }
    return ans;
}

/*
const int M = 1e6 + 10;
int composite[M] = {0};

void sieve()
{
    FOR(i,2,M)
    {
        if (!composite[i])
        {
            for (int j = 2*i; j < M; j += i)
                composite[j] = max(composite[j], i);
        }
    }
}
*/

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,l; cin >> n >> l;
    int sum = 0;
    FOR(i,1,n+1) sum += (l+i-1);
    int ans, y = inf;
    FOR(i,1,n+1)
    {
        int x = sum - (l+i-1);
        int z = abs(sum - x);
        if (z < y)
        {
            y = z;
            ans = x;
        }
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 256