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

template<typename T>
struct SparseTable{
    vector<vector<T>> dat;
    vector<int> lookup;
    typedef function<T(T a, T b)> Func;
    Func f;
    T e;

    SparseTable(){}
    SparseTable(const vector<T> &v, Func f, T e){ initialize(v, f, e); }
    void initialize(const vector<T> &v, Func fin, T ein){
        f = fin;
        e = ein;
        int b = 0;
        while((1<<b) <= v.size()) b++;
        int N = 1<<b;
        dat.assign(b, vector<T>(N, e));
        for(int i=0; i<v.size(); i++) dat[0][i] = v[i];

        for(int i=1; i<b; i++){
            int d = 1<<i;
            for(int j=0; j+d<=N; j++){
                dat[i][j] = f(dat[i-1][j], dat[i-1][j+d/2]);
            }
        }
        lookup.resize(N+1, 0);
        for(int i=2; i<=N; i++){
            lookup[i] = lookup[i>>1] + 1;
        }
    }

    T between(int l, int r) {
        r++;
        int b = lookup[r-l];
        return f(dat[b][l], dat[b][r-(1<<b)]);
    }
};

int main(){
    int N, K;
    cin >> N >> K;
    vector<int> P(N), pos(N);
    for(int i=0; i<N; i++){
        cin >> P[i];
        pos[P[i]] = i;
    }
    SparseTable<int> stmin(P, [](int a, int b){ return min(a, b); }, 1e9);
    SparseTable<int> stmax(P, [](int a, int b){ return max(a, b); }, -1e9);
    vector<int> nextlow(N), prevhigh(N);
    for(int i=0; i<N; i++){
        int ng = i, ok = N;
        while(ok-ng>1){
            int mid = (ng+ok)/2;
            (stmin.between(i, mid) < P[i] ? ok : ng) = mid;
        }
        nextlow[i] = ok;
        ok = -1, ng = i;
        while(ng-ok>1){
            int mid = (ng+ok)/2;
            (stmax.between(mid, i) > P[i] ? ok : ng) = mid;
        }
        prevhigh[i] = ok;
    }
    // for(int i=0; i<N; i++) cerr << nextlow[i] << " \n"[i==N-1];
    // for(int i=0; i<N; i++) cerr << prevhigh[i] << " \n"[i==N-1];
    SparseTable<int> st_nextlow(nextlow, [](int a, int b){ return min(a, b); }, 1e9);
    SparseTable<int> st_prevhigh(prevhigh, [](int a, int b){ return max(a, b); }, -1e9);

    set<pair<int, int>> ans;
    for(int l=0; l+K<=N; l++){
        int r = l+K-1;
        int ok = l-1, ng = r+1;
        while(ng-ok>1){
            int mid = (ng+ok)/2;
            (st_nextlow.between(l, mid) > r ? ok : ng) = mid;
        }
        int L = ng;
        ok = r+1, ng = l-1;
        while(ok-ng>1){
            int mid = (ng+ok)/2;
            (st_prevhigh.between(mid, r) < l ? ok : ng) = mid;
        }
        int R = ng;
        if(L >= R) L = R = -1;
        ans.insert({L, R});
    }
    cout << ans.size() << endl;
    return 0;
}


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

signed main(){
  int N,M;
  cin>>N>>M;
  int MA=0,MI=1e10+7;
  rep(i,M){
    int T,U;
    cin>>T>>U;
    MA=max(MA,T);
    MI=min(MI,U);
  }
  int ans=MI-MA+1;
  if(ans<0)ans=0;
  cout<<ans<<endl;
}

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

#define int long long
#define pb push_back


int dp[100005][3];
int a[100005][3];
int n;
int solve(int i,int cr) {
    if(i==n) return 0;
    if(dp[i][cr]!=-1) return dp[i][cr];
    if(cr==0) {
        dp[i][0]=a[i][0]+max(solve(i+1,1),solve(i+1,2));
    }
    else if(cr==1) {
        dp[i][1]=a[i][1]+max(solve(i+1,0),solve(i+1,2));
    }
    else if(cr==2) {
        dp[i][2]=a[i][2]+max(solve(i+1,1),solve(i+1,0));
    }
    return dp[i][cr];
}

signed main() {
memset(dp,-1,sizeof(dp));
    cin>>n;
    for(int i=0;i<n;i++) {
        cin>>a[i][0]>>a[i][1]>>a[i][2];
    }
    int ans=-1;
    for(int i=0;i<3;i++) {

        ans=max(ans,solve(0,i));
    }
    cout<<ans;
}


Measured memory_bytes: 11136
#include"bits/stdc++.h"
using namespace std;
typedef unsigned long long ll;


using Graph = vector<vector<int>>;//グラフ型
void dfs(const Graph& G, int v/*根*/, vector<bool>& seen) {
	seen[v] = true;  //vを訪問済にする
	for (auto next_v : G[v]) { //訪問済にしたvとつながっている場所を順番に探す
		if (seen[next_v]) continue; //もし探索済みならスルー
		dfs(G, next_v, seen); //再帰的に探索
	}
}

void bfs(const Graph& G, queue<int>& que/*発見したが訪問はしていない*/, vector<int>& dist/*開始地点からの距離*/) {
	
	while (!que.empty()) {
		int v = que.front();//queのうち先頭のものからスタート
		que.pop();//先頭を削除

		for (int nv : G[v]) {//vとつながっている点を列挙
			if (dist[nv] != -1) continue;//発見済(=距離が格納されている)であればスルー
			dist[nv] = dist[v] + 1;//vとつながっている点に距離の情報を追加
			que.push(nv);//vとつながっている点を発見済にする
		}
	}
}

int main(void) {
	double l;
	cin >> l;
	l /= 3;
	cout << setprecision(7) << l * l * l;
}


Measured memory_bytes: 256
def resolve():
    S = input()

    rep_S = S.replace("BC", "D")
    cnt = 0
    ans = 0
    for i in range(len(rep_S)):
        if rep_S[i] == "A":
            cnt += 1
        elif rep_S[i] == "D":
            ans += cnt
        else:
            cnt = 0

    print(ans)


if __name__ == "__main__":
    resolve()

