akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cstdlib>
#define MAXN 100002
using namespace std;
typedef long long ll;

int N;
int a[MAXN];
int ans[MAXN];
int total;
int pre;
int prepre;

int main() {
	total = 0;
	a[0] = 0;

	cin >> N;
	for (int i = 1; i<=N; i++) {
		cin >> a[i];
		total += abs(a[i] - a[i - 1]);
		if (i != 1) {
			ans[i - 1] = abs(a[i] - a[i - 2]) - abs(a[i] - a[i - 1]) - abs(a[i - 1] - a[i - 2]);
		}
	}
	total += abs(a[N]);
	ans[N] = abs(a[N - 1]) - abs(a[N]) - abs(a[N] - a[N - 1]);

	for (int i = 1; i <= N; i++) {
		cout << total + ans[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 2048
#include <stdio.h>
    
int main(void)
{
	 char ch[10001];
	int i=0,joi,ioi;
	while(scanf("%s",&ch)==1)
	{
		ioi=0;
		joi=0;
		i=0;
		while(ch[i]!='\0')
		{
			if(ch[i]=='J' && ch[i+1]=='O' && ch[i+2]=='I')
			{
				joi++;
			}
			if(ch[i]=='I' && ch[i+1]=='O' && ch[i+2]=='I')
			{
				ioi++;
			}
			i++;
		}
		printf("%d\n%d\n",joi,ioi);
	}
	return 0;
}


Measured memory_bytes: 1916
#include<cmath>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
struct node
{
	int x,id;
}b[2010];
int n,k,q,a[2010],c[2010],nxt[2010];
int d[2010],e[2010],kd,ke;
bool cmp(node x,node y)
{
	return x.x<y.x;
}
void add(int l,int r)
{
	int kd=r-l+1;
	if (kd<k)
	{
		return;
	}
	kd=0;
	for (int i=l;i<=r;i++)
	{
		kd++;
		d[kd]=a[i];
	}
	sort(d+1,d+kd+1);
	for (int i=1;i<=kd-k+1;i++)
	{
		ke++;
		e[ke]=d[i];
	}
}
int main()
{
	scanf("%d%d%d",&n,&k,&q);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		b[i].x=a[i];
		b[i].id=i;
	}
	sort(b+1,b+n+1,cmp);
	for (int i=1;i<=n;i++)
	{
		c[i]=b[i].id;
	}
	nxt[0]=n+1;
	int ans=2e9;
	for (int i=1;i<=n;i++)
	{
		int now=0;
		ke=0;
		while (now<=n)
		{
			add(now+1,nxt[now]-1);
			now=nxt[now];
		}
		if (ke<q)
		{
			break;
		}
		sort(e+1,e+ke+1);
		ans=min(ans,e[q]-e[1]);
		now=0;
		while (now<=n)
		{
			if (nxt[now]>c[i])
			{
				nxt[c[i]]=nxt[now];
				nxt[now]=c[i];
				break;
			}
			now=nxt[now];
		}
	}
	printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <tuple>
using namespace std;
typedef long long ll;
#define REP(i,n) for (int i = 0; i < n; i++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;

string s;
string t;
ll dp[26][100010];

int main ()
{
    cin >> s >> t;
    int pre[26] = {};
    
    for (int i = 1000000; i >= 0; i--) {
        for (int j = 0; j < 26; j++) {
            dp[j][i % s.size()] = pre[j];
        }
        pre[s[i % s.size()] - 'a'] = i % s.size();
    }

    bool used[26] = {};
    REP(i,s.size()) used[s[i] - 'a'] = true;
    REP(i,t.size()) {
        if (!used[t[i] - 'a']) {
            cout << -1 << endl;
            return 0;
        }
    }

    ll ans = 0;
    while (t[0] != s[ans]) ans++;
    for (int i = 1; i < t.size(); i++) {
        ll pre = ans % s.size();
        ll nxt = dp[t[i] - 'a'][pre];
        if (pre == nxt) {
            ans += (ll)s.size();
        } else if (pre < nxt) {
            ans += abs(nxt - pre);
        } else {
            ans += (ll)s.size() - abs(nxt - pre);
        }
    }

    cout << ans + 1 << endl;

    return 0;
}


Measured memory_bytes: 20864
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    ll n;
    cin >> n;
    cout << n*(n-1)/2 << "\n";
    return 0;
}

Measured memory_bytes: 256
import sys
input = lambda: sys.stdin.readline().rstrip('\r\n')

from collections import defaultdict

N = int(input())

S = 'RULD'

class Plane:
	__slots__ = ('x', 'y', 'd')

	def __init__(s, x, y, d):
		s.x, s.y, s.d = int(x), int(y), d

	def __lt__(s, o):
		return s.x < o.x

	def rotate(s):
		s.x, s.y = -s.y, s.x
		s.d = S[(S.index(s.d)+1)%4]

P = []
for _ in range(N):
	x, y, d = input().split()
	P.append((int(x), int(y), d))

def rotate(s):
	return (-s[1], s[0], S[(S.index(s[2])+1)%4])

INF = 10 ** 18
best = INF
MAXC = 400000

for trial in range(4):
	P.sort(key=lambda v: v[0])

	rdu, rdd, ry = ([INF] * (2*MAXC+1) for _ in range(3))

	for (x, y, d) in P:
		if d == 'R':
			ry[y+MAXC] = x
			rdu[y-x+MAXC] = x
			rdd[y+x+MAXC] = x
		elif d == 'L':
			ty = y + MAXC
			if ry[ty] != INF:
				best = min(best, (x - ry[ty]) * 5)
		elif d == 'U':
			ty = x + y + MAXC
			if rdd[ty] != INF:
				best = min(best, (x - rdd[ty]) * 10)
		elif d == 'D':
			ty = y - x + MAXC
			if rdu[ty] != INF:
				best = min(best, (x - rdu[ty]) * 10)

	if trial != 3:
		P = [rotate(p) for p in P]

print('SAFE' if best == INF else best)


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

int main()
{
  int n;
  char s[10010];
  scanf("%d %s", &n, s);

  int len = strlen(s);
  for (int i = 0; i < len; i++)
  {
    int x = s[i] - 'A';
    x = (x + n) % 26;
    s[i] = x + 'A';
    putchar(s[i]);

  }

  putchar('\n');
  return 0;
}


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

int main() {
	int N;
	int p;

	cin >> N;
 	vector<int> a(N);
	rep(i, N) cin >> a.at(i);
	if (N<3) {
		cout << 0 << endl;
		return 0;
	}
	p=0;
	rep(i, N-2){
		rep2(j, i+1,N-1){
			if(a.at(i)==a.at(j)) continue;
			rep2(k, j+1,N){
				if(a.at(i)==a.at(k)) continue;
				if(a.at(j)==a.at(k)) continue;
				if(a.at(i)+a.at(j)<=a.at(k)) continue;
				if(a.at(j)+a.at(k)<=a.at(i)) continue;
				if(a.at(k)+a.at(i)<=a.at(j)) continue;
				p++;
			}
		}
	}
	cout << p << endl;
	return 0;
}


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

// macro
#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define all(v) v.begin(), v.end()

// code starts
int main()
{
  int n;cin>>n;
  vector<int> a(n);
  vector<int> b(n);
  int i;
  rep(i,n)cin>>a[i];
  rep(i,n)cin>>b[i];
  rep(i,n)
  {
    a[i]--;
    b[i]--;
  }
  //vector<int> pos(n,0);
  //rep(i,n)pos[a[i]]=i;
  vector<int> counts(n,0);
  rep(i,n)
  {
    counts[b[i]]++;
  }
  bool ok=true;
  vector<bool> bfind(n,false);
  rep(i,n)
  {
    if(counts[i]!=1)ok=false;
    bfind[b[i]]=true;
  }
  if(ok)cout<<"Yes"<<endl;
  else
  {
    cout<<"No"<<endl;
    rep(i,n)
    {
      if(i!=0)cout<<' ';
      cout<<1;
    }
    cout<<endl;
    int count=1;
    rep(i,n)
    {
      if(i!=0)cout<<' ';
      if(!bfind[a[i]])
      {
        cout<<count+1;
        count++;
      }
      else cout<<1;

    }
    cout<<endl;
  }
}



Measured memory_bytes: 4076
def digit(a):
    tmp = list(str(a))
    x = 0
    for j in tmp:
        x += int(j)
    return x
n=int(input())
min_ = n
for i in range(1,n//2):
    y = digit(i)+digit(n-i)
    min_ = min(min_,y)
print(min_)

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

int main(){
    int a, b, c, buf;
    cin >> a >> b >> c;
    if(a>b){
        buf=a;
        a=b;
        b=buf;
    }
    if(b>c){
        buf=b;
        b=c;
        c=buf;
    }
    if(a>b){
        buf=a;
        a=b;
        b=buf;
    }
    cout << a << " " << b << " " << c << endl;
}


Measured memory_bytes: 3072
n, c, k = map(int, input().split())
times = sorted([int(input()) for _ in range(n)])

count = 1
passengers = 0
border = times[0] + k
for t in times:
    passengers += 1
    if c < passengers or border < t:
        count += 1
        passengers = 1
        border = t + k

print(count)

Measured memory_bytes: 8280
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.HashMap;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Jaynil
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ERemOfSumIsNum solver = new ERemOfSumIsNum();
        solver.solve(1, in, out);
        out.close();
    }

    static class ERemOfSumIsNum {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int k = in.nextInt();
            long ans = 0;
            HashMap<Long, Long> map = new HashMap<>();
            long pre[] = new long[n + 1];
            for (int i = 1; i <= n; i++) {
                pre[i] += pre[i - 1] + in.nextLong();
            }
            map.put(0L, 1L);
            for (int i = 1; i <= n; i++) {
                if (i - k >= 0) {
                    if (map.containsKey((pre[i - k] - (i - k)) % k) && map.get((pre[i - k] - (i - k)) % k) > 0)
                        map.put(((pre[i - k] - (i - k)) % k), map.get((pre[i - k] - (i - k)) % k) - 1);
                    else {
                        map.remove((pre[i - k] - (i - k)) % k);
                    }
                }
//            out.println(map.get((pre[i]-i)%k));
                if (map.containsKey((pre[i] - i) % k) && map.get((pre[i] - i) % k) > 0) {
                    ans += map.get((pre[i] - i) % k);
                }
                if (map.containsKey((pre[i] - i) % k) && map.get((pre[i] - i) % k) >= 0) {
                    map.put((pre[i] - i) % k, map.get((pre[i] - i) % k) + 1);
                } else {
                    map.put((pre[i] - i) % k, 1L);
                }

            }
            out.println(ans);

        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
}



Measured memory_bytes: 60960
N=int(input())
S=input()

current_and_left_w=0
ans=current_and_right_e=S.count("E")

for i in S:
    if i=="E":
        current_and_right_e-=1
    else: 
        current_and_left_w+=1
        
    ans=min(ans,current_and_right_e+current_and_left_w)
print(ans)

Measured memory_bytes: 3700
#include <iostream>
using namespace std;
using ll = long long;
constexpr ll M = 1e9 + 7;
#define MOD(a, b) ( ( ((ll)(a)%M) * ((ll)(b)%M) ) % M)
ll mypw(int x, int n)
{
    if (n <= 0) return 1;
    if (n == 1) return x;
    ll k = mypw(x, n/2);
    k = MOD(k, k);
    if (n % 2 == 0) {
        return k;
    }
    else {
        return MOD(k, x);
    }
}
int main()
{
    int n;
    cin >> n;
    cout << (mypw(10, n) - 2 * mypw(9, n) + mypw(8, n) + 2*M) % M << endl;
    return 0;
}

Measured memory_bytes: 3620
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "math.h"
#include "utility"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "random"

using namespace std;
const long long int MOD = 1000000007;

int N, K;

int main() {
	cin >> N;
	cin >> K;
	while (N&&K) {
		set<int>S;
		int num[10] = {};
		int rate[10] = {};
		for (int i = 0; i < N; i++) {
			cin >> num[i];
			if (num[i] >= 10)rate[i] = 100;
			else rate[i] = 10;
		}
		if (K == 2) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (i == j)continue;
					int box = num[i] * rate[j];
					box += num[j];
					S.insert(box);
				}
			}
		}
		if (K == 3) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (i == j)continue;
					for (int k = 0; k < N; k++) {
						if (i == k || j == k)continue;
						int box = num[i] * rate[j];
						box += num[j];
						box *= rate[k];
						box += num[k];
						S.insert(box);
					}
				}
			}
		}
		if (K == 4) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (i == j)continue;
					for (int k = 0; k < N; k++) {
						if (i == k || j == k) continue;
						for (int l = 0; l < N; l++) {
							if (i == l || j == l || k == l)continue;
							int box = num[i] * rate[j];
							box += num[j];
							box *= rate[k];
							box += num[k];
							box *= rate[l];
							box += num[l];
							S.insert(box);
						}
					}
				}
			}
		}
		cout << S.size() << endl;
		cin >> N;
		cin >> K;
	}
	return 0;
}

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

