akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;
using static Input;

public class Prog
{
    private const int INF = 1000000007;
    private const long INFINITY = 9223372036854775807;
    private static int[] make_cost = { 0, 2, 5, 5, 4, 5, 6, 3, 7, 6 };
    public static void Main()
    {
        int N = NextInt();
        int M = NextInt();
        int[] A = LineInt();
        for (int i = 0; i < N; i++) A[i] %= M;
        List<int> B = new List<int>();
        B.Add(0);
        for (int i = 0; i < N; i++) B.Add((B[i] + A[i]) % M);
        B.Sort();
        long ans = 0;
        for (int i = 0; i <= N;)
        {
            int b = B[i];
            long c = 0;
            for (; i <= N; i++)
            {
                if (B[i] != b) break;
                c++;
            }
            ans += c * (c - 1) / 2;
        }
        Console.WriteLine(ans);
    }
}

public class Input
{
    private static Queue<string> q = new Queue<string>();
    private static void Confirm() { if (q.Count == 0) foreach (var s in Console.ReadLine().Split(' ')) q.Enqueue(s); }
    public static int NextInt() { Confirm(); return int.Parse(q.Dequeue()); }
    public static long NextLong() { Confirm(); return long.Parse(q.Dequeue()); }
    public static string NextString() { Confirm(); return q.Dequeue(); }
    public static double NextDouble() { Confirm(); return double.Parse(q.Dequeue()); }
    public static int[] LineInt() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] LineLong() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] LineString() { return Console.ReadLine().Split(' ').ToArray(); }
    public static double[] LineDouble() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
}


Measured memory_bytes: 22880
from sys import stdin
N = int(stdin.readline().rstrip())
ans = 0
for i in range(1,N+1):
    if i % 3 == 0 and i % 5 == 0:
        continue
    elif i % 3 == 0:
        continue
    elif i % 5 == 0:
        continue
    else:
        ans += i
        
print(ans)

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

int main() {
  ll x;
  cin >> x;
  ll y=100;
  int i= 0;
  while(x>y) {
    y*=1.01;
    i++;
  }
  cout << i << endl;
  return 0;
}

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