Measured memory_bytes: 9292
#include<bits/stdc++.h>
#include<boost/variant.hpp>
using namespace std;
typedef long long ll;
typedef vector<boost::variant<bool, ll, int, string, double, char*, const char*>> any;
template<typename T> inline void pr(const vector<T> &xs){
	for(int i=0; i<xs.size()-1; i++) cout<<xs[i]<<" ";
	(xs.empty()?cout:(cout<<xs[xs.size()-1]))<<endl;
}
#ifdef DEBUG
#define debug(...) pr(any{__VA_ARGS__})
#define debugv(x) pr((x))
#else
#define debug(...)
#define debugv(x)
#endif

int main(){
	int N, M;
	cin >> N >> M;
	vector<int> X(N);
	for(int i=0; i<N; i++) cin >> X[i];

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

	bool mark = false;
	vector<int> cnt(M), pair(M);
	for(int i=0; i<N; i++){
		cnt[X[i]%M]++;
		if(i<N-1&&X[i]==X[i+1]&&!mark){
			pair[X[i]%M]++;
			mark = true;
		} else {
			mark = false;
		}
	}

	ll ans = 0;
	for(int i=1; i<(M+1)/2; i++){
		debug(cnt[i], cnt[M-i]);
		int x = min(cnt[i], cnt[M-i]);
		ans += x;
		ans += min(max(0, cnt[i]-x)/2, pair[i]);
		ans += min(max(0, cnt[M-i]-x)/2, pair[M-i]);
	}
	ans += cnt[0]/2;
	if(M%2==0) ans += cnt[M/2]/2;
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1e9 +7;
template<typename T>T read()
{
    T ans=0,F=1;
    char ch=getchar();
    while(!isdigit(ch)&&ch!='-')ch=getchar();
    if(ch=='-')F=-1,ch=getchar();
    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch-'0'),ch=getchar();
    return ans*F;
}

struct node
{
	int x,v;
}A[2020202];
bool cmp(node u,node w){return u.x<w.x;}
struct LINE
{
	int x,y;
}line[2020202];
int a[2020202],pre[2020202],nxt[2020202];
int n,num,xx,yy;
void sol(int x)
{
	xx=x; yy=x;
	int l=1,r=x-1;
	while (l<=r)
	{
		int mid=(l+r)/2;
		if (pre[mid]>=a[x])
		{
			xx=min(xx,mid);
			r=mid-1;
		}
		else l=mid+1;
	}

	l=x+1; r=n;
	while (l<=r)
	{
		int mid=(l+r)/2;
		if (nxt[mid]<=a[x])
		{
			yy=max(yy,mid);
			l=mid+1;
		}
		else r=mid-1;
	}
	++num; line[num]=(LINE){xx,yy};
}
ll f[2020202],s[2020202];
int thing[2020202];
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i) A[i].x=read<int>(),A[i].v=read<int>();
	sort(A+1,A+1+n,cmp);
	for (int i=1;i<=n;++i) a[i]=A[i].v;
	
	for (int i=1;i<=n;++i) pre[i]=max(pre[i-1],a[i]);
	nxt[n]=a[n];
	for (int i=n-1;i>=1;--i) nxt[i]=min(nxt[i+1],a[i]);
//	for (int i=1;i<=n;++i) printf("%d ",pre[i]);
//	printf("\n");
//	for (int i=1;i<=n;++i) printf("%d ",nxt[i]);

	for (int i=1;i<=n;++i) sol(i);

	int dog=0;
	for (int i=1;i<=num;++i) 
	{
		thing[line[i].y+1]=max(thing[line[i].y+1] , line[i].x);
		dog=max(dog,line[i].x);
	}
//	for (int i=1;i<=num;++i) printf("(%d,%d)\n",line[i].x,line[i].y);

	s[0]=1;
	int doe=0;
	for (int i=1;i<=n;++i)
	{
		doe=max(doe,thing[i]);
		f[i]=((s[i-1]-s[doe-1])%mod +mod)%mod;
		s[i]=(s[i-1]+f[i])%mod;
	}
	
	ll ans=0;
	for (int i=dog;i<=n;++i) (ans+=f[i])%=mod;
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 25600
import itertools
from scipy.sparse.csgraph import dijkstra
import sys 
input = sys.stdin.readline
def solve():
  n,m,R = (int(i) for i in input().split())
  r = list(int(i) for i in input().split())
  d = [[float("Inf")]*n for _ in range(n)]
  for i in range(m):
    a,b,c = (int(i) for i in input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
    
  d = dijkstra(d)

  perm = list(itertools.permutations(range(R)))
  cost = float("Inf")
  for i in range(len(perm)):
    root = perm[i]
    tempcost = 0
    for j in range(R-1):
      na = r[root[j]]-1
      nb = r[root[j+1]]-1
      tempcost += d[na][nb]
    cost = min(tempcost,cost)
  print(int(cost))
solve()

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

using Lint=long long;
const int LEN=60;
const int mod=1e9+7;

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

   vector<vector<int>> cnt(LEN,vector<int>(2));
   for(int i=0;i<N;i++){
      for(int j=0;j<LEN;j++){
         cnt[j][a[i]>>j&1]++;
      }
   }

   int ans=0;
   for(int i=0;i<LEN;i++){
      ans+=(1LL<<i)%mod*cnt[i][0]%mod*cnt[i][1]%mod;
      ans%=mod;
   }
   cout<<ans<<endl;
   return 0;
}



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

int main() {
  int n, x;
  vector<int> com(10000);
  int idx = 0;
  while(true) {
    cin >> n >> x;
    if(n == 0 && x == 0) {
      com.at(idx) = -1;
      break;
    }
    int num = 0;
    if(5 < x) {
      for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
          for(int k = 1; k <= n; k++) {
            if(((i != j) && (j != k) && (i != k)) && i + j + k == x) num += 1;
          }
        }
      }
    }
    num /= 6;
    com.at(idx) = num;
    idx++;
  }
  idx = 0;

  while(com.at(idx) != -1) {
    cout << com.at(idx) << endl;
    idx++;
  }
}


Measured memory_bytes: 3120
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    H, W = map(int, input().split())
    A = [input() for _ in range(H)]
    adj = [[] for _ in range(W*H)]
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    
    # 黒のマスからbfsする
    queue = deque()
    visit = [-1] * (W*H)

    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                queue.append(W*i + j)
                visit[W*i + j] = 0
            for k in range(4):
                y = i + dy[k]
                x = j + dx[k]
                if 0 <= y < H and 0 <= x < W:
                    adj[W*i + j].append(W*y + x)
    
    while queue:
        now = queue.popleft()
        for u in adj[now]:
            if visit[u] < 0:
                queue.append(u)
                visit[u] = visit[now] + 1
    print(max(visit))