using namespace std;
using ll = long long;
using vl = vector<ll>;
using pll = pair<ll, ll>;

constexpr ll INF = 0x3f3f3f3f3f3f3f3fLL;

#define rep(i, n) for (ll i = 0, xxx_rep_end = (n); i < xxx_rep_end; ++i)
#define all(x) (x).begin(), (x).end()

template <class T1, class T2>
inline void chmax(T1 &a, const T2 &b)
{
    if (a < b)
    {
        a = b;
    }
}
template <class T1, class T2>
inline void chmin(T1 &a, const T2 &b)
{
    if (a > b)
    {
        a = b;
    }
}
int main()
{
    ll R, C, K;
    cin >> R >> C >> K;
    vector<vector<ll>> item(R + 1, vector<ll>(C + 1));
    rep(i, K)
    {
        ll r, c, v;
        cin >> r >> c >> v;
        item[r - 1][c - 1] = v;
    }

    vector<vector<vector<ll>>> dp(R + 1, vector<vector<ll>>(C + 1, vector<ll>(4)));
    dp[0][0][1] = item[0][0];
    rep(i, R)
    {
        rep(j, C)
        {
            rep(k, 4)
            {
                chmax(dp[i + 1][j][0], dp[i][j][k]);
                if (item[i + 1][j] != 0)
                {
                    chmax(dp[i + 1][j][1], dp[i][j][k] + item[i + 1][j]);
                }

                chmax(dp[i][j + 1][k], dp[i][j][k]);
                if (k != 3 && item[i][j + 1] != 0)
                {
                    chmax(dp[i][j + 1][k + 1], dp[i][j][k] + item[i][j + 1]);
                }
            }
        }
    }

    ll ans = 0;
    for (auto x : dp[R - 1][C - 1])
    {
        chmax(ans, x);
    }
    cout << ans << endl;
}