int main()
{
    int N;
    cin >> N;
    vector<long int> L(N);
    int i, j, k;
    for (i = 0; i < N; i++)
    {
        cin >> L[i];
    }
    long int count = 0;
    vector<long int> Ls(3);
    for (i = 0; i < N; i++)
    {
        for (j = i + 1; j < N; j++)
        {
            for (k = j + 1; k < N; k++)
            {
                Ls[0] = L[i];
                Ls[1] = L[j];
                Ls[2] = L[k];
                sort(Ls.begin(), Ls.end());
                if (Ls[0] + Ls[1] > Ls[2] && Ls[0] != Ls[1] && Ls[1] != Ls[2])
                {
                    count += 1;
                }
            }
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 3596
n=int(input())
g=[[]for i in range(n)]
for i in range(n):
    d=list(map(int,input().split()))
    for j in range(d[1]):
        g[d[0]].append((d[2+j*2+1],d[2+j*2]))

def dijkstra(g,st,ed):
    from heapq import heappush, heappop, heapify
    inf=10**18
    dist=[inf for i in range(len(g))]
    visited=[False for i in range(len(g))]
    dist[st]=0
    que=[]
    heappush(que,(0,st))
    while que:
        c,v=heappop(que)
        if visited[v]:
            continue
        visited[v]=True
        for x in g[v]:
            tmp=x[0]+c
            if tmp<dist[x[1]] and not visited[x[1]]:
                dist[x[1]]=tmp
                heappush(que,(tmp,x[1]))
    return dist

dist=dijkstra(g,0,n-1)
for i in range(n):
    print(i,dist[i])


Measured memory_bytes: 68840
// #define _CRT_SECURE_NO_WARNINGS
// #define _USE_MATH_DEFINES
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <locale>
#include <cctype>
#include <sstream>
#include <iomanip>	// 10桁出力 cout << setprecision(10) << double;
#include <queue>
using namespace std;

typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef map<int, int> MAPII;
typedef multimap<int, char, greater<int> > MuMAPIC;
typedef vector<pair<int, int> > VPII;
typedef multimap<int, string, greater<int> > MuMIS;
typedef pair<int, int> P;
typedef pair<int, pair<P, P> > PP;

#define MP make_pair
#define FAST_IO  cin.tie(0); ios::sync_with_stdio(false);
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
//for gcc (未test)
// #define FOREACH_IT(it,c) for(typeof(c)::iterator it=(c).begin(); it!=(c).end(); ++it)
//for Visual Studio
#define foreach_it(type,it,c) for(type::iterator it=c.begin(),c_end=c.end();it!=c_end;++it)
// for Debug.
#define DUMP_VVI(b) FOR(i,0,b.size()){FOR(j,0,b[i].size())printf("%d ",b[i][j]);puts("");}
#define D_OUT(str,value) if(dbgF){cout<<str<<" : "<<value<<endl;}
// 入力をpush_back(d)やarray[d]に使う時に1行で書ける
// int INPUT_INT() {int d;cin>>d;return d;}
template<class T>T IN() { T d; cin >> d; return d; }
// 最大公約数（Greatest Common Divisor）
LL gcd(LL a, LL b) { return (b > 0) ? gcd(b, a%b) : a; }
// 最小公倍数（Least Common Multiple）
LL lcm(LL a, LL b) { return a / gcd(a, b) * b; }
// Y年はうるう年か否か
bool uruu(LL Y) { return (((Y % 4 == 0 && Y % 100 != 0) || Y % 400 == 0) ? true : false); }

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

// vector注意
// vec[i][j]の形に入力を入れるとき、vecは初期化してある必要がある.

// ------------------- include, typedef, define END. -------------------
struct ToUpper {
	char operator()(char c) { return toupper(c); }
};
int main() {
	FAST_IO;
	// for D_OUT(str, value)  ... cout<< str <<" : "<< value <<endl;
	bool dbgF = true;

	//コードはここから書く.
	string a, b, c;
	cin >> a >> b >> c;
	transform(a.begin(), a.end(), a.begin(), ToUpper());
	transform(b.begin(), b.end(), b.begin(), ToUpper());
	transform(c.begin(), c.end(), c.begin(), ToUpper());
	cout << a[0] << b[0] << c[0] << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; ++i)
#define REPP(i, n) for(int i = 1; i <= n; ++i)
#define REPR(i, n) for(int i = n-1; i >= 0; --i)
#define FOR(i, m, n) for(int i = m; i < n; ++i)
#define ALL(v) v.begin(), v.end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1000000007;
const ll INF = 1000000000;

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b) {if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b) {if(a<b) a=b;}

struct UnionFind {
    vector<int> par, size;
    UnionFind(int n) : par(n), size(n,1) {
        for(int i = 0; i < n; ++i) par[i] = i;
    }
    void Union(int x, int y) {
        x = Find(x), y = Find(y);
        if(x == y) return;
        if(size[x] < size[y]) swap(x,y);
        size[x] += size[y];
        par[y] = x;
    }
    int Find(int x) {
        if(par[x]==x) return x;
        else return par[x] = Find(par[x]);
    }
    bool Same(int x, int y) {
        return Find(x) == Find(y);
    }
    int Size(int x) {
        return size[Find(x)];
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m; cin >> n >> m;
    vector<int> p(n);
    REP(i,n) {
        cin >> p[i]; -- p[i];
    }
    UnionFind uf(n);
    REP(i,m) {
        int x,y; cin >> x >> y; --x, --y;
        uf.Union(x,y);
    }
    int ans = 0;
    REP(i,n) {
        if(uf.Same(i,p[i])) ++ ans;
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
    int N;
    cin>>N;
    vector<string> S(N);
    for(int i=0;i<N;i++){
        cin>>S.at(i);
    }
    sort(S.begin(),S.end());
    int count=0;
    for(int i=0;i<N-1;i++){
        if(S.at(i)==S.at(i+1)){
            count++;
        }    
    }
    cout<<N-count<<endl;
}

Measured memory_bytes: 9552
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define ALL(a) (a).begin(), (a).end()
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll, ll> pii;
const ll INF = 1LL << 58;
const ll MOD = 1000000007;
typedef vector<pii> vpii;
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;
}

signed main()
{
    //  以降 cin の入力元が 'input.txt' になる
    //std::ifstream in("input.txt");
    //std::cin.rdbuf(in.rdbuf());
    int a,b,c;
    cin >> a >> b >> c;
    cout << c << " " << a << " " << b << endl;

    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define MOD (ll)(1e9+7)
#define INF 1e17
#define int ll
#define EPS (1e-6)
using namespace std;
using ll=long long;
using pii=pair<int,int>;

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

int fpow(int b,int p)
{
	if(p==0) return 1;
	int h=fpow(b,p/2);
	if(p%2) return h*b%MOD*h%MOD;
	return h*h%MOD;
}

struct Node{
	int len;
	int par;
	map<int,int> con;
}; vector<Node> grp;

void bfs(int k){
	queue<int> que;
	que.emplace(k);
	while(!que.empty()){
		int now=que.front(); que.pop();
		for(auto &i:grp[now].con){
			if(i.F!=grp[now].par){
				que.emplace(i.F);
				grp[i.F].par=now;
				grp[i.F].len=grp[now].len+i.S;
			}
		}
	}
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n; cin>>n;
	grp.resize(n+1);
	int s,t,l;
	For(i,0,n-2){
		cin>>s>>t>>l;
		grp[s].con[t]=l;
		grp[t].con[s]=l;
	}
	int q,k; cin>>q>>k;
	grp[k].par=0;
	grp[k].len=0;
	bfs(k);
	while(q--){
		cin>>s>>t;
		cout<<grp[s].len+grp[t].len<<"\n";
	}
	return 0;
}





























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

#define FOR(i,a,b) for(int i = (a);i < (b);i++)
#define RFOR(i,a,b) for(int i = (b)-1;i >= (a);i--)
#define REP(i,n) FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))

using namespace std;

typedef pair<int, int> P;
#define pb push_back
#define mp make_pair
#define ft first
#define sd second

#define INF 1000000000
#define index(a, b, c) (a)*81+(b)*9+(c)

int N;
char s[100004];
int dp[2][2*9*9];

bool input(){
  cin>>s;
  if(s[0]=='#')return false;
  N = strlen(s);
  REP(i, N)s[i] -= '1';
  return true;
}

int x[9] = {0,1,2,0,1,2,0,1,2};

void solve(){
  REP(i, 2) {
  	REP(j, 9) {
  		REP(k, 9) {
  			if(x[j]>x[k]) dp[0][index(i, j, k)] = INF;
  			else dp[0][index(i, j, k)] = 0;
  		}
  	}
  }
  
  REP(l, N) {
    REP(i, 2*9*9)dp[1][i] = INF;
    
  	REP(i, 2) {
  		REP(j, 9) {
  			REP(k, 9) {
  				if(dp[0][index(i, j, k)] == INF)continue;
  				if(x[s[l]]<=x[k])
  				dp[1][index(0, s[l], k)] = min(dp[1][index(0, s[l], k)], dp[0][index(i, j, k)]+(i==0));
  				if(x[s[l]]>=x[j])
  				dp[1][index(1, j, s[l])] = min(dp[1][index(1, j, s[l])], dp[0][index(i, j, k)]+(i==1));
  				
  			}
  		}
  	}
  	
    REP(i, 2*9*9)dp[0][i] = dp[1][i];
  }
  
  int a = INF;
  /*REP(i, N+1){
    REP(j,2*9*9){
      if(dp[i][j] == INF)
        cout<<'N';
      else
        cout<<dp[i][j];
      if((j+1)%9==0)cout<<' ';
    }
    cout<<endl;
  }*/
  REP(i, 2*9*9) {
    a = min(a, dp[1][i]);
  }
  cout<<a<<endl;
}

int main(){
  //cin.tie(0);
  
  while (input()){
      solve();
  }
  
  return 0;
}

Measured memory_bytes: 3148
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);
    int num[100005];
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&num[i]);
    }
    int sum=0;
    for(int i=1; i<=n; i++)
    {
        if(num[i]==i)
        {
            if(i==1)
                swap(num[i],num[i+1]);
                else if(num[i+1]==i+1)
                    swap(num[i],num[i+1]);
                    else if(num[i-1]==i-1)
                        swap(num[i],num[i-1]);
                        else
                            swap(num[i],num[i-1]);
                            sum++;
        }
    }
    printf("%d\n",sum);
    return 0;
}