if __name__ == "__main__":
    main()

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

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PrintStream out = new PrintStream(System.out);
        String A, B, C;

        A = sc.next();
        B = sc.next();
        C = sc.next();

        if (A.charAt(A.length()-1) == B.charAt(0) && B.charAt(B.length()-1) == C.charAt(0)) {
            out.println("YES");
        } else {
            out.println("NO");
        }
        
        
        sc.close();
    }
}

Measured memory_bytes: 21844
import java.util.*;

class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		char[] c = s.toCharArray();
		
		List<Integer> list = new ArrayList<>();
		for (int i = 0; i < c.length; i++) {
			switch (c[i]) {
			case '0':
				list.add(0);
				break;
			case '1':
				list.add(1);
				break;
			case 'B':
				if (list.size() == 0) {
					break;
				}
				list.remove(list.size() - 1);
			}
		}
		
		for (Integer integer : list) {
			System.out.print(integer);
		}
	}
}

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

int main()
{
	int a, b;
	char op;
	while (true)
	{

		cin >> a >> op >> b;
		switch (op)
		{
		case '+':
			cout << a + b << endl;
			break;
		case '-':
			cout << a - b << endl;
			break;
		case '*':
			cout << a * b << endl;
			break;
		case '/':
			cout << a / b << endl;
			break;
		case '?':
			return 0;
		default:
			return 0;
		}
	}

    return 0;
}

Measured memory_bytes: 1160
def func(M):
    num = []
    for i in range(1, int(M**0.5)+1):
        if not M % i:
            num.append(i)
            num.append(M//i)

    num.sort()
    return num

N, M = list(map(int, input().split()))
ans = 1
x = M / N

num = func(M)

for n in num:
    if n <= x:
        ans = n
    else:
        break
print(ans)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define rep(i, ss, ee) for (int i = (ss); i < (ee); ++i)

using ll = long long;
using P = pair<ll, int>;
using Vi = vector<int>;
using VP = vector<P>;

// Sieve of Eratosthenes
// https://youtu.be/UTVg7wzMWQc?t=2774
// https://github.com/atcoder/live_library/blob/master/prime.cpp

struct Sieve {
  int n;
  Vi f, primes;
  Sieve(int n = 1) : n(n), f(n + 1) {
    f[0] = f[1] = -1;
    for (ll i = 2; i <= n; ++i) {
      if (f[i]) continue;
      primes.push_back(i);
      f[i] = i;
      for (ll j = i * i; j <= n; j += i) {
        if (!f[j]) f[j] = i;
      }
    }
  }
  bool isPrime(int x) { return f[x] == x; }
  Vi factorList(int x) {
    Vi res;
    while (x != 1) {
      res.push_back(f[x]);
      x /= f[x];
    }
    return res;
  }
  VP factor(int x) {
    Vi fl = factorList(x);
    if (fl.size() == 0) return {};
    VP res(1, P(fl[0], 0));
    for (int p : fl) {
      if (res.back().first == p) {
        res.back().second++;
      } else {
        res.emplace_back(p, 1);
      }
    }
    return res;
  }
  VP factor(ll x) {
    VP res;
    for (int p : primes) {
      int y = 0;
      while (x % p == 0) x /= p, ++y;
      if (y != 0) res.emplace_back(p, y);
    }
    if (x != 1) res.emplace_back(x, 1);
    return res;
  }
};

void solve() {
  ll n, ans = 0;
  cin >> n;
  Sieve s(sqrt(n));
  for (const auto &p : s.factor(n)) {
    ll x = p.second;
    ll i = 1;
    while (x >= i) {
      ans++;
      x -= i++;
    }
  }
  cout << ans << endl;
}

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

Measured memory_bytes: 7808
/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;
class Main {
    static int check;
	public static void main (String[] args) {
		//System.out.println("GfG!");
		int n;
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		int W = sc.nextInt();
		int val[]=new int[n];
		int wt[]=new int[n];
		for(int i=0;i<n;i++){
		    wt[i]=sc.nextInt();
		    val[i]=sc.nextInt();
		    
		}
		long K[][]=new long[n+1][W+1]; 
  
   // Build table K[][] in bottom up manner 
   for (int i = 0; i <= n; i++) 
   { 
       for (int w = 0; w <= W; w++) 
       { 
           if (i==0 || w==0) 
               K[i][w] = 0; 
           else if (wt[i-1] <= w) 
                 K[i][w] = Math.max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]); 
           else
                 K[i][w] = K[i-1][w]; 
       } 
   } 
  
   System.out.println(K[n][W]); 
	}}

Measured memory_bytes: 127060
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace A
{
    public class Program
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var AB = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();
            var A = AB[0];
            var B = AB[1];

            var answer = A % 3 == 0 || B % 3 == 0 || (A + B) % 3 == 0;
            Console.WriteLine(answer ? "Possible" : "Impossible");
        }
    }
}