Measured memory_bytes: 707288
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    while True:
        m,n = LI()
        if m + n == 0: return

        goal = m + n + 1
        b = []
        r = []
        for _ in range((m-1)//10+1):
            b.extend(LI())
        for _ in range((n-1)//10+1):
            r.extend(LI())

        edge = [set() for _ in range(goal+1)]
        for i in range(1,m+1):
            edge[0].add(i)
        for i in range(m+1,goal+1):
            edge[i].add(goal)
        for i in range(m):
            for j in range(n):
                if math.gcd(b[i],r[j]) > 1:
                    edge[i+1].add(j+m+1)

        ans = 0
        while True:
            node = [-1] * (goal+1)
            q = collections.deque()
            node[0] = 0
            q.append(0)
            while q:
                u = q.pop()
                for v in edge[u]:
                    if node[v] >= 0: continue
                    node[v] = u
                    if v == goal:
                        ans += 1
                        break
                    q.append(v)
                else:
                    continue
                break
            else:
                break
            v = goal
            while v > 0:
                u = node[v]
                edge[u].remove(v)
                edge[v].add(u)
                v = u
        print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 17160
import java.io.*;
import java.util.*;

public class Main {
    private static ArrayList<LinkedList<Integer>> graph;
    private static int[] in;
    public static void main(String[] args) throws Exception{
        FastScanner scanner = new FastScanner();
        int V = scanner.nextInt();
        int E = scanner.nextInt();

        graph = new ArrayList<>(V);
        in = new int[V];
        for(int i = 0; i < V; ++i){
            graph.add(new LinkedList<>());
        }

        for(int i = 0; i < E; ++i){
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            graph.get(u).add(v);
            ++in[v];
        }

        LinkedList<Integer> queue = new LinkedList<>();
        for(int i = 0; i < V; ++i){
            if(in[i] == 0){
                queue.add(i);
            }
        }

        List<Integer> result = new ArrayList<>(V);
        while(!queue.isEmpty()){
            Integer u = queue.remove();
            result.add(u);
            for(Integer v : graph.get(u)){
                --in[v];
                if(in[v] == 0){
                    queue.add(v);
                }
            }
        }

        PrintWriter printWriter = new PrintWriter(System.out);
        for(Integer n : result){
            printWriter.println(n);
        }
        printWriter.flush();
    }

    private static class FastScanner{
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;
        private boolean hasNextByte() {
            if(ptr < buflen) {
                return true;
            } else {
                ptr = 0;
                try {
                    buflen = in.read(buffer);
                } catch(IOException e) {
                    e.printStackTrace();
                }
                if(buflen <= 0) {
                    return false;
                }
            }
            return true;
        }
        private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
        private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
        private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
        public boolean hasNext() { skipUnprintable(); return hasNextByte();}
        public String next() {
            if (!hasNext()) throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while(isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
        public int nextInt(){
            return Integer.parseInt(next());
        }
        public double nextDouble(){
            return Double.parseDouble(next());
        }
    }
}

Measured memory_bytes: 42752
#include <iostream>
#include <string>
#include <cstdio>

using namespace std;

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

int solve(int a, int b, int c);

int main()
{
    int a, b, c;
    while (scanf("%d", &a) != EOF) {
        cin >> b >> c;
        cout << solve(a%b*10, b, c) << endl;
    }
    return 0;
}

int solve(int a, int b, int c)
{
    int ans = 0;
    
    loop(i, c) {
        ans += a/b;
        a %= b;
        a *= 10;
    }

    return ans;
}

Measured memory_bytes: 3112
#include <bits/stdc++.h>
#include <iomanip>
#include <math.h>
#include <unistd.h>
#include <stdio.h>
#define rep(i,x) for(ll i = 0;i<x;i++)
#define all(a) (a).begin(),(a).end()
#define vecin(a) rep(i,a.size())cin >> a[i]
#define vecout(a) rep(i,a.size())cout << a[i] << " ";cout << "\n"
#define vecvec(a) vector<vector<(a)>>
using ll = long long;
using ld = long double;
using namespace std;
using dou = double;
const ll inf = 2147483647;
const ll INF = 1LL << 60;
const ld pi = 3.14159265358;
const ll mod = 1000000007;
typedef pair<ll,ll> P;
using graph = vector<vector<ll>>;
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;}
template<class T> inline bool change(T a,T b){if(a > b){swap(a,b);return true;}return false;}
ll gcd(ll a,ll b){
    if(a < b)swap(a,b);
    if(a % b == 0)return b;
    else return gcd(b,a%b);
}
//素数判定O(sqrt(N))
bool isp(ll n){
    bool res = true;
    if(n == 1)return false;
    else{
        for(ll i = 2;i * i <= n;i++){
            if(n % i == 0){
                res = false;
                break;
            }
        }
        return res;
    }
}
const ll cmax = 1000000;
ll fac[cmax], finv[cmax], inv[cmax];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < cmax; i++){
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod%i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}

// 二項係数計算
ll nCk(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
//nのm乗をMODで割ったあまりO(logN)
ll modpow(ll n,ll m,ll MOD){
    ll res = 1;
    while(m){
        if(m & 1)res = (res * n) % MOD;
        m >>= 1;
        n *= n;
        n %= MOD;
    }
    return res;
}

//printf("%.10f\n", N);
/*  vector<ll> vec = {1,2,5,6,8,9,10};
    cout << binary_search(all(vec),5) << endl; -> true*/
/*
    vector<ll> vec = {1,2,5,6,8,9,10};
    auto n = upper_bound(all(vec),4);
    cout << *n << endl; -> 5*/

//    cout << fixed << setprecision(15);

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll N;
    cin >> N;
    graph G(N);
    ll ten,kazu,to;
    rep(i,N){
        cin >> ten;ten--;
        cin >> kazu;
        rep(j,kazu){
            cin >> to;to--;
            G[ten].push_back(to);
        }
    }
    queue<ll> que;
    vector<ll> dist(N,INF);
    dist[0] = 0;
    que.push(0);
    while(que.size()){
        ll n = que.front();que.pop();
        for(auto x : G[n]){
            if(dist[x] == INF){
                que.push(x);
                dist[x] = dist[n] + 1;
            }
        }
    }
    rep(i,N){
        if(dist[i] == INF){
            cout << i + 1 << " " << -1 << endl;
        }
        else cout << i + 1 << " " << dist[i] << endl;
    }
}


Measured memory_bytes: 3172
s1=raw_input()
s2=raw_input()
m=len(s1);n=len(s2)
dp=[[float("inf")]*(n+1) for _ in xrange(m+1)]
for i in xrange(m+1):
    dp[i][0]=i
for j in xrange(n+1):
    dp[0][j]=j
delete=1
insert=1
replacement=1
for i in xrange(m):
    for j in xrange(n):
        if s1[i]!=s2[j]:
            dp[i+1][j+1]=min(dp[i][j+1]+delete,dp[i+1][j]+insert,dp[i][j]+replacement)
        else:
            dp[i+1][j+1]=min(dp[i][j+1]+delete,dp[i+1][j]+insert,dp[i][j]+0)
print dp[m][n]

Measured memory_bytes: 36456
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;

const int N = 2e5+1000;
#define ll long long
#define read(x) scanf("%d",&x)
#define Read(x,y) scanf("%d%d",&x,&y)
#define gc(x) scanf(" %c",&x)
#define sread(x,y,z) scanf("%d%d%d",&x,&y,&z)
ll f[N];
map<ll,ll> hap;
int main()
{
    int n,m;
    Read(n,m);
    for(int i = 1;i <= n;++i){
        scanf("%lld",&f[i]);
        f[i] += f[i-1];
    }
    for(int i = 1;i <= n;++i){
        f[i] = (f[i] - i) % m;
    }
    m --;
    m = min(n,m);
    for(int i = 0;i < m;i ++ ){
        hap[f[i]] ++;
    }
    ll sum = 0;
    for(int i = m ;i <= n;++i){
        hap[f[i]] ++;
        sum += hap[f[i-m]] - 1;
        hap[f[i-m]] --;
    }
    for(int i = n-m + 1;i <= n;++i){
        sum += hap[f[i]] - 1;
        hap[f[i]] --;
    }
    cout<<sum;
}

Measured memory_bytes: 14336
#include<bits/stdc++.h>
#define se second
#define fi first
#define pb push_back
#define cn cout<<"\n"
#define rep(i,a,b) for(int i = a; i < b; i++)
#define repr(i,a,b) for(int i = a; i >= b; i--)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()

#define _ ios::sync_with_stdio(0); cin.tie(0);

#define vi vector<int>
#define ii pair<int,int>
#define vii vector<ii>
#define ll long long
#define vll vector<ll>
#define flush fflush(stdout)

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

using namespace std;


vll a, b, c;

int main(){
	_

	int t = 1;

	int x, y, z, k;
	ll aux;
	cin>>x>>y>>z>>k;

	priority_queue< tuple<ll, int, int> > p;

	rep(i, 0, x){
		cin>>aux;
		a.pb(aux);
	}

	rep(i, 0, y){
		cin>>aux;
		rep(j, 0, a.size())
			b.pb(aux + a[j]);
	}

	sort(allr(b));

	rep(i, 0, z){
		cin>>aux;
		c.pb(aux);
	}

	sort(allr(c));

	rep(i, 0, z)
		p.push(make_tuple(c[i] + b[0], i, 0));

	int i = 0, j = z - 1;
	while(i < k){

		tuple<ll, int, int> top = p.top(); p.pop();
		ll val = get<0>(top);
		int uu = get<1>(top);
		int vv = get<2>(top);

		cout<<val; cn;

		int next = vv + 1;

		if(next < b.size()) p.push(make_tuple(c[uu] + b[next], uu, next));
		
		i++;
	}


	return 0;
}

Measured memory_bytes: 10604
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
const ull B = 1000000007;

int main(){
    int n, m;
    string s;
    cin >> n >> m >> s;
    vector<ull> v(n+1);
    v[0] = 0;
    for(int i = 0; i < n; i++){
        v[i+1] = v[i]*B + s[i];
    }
    vector<ull> f(n+1);
    f[0] = 1;
    for(int i = 1; i <= n; i++) f[i] = f[i-1]*B;
    int a = 1, b = 1;
    vector<ull> ans;
    while(m--){
        string s;
        cin >> s;
        if(s == "L++")  a++;
        if(s == "R++")  b++;
        if(s == "L--")  a--;
        if(s == "R--")  b--;
        ans.push_back(v[b]-v[a-1]*f[b-a+1]);
    }
    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(),ans.end()),ans.end());
    cout << ans.size() << endl;
    return 0;
}