Measured memory_bytes: 640
import java.util.*;

public class Main{
    
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int[] d = new int[N];
        
        long ans = 0;
        for(int i = 0; i < N; i++){
            d[i] = sc.nextInt();
        }
        for(int i = 0; i < N; i++){
            for(int j = i+1; j < N; j++){
                ans += d[i]*d[j];
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 22996
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


# 処理内容
def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = 1
    if 0 in A:
        ans = 0
    else:
        for a in A:
            ans *= a
            if ans > 1000000000000000000:
                ans = -1
                break
    print(ans)


if __name__ == '__main__':
    main()

Measured memory_bytes: 87000
#include<iostream>
#include<map>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
    string S;
    cin>>S;
    map<char, int> chrmap;
    for(int i=0;i<S.size();++i){
        chrmap[S[i]]++;
    }
    char ans = 'A';
    for(char i='a';i<='z';++i){
        if(chrmap[i]==0){
            ans = i;
            break;
        }
    }
    if(ans=='A'){
        bool can = false;
        int index;
        vector<char> arr;
        char max;
        for(int i=25;i>=1;--i){
            if(S[i-1]<S[i]){
                can = true;
                index = i-1;
                max = S[i-1];
                arr.push_back(S[i]);
                break;
            }
            else {
                arr.push_back(S[i]);
            }
        }
        if(can){
        for(int i=0;i<index;++i){
            cout<<S[i];
        }
        sort(arr.begin(), arr.end());
        for(int i=0;i<arr.size();++i){
            if(S[index]<arr[i]){
                cout<<arr[i]<<endl;
                break;
            }
        }
        }
        else cout<<-1<<endl;
    }
    else cout<<S+ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(n); ++i)
#define repr(i, a, b) for (int i=a; i<(b); ++i)
#define reprev(i, n) for (int i=n-1; i>=0; --i)
#define reprrev(i, a, b) for (int i=b-1; i>=(a); --i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
    cout << fixed << setprecision(10);
    
    int N; cin >> N;
    rep(i, 3) {
        if (N % 10 == 7) {
            cout << "Yes" << endl;
            return 0;
        }
        N /= 10;
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3568
n=int(input())
f=[list(map(int,input().split())) for _ in [0]*n]
p=[list(map(int,input().split())) for _ in [0]*n]
s=-float('inf')
for i in range(1,2**10):
    l=list(map(int,'0'*(12-len(bin(i)))+bin(i)[2:]))
    s=max(s,sum(p[j][sum(l[i] and f[j][i] for i in range(10))] for j in range(n)))
print(s)

Measured memory_bytes: 3064
#include <iostream>
#include <ios>
#include <iomanip>
using namespace std;

int main(void){
  int a;
  int student;
  cout<<setfill('0')<<right;
  while(cin>>a){
    student=a%39;
    if(student==0){
      student=39;
    }
    cout<<"3C"<<setw(2)<<student<<endl;
  }
  return 0;
}



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

using namespace std;

#define inf 1<<30
#define llong long long
#define usd unsigned
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define fn fill_n
typedef pair<int, int> P;
typedef struct data{
	int now;
	int cost;
}data;
int nw[9] = {0, 1, 0, -1, -1, 1, 1, -1, 0};
int nh[9] = {1, 0, -1, 0, 1, 1, -1, -1, 0};
int a,b,c,d, A[100], B[100], C[100][100], D[100][100][100];
string s, t, r;




int main(){
	cin >> a >>b >>c;
	cout << min(min(abs(a-b)+abs(b-c), abs(b-c)+abs(c-a)), abs(c-a)+abs(a-b)) << endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String x = in.next();
        if (n >= 3200) {
            System.out.println(x);
        } else {
            System.out.println("red");
        }


    }

}


Measured memory_bytes: 22100
import math
def dist(p, x, y):
    s = 0
    for i, j in zip(x, y):
        s += abs(i - j) ** p
    return s ** (1 / p)

n = int(input())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
print(dist(1, x, y))
print(dist(2, x, y))
print(dist(3, x, y))
print(max(abs(i-j) for i, j in zip(x, y)))


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

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
const int INF = 1e9;

int main() {
  ll n, k;
  cin >> n >> k;
  vector<ll> x(n);

  rep(i, n) cin >> x[i];

  ll ans = INF;
  for (int i = 0; i < n - k + 1; ++i) {
    ans = min({ans, abs(x[i]) + abs(x[i + k - 1] - x[i]),
               abs(x[i + k - 1]) + abs(x[i + k - 1] - x[i])});
  }

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


Measured memory_bytes: 1024
#include <stdio.h>
#include <stdlib.h>
int desc(const void *a, const void *b) {
  return *(int *)b - *(int *)a;
}

int main(void){
    int n,i,r=1,before;
    int arr[999];
    scanf("%d",&n);
    for(i=0;i<n;i++)scanf("%d",arr+i);
    printf(arr+i);
    qsort(arr,n,4,desc);
    before=arr[0];
    for(i=1;i<n;i++){
        if(before!=arr[i]){
            before=arr[i];
            r++;
        }
    }
    printf("%d\n",r);
    return 0;
}

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

int main() {
    int n, Z, W, a[2000];
    cin >> n >> Z >> W;
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    if(n == 1){
        cout << abs(W - a[0]) << endl;
    }
    else{
        cout << max(abs(W - a[n-1]), abs(a[n-2] - a[n-1])) << endl;
    }
    return 0;
}


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


int main() {
  int a, b, c, K; cin >> a >> b >> c >> K;
  int m = max(a, max(b, c));
  int  _m = m;

  for(int i=0; i<K; i++){
    m = 2 * m;
  }

  cout << a+b+c+m-_m << endl;

  return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <climits>
#include <iomanip>
#include <deque>
#include <limits>
#include <map>
#include <set>
#include <functional>

using namespace std;

const string YES = "Yes";
const string NO = "No";

int main()
{
  int X, Y;

  cin >> X >> Y;

  if ((4 * X - Y) % 2 == 0 && (Y - 2 * X) % 2 == 0 && 4 * X - Y >= 0 && Y - 2 * X >= 0) {
    cout << YES << endl;
  }
  else {
    cout << NO << endl;
  }

  return 0;
}


Measured memory_bytes: 3624
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
using namespace std;
#define MOD 1000000007
#define INF (1<<29)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

Int n, s, res;
Int x[108000], p[108000];

int main(){
  cin >> n >> s;
  for(int i = 0;i < n;i++){
    cin >> x[i] >> p[i];
  }
  int l = 0, r = n-1;
  vector<Int> pos;
  while(x[l] < s && s < x[r]){
    if(p[l] >= p[r]){
      pos.push_back(x[r]);
      p[l] += p[r];
      r--;
    }
    else{
      pos.push_back(x[l]);
      p[r] += p[l];
      l++;
    }
  }
  if(x[r] < s)pos.push_back(x[l]);
  else pos.push_back(x[r]);
  for(int i = pos.size() - 1;i >= 0;i--){
    res += abs(s - pos[i]);
    s = pos[i];
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 2936
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
using namespace std;
#define REP(i,a,n) for(int i = a ; i < n ; i++)
#define rep(i,n) REP(i,0,n)

typedef long long ll;

void solve(){
}

int main(){
  double min=-1,max=-1;
  double h;

  while(cin>>h){
    if(min == -1 || min > h) min = h;
    if(max == -1 || max < h) max = h;
  }
  printf("%.1f\n",max-min);
}

Measured memory_bytes: 0
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(N)]
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(N):
    for w in range(1,W+1):
        if w-wv[i][0]<0:
            dp[i+1][w] = dp[i][w]
            continue
        dp[i+1][w] = max(dp[i][w],dp[i][w-wv[i][0]]+wv[i][1])
print(dp[N][W])

Measured memory_bytes: 173448
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int N, L[200];
    cin >> N;
    for (int i = 0; i < 2 * N; i++) cin >> L[i];
    sort(L, L + 2 * N);
    int ans = 0;
    for (int i = 0; i < 2 * N; i+=2) ans += L[i];
    cout << ans << endl;
}


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

using namespace std;

int main(void)
{
    int N;
    cin >>N;

    vector<int> K(3,0);

    long long result = 1; 
    long long lim = 1000000007;
    for(int i=0;i<N;i++){
        int num;
        cin>>num;
        bool first = true;
        long long times = 0;
        for(int j=0;j<3;j++){
            if(K[j]==num){
                times++;
                if(first){
                    K[j]++;
                  first =false;
                }
            }
        }
        result *= times;
        result %= lim;
    }

    cout<<result<<endl;

    return 0;
}

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

class Main
{

	public static void main(String[] args) throws NumberFormatException, IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		ArrayList<String> strLst = new ArrayList<String>();
		int cnt = 0;
		int max;
		int other;
		String inputLine = "";
		String[] lines;

		br.readLine();
		while (cnt <= 1000 && (inputLine = br.readLine()) != null)
		{
			max = 0;
			other = 0;
			lines = inputLine.split(" ");

			for (int i = 0; i < 3; ++i)
			{
				other += (int) Math.pow(Integer.parseInt(lines[i]), 2);
				if (max < Integer.parseInt(lines[i]))
				{
					max = Integer.parseInt(lines[i]);
				}
			}
			other -=(int) Math.pow(max, 2);

			if (other == (int) Math.pow(max, 2))
				strLst.add("YES");
			else
				strLst.add("NO");

			++cnt;
		}

		for(String result : strLst)
		{
			System.out.println(result);
		}

	}

}

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

#define int long long int
#define mp make_pair
using namespace std;

int32_t main() {
    int n;
    scanf("%lld", &n);
    int p = 1;
    int c = 0;
    while((p*(p+1))/2 <= n){
        if((p*(p+1))/2 == n){
            c = 1;
        }
        //printf("%lld",p);
        p++;
    }
    if(c == 0){
        printf("No");
        return 0;
    }
    vector<int> v[p];
    //printf("here");
    int index = 1;
    int x = 2;
    int no = 1;
    while(no <= n){
        for (int i = 0; i < index; ++i) {
            v[i].push_back(no);
            v[index].push_back(no);
            no++;
        }
        index++;
    }
    printf("Yes\n");
    printf("%lld\n",index);
    for (int i = 0; i < index; ++i) {
        int a = v[i].size();
        printf("%lld ",v[i].size());
        for (int j = 0; j < v[i].size(); ++j) {
            printf("%lld ",v[i][j]);
        }
        printf("\n");
    }
    return 0;
}

Measured memory_bytes: 3200
import           Control.Monad
import           Control.Monad.ST
import qualified Data.Array                    as A
import qualified Data.Array.ST                 as ST
import qualified Data.Array.Unboxed            as AU
import qualified Data.ByteString.Char8         as BS
import           Data.Char
import           Data.Int
import qualified Data.IntMap                   as IM
import           Data.List
import qualified Data.Map                      as M
import           Data.Maybe
import           Data.Ord
import qualified Data.Set                      as S
import           Data.Time
import qualified Data.Vector                   as V
import qualified Data.Vector.Mutable           as VM
import qualified Data.Vector.Unboxed           as VU
import qualified Data.Vector.Unboxed.Mutable   as VUM

readInt :: IO [Int]
readInt = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine

readInts :: Int -> IO [[Int]]
readInts n = replicateM n readInt

readString :: IO [String]
readString = map BS.unpack . BS.words <$> BS.getLine

readStrings :: Int -> IO [[String]]
readStrings n = replicateM n <$> readString

toPair :: [a] -> (a, a)
toPair [x, y] = (x, y)

main = do
    [h, w] <- readInt
    m      <- replicateM h getLine
    putStrLn $ solve m h w

solve :: [[Char]] -> Int -> Int -> String
solve m h w | b         = "Yes"
            | otherwise = "No"
  where
    am = A.array
        ((0, 0), (h - 1, w - 1))
        [ ((i, j), f $ m !! i !! j) | i <- [0 .. h - 1], j <- [0 .. w - 1] ]
    b = and [ g am u o h w | u <- [0 .. h - 1], o <- [0 .. w - 1] ]

g :: A.Array (Int, Int) Bool -> Int -> Int -> Int -> Int -> Bool
g am i j h w
    | am A.! (i, j) = am A.! (i, j) && any (\(i', j') -> am A.! (i', j'))
                                           (s i j h w)
    | otherwise = True

s i j h w =
    filter (\(a, b) -> 0 <= a && a < h && 0 <= b && b < w)
        $ [(i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)]

f :: Char -> Bool
f s | s == '#'  = True
    | otherwise = False


Measured memory_bytes: 1148
#include<stdio.h>
#include<string.h>
int main()
{
	int s;
	scanf("%c",&s);
	if(s=='S'){
		printf("Cloudy\n");
	}
	if(s=='C'){
		printf("Rainy\n");
	}
	if(s=='R'){
		printf("Sunny\n");
	}
	return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define REP(i, n) for(int i = 1; i < (int)(n); ++i)
using namespace std;

vector<int> size(51, 1);
vector<int> MAX(51, 1);

int f(int n, int x) {
    if (n == 0) return x;
    if (x == 0) return 0;
    if (x < size[n - 1] + 2) return f(n - 1, x - 1);
    if (x == size[n - 1] + 2) return MAX[n - 1] + 1;
    if (x == size[n]) return MAX[n];
    return MAX[n - 1] + 1 + f(n - 1, x - size[n - 1] - 2);
}

signed main() {
    int N, X;
    cin >> N >> X;
    
    REP(i, 51) size[i] = 2 * size[i - 1] + 3;
    REP(i, 51) MAX[i] = MAX[i - 1] * 2 + 1;
    cout << f(N, X) << endl;
    return 0;
}


Measured memory_bytes: 256
/*                             //
         frostbyte02
//                             */
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=a; i<=b; i++)
#define LLFOR(i,a,b) for (ll i=a; i<=b; i++)
#define FORD(i,a,b) for (int i=a; i>=b; i--)
#define fi first
#define se second
#define pb push_back
#define fastio {ios_base::sync_with_stdio(false); cin.tie(0);}
#define sqr(x) (x)*(x)
#define sqrmod(x) (((x)%MOD)*((x)%MOD))%MOD

using namespace std;
const int MOD = 1e9+7;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;

int main()                                
{
        fastio
        int n; cin >> n;
        int h[n];
        int res = 0;
        FOR(i,0,n-1)
        {
                cin >> h[i];
                bool ok = true;
                FOR(j,0,i-1)
                {
                        if (h[j]>h[i])
                        {
                                ok = false;
                                break;
                        }
                }
                if (ok) res++;
        }
        cout << res;
        return 0;  
}


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

int main() {
	int n, m;
	vector<int> vec;
	
	cin >> n;
	for( int i = 0; i < n; i++ ){
		int h, mi;
		cin >> h >> mi;
		vec.push_back(h * 60 + mi);
	}
	cin >> m;
	for( int i = 0; i < m; i++ ){
		int h, mi;
		cin >> h >> mi;
		vec.push_back(h * 60 + mi);
	}
	
	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end());	//[begin, end)?????????
	
	for( int i = 0; i < vec.size(); i++ ){
		int h = vec[i] / 60;
		int mi = vec[i] % 60;
		if( mi < 10 )
			printf("%d:0%d", h, mi);
		else
			printf("%d:%d", h, mi);
		if( i + 1 < vec.size() )
			printf(" ");
	}
	printf("\n");
	return 0;
}

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

#define KEY_NUM 100

char process_key(char c, int key) {
    
    int num=0;
    //cout << "[" << c << "," << key << "," << num << "]";
    if ('a' <= c && c <= 'z') {
        num = 25 - (int)('z' - c);
    }
    if ('A' <= c && c <= 'Z') {
        num = 51 - (int)('Z' - c);
    }
    num = (num - key + 104) % 52;
    if ( 0 <= num && num <= 25) {
        c = 'a' + num;
    }
    if (26 <= num && num <= 51) {
        c = 'A' + (num - 26);
    }
    //cout << "[" << c << "," << key << "," << num << "]";
    return c;
}

int main(void) {
    string s;
    int n;
    int keys[KEY_NUM];
    while (cin >> n, n) {
        for (int i=0; i<n; i++) {
            cin >> keys[i];
        }
        cin >> s;
        //cout << n << endl;
        for (int i=0; i<s.size(); i++) {
            //cout << process_key(s[i], keys[i % n]) << "_";
            cout << process_key(s[i], keys[i % n]);
        }
        //cout << s << endl;
        cout << endl;
    }
}

Measured memory_bytes: 1196
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int h, w, k;
  cin >> h >> w >> k;
  
  vector<string> vec(h);
  for (int i = 0; i < h; i++) {
    cin >> vec.at(i);
    //cout << vec.at(i) << endl;
  }

  int ans = 0;
  for(int mask_h = 0; mask_h < (1<<h) - 1; mask_h++) {
    for(int mask_w = 0; mask_w < (1<<w) - 1; mask_w++) {
      // マスクするパターン(2^h * 2^w 通り)

      // 全マスのmask_hとmask_w以外の黒色をカウントする
      int cnt = 0;
      for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
          //マスク対象の行・列は除外する
          if(mask_h&(1<<i)) continue;
          if(mask_w&(1<<j)) continue;
          //黒色のマスをカウントする
          if(vec.at(i).at(j) == '#') cnt++;
        }
      }
      //cout << mask_h << ":" << mask_w << "...マスク後の黒マスは" << cnt << endl;
      if(cnt == k) ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3632
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define itrep(i, a) for (auto i = (a).begin(); i != (a).end(); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()
#define mp(a, b) make_pair((a), (b))

using namespace std;

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

template<class T> void inputVector(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < v.size(); i++) cin >> v[i];
}

signed main() {
	string S;
	cin >> S;

	int ret = 0;
	int cnt = 0;
	rep(i, S.size()) {
		if (S[i] == 'B') {
			cnt++;
		} else {
			ret += cnt;
		}
	}

	cout << ret << endl;

    return 0;
}


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

void dfs(int v, int p, const vector<vector<int>> &G, vector<ll> &sum) {
    for (auto nv : G[v]) {
        if (nv == p) continue;
        sum[nv] += sum[v];
        dfs(nv, v, G, sum);
    }
}

int main() {
    int n, q; cin >> n >> q;
    vector<vector<int>> G(n);
    vector<ll> sum(n,0);
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v; u--; v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 0; i < q; i++) {
        int p; ll x; cin >> p >> x; p--;
        sum[p] += x;
    }

    dfs(0, -1, G, sum);

    for (int i = 0; i < n; i++) cout << sum[i] << (i == n - 1 ? "\n" : " ");
    return 0;
}

Measured memory_bytes: 31436
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i, n)for(int i=0; i<n; i++)
using ll = long long int;
using namespace std;

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> l(n);
    rep(i, n) cin >> l[i];

    sort(l.begin(), l.end(), greater<int>());
    int ans=0;
    rep(i, k) ans += l[i];

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3608
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def divisor(n):
        i = 1
        table = []
        while i * i <= n:
            if n % i == 0:
                table.append(i)
                table.append(n // i)
            i += 1
        table = list(set(table))
        return table


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)

    def list(self):
        return self.__q

    def length(self):
        return len(self.__q)