Measured memory_bytes: 27996
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>
using namespace std;
long long n,lg,x[101010],v[101010],a[101010],b[101010],c[101010],d[101010],l,r,ans;
int main()
{
	cin>>n>>lg;
	for(int i=0;i<n;i++)
	{
		cin>>x[i]>>v[i];
	}
	for(int i=0;i<n;i++)
	{
		l+=v[i];
		r+=v[n-i-1];
		a[i+1]=max(a[i],l-x[i]);
		b[i+1]=max(b[i],l-x[i]*2);
		c[n-i-1]=max(c[n-i],r-(lg-x[n-i-1]));
		d[n-i-1]=max(d[n-i],r-(lg-x[n-i-1])*2);
	}
	for(int i=0;i<=n;i++)
	{
		ans=max(ans,max(a[i]+d[i],b[i]+c[i]));
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 4992
N = int(input())

proof = [[] for _ in range(N)]
for i in range(N):
    for j in range(int(input())):
        x, y = map(int, input().split())
        proof[i].append([x-1, y])

ans = 0
for i in range(1, 2**N):
    flag = 0
    for j in range(N):
        if (i>>j) & 1 == 1:
            for x, y in proof[j]:
                if (i>>x)&1 != y:
                    flag = 1
                    break
    if flag == 0:
        ans = max(ans, bin(i)[2:].count('1'))
print(ans)

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

int main(){
    ll n,m;
    cin >> n >>m;
    if(n<m/2){
    cout << (n+(m/2))/2 <<endl;}
    else cout << m/2 <<endl;
    }

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

int main() {
    ll n, m;
    cin >> n >> m;
    vector<vector<ll>> cakes(n, vector<ll>(3));
    rep(i, n) {
        rep(j, 3) {
            cin >> cakes[i][j];
        }
    }
    ll ans = 0;
    for (ll bit = 0; bit < (1 << 3); bit++) {
        vector<ll> scores;
        for (ll i = 0; i < n; i++) {
            ll score = 0;
            for (ll k = 0; k < 3; k++) {
                score += (bit & (1 << k) ? cakes[i][k] : -cakes[i][k]);
            }
            scores.push_back(score);
        }
        sort(scores.rbegin(), scores.rend());
        ll sum = 0;
        for (ll i = 0; i < m; i++) {
            sum += scores[i];
        }
        ans = max(ans, sum);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
N, K = list(map(int, input().split(" ")))

A = list(map(int, input().split(" ")))

ans = False

A = sorted(A)

key = 99999999999999
    
if A[-1] < K:
    ans = False

else:
    for i in range(2, A[0]+1):
        key_flag = True
        for a in A:
            if a % i !=0:
                key_flag = False
                break
                
        if key_flag == True:
            key = i
            break

    if key_flag == False:
        ans = True
#         print(1)
    elif K % key == 0:
        ans = True
#         print(2)
    else:
#         print(3)
        ans = False           
    
if ans == True:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Measured memory_bytes: 14096
<?php
list($h, $w) = ints();
$n = 10;
for ($i = 0; $i < 10; ++$i) {
    $c = ints();
    foreach ($c as $j => $v) {
        $g[$i][] = $j;
        $d[$i][$j] = $v;
    }
}
for ($i = 0; $i < 10; ++$i) $mindist[$i][1] = dijkstra($i)[1];
$ans = 0;
for ($i = 0; $i < $h; ++$i) {
    $a = ints();
    foreach ($a as $v) {
        $ans += $v !== -1 ? $mindist[$v][1] : 0;
    }
}
echo $ans;

function ints()
{
    return array_map('intval', explode(' ', trim(fgets(STDIN))));
}

function dijkstra($i)
{
    global $g, $d;
    $q = new SplQueue(); // キューを用意
    $mindist[$i] = 0; // スタート地点からの距離格納配列
    $q->enqueue($i); // キューにスタート地点を追加

    while (!$q->isEmpty()) {
        $v = $q->dequeue();
        foreach ($g[$v] as $next_v) {
            if (!isset($mindist[$next_v]) || $mindist[$next_v] > $mindist[$v] + $d[$v][$next_v]) {
                $mindist[$next_v] = $mindist[$v] + $d[$v][$next_v];
                $q->enqueue($next_v);
            }
        }
    }
    return $mindist;
}


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

int main(){
  string s, t; cin >> s >> t;
  int n, m;
  n = s.size(); m = t.size();
  int dpv[n+1][m+1];
  rep(i, n+1)rep(j, m+1) dpv[i][j] = 0;
  P dp[n+1][m+1];
  rep(i, n)rep(j, m){
    if(s[i] == t[j]){
      dpv[i+1][j+1] = dpv[i][j] + 1;
      dp[i+1][j+1] = P(i, j);
    }
    else if(dpv[i][j+1] > dpv[i+1][j]){
      dpv[i+1][j+1] = dpv[i][j+1];
      dp[i+1][j+1] = P(i, j+1);
    }
    else{
      dpv[i+1][j+1] = dpv[i+1][j];
      dp[i+1][j+1] = P(i+1, j);
    }
  }
  int x = n, y = m;
  string ans = "";
  while(x!=0 || y!=0){
    int nx = dp[x][y].first, ny = dp[x][y].second;
    if(nx==x-1 && ny==y-1){
      ans += s[nx];
    }
    x = nx; y = ny;
  }
  reverse(ans.begin(), ans.end());
  cout << ans << endl;
}

Measured memory_bytes: 105856
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<functional>
#include<queue>
using namespace std;
int e[200009][26], dp[200009]; string S;
int main() {
	cin >> S; S = '-' + S;
	for (int i = 0; i < 26; i++) {
		int r = S.size();
		for (int j = S.size() - 1; j >= 0; j--) {
			e[j][i] = r;
			if (S[j] == ('a' + i))r = j;
		}
	}
	for (int i = S.size() - 1; i >= 0; i--) {
		int maxn = 0;
		for (int j = 0; j < 26; j++) {
			maxn = max(maxn, e[i][j]);
		}
		dp[i] = dp[maxn] + 1;
	}
	string T = ""; int cx = 0;
	while (cx != S.size()) {
		for (int i = 0; i < 26; i++) {
			if (dp[e[cx][i]] == dp[cx] - 1) { cx = e[cx][i]; T += ('a' + i); break; }
		}
	}
	cout << T << endl;
	return 0;
}

Measured memory_bytes: 21696
#include <iostream>
   
int main(){
   int N, M, K, A;
   std::cin >> N >> M;
   int like[M];
   for(int i=0; i<M; ++i)
      like[i] = 0;

   for(int i=0; i<N; ++i){
      std::cin >> K;
      for(int j=0; j<K; ++j){
	 std::cin >> A;
	 like[A-1] += 1;
      }
   }

   int n = 0;
   for(int i=0; i<M; ++i)
      if(like[i]==N) ++n;

   std::cout << n << std::endl;

   return 0;
}


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

typedef long long ll;

int main()
{
    ll t, n, i;

    cin>>t;
    map<string,ll>use;
    string s;
    for(i=0; i<t; i++)
    {
        cin>>s;
        use[s]++;
    }


        cout<<"AC x "<<use["AC"]<<endl;
     cout<<"WA x "<<use["WA"]<<endl;
        cout<<"TLE x "<<use["TLE"]<<endl;
        cout<<"RE x "<<use["RE"]<<endl;
    
}

Measured memory_bytes: 3632
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>

using namespace std;
using ll = long long;
using pint = pair<int, int>;

ll INF = 1LL << 60;

int main() {
	string S;
	cin >> S;
	int count = 0;
	for (auto s : S) {
		if (s == 'R') count++;
	}
	if (count == 2) {
		if (S[1] == 'S') count = 1;
	}
	cout << count << endl;
	return 0;
}

Measured memory_bytes: 3624
#!/usr/bin/env python

def main():
    h, w = map(int, input().split())
    hw = h * w
    if h == 1 or w == 1:
        print(1)
    else:
        if hw % 2 == 0:
            print(hw // 2)
        else:
            print(hw // 2 + 1)

if __name__ == '__main__':
    main()


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

int main(){
    int n; cin>>n;
    vector<int> v(n);
    rep(i,n) cin>>v[i];
    sort(v.begin(),v.end());
    double ans=v[0];
    for(int i=1;i<n;i++) ans=(ans+v[i])/2;
    printf("%.10f\n",ans);
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;++i)
#include<string>
using namespace std;
typedef long long ll;
//max=({});
//条件式が真ならwhileの中身を回し続ける

int n;
ll h;

int main() {
	cin >> h >> n;
	vector<int>A(n);
	int total = 0;
	rep(i, n) {
		cin >> A[i];
		total += A[i];
	}
	if (total >= h)puts("Yes");
	else puts("No");
	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define LLI long long int
#define FOR(v, a, b) for(LLI v = (a); v < (b); ++v)
#define FORE(v, a, b) for(LLI v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define REV(v, a, b) for(LLI v = (a); v >= (b); --v)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it)
#define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
#define EXIST(c,x) ((c).find(x) != (c).end())
#define fst first
#define snd second
#define popcount __builtin_popcount
#define UNIQ(v) (v).erase(unique(ALL(v)), (v).end())
#define bit(i) (1LL<<(i))

#ifdef DEBUG
#include <misc/C++/Debug.cpp>
#else
#define dump(...) ((void)0)
#endif

#define gcd __gcd

using namespace std;
template <class T> constexpr T lcm(T m, T n){return m/gcd(m,n)*n;}

template <typename I> void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost<<d; ost<<*i;}ost<<endl;}
template <typename T> istream& operator>>(istream &is, vector<T> &v){for(auto &a : v) is >> a; return is;}

template <typename T, typename U> bool chmin(T &a, const U &b){return (a>b ? a=b, true : false);}
template <typename T, typename U> bool chmax(T &a, const U &b){return (a<b ? a=b, true : false);}
template <typename T, size_t N, typename U> void fill_array(T (&a)[N], const U &v){fill((U*)a, (U*)(a+N), v);}

struct Init{
  Init(){
    cin.tie(0);
    ios::sync_with_stdio(false);
  }
}init;

template <typename T> vector<int> z_algorithm(const T &s){
  int n = s.size();
  vector<int> ret(n, 0);
  int j = 0;

  FOR(i,1,n){
    if(i+ret[i-j] < j+ret[j]){
      ret[i] = ret[i-j];
    }else{
      int k = max<int>(0, j+ret[j]-i);
      while(i+k < n and s[k] == s[i+k]) ++k;
      ret[i] = k;
      j = i;
    }
  }

  ret[0] = n;

  return ret;
}





int main(){
  int N;
  string s;
  while(cin >> N >> s){
    int ans = 0;

    REP(i,N){
      auto t = s.substr(i);
      dump(t);
      auto z = z_algorithm(t);
      dump(z);

      REP(j,N-i){
        if(z[j] <= j) chmax(ans, z[j]);
      }
    }
    

    

    cout << ans << endl;
  }


  return 0;
}


Measured memory_bytes: 384
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cassert>
#include<cmath>
using namespace std;
typedef long long lint;
typedef vector<int>vi;
typedef pair<int,int>pii;
typedef pair<lint,lint>pll;
typedef pair<pll,lint>pplll;
#define rep(i,n)for(int i=0;i<(int)(n);++i)

pll fundamental_unit(lint d){
  vi ans;
  lint x=0,y=1,z=1;//(x+y*sqrt(d))/z
  double sqrtd=sqrt(d);
  set<pplll>seen;
  while(1){
    if(seen.count(pplll(pll(x,y),z)))break;
    seen.insert(pplll(pll(x,y),z));
    lint q=floor((x+sqrtd*y)/z);
    if(0){
      cerr<<"x,y,z=("<<x<<"+"<<y<<"*sqrt(d))/"<<z<<endl;
      cerr<<"q="<<q<<endl;
    }
    ans.push_back(q);
    x-=q*z;
    lint norm=x*x-d*y*y;
    y=-y;
    z=norm/z;
    if(z<0){
      x=-x;y=-y;z=-z;
    }
  }
  // recover
  lint num=0,den=1;
  for(int i=(int)ans.size()-2;i>=0;--i){
    lint z=num+ans[i]*den;
    num=den;den=z;
  }
  if(den*den-d*num*num==-1){
    lint x=den*den+d*num*num;
    lint y=2*den*num;
    den=x;num=y;
  }
  assert(den*den-d*num*num==1);
  return pll(den,num);
}

pll solve(lint n){
  rep(i,200)
    if(i*i==2*n)
      return pll(i,1);
  return fundamental_unit(2*n);
}

int main(){
  for(int t=1;;++t){
    lint n;
    cin>>n;
    if(n==0)break;
    pll ans=solve(n);
    cout<<"Case "<<t<<": "<<ans.first<<" "<<ans.second<<endl;
  }
}



Measured memory_bytes: 3116
/* CODE BY NITIN 
ON 31 MARCH 2020--------------
*/

#include <bits/stdc++.h>
//#include<boost/multiprecision/cpp_int.hpp>
#define mod 1000000007
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define REPN(i, n) for (int i = 1; i <=(n); i++)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
#define T(a) ll a;  cin >> a;
#define TT(t) T(t); while (t--)
#define pb push_back
#define mp make_pair
 #define ll long long int
using namespace std;

int solve()
{
	//int t; 
//	cin>>t;
	//while(t--){
		T(x)
		ll ans1;
		ll ans2;
		ans1 = x%500;
		ans2=ans1/5;
		cout<<(1000*(x/500))+(5*ans2)<<endl;
		
		
//	}
}
int main()
{
	
	
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	solve();
	
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Random;
 
class Main {
    public static void main(String[] args){
        try {
 
        BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        PrintWriter pw = new PrintWriter(System.out);
        Restaurant rr[] = new Restaurant[N];
 
        for(int i = 0; i < N; i++){
            String str[] = (br.readLine()).split("\\s+");
            rr[i] = new Restaurant(str[0],Integer.parseInt(str[1]),i+1);
        }
 
        QuickSort(rr, 0, N-1);
        // 標準出力
        for(Restaurant node : rr) { pw.println(node.i); }
 
        pw.flush();
 
        } catch(IOException e) { System.out.println("Exception :" + e); }
    }
 
    static void QuickSort (Restaurant rr[], int left, int right) {
        /*配列の個数を計算する*/
        if((right - left + 1) == 0)
            return;
 
        int i = left, j = right;
 
        /*与えられたインデックス間の乱数をとる*/
        Random random = new Random();
        Restaurant temp = new Restaurant();
        Restaurant p = rr[random.nextInt(right - left + 1) + left].copy();
 
        while(true){
            while( rr[i].compare(p) < 0 && i < right)
                i++;
 
            while( rr[j].compare(p) > 0 && j > left)
                j--;
 
            if(i >= j)
                break;
            else{
                temp = rr[i].copy();
                rr[i] = rr[j].copy();
                rr[j] = temp.copy();
                i++; j--;
            }
        }
        if(left < i-1)
            QuickSort(rr, left, i-1);
        if(j+1 < right)
            QuickSort(rr, j+1, right);
    }
 
}
 
class Restaurant {
    String S;
    int P,i;
 
    Restaurant () {
        this("NO NAME",-1,-1);
    }
 
    Restaurant (String S, int P, int i) {
        this.S = S; this.P = P; this.i = i;
    }
 
    // Restaurantクラスの比較メソッド
    int compare (Restaurant rr) {
        if ((this.S).compareTo(rr.S) < 0)
            return -1;
        else if ((this.S).compareTo(rr.S) > 0)
            return 1;
        else return rr.P - this.P;
    }
 
    // Resturantクラスの複製メソッド
    Restaurant copy () {
        Restaurant rr = new Restaurant(this.S,this.P, this.i);
        return rr;
    }
}

Measured memory_bytes: 20820
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <iterator>
#include <math.h>
#include <algorithm>
#include <numeric>

using namespace std;

int main(){
    int N;
    cin  >> N;
    vector<int> v(N); 
    int dist = 0;
    int center;

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

    int amari = accumulate(v.begin(), v.end(), 0)%v.size();
    if( v.size()/2 < amari ){
        center = accumulate(v.begin(), v.end(), 0)/v.size() + 1;
    }else{
        center = accumulate(v.begin(), v.end(), 0)/v.size();
    }

    for(int i=0; i<v.size(); ++i){
        int tmp = (v[i] - center) * (v[i] - center);
        dist += tmp;
    }

    cout << dist << endl;
}

Measured memory_bytes: 256
import java.io.PrintWriter
val pw = PrintWriter(System.out)

fun main(args : Array<String>) {
    func()
    pw.flush()
}

fun func() {
    val n = nextInt()
    val s = next()
    var count = 0
    var max = 0

    s.forEach {
        if (it == 'I') count++
        if (it == 'D') count--
        if (count > max) max = count
    }

    println(max)
}

fun next() = readLine()!!
fun nextInt() = next().toInt()

fun println(value : Any) {
    pw.println(value)
}

Measured memory_bytes: 33792
s = input()
K = int(input())
result = []
for i in range(len(s)):
    for j in range(i + 1, min(i + K + 1, len(s) + 1)):
        result.append(s[i:j])

result = list(set(result))
result.sort()
# print(result)
# print(len(result))
print(result[K - 1])


Measured memory_bytes: 5068
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int main() {
    int count = 0;
    string s, p;
    cin >> s;
    std::transform(s.begin(), s.end(), s.begin(), ::toupper);
    while(cin >> p){
        if(p == "END_OF_TEXT") break;
        std:transform(p.begin(), p.end(), p.begin(), ::toupper);
        if (s == p) {
            count += 1;
        }   
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 1192
s=list(input())
odd = ["R","U","D"]
even = ["L", "U", "D" ]

frg = 0

for i in s[0::2]:
    if i in odd:         #偶数のものが奇数番にあったらよくない
        frg += 1

for i in s[1::2]:
    if i in even:
        frg += 1

if frg == len(s):
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3064
#include <stdio.h>
 
int main(){
 int a, b, c;
 
 scanf("%d %d %d",&a,&b,&c);
 
 if(b > c){
  int temp = b;
  b = c;
  c = temp;
 }
 if(a > b){
  int temp = a;
  a = b;
  b = temp;
 }
 if(b > c){
  int temp = b;
  b = c;
  c = temp;
 }

 printf("%d %d %d\n", a, b, c);

 return 0;
}

Measured memory_bytes: 1796
#include <iostream>
#include <algorithm>
#include <array>
#include <atomic>
#include <bitset>
#include <deque>
#include <forward_list>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>
using namespace std;

#define rep(i, a, n) for(int i = a; i <= n; i++)
#define sum(start, end) accumulate(start, end, 0)

typedef long long ll;


void solve() {
    string a, b, c;
    cin >> a >> b >> c;
    cout << (a[a.size()-1] == b[0] && b[b.size()-1] == c[0] ? "YES" : "NO") << endl;
}

int main() {	
    std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);
    solve();
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main ()
{
  int n;
  long long int a,b,x,x0,x1,ans=0;
  cin >> n >> a >> b;
  cin >> x;
  x0 = x;
  for(int i=0;i<(n-1);i++){
    cin >> x;
    x1 = x;
    ans += min((x1-x0)*a,b);
    x0 = x;
  }
  cout << ans << endl;
  return 0;
}

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

int main() {
   
    
   string s;
    cin>>s;
    
    int nn = stoi(s);
    
    int n = s.size();
    
    long long sum = 0;
    for(int i=0;i<n;++i)
    {
        sum+= (s[i]-'0');
    }
    
    if(nn%sum==0)
        cout<<"Yes";
    else
        cout<<"No";
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <map>
#include <vector>

using namespace std;

int main(int argc, char *argv[]) {
  int n, m, sum;
  vector< pair<string, int> > elected;
  while (true) {
    cin >> n >> m;
    if (n == 0 && m == 0)
      break;

    sum = 0;
    for (int i = 0; i < n; i++) {
      string s;
      int n;
      cin >> s >> n;
      elected.push_back(pair<string, int>(s, n));
    }

    for (int i = 0; i < m; i++) {
      string s;
      cin >> s;
      for (int j = 0; j < elected.size(); j++) {
        for (int k = 0; k < elected[j].first.size(); k++) {
          if (elected[j].first[k] != '*' && elected[j].first[k] != s[k])
            break;
          if (k == elected[j].first.size() - 1) {
            sum += elected[j].second;
          }
        }
      }
    }

    cout << sum << endl;
    elected.clear();
  }

  return 0;
}

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

int main()
{
    int N, W;
    cin >> N >> W;
    
    int w[N+1], v[N+1];
    for(int i = 1; i <= N; i++) cin >> w[i] >> v[i];
    
    unsigned long long V[N+1][W+1];
    for(int i = 0; i <= N; i++) for(int j = 0; j <= W; j++) V[i][j] = 0;
    
    for(int i = 1; i <= N; i++) for(int j = 1; j <= W; j++)
    {
        if(j - w[i] >= 0) V[i][j] = V[i-1][j - w[i]] + v[i];
        V[i][j] = max(V[i][j], max(V[i-1][j], V[i][j-1]));
    }
    cout << V[N][W] << '\n';
    return 0;
}

Measured memory_bytes: 79104
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <algorithm>

typedef long long ll;
const ll MOD = 1e9 + 7;
const long long INF = 1LL<<60;
const double PI=3.14159265358979323846;
const int NMAX=100005;
using namespace std;

int done[51][51];
int c[51][51];

void dfs(int i, int j, int w, int h){
    if(i < 0 || i >= h || j < 0 || j >= w) return;
    if(done[i][j] != 0) return;

    done[i][j] = 1;
    
    if(c[i][j] == 1){
        dfs(i-1,j-1,w,h);
        dfs(i-1,j,w,h);
        dfs(i-1,j+1,w,h);
        dfs(i,j-1,w,h);
        dfs(i,j+1,w,h);
        dfs(i+1,j-1,w,h);
        dfs(i+1,j,w,h);
        dfs(i+1,j+1,w,h);
    }
}

void solve(int w, int h){
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            cin >> c[i][j];
            done[i][j] = 0;
        }
    }
    int ans = 0;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            if(done[i][j] == 0 && c[i][j] == 1){
                ans += 1;
                dfs(i,j,w,h);
            }
        }
    }
    cout << ans << endl;
}

int main(){
    while(true){
        int w,h;
        cin >> w >> h;
        if(w == 0 && h == 0) break;
        solve(w,h);
    }

    return 0;
}


Measured memory_bytes: 3212
#include<bits/stdc++.h>
using namespace std;
#define int long
main(){
  int w,h,n,r=0;
  cin>>w>>h>>n;
  vector<vector<int>> p(w,vector<int>(h,1));
  while(n--){
    int x,y,a;
    cin>>x>>y>>a;
    a--;
    if(a/2)for(int i=0;i<w;++i)for(int j=(a%2?y:0);j<(a%2?h:y);++j)p[i][j]=0;
    else   for(int i=(a%2?x:0);i<(a%2?w:x);++i)for(int j=0;j<h;++j)p[i][j]=0;
  }
  for(auto v:p)for(auto i:v)r+=i;
  cout<<r;
}

Measured memory_bytes: 384
import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws NumberFormatException,
			IOException {
		new Main().run();
	}

	private void run() throws NumberFormatException, IOException {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[][] pre = new int[n][2];
		for (int i = 0; i < n; i++) {
			pre[i][0] = scanner.nextInt();
		}
		for (int i = 0; i < n; i++) {
			int t = scanner.nextInt();
			for (int j = 0; j < n; j++) {
				if (pre[j][0] == t) {
					pre[j][1] = i;
				}
			}
		}
		rec(0, n, pre);

	}

	int pos = 0;

	private void rec(int l, int r, int[][] pre) {
		if (l >= r)
			return;
		int root = pre[pos][0];
		int m = pre[pos][1];
		pos++;
		rec(l, m, pre);
		rec(m + 1, r, pre);
		System.out.print(root);
		System.out.print(root == pre[0][0] ? '\n' : ' ');
	}
}

Measured memory_bytes: 18284
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define sar(a,n) {cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl;}

using namespace std;

template<typename S,typename T>auto&operator<<(ostream&o,pair<S,T>p){return o<<"{"<<p.fi<<","<<p.se<<"}";}
template<typename T>auto&operator<<(ostream&o,set<T>s){for(auto&e:s)o<<e<<" ";return o;}
template<typename S,typename T,typename U>
auto&operator<<(ostream&o,priority_queue<S,T,U>q){while(!q.empty())o<<q.top()<<" ",q.pop();return o;}
template<typename K,typename T>auto&operator<<(ostream&o,map<K,T>&m){for(auto&e:m)o<<e<<" ";return o;}
template<typename T>auto&operator<<(ostream&o,vector<T>v){for(auto&e:v)o<<e<<" ";return o;}
void ashow(){cout<<endl;}template<typename T,typename...A>void ashow(T t,A...a){cout<<t<<" ";ashow(a...);}
template<typename S,typename T,typename U>
struct TRI{S fi;T se;U th;TRI(){}TRI(S f,T s,U t):fi(f),se(s),th(t){}
bool operator<(const TRI&_)const{return(fi==_.fi)?((se==_.se)?(th<_.th):(se<_.se)):(fi<_.fi);}};
template<typename S,typename T,typename U>
auto&operator<<(ostream&o,TRI<S,T,U>&t){return o<<"{"<<t.fi<<","<<t.se<<","<<t.th<<"}";}

typedef pair<int, int> P;
typedef pair<ll, ll> pll;
typedef TRI<int, int, int> tri;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<P> vp;
typedef vector<double> vd;
typedef vector<string> vs;

const int MAX_N = 100005;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int cnt = 0;
    rep(i,3){
        int a;
        cin >> a;
        if(a % 2) cnt++;
    }
    if(cnt >= 2){
        cout << "Hom\n";
    }else{
        cout << "Tem\n";
    }
    return 0;
}



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

using namespace std;

#define int long long
int const maxn = 2e5 + 5;
int a[maxn], pref[maxn], L[maxn], R[maxn];
map < pair < int, int >, int > f;
int inf = 1e18;
set < pair < int, pair < int, int > > > Q;

int get(int l, int r) {
    return pref[r] - pref[max(0ll, l - 2)] - (pref[r - 1] - pref[max(0ll, l - 1)]);
}

void del(int l, int r) {
    Q.erase({f[{l, r}], {l, r}});
}

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, ans = 0;
    cin >> n;
    a[1] = -inf;
    for (int i = 2; i <= n + 1; ++i) cin >> a[i];
    a[n + 2] = -inf;
    for (int i = 1; i <= n + 2; ++i) pref[i] = pref[max(i - 2, 0ll)] + a[i];
    for (int i = 1; i <= n + 2; ++i) Q.insert({a[i], {i, i}}), L[i] = i, R[i] = i, f[{i, i}] = a[i];
    for (int i = 1; i <= n / 2; ++i) {
        auto p = (*Q.rbegin());
        ans += p.first;
        Q.erase(p);
        int l = p.second.first, r = p.second.second;
        int nxtl = R[l - 1], nxtr = L[r + 1];
        del(nxtl, l - 1);
        del(r + 1, nxtr);
        Q.insert({get(nxtl, nxtr), {nxtl, nxtr}});
        L[nxtl] = nxtr, R[nxtr] = nxtl;
        f[{nxtl, nxtr}] = get(nxtl, nxtr);
    }
    cout << ans << '\n';
    return 0;
}



Measured memory_bytes: 34904
#include<stdio.h>
int main()
{
	int map[2][105];
	int n;
	while (~scanf("%d", &n))
	{
		int search[105] = {0};
		int max = 0;
		for (int i = 0; i < 2;i++)
		for (int j = 0; j < n; j++)
		{
			scanf("%d", &map[i][j]);
		}
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j <= i; j++)
			{
				search[i] += map[0][j];
			}
			for (int j = i; j < n; j++)
			{
				search[i] += map[1][j];
			}
			if (search[i]>max)
				max = search[i];
		}
		printf("%d\n", max);
	}
}