Measured memory_bytes: 12200
#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 n, k;
  cin >> n >> k;
  vector<ll> a(n);
  for (ll i=0; i<n; ++i) {
    cin >> a.at(i);
  }
  
  for (ll i=k, j=0; i<n; ++i, ++j) {
    if (a.at(j)<a.at(i)) {
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
  }
  
  return 0;
}

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

int n, w;
long long wei[101], val[101], dp[101][100001];

int main(){
	scanf("%d %d", &n, &w);
	for (int i=1; i<=n; i++) scanf("%lld %lld", &wei[i], &val[i]);
	for (int i=1; i<=n; i++){
		for (int j=0; j<=w; j++){
			if (j>=wei[i]) dp[i][j]=max(dp[i-1][j], dp[i-1][j-wei[i]]+val[i]);
			else dp[i][j]=dp[i-1][j];
		}
	}
	printf("%lld\n", dp[n][w]);
}

Measured memory_bytes: 78336
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long ll;
#define endl '\n'

void solve() {
    string s;
    cin >> s;

    if (s[1] == 'B') {
        cout << "ARC" << endl;
    } else {
        cout << "ABC" << endl;
    }
 
}

int main() {
    FAST_IO;

    int t;
    // cin >> t;
    t = 1;
    while (t--) {
        solve();
    }
    
    return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define pb push_back
#define MP(a, b) make_pair((a), (b))
template <class T> vector<T> make_vec(size_t a, T val) {
    return vector<T>(a, val);
}
template <class... Ts> auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec(ts...))>(a, make_vec(ts...));
}
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using Graph = vector<vector<int>>;
template <typename T> struct edge {
    int to;
    T cost;
    edge(int t, T c) : to(t), cost(c) {}
};
template <typename T> using WGraph = vector<vector<edge<T>>>;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