sys.setrecursionlimit(1000000)
MOD = int(1e09) + 7
INF = int(1e30)


def main():
    # sys.stdin = open("Sample.txt")
    N = Scanner.int()
    S = Scanner.string()
    ans = 0
    for i in range(1000):
        s = str(i).rjust(3, "0")
        p = 0
        for j in range(N):
            if S[j] == s[p]:
                p += 1
                if p == 3:
                    break
        if p == 3:
            ans += 1
    print(ans)
    return


if __name__ == "__main__":
    main()


Measured memory_bytes: 40812
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

#define int long long
#define endl "\n"

const long long INF = (long long)1e18;
const long long MOD = 1'000'000'007; 

string yn(bool f){return f?"Yes":"No";}
string YN(bool f){return f?"YES":"NO";}

template<typename T>
class lazy_segment_tree{
	int n;
	T fval;
	vector<T> dat, lazy;
	
public:
	
	lazy_segment_tree(){
		
	}
	
	lazy_segment_tree(int n_, T val){
		init(n_, val);
	}
	
	~lazy_segment_tree(){
		
	}
	
	void init(int n_, T val){
		fval = val;
		
		n = 1;
		
		while(n < n_) n *= 2;
		
		dat.resize(2 * n - 1);
		lazy.resize(2 * n - 1, fval);
	
		for(int i = 0; i < 2 * n - 1; i++) dat[i] = fval;
	}
	