Measured memory_bytes: 128
#include<stdio.h>

int main(){

  int i, j, n, count=0; 
  int G[101][101], c[101], d[101], p[101], min, I; 

  scanf("%d", &n);

  for(i=0; i<n; i++){
    for(j=0; j<n; j++){
      scanf("%d", &G[i][j]);
    }
  }

  for(i=0; i<n; i++){
    c[i]=0;
    p[i]=-1;
    d[i]=2001;
  }

  d[0]=0;

  while(1){
    min=2001;
    for(i=0; i<n; i++){
      if(c[i] != 2 && d[i] < min){
	min=d[i];
	I=i;
      }
    }

    if(min == 2001) break;
    c[I]=2;
    for(i=0; i<n; i++){
      if(G[I][i] != -1 && c[i] != 2 && G[I][i] < d[i]){
	p[i]=I;
	d[i]=G[I][i];
	c[i]=1;
      }
    }
  }

  for(i=0; i<n; i++){
    if(p[i] != -1){
      count += G[i][p[i]];
    }
  }
  printf("%d\n", count);
  return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
#include <string>

using namespace std;
typedef long long ll;

#define rep(i, n) for(int i = 0; i < n ; i++ )
#define For(i, a, b) for(int i = (a); i < (b) ; i++ )
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

bool is_M(int bin){
    if ( 1 <= bin && bin <= 12){
        return true;
    }
    return false;
}

int main(void){
    int S;

    cin >> S;

    int f, s;
    bool f_is_M, s_is_M;
    f = S / 100;
    s = S % 100;

    f_is_M = is_M(f);
    s_is_M = is_M(s);

    if (f_is_M && s_is_M){
        cout << "AMBIGUOUS" << endl;
    }else if (f_is_M){
        cout << "MMYY" << endl;
    }else if (s_is_M){
        cout << "YYMM" << endl;
    }else{
        cout << "NA" << endl;
    }   

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#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;

long long GCD(long long x, long long y) {
    if (x % y == 0) return y;
    else return GCD(y, x % y);
}

long long LCM(long long x, long long y) {
    return x / GCD(x, y) * y;
}

int main() {
    long long A, B, C, D;
    cin >> A >> B >> C >> D;
    
    long long L = LCM(C, D);
    long long x = B / L - (A - 1) / L;
    long long y = B / C - (A - 1) / C;
    long long z = B / D - (A - 1) / D;
    cout << B - A + 1 - y - z + x << endl;
    return 0;
}


Measured memory_bytes: 256
//Created by Kira

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

#define IOS cin.sync_with_stdio(0);cin.tie(0); cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pii pair<int,int> 
#define pb push_back
#define vi vector<int> 
using ll = long long;

const int mod = 1e9 + 7;

ll pwr(ll a, ll b);

int n, m, q, ans = 0;
vi a,b, c, d, A;
void gen_seq(int i, int last){
    if(i == n){
        int tot = 0;
        for(int i = 0; i < q; i++){
            tot += (A[b[i] - 1] - A[a[i] - 1] == c[i])*d[i];
        }
        ans = max(ans, tot);
        return;
    }
    
    for(int x = last; x <= m; x++){
        A[i] = x;
        gen_seq(i+1, x);
        A[i] = 0;
    }
}


int main(){
   IOS

   cin>>n>>m>>q;

   a.resize(q), b.resize(q), c.resize(q), d.resize(q);

   A.resize(n);

   for(int i = 0; i < q; i++){
       cin>>a[i]>>b[i]>>c[i]>>d[i];
   }

   gen_seq(0,1);

   cout<<ans<<"\n";


}

ll pwr(ll a, ll b){
   a %= mod;	//Remove mod if not required
   ll res = 1;
   while(b > 0){
    if(b&1)
        res = res * a % mod;
        a = a * a % mod;
    b >>= 1;
    }

    return res;
}



Measured memory_bytes: 3660
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<iostream>
#include<fstream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<cstring>
#include<climits>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<deque>
#include<tuple>
#include<list>
#include<unordered_map>
#include<unordered_set>
#include<random>
#include<functional>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pp pair<pair<ll, ll>,pair<ll, ll>>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define vii vector<int>
#define vll vector<ll>
#define mat vector<vector<ll>>
#define lb lower_bound
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define LB(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define UB(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
#define ERASE(v) v.erase(unique(v.begin(),v.end()),v.end())
// #define int ll
using namespace std;
const ll INF = (1 << 30 ) - 1;
const ll LLINF = (1LL << 60LL);
const ll MOD = 1000000007;
const ll mod = 998244353;
const ll MAX = 1100000;
const double pi = acos(-1);
const double eps = 1e-10;
ll dx[4] ={1,0,-1,0} , dy[4] ={0,1,0,-1};


signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    ll n,a[100010],cnt[100010]={};
    cin>>n;
    rep(i,n){
        cin>>a[i];
        cnt[a[i]]++;
        cnt[a[i]-1]++;
        cnt[a[i]+1]++;
    }
    ll ans=0;
    rep2(i,1,100001){
        ans=max(ans,cnt[i]);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1792