int main() {
    ll H, N;
    cin >> H >> N;
    vector<ll> A(N), B(N);
    rep(i, N) { cin >> A[i] >> B[i]; }
    auto dp = make_vec(N + 1, H + 1, LINF);
    rep(i, N) dp[i][0] = 0;
    // dp[i][j]:=i-1番目の魔法まで見て、ダメージをj与えるときの最小
    for(int i = 0; i < N; i++) {
        for(int j = 0; j <= H; j++) {
            dp[i + 1][min(H, j + A[i])] =
                min(dp[i + 1][min(H, j + A[i])], dp[i][j] + B[i]);
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
        }
        for(int j = 0; j <= H; j++) {
            dp[i + 1][min(H, j + A[i])] =
                min(dp[i + 1][min(H, j + A[i])], dp[i + 1][j] + B[i]);
        }
    }
    cout << dp[N][H] << endl;
}

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

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

ll n;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  if (n & 1)
    cout << 0 << endl;
  else {
    ll res = 0;
    ll base = 10;
    while (base <= n) {
      res += n / base;
      base *= 5;
    }
    cout << res << endl;
  }
  
  return 0;
}

// 0, 1, 2, 3, 4, 5,  6,  7,   8,   9
// 1, 1, 2, 3, 8, 15, 48, 105, 384, 9 * 105