	void eval(int k, int l, int r){
		
		if(lazy[k] != fval){
			dat[k] = dat[k] + lazy[k];
			
			if(r - l > 1) {
				lazy[2*k+1] = lazy[2*k+1] + lazy[k]/2;
				lazy[2*k+2] = lazy[2*k+2] + lazy[k]/2;
			}
			
			lazy[k] = fval;
		}
	}
	
	void update(int a, int b, T x, int k = 0, int l = 0, int r = -1){
		if(r < 0) r = n;
		eval(k, l, r);
		if(b <= l || r <= a) {return ;}
		if(a <= l && r <= b){
			lazy[k] = lazy[k] + (r - l) * x;
			eval(k, l, r);
		} else {
			update(a, b, x, 2*k+1, l, (l+r)/2);
			update(a, b, x, 2*k+2, (l+r)/2, r);
			dat[k] = dat[2*k+1] + dat[2*k+2];
		}
	}
	
	T query(int a, int b, int k = 0, int l = 0, int r = -1){
		if(r < 0) r = n;
		eval(k, l, r);
		if(r <= a || b <= l){
			return fval;
		}
		if(a <= l && r <= b){
			return dat[k];
		}else {
			T vl = query(a, b, k * 2 + 1, l, (l + r) / 2 );
			T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
			return vl + vr;
		}
	}
};


signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	lazy_segment_tree<long long> lseg;
	
	int n, q;
	
	cin>>n>>q;
	
	lseg.init(n+2, 0);
	
	for(int i = 0; i < q; i++){
		int com, s, t, x;
		cin>>com>>s;
		
		if(com){
			cout<<lseg.query(s,s+1)<<endl;
		} else {
			cin>>t>>x;
			lseg.update(s, t+1, x);
		}
	}
	
	return 0;
}


Measured memory_bytes: 6984
import java.io.IOException;
import java.util.Locale;
import java.util.Scanner;


public class Main {

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

		while (sc.hasNext()) {
			System.out.println(sc.nextLine().toUpperCase(Locale.ENGLISH));
		}

	}
}

Measured memory_bytes: 17120
#include <bits/stdc++.h>
using namespace std;
#define rep(i,k,n) for(int i = k; i < n; i++)  
#define repp(i,k,n) for(int i = k; i <= n; i++) 
#define per(i,k,n) for(int i = k; i >= n; i--)

#define int long long
#define all(a) a.begin(),a.end()       

#define pb push_back
typedef long long ll; 
typedef pair<int, int> ii;
typedef pair<int,ii > iii; 
typedef vector<ii> vii;
typedef vector<char> vchar;
typedef vector<int> vi;
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound

#define mem(a, b) memset(a, b, sizeof(a));
#define mem0(a) memset(a, 0, sizeof(a));

#define INF 1000000000
//#define mod 998244353
#define mod 1000000007
#define endl "\n"


   //=\/=\/=\/=\/=\/=\/=\/=\/=\/=\        Jai Hind Dosto        /=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\\
  //=\/=\/=\/=\                    ̿̿ ̿̿ ̿̿ ̿'̿'\̵͇̿̿\з= ( ▀ ͜͞ʖ▀) =ε/̵͇̿̿/’̿’̿ ̿ ̿̿ ̿̿ ̿̿                             /=\/=\/=\/=\\
 //=\/=\/=\/=\                                                                               /=\/=\/=\/=\\
//=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\/=\\



int modPow(int a, int b);           

                
void solve(){
    int n ;
    cin >> n ;
    if(n%1000==0){
        cout << 0;
        return;
    }
    cout << 1000 - n%1000;
    
}






signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //cout << fixed;
    //cout <<setprecision(6);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    
  //  int test=1; cin >> test; while(test--)
    solve();
}

int modPow(int a, int b){
    if(b==0)return 1;
    if(b%2==0){
        int x = a*a;
        x%=mod;
        return modPow(x,b/2);
    }
    return (a*modPow(a,b-1))%mod;
}




Measured memory_bytes: 3652
n, k = gets.split.map(&:to_i)
mod = 1e9 + 7
sum = 0
k.upto(n + 1) do |i|
  fs = ((i - 1) * i) / 2
  en = ((2 * n - (i - 1)) * i) / 2
  sum += en - fs + 1
  sum %= mod
end
puts sum.to_i

Measured memory_bytes: 14368
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll N,M,Q;
vector<ll>a,b,c,d;

int dfs(int t,int num,vector<int> q){
    if(t>=N){
        // cerr << "goal" << endl;
        // for(int i=0;i<N;i++){
        //     cerr << q[i] << endl;
        // }
        int sum =0;
        for(int i=0;i<Q;i++){
            if(q[b[i]]-q[a[i]] == c[i]){
                sum += d[i];
            }
        }
        // cerr <<sum  << endl;
        return sum;
    }
    int retVal =0;
    for(int i=num;i<=M;i++){
        vector<int> qn(q.size());
        copy(q.begin(),q.end(),qn.begin()); 
        qn.push_back(i);
        retVal = max(retVal, dfs(t+1,i,qn));
    }
    return retVal;

}



int main(){
    scanf("%lld",&N);
    scanf("%lld",&M);
    scanf("%lld",&Q);
    a.resize(Q);
    b.resize(Q);
    c.resize(Q);
    d.resize(Q);
    for(int i = 0 ; i < Q ; i++){
       int e,f,g,h;
       cin >> e >> f>>g>>h;
       --e;--f;
       a[i] = e;
       b[i] = f;
       c[i] =g;
       d[i] =h;
    }
    vector<int> q;
    q.push_back(1);
    cout << dfs(1,1,q) << endl;
    return 0;
}


Measured memory_bytes: 3696
import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

immutable long MOD = 10^^9 + 7;
long[] F;
long[] G;