// even: 0, 2, 4, 6, 8, 10
// odd:  1, 3, 5, 7, 9, 11


Measured memory_bytes: 256
package main

import (
	"fmt"
	"math"
)

type Status struct {
	val string
	len int
}

func main() {
	n := SingleInt()
	k := SingleInt()
	s := SingleStr()
	ss := make([]int, 0, n)

	now := "1"
	cnt := 0
	for i := 0; i < n; i++ {
		if string(s[i]) == now {
			cnt++
		} else {
			ss = append(ss, cnt)
			now = reverse(now)
			cnt = 1
		}
	}
	if cnt != 0 {
		ss = append(ss, cnt)
	}
	if len(ss)%2 == 0 {
		ss = append(ss, 0)
	}

	// fmt.Printf("%#v\n", ss)

	add := 2*k + 1
	ans := 0

	tmp := 0 // [left, right)のsum ([left, right) leftは含むがrightは含まない)

	sslen := len(ss)

	accumSums := make([]int, sslen+1, sslen+1)
	for i := 0; i < sslen; i++ {
		accumSums[i+1] = accumSums[i] + ss[i]
	}

	// fmt.Printf("%#v\n", accumSums)

	for i := 0; i < sslen; i += 2 {
		left := i
		right := Min(i+add, sslen)

		tmp = accumSums[right] - accumSums[left]

		// fmt.Printf("right %#v, left %#v\n", right, left)
		// fmt.Printf("tmp %#v\n\n", tmp)

		ans = Max(tmp, ans)
	}
	fmt.Printf("%#v\n", ans)
}

func Max(nums ...int) int {
	if len(nums) == 0 {
		panic("function max() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Max(float64(res), float64(nums[i])))
	}
	return res
}

func Min(nums ...int) int {
	if len(nums) == 0 {
		panic("function min() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Min(float64(res), float64(nums[i])))
	}
	return res
}

func reverse(v string) string {
	if v == "0" {
		return "1"
	}
	return "0"
}

func SingleStr() string {
	var s string
	fmt.Scan(&s)
	return s
}

func SingleInt() int {
	var n int
	fmt.Scan(&n)
	return n
}


Measured memory_bytes: 2816
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=100010;
int a[MAXN],n,cnt,m;
int read(){
    int f=1,x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    return f*x;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int k;
        cin>>k;
        int haha[k];
        for(int j=1;j<=k;j++){
            cin>>haha[j];
            a[haha[j]]++;
            if(a[haha[j]]==n) cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

Measured memory_bytes: 384
import java.util.*;
import java.lang.Math;
class Main{
    static Scanner sc=new Scanner(System.in);
    public static void main(String[] args){
        long N = sc.nextLong();
        long K = sc.nextLong();
        long t = N/K;
        long temp1=Math.abs(N-K*t);
        long temp2=Math.abs(temp1-K);
        System.out.println((temp1<=temp2) ? temp1 : temp2);
    }
}

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

using namespace std;

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

int main(){
    int n,x;
    cin>>n>>x;
    vector<int>v(n);
    
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    
    sort(v.begin(),v.end());
    int gc;
    for(int i=1;i<n;i++){
        if(i==1)
            gc=v[i]-v[i-1];
         gc=gcd(gc,v[i]-v[i-1]);
    }
    
    if(x<=v[0]){
        cout<<gcd(gc,v[0]-x)<<"\n";
        return 0;
    }
    if(x>=v[n-1]){
        cout<<gcd(gc,x-v[n-1])<<"\n";
        return 0;
    }
    //cout<<gc<<endl;
    for(int i=0;i<n;i++){
        if(v[i]>=x){
           // cout<<"here"<<endl;
            cout<<max(gcd(gc,v[i]-x),gcd(gc,x-v[i-1]))<<"\n";
            return 0;
        }
    }
    
    
    
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <cmath>
using namespace std;
typedef long long i64;
typedef long double ld;
typedef pair<i64,i64> P;
#define rep(i,s,e) for(int i = (s);i <= (e);i++)

int a, b,c;

bool d(int x,int y ,int z)
{
    return x + y == z;
}

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

    if(d(a,b,c) || d(a,c,b) || d(b,c,a))
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout <<"No" << endl;
    }

}

Measured memory_bytes: 256
fn get_input() -> String {
    let mut word = String::new();
    std::io::stdin().read_line(&mut word).unwrap();
    word.trim().to_owned()
}

fn main() {
    let _n: usize = get_input().parse().unwrap();
    let mut h: Vec<i64> = Vec::new();
    let mut ans = 0;

    for hx in get_input().split_whitespace() {
        let hi = hx.parse().unwrap();
        if (0..h.len())
            .filter(|&i| h[i] > hi)
            .count()
            == 0
        {
            ans += 1;
        }
        h.push(hi);
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <set>
#include <stdio.h>
#include <string>
#include <utility>
#include <vector>

using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> p(n);
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    p[a].push_back(b);
    p[b].push_back(a);
  }
  pair<int, int> dp[101010][11];
  for (int i = 0; i < n; i++)
    for (int j = 0; j < 11; j++)
      dp[i][j] = make_pair(0, 0);
  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    int v, d, c;
    cin >> v >> d >> c;
    v--;
    dp[v][d] = make_pair(i + 1, c);
  }
  for (int d = 9; d >= 0; d--) {
    for (int i = 0; i < n; i++) {
      if (dp[i][d].first < dp[i][d + 1].first) {
        dp[i][d] = dp[i][d + 1];
      }
      for (int j = 0; j < p[i].size(); j++) {
        if (dp[i][d].first < dp[p[i][j]][d + 1].first) {
          dp[i][d] = dp[p[i][j]][d + 1];
        }
      }
    }
  }
  for (int i = 0; i < n; i++)
    cout << dp[i][0].second << endl;
  return 0;
}


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

using namespace std;

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

const long long MOD = 1e9 + 7;
const int INF = 1e9;
const double EPS = 1e-9;

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

int main() {
  int N;
  cin >> N;
  Int lcm = 1;
  vector<Int> v(N);
  for (int i = 0; i < N; ++i) {
    cin >> v[i];
    Int g = gcd(lcm, v[i]);
    lcm = v[i] / g * lcm;
  }
  cout << lcm << endl;
}

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


int main(){
    string s; cin >> s;
    int cons = 0;
    int ans = 0;
    for(char& c : s){
        if(c == 'R') 
            {cons++; ans = max(ans, cons);}
        else cons = 0;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3612
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <climits>
#include <stack>
#include <queue>
#include <set>
#include <cctype>
#include <bitset>
#include <type_traits>

#include <list>
using namespace std;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define YES(j) cout << (j ? "YES" : "NO") << endl;
#define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
#define yes(j) std::cout << (j ? "yes" : "no") << endl;
using ll = long long;

int n, m, q;
int a[100], b[100], c[100], d[100];
int arr[100];
long long ans = 0;

void calc(int pos, int num)
{
    if (pos == n)
    {
        // 点数計算
        long long tmp = 0;
        REP(i, q)
        {
            if (arr[b[i]] - arr[a[i]] == c[i])
            {
                tmp += d[i];
            }
        }
        ans = max(ans, tmp);
    }
    else
    {
        for (int i = num; i <= m; i++)
        {
            arr[pos] = i;
            calc(pos + 1, i);
        }
    }
}

int main(void)
{

    cin >> n >> m >> q;
    REP(i, q)
    {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--;
        b[i]--;
    }
    for (int i = 1; i <= m; i++)
    {
        arr[0] = i;
        calc(1, i);
    }
    cout << ans << endl;
}

Measured memory_bytes: 3624
program abc166c
      implicit none
      integer(8)::n,m
      integer(8),allocatable::h(:),a(:),b(:),flag(:)
      integer(8)::i,j,ans

         read *, n,m
         allocate(h(n),a(m),b(m),flag(n))
         read *, h(1:n)

         do i=1,m
            read *, a(i),b(i)
         end do

         flag=1
         do i=1,m
            if ( h(a(i)) < h(b(i)) ) then
               flag(a(i))=0
            else if ( h(a(i)) > h(b(i)) ) then
               flag(b(i))=0
            else
               flag(a(i))=0;flag(b(i))=0
            end if
         end do

         ans=0
         do i=1,n
            if (flag(i)==1) ans=ans+1
         end do

         print *, ans

   end program abc166c

Measured memory_bytes: 6220
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))
    table = sorted(table)
    return table

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

A, B = map(int, input().split())

A_list = set(divisor(A))
B_list = set(divisor(B))

list = A_list & B_list

cnt = 1

for i in list:
    if is_prime(i):
        cnt += 1

print(cnt)

Measured memory_bytes: 11084
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a;
  cin >> a;
  if (a / 100 % 11 == 0 || a / 10 % 100 % 11 == 0 || a % 100 % 11 == 0) {
    cout << "Bad";
  } else {
    cout << "Good";
  }
}

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

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int sum = 0;
            string num = "", input;

            while ((input = Console.ReadLine()) != null)
            {
                input += " ";

                for (int i = 0; i < input.Length; i++)
                {
                    if (input[i] >= '0' && input[i] <= '9')
                    {
                        num += input[i];
                    }
                    else if (num != "")
                    {
                        sum += int.Parse(num);
                        num = "";
                    }
                }
            }
            Console.WriteLine(sum);
        }
    }
}

Measured memory_bytes: 9120
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N; string S;
  cin >> N >> S;
  int count=0;
  for (int i; i < N-2; i++){
    if ( S.at(i)=='A' && S.at(i+1)=='B' && S.at(i+2)=='C' ){
      count++;
    }
  }
  cout << count << endl; 
}
 

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

int main(){
  int n; cin>>n;
  vector<int> p(n);
  vector<int> index(n);
  rep(i,n) cin>>p[i];
  rep(i,n) p[i]--;
  rep(i,n) index[p[i]]=i;

  set<int> s;
  ll ans=0;
  for(int i=n-1;i>=0;i--){
    int x=index[i];
    s.insert(x);
    ll c=0;
    // cout<<"i "<<i<<" x "<<x<<endl;
    {
      vector<int> l(2,-1);
      vector<int> r(2,n);
      {
        auto it=s.find(x);
        rep(j,2){
          if(it==s.begin()) break;
          it--;
          l[j]=*it;
        }
      }
      {
        auto it=s.find(x);
        rep(j,2){
          it++;
          if(it==s.end()) break;
          r[j]=*it;
        }
      }
      vector<int> ls(2);
      vector<int> rs(2);
      ls[0]=index[i]-l[0]; ls[1]=l[0]-l[1];
      rs[0]=r[0]-index[i]; rs[1]=r[1]-r[0];
      c=(ll)ls[0]*rs[1]+(ll)ls[1]*rs[0];
    }
    // cout<<"c "<<c<<endl;
    ans+=c*(i+1);
  }

  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 5760
#include <iostream>

using namespace std;

typedef long long ll;

int m[100][100];
int H,W,N;
int a[10000];
int c[10000];

int main(){
    cin >> H >> W >> N;
    for(int i=0;i<N;i++) cin >> a[i];
    int count = 0;
    for(int i=0;i<N;i++){
        for(int j=0;j<a[i];j++){
            c[count++] = i+1;
        }
    }
    count = 0;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            int p;
            if(i % 2 == 0){
                p = j;
            }else{
                p = W - j - 1;
            }
            m[i][p] = c[count++];
        }
    }
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            cout << m[i][j];
            if(j != W-1) cout << " ";
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 384
<?php