void main() {
    auto N = readln.chomp.to!int;
    auto A = readln.split.map!(to!long).array;

    auto B = new long[](N+1);
    foreach (i; 0..N) B[i+1] = (B[i] + A[i]) % MOD;

    F = new long[](N+1);
    G = new long[](N+1);
    F[0] = G[0] = 1;
    foreach (i; 1..N+1) F[i] = F[i-1] * i % MOD;
    foreach (i; 1..N+1) G[i] = powmod(F[i], MOD-2, MOD);

    long ans = 0;
    long tmp = 0;
    foreach (i; 1..N-1) tmp = (tmp + A[i]) % MOD;
    int left = 1;
    int right = N-2;
    auto mem = new long[](N+2);
    int p = 1;

    foreach (len; 1..N+1) {
        mem[len] = tmp;
        if (len == N) {
            ans += B[N] * F[N] % MOD;
            ans %= MOD;
        } else if (len == N - 1) {
            ans += B[N-1] * F[N-1] % MOD;
            ans += (B[N] - B[1]) * F[N-1] % MOD;
            ans %= MOD;
        } else {
            auto comb1 = comb(N, len+1);
            auto tmptmp = comb1 * F[len] % MOD * F[N-len-1] % MOD;
            auto tmp1 = tmptmp * B[len] % MOD;
            auto tmp2 = tmptmp * ((B[N] - B[N-len]) % MOD) % MOD;
            auto tmp3 = comb(N, len+2) * 2 % MOD * F[len] % MOD * F[N-len-2] % MOD * tmp % MOD;
            ans += (tmp1 + tmp2 + tmp3) % MOD;
            ans %= MOD;
        }

        left += 1;
        right -= 1;
        if (left <= right) {
            tmp += B[right+1] - B[left];
            tmp %= MOD;
            if (left != right) p += 1;
        } else if (p >= 0) {
            tmp = mem[p];
            p -= 1;
        }
    }

    ans = (ans % MOD + MOD) % MOD;
    ans.writeln;
}


long comb(long n, long r) {
    return F[n] * G[n-r] % MOD * G[r] % MOD;
}

long powmod(long a, long x, long m) {
    long ret = 1;
    while (x) {
        if (x % 2) ret = a * ret % m;
        a = a * a % m;
        x /= 2;
    }
    return ret;
}


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

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

  vector<int> B;
  B.push_back(0);
  bool flag = true;
  for(int i = 0; i < N; i++){
    int idx = B.size() - 1;
    if(B[idx] == A[i]) continue;
    if(flag){
      if(B[idx] > A[i]) B[idx] = A[i];
      else{
        B.push_back(A[i]);
        flag = false;
      }
    }else{
      if(B[idx] < A[i]) B[idx] = A[i];
      else{
        B.push_back(A[i]);
        flag = true;
      }
    }
  }
  if(B.size() == 1){
    cout << "0\n";
    return 0;
  }
  if(B.size() <= 3){
    cout << "1\n";
    return 0;
  }
  if(B[B.size() - 1] != 0){
    if(B.size() % 2 == 0){
      B.push_back(0);
    }else{
      B[B.size() - 1] = 0;
    }
    
  }

  // for(int i : B){
  //   cout << i << " ";
  // }
  // cout << "\n";
  
 
  vector<pair<int, int>> v;
  for(int i = 1; i < B.size(); i += 2){
    v.push_back(make_pair(B[i - 1], B[i]));
    if(i + 1 < B.size()){
      v.push_back(make_pair(B[i + 1], B[i]));
    }
  }

  map<int, int> m;
  for(int i = 0; i < v.size(); i++){
    if(v[i].first != 0){
      if(m.count(v[i].first) == 0){
        m.insert(make_pair(v[i].first, 1));
      }else{
        m[v[i].first]++;
      }
    }
  }

  map<int, int> m2;
  for(int i = 0; i < v.size(); i++){
    if(v[i].first != 0){
      if(m2.count(v[i].first) == 0){
        m2.insert(make_pair(v[i].first, 1));
      }else{
        m2[v[i].first]++;
      }
    }
    if(m2.count(v[i].second) == 0){
      m2.insert(make_pair(v[i].second, 1));
    }else{
      m2[v[i].second]++;
    }
  }

  sort(v.begin(), v.end());
  
  // for(int i = 0; i < v.size(); i++){
  //   cout << v[i].first << " " << v[i].second << "\n";
  // }
  
  int n = v.size();
  priority_queue<int, vector<int>, greater<int>>qr;
  int g = 1;
  qr.push(v[0].second);
  int k;
  for(int i = 1; i < n; i++){
    k = v[i].first;
    qr.push(v[i].second);
    // cout << qr.top() << "\n";
    if(k > qr.top()){
     while(!qr.empty()){
        if(k <= qr.top()){
          break;
        }else{
          qr.pop();
        }
      }
    }
    int t = 0;
    if(m2.count(k) != 0){
      t = m2.at(k);
    }
    if(m.count(k) != 0){
      t -= m.at(k);
    }
    g = max(g, (int)qr.size() - t);
  }
  cout << g / 2<< "\n";
  // cout << m2[2] << "\n";
  // cout << m.size() << "\n";
  return 0;
}


Measured memory_bytes: 9244
#include<cstdio>
using namespace std;
int main(void)
{
	int a,b,i,j,hit,brow,p;
	char x[5],kaitou[5];
	scanf("%s %s",x,kaitou);
	while(!(x[0]=='0' && kaitou[0]=='0')){
		hit=0;
		brow=0;
		for(i=0;i<4;i++){
			if(x[i]==kaitou[i]){
				hit++;
			}
			else {
				for(j=0;j<4;j++){
					if(kaitou[j]==x[i]){
					brow++;
					}
				}
			}
		}
		
		printf("%d %d\n",hit,brow);
		scanf("%s %s",x,kaitou);
	}
	return 0;
}
		

Measured memory_bytes: 968