fscanf(STDIN, "%d", $a);

if ($a == 25) {
    echo "Christmas\n";
} else if ($a == 24) {
    echo "Christmas Eve\n";
} else if ($a == 23) {
    echo "Christmas Eve Eve\n";
} else if ($a == 22) {
    echo "Christmas Eve Eve Eve\n";
}


Measured memory_bytes: 4728
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,a[100005],i,t=1,ans=0;
	cin>>n;
	for(i=1;i<=n;i++)
		cin>>a[i];
	sort(a+1,a+1+n);
	for(i=1;i<=n;i++)
	{
		if(a[i]==a[i+1])
			t++;
		if(a[i]!=a[i+1]||i==n-1)
		{
			if(a[i]<t) 
				ans+=t-a[i];
			if(a[i]>t) 
				ans+=t;
			if(a[i]!=a[i+1]&&i==n-1) 
				ans++;
			if(i<n-1) 
				t=1;
			else break;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 640
/* BISMILLAHIR RAHMANIR RAHIM */
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define s(v)       sort(v.begin(),v.end())
#define r(v)       reverse(v.begin(),v.end())
#define pf         printf
#define sf         scanf
#define GCD(x,y)   __gcd(x, y)
#define pb         push_back
#define ll         long long
#define vs         v.size()
#define ss         s.size()
using namespace std;

int main ()
{
    fast
    int n;
    cin>>n;
    if(n>=30) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}


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

using namespace std;
 
#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

typedef int64_t ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int MD = 1e9+7; typedef vector<ll> VL;
void dbg(){ cerr << "\n"; } template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }


int ym, xmx=4, a, b, c;
int ans = 1<<29;
vector<int> ct, l;
void rcf(int idx){
	if(idx==ym){
		VI ht(4), su(4);
		rep(i, ym){ ht[ct[i]] += l[i]; su[ct[i]]++;}
		int sm = 0;
		rep(i, 3) if(su[i] > 1) sm += 10 * (su[i]-1);
		rep(i, 3) if(ht[i] ==0) return;
		sm += abs(a - ht[0]) + abs(b - ht[1]) + abs(c - ht[2]);
		ans = min(ans,  sm);
		return ;
	}

	rep(i, xmx){
		ct[idx]=i;
		rcf(idx+1);
	}
}



int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	int n;
	cin >>n >>a >>b >>c;
	l.resize(n);
	rep(i, n) cin >>l[i];
	ym = n;
	ct.assign(n, 0);
	rcf(0);
	cout << ans <<"\n";
	return 0;
}


Measured memory_bytes: 256
import itertools
N, M, Q  = map(int,input().split())
query = []
for q in range(Q):
    a,b,c,d = map(int,input().split())
    a-=1
    b-=1
    query.append((a,b,c,d))
mx = 0
for comb in itertools.combinations_with_replacement([i for i in range(1,M+1)],N):
    score = 0
    for a,b,c,d in query:
        if (comb[b] - comb[a] == c):
            score += d
    mx = max(score,mx)
print (mx)




Measured memory_bytes: 67996
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
//#pragma GCC optimize ("unroll-loops")

using namespace std;
using namespace __gnu_pbds;

#define all(x) x.begin(), x.end()
#define mp make_pair
#define X first
#define Y second

template<typename T> // order_of_key(), *find_by_order()
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
mt19937_64 gen(time(nullptr));

ll const mod = 1e9 + 7;

namespace {
    ll mul(ll a, ll b) {
        ll val = a * b - (ll) ((ld) a * b / mod) * mod;
        if (val < 0) val += mod;
        if (val >= mod) val -= mod;
        return val;
    }

    ll poww(ll a, ll b) {
        ll val = 1;
        a %= mod;
        while (b > 0) {
            if (b % 2) val = mul(a, val);
            a = mul(a, a);
            b >>= 1;
        }
        return val % mod;
    }

    ll inv(ll a) {
        return poww(a, mod - 2);
    }
}
ll const maxn = 3e5 + 5;

unordered_set<int> g[maxn];
ld sum[maxn];
ll cnt[maxn];
ld rzn[maxn];

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n, m;
    cin >> n >> m;
    vector<ld> dp(maxn);
    vector<pair<int, int>> edges;
    for (ll i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        edges.emplace_back(u, v);
        g[u].insert(v);
    }
    dp[n] = 0;
    for (ll i = n - 1; i >= 1; i--) {
        cnt[i] = g[i].size();
        ld sm = 0;
        for (ll v : g[i]) {
            sm += dp[v];
        }
        sum[i] = sm;
        dp[i] = 1 + (1.0 / cnt[i]) * (sm);
    }
    ld ans = dp[1];
    for (ll u = n - 1; u >= 1; u--) {
        auto dpp = dp;
        dpp[u] -= 1;
        for (ll i = u - 1; i >= 1; i--) {
            ld sm = 0;
            for (ll v : g[i]) {
                sm += dpp[v];
            }
            dpp[i] = 1 + (1.0 / cnt[i]) * sm;
        }
        rzn[u] = dp[1] - dpp[1];
    }
    for (auto p : edges) {
        int u = p.X, v = p.Y;
        if (dp[u] == 1 + dp[v]) continue;
        ld new_sum = sum[u] - dp[v];
        ld new_dp = 1 + (1.0 / (cnt[u] - 1)) * new_sum;
        ld razn = dp[u] - new_dp;
        ans = min(ans, dp[1] - rzn[u] * razn);
    }
    cout << fixed << setprecision(10) << ans << endl;
    return 0;
}
/*
6
3 4 1
5 1 6
5 4 2
2 4 3
2 5 6
6 1 3

3
1 2 3
2 3 1
1 2 3
*/

Measured memory_bytes: 40816