akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>

#define INF 100000001

int DP[101][101];
int p[101];

int rec(int r, int c){
  int min=INF;
  int num=c-r;
  int i;

  for(i=0; i<num; i++)
    if(DP[r][r+i]+DP[r+i+1][c]+p[r-1]*p[r+i]*p[c]<min)
      min=DP[r][r+i]+DP[r+i+1][c]+p[r-1]*p[r+i]*p[c];

  return min;

}

int main(){
  int n,i,j,x;
  scanf("%d",&n);

  for(i=1; i<n+1; i++)
    DP[i][i]=0;

  scanf("%d%d",&p[0],&p[1]);
  for(i=2; i<n+1; i++)
    scanf("%d%d",&x,&p[i]);

  for(i=1; i<n; i++)
    DP[i][i+1]=p[i-1]*p[i]*p[i+1];

  for(i=0; i<=n-3; i++)
    for(j=i+3; j<=n; j++)
      DP[j-i-2][j]=rec(j-i-2,j);

  printf("%d\n",DP[1][n]);

  return 0;
}

  



Measured memory_bytes: 2112
# import sys
# input = sys.stdin.readline

def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))

n = int(input())
x = list(input())
xc = x.count("1")
xu = []
xd = []
if xc == 0:
    for i in range(n):
        print(1)
        exit()
t = 1
for i in range(n):
    mod = xc+1
    xu.append(t%mod)
    t *= 2
    t %= mod
t = 1
flag = False
for i in range(n):
    mod = xc-1
    if mod == 0:
        xd.append(0)
        flag = True
    else:
        xd.append(t%mod)
        t *= 2
        t %= mod
xu.reverse()
xd.reverse()
s_xu = 0
s_xd = 0
for i in range(n):
    if x[i] == "1":
        s_xu += xu[i]
        s_xd += xd[i]

# print(xu)
# print(xd)

for i in range(n):
    cnt = 1
    if x[i] == "0":
        tar = (s_xu+xu[i])%(xc+1)
        #print(tar)
        while tar != 0:
            b_tar = bin(tar)
            tar %= b_tar.count("1")
            cnt += 1
        print(cnt)
    else:
        if flag:
            print(0)
        else:
            tar = (s_xd-xd[i])%(xc-1)
            #print(tar)
            while tar != 0:
                b_tar = bin(tar)
                tar %= b_tar.count("1")
                cnt += 1
            print(cnt)







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

#define fastio 			ios::sync_with_stdio(0);	cin.tie(0); cout.tie(0);  cout<<fixed;  cout<<setprecision(12);
#define randomINT 		mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define	newl 			cout<<"\n"
#define DISP(as)		for(auto it : as) cout<<it<<" ";newl;
#define all(x)         	(x).begin(),(x).end()
#define mset(x,val)    	memset(x,val,sizeof(x))
#define newl           	cout<<"\n"
#define pb             	push_back
#define mp             	make_pair
#define f 				first
#define s 				second
#define dline          cerr<<"///REACHED///\n";
#define deb1(x)        cerr<<#x<<" = "<<x<<'\n';
#define deb2(x,y)      cerr<<'['<<#x<<','<<#y<<"] = "<<'['<<x<<','<<y<<']'<<'\n';
#define deb3(x,y,z)    cerr<<'['<<#x<<','<<#y<<','<<#z<<"] = "<<'['<<x<<','<<y<<','<<z<<']'<<'\n';

typedef long long 				ll;
typedef long double 			ld;
typedef vector<ll> 				vll;
typedef pair<ll , ll> 			pll;
typedef pair<ld, ld> 			pld;
typedef unordered_map<ll, ll> 	um;
typedef vector<pll> 			vpll;

const ll 	MAX5 	= 	1e+5 + 7;
const ll 	MAX7 	= 	1e+7 + 7;
const ll 	MAXN 	= 	MAX7;
const ll   	INF   	=  	0x7f7f7f7f7f7f7f7f;
const int  	INFi 	=  	0x7f7f7f7f;
const ll 	MOD		=  	1e+9 + 7;

int dx4[] = {0, 1, 0, -1}, dy4[] = {1, 0, -1, 0};

// <------------- Declare Variables Here ------------> //

ll T = 1;
ll n, m, x, y, q, k;
string s, t;

// <------------- Implement Functions Here ----------> //

bool comp(pll &a , pll &b) {
	if(a.s == b.s) return a.f > b.f;
	return a.s > b.s;
}

// <------------- Start of main() -------------------> //

void MAIN() {
	cin>>n>>m;
	vll a(n);
	vpll b(m);
	vll c(n);
	for(ll i=0;i<n;i++) {
		cin>>a[i];
	}
	sort(all(a));

	for(ll i=0;i<m;i++) {
		cin>>b[i].f>>b[i].s;	
	}
	sort(all(b),comp);

	ll j = 0;
	for(ll i=0;i<n;i++) {
		if(b[j].f) {
			c[i] = b[j].s;
			b[j].f --;
		}
		else {
			j++;
			if(j == m) break;
			c[i] = b[j].s;
			b[j].f --;
		}
	}

	ll sum = 0;

	for(ll i=0;i<n;i++) sum += max(a[i],c[i]);

	cout<<sum;
}

int main() {
	fastio; randomINT;
	//cin >> T;
	while (T--) {
		MAIN();
	}
	return 0;
}


Measured memory_bytes: 6340
n = int(input())
s = [[]for i in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        s[i].append(list(map(int, input().split())))
ans = 0
def bfs(honest):
    if len(honest) == n:
        global ans
        for i in range(n):
            if honest[i]==1:  
                for j in s[i]:
                    target, istrue = j
                    if (honest[target-1] != istrue):
                        return
        ans = max(ans, honest.count(1))
    else:
        bfs(honest + [0])
        bfs(honest + [1])
bfs([])
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001
#define mod 1000000007
#define pi 3.141592653589793
#define all(v) v.begin(),v.end()
typedef vector<int> vi;
typedef vector<ll> vl;
ll gcd(ll a,ll b){
    if(b>a) swap(a,b);
    if(b==0) return a;
    return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    ll g=gcd(a,b);
    return a/g*b;
}
ll rep_jijo(ll n,ll x){
    if(x==0) return 1;
    if(x%2==0){
        ll t=rep_jijo(n,x/2);
        return t*t%mod;
    }
    return n*rep_jijo(n,x-1)%mod;
}
ll com(ll n,ll r){
    ll x=1,y=1;
    ll tmp=n;
    while(tmp>=n-r+1){
        x=x*tmp%mod;
        tmp--;
    }
    while(r>0){
        y=y*r%mod;
        r--;
    }
    return x*rep_jijo(y,mod-2)%mod;
}

int main(){
    string s,t;
    cin >> s >> t;
    int len=s.size();
    string v,w;
    char now='a';
    vector<pair<bool,char>>dones(26);
    vector<pair<bool,char>>donet(26);
    rep(i,len){
        if(dones[s[i]-'a'].first) {
            v+=dones[s[i]-'a'].second;
        }
        else{
            v+=now;
            dones[s[i]-'a'].first=true;
            dones[s[i]-'a'].second=now;
            now++;
        }
    }
    now='a';
    rep(i,len){
        if(donet[t[i]-'a'].first) {
            w+=donet[t[i]-'a'].second;
        }
        else{
            w+=now;
            donet[t[i]-'a'].first=true;
            donet[t[i]-'a'].second=now;
            now++;
        }
    }
    if(v==w) cout << "Yes" <<endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 1168
parse :: String -> [(Double , Double)]
parse xs = case read ("(" ++ xs ++ ")") of
    (xa,ya,xb,yb,xc,yc,xd,yd) -> [(xa,ya),(xb,yb),(xc,yc),(xd,yd)]

-- ???ABC???????§?????????????
isObtuseAngle :: (Double , Double) -> (Double , Double) -> Bool
isObtuseAngle ab bc = fst ba * snd bc - snd ba * fst bc < 0
    where
        ba = (negate $ fst ab , negate $ snd ab)

solve :: [(Double , Double)] -> IO ()
solve [a,b,c,d] = putStrLn $ maybe "NO" (const "YES") $
    foldr1 (\ (Just x) y -> case y of Just z -> if x == z then Just z else Nothing ; Nothing -> Nothing) $ map Just [isObtuseAngle da ab , isObtuseAngle ab bc , isObtuseAngle bc cd , isObtuseAngle cd da]
    where
        ab = (fst b - fst a , snd b - snd a)
        bc = (fst c - fst b , snd c - snd b)
        cd = (fst d - fst c , snd d - snd c)
        da = (fst a - fst d , snd a - snd d)
solve _ = undefined
    
main :: IO ()
main = getContents
    >>= mapM_ solve . map parse . lines

Measured memory_bytes: 4232
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    if(a+b > c+d)cout << "Left"<<endl;
    else if(a+b < c+d)cout << "Right"<<endl;
    else cout << "Balanced"<<endl;
}


Measured memory_bytes: 256
/*B - Common Raccoon vs mOnster*/
#include <bits/stdc++.h>

using namespace std;

int main(){

int health;
int tam;
int suma = 0;
int aux;

cin >> health >> tam;

for(int i = 0; i < tam; i++){
   cin >> aux;
   suma += aux;
}

if(suma >= health)
  cout << "Yes";
else
  cout << "No";

return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using ll = long long;
typedef pair<int, int> P;
ll Mod = 1000000007;
int main() {
  int N;
  ll K;
  cin >> N >> K;
  int P[N];
  ll C[N];
  int Group[N];
  ll Cy[N];
  vector<int> S[N];
  for (int i = 0; i < N; i++) {
    Group[i] = -1;
    cin >> P[i];
    P[i]--;
    Cy[i] = 0;
  }
  for (int i = 0; i < N; i++) {
    cin >> C[i];
  }
  int cnt = 0;
  for (int i = 0; i < N; i++) {
    if (Group[i] == -1) {
      bool Q[N];
      for (int i = 0; i < N; i++) Q[i] = false;
      int now = i;
      while (0 == 0) {
        int pr = now;
        now = P[pr];
        if (Q[pr]) {
          break;
        } else {
          Group[pr] = cnt;
          Q[pr] = true;
          S[cnt].push_back(pr);
        }
      }
      cnt++;
    }
  }
  ll ans = -Mod * 100LL;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < (int)S[i].size(); j++) {
      Cy[i] += C[S[i][j]];
    }
  }
  for (int i = 0; i < N; i++) {
    ll res = 0;
    ll time = 0;
    if (Cy[Group[i]] > 0) {
      ll now = 0;
      for (int j = 0; j < (ll)S[Group[i]].size(); j++) {
        if (S[Group[i]][j] == i) {
          now = j;
          break;
        }
      }
      res = Cy[Group[i]] * ((K-1) / (ll)S[Group[i]].size());
      time = K % (ll)S[Group[i]].size();
      if (time == 0) {
        time = (ll)S[Group[i]].size();
      }
      ll mx = 0;
      ll sum = 0;
      for (int j = 0; j < time; j++) {
        sum += C[S[Group[i]][(j+now)%(int)S[Group[i]].size()]];
        mx = max(mx,sum);
      }
      res += mx;
      ans = max(ans,res);
    } else {
      //
      ll now = 0;
      for (int j = 0; j < (ll)S[Group[i]].size(); j++) {
        if (S[Group[i]][j] == i) {
          now = j;
          break;
        }
      }
      res = 0;
      time = K;
      if (K > (ll)S[Group[i]].size()) {
        time = (ll)S[Group[i]].size();
      }
      ll mx = -100LL * Mod;
      ll sum = 0;
      for (int j = 0; j < time; j++) {
        sum += C[S[Group[i]][(j+now)%(int)S[Group[i]].size()]];
        mx = max(mx,sum);
      }
      res += mx;
      ans = max(ans,res);
      //
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3864
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <set>
#include <vector>
#define ii pair<int,int>
#define X first
#define Y second
using namespace std;
const int maxn = 100000;
int n;
string a;
vector<int> V;
vector<ii> E;
int main()
{
	ios_base::sync_with_stdio(0);
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	cin >> a;
	n=a.size();
	a="0"+a;
	
	for (int i=1; i<=n; i++)
	if (a[i]!=a[n-i]) 
	{
		//cout << i << ' ' << n-i << '\n';
		cout << -1;
		return 0;
	}
	
	if (a[1]=='0')
	{
		cout << -1;
		return 0;
	}
	
	for (int i=n; i>=1; i--)
		if (a[i]=='1')
			V.push_back(i);
	
	int root=1;
	int cnt=1;
	for (auto it=V.begin(); it!=V.end(); it++)
	{
		int p=(*it);
		for (int i=1; i<=n-1-p; i++)
		{
			cnt++;
			E.push_back(ii(root,cnt));
		}
		cnt++;
		E.push_back(ii(root,cnt));
		root=cnt;
		n-=(n-p);
		//cout << n << '\n';
	}
	
	for (auto it=E.begin(); it!=E.end(); it++)
		cout << (*it).X << ' ' << (*it).Y << '\n';
		
	
	return 0;
}



Measured memory_bytes: 2788
from numba import jit
import numpy as np


n, k = map(int, input().split())
A = np.array([*map(int, input().split())],dtype=np.int64)

# for _ in range(min(k,int(math.log(n,2)))):

@jit
def loop(A):
    for _ in range(k):
        b=np.zeros(n,dtype=np.int64)
        
        for i,v in enumerate(A):
            # if i>v:
            b[max(0,i-v)]+=1
                # b[i-v]+=1
            # else:
                # b[0]+=1
            # j=i-~v
            if i+v+1<n:
                b[i+v+1]-=1
            # if j<n:
            #     b[j]-=1
        
        # update ans
        # cnt=0
        # for i in range(1,n):
        #     b[i]+=b[i-1]
        A=np.cumsum(b)
        
        if min(A)==n:
            break
    return A
print(" ".join(map(str,loop(A))))

Measured memory_bytes: 131736
#include <bits/stdc++.h>
#include <iostream>
#include <utility> // pair
#include <string>
#include <vector>
#define MAX_N 100001
#define rep(i, n) for(ll i=0; i<n; i++)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll n;
string s;
signed main(){
    cin >> s;
    int n = s.size();
    int ret = n;
    rep(i, n-1){
        if(s[i+1] != s[i]){
            int k = max(i+1, n-i-1);
            ret = min(ret, k);
        }
    }
    cout << ret << endl;
    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;


int n, m;
pair<int, int> doll[200];
int dp[200] = { 1 };


int solve(){
	for (int i = 0; i < n + m; i++){
		vector<int> mem = { -1 };
		for (int j = 0; j < i; j++){
			if (doll[j].first < doll[i].first && doll[j].second < doll[i].second){
				mem.push_back(dp[j]);
			}
		}
		if (mem.back() != -1)
			dp[i] = *max_element(mem.begin(), mem.end()) + 1;
	}
	return *max_element(dp, dp + n + m);
}


void clear(){
	for (int i = 0; i < 200; i++){
		doll[i] = { 0, 0 };
		dp[i] = 0;
	}
	dp[0] = 1;
}


int main(){
	while (cin >> n, n){
		for (int i = 0; i < n; i++) cin >> doll[i].first >> doll[i].second;
		cin >> m;
		for (int i = n; i < n + m; i++) cin >> doll[i].first >> doll[i].second;

		sort(doll, doll + n + m);

		cout << solve() << endl;

		clear();
	}
	
	return 0;
}

Measured memory_bytes: 3060
#include "bits/stdc++.h"
using namespace std;
 
int main(void) {
	int a, b;
	cin >> a >> b;

	int digit = 1;
	int B = b;
	while(B>9) {
		B /= 10;
		digit++;
	}

	int c = b + a*pow(10,digit);

	int sq = sqrt(c);	

	if(sq*sq == c) cout << "Yes" << endl;
	else cout << "No" << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<queue>
using namespace std;
const int mod = 1000000007;
#define ll long long

int sum[2010][2010] = { 0 };
int L[2010];
int main()
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> L[i];
	}
	sort(L, L + N, greater<int>());
	int ans = 0;
	for (int i = 0; i < N - 2; i++) {
		for (int j = i + 1; j < N - 1; j++) {
			for (int k = N - 1; k > j; k--) {
				if (L[i] - L[j] < L[k]) {
					//cout << j << " " << k << endl;
					ans += k - j;
					break;
				}
			}
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#define F 44
 
int fibonacci(int n){
  int i;
  int a = 1, b = 1, temp = 1;
 
  for(i = 2; i <= n; i++){
    temp = a + b;
    a = b;
    b = temp;
  }
  return temp;
}
 
int main(){
  int i, n;
 
  scanf("%d", &n);
  printf("%d\n", fibonacci(n));
 
  return 0;
}

Measured memory_bytes: 596
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 整数の入力
        int k = sc.nextInt();
        // スペース区切りの整数の入力
        int x = sc.nextInt();
        // 結果の出力
        int min = x - (k - 1);
        int max = x + (k - 1);

        for(int i = min; i <= max; i++){
            System.out.print(i);
            if(i != max) {
                System.out.print(" ");
            }
        }
    }
}


Measured memory_bytes: 21844
n = int(input())
graph = {}
for _ in range(n):
  i = list(map(int,input().split()))
  graph[i[0]] = i[2:]

first = {i:0 for i in range(1,n+1)}
last = {i:0 for i in range(1,n+1)}
seen = set()
time = 1

def dfs(v):
  global time
  seen.add(v)
  first[v] = time
  time += 1
  for nxt in graph[v]:
    if nxt in seen:
      continue
    dfs(nxt)
  last[v] = time
  time += 1

for i in range(1,n+1):
  if i not in seen:
    dfs(i)
  
for i in range(1,n+1):
  print(i, first[i], last[i])




Measured memory_bytes: 5720
sum[3<<17],cnt[3<<17];
N,i,acc,t,k,x;
char f[10];
main()
{
	for(;;)
	{
		k=getchar_unlocked();
		if(k<'0'||k>'9')break;
		N=N*10+k-'0';
	}
	for(i=0;i<N;i++)
	{
		x=0;
		for(;;)
		{
			k=getchar_unlocked();
			if(k<'0'||k>'9')break;
			x=x*10+k-'0';
		}
		++sum[cnt[x]++];
	}
	i=0;
	for(t=N;t;t--)
	{
		while(acc>=i*t)acc+=sum[i++];
		cnt[t]=i-1;
	}
	for(i=1;i<=N;i++)
	{
		if(!cnt[i])
		{
			putchar_unlocked('0');
		}
		else
		{
			if(cnt[i-1]!=cnt[i])
			{
				k=0;
				t=cnt[i];
				while(t)
				{
					f[k++]=t%10;
					t/=10;
				}
				acc=k;
			}
			else k=acc;
			while(k)putchar_unlocked(f[--k]+'0');
		}
		putchar_unlocked('\n');
	}
}

Measured memory_bytes: 3072
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
class Program
{
    static void Main(string[] args)
    {
            // 入力
            List<char> sS = Console.ReadLine().ToList();

            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            sw.Start();

            // 解析
            int iOut = 700 + 100 * sS.Count(x => x == 'o');

            // 出力
            Console.WriteLine("{0}", iOut.ToString().Trim());

            sw.Stop();
#if DEBUG
            Console.WriteLine();
            Console.WriteLine("{0}", sw.Elapsed.ToString());
            Console.WriteLine("続行するには何かキーを押してください．．．");
            Console.ReadKey();
#endif
    }

}


Measured memory_bytes: 11348
#include <iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
    int N,M,C,a,b;
    cin>>N>>M>>C;
    vector<int> vec0(N*M);
    vector<int> vec1(M);
  
    a=0;
    for(int i=0;i<M;i++){
        cin>>vec1.at(i);
    }
    for(int j=0;j<N*M;j++){
        cin>>vec0.at(j);
    }
    for(int l=0;l<N;l++){ 
       b=0;
        for(int m=0;m<M;m++){   
      
           b=b+(vec0.at(m+l*M)*vec1.at(m));
        }
     
        b=b+C;
        if(b>0){
            a++;
        } 
    }
cout<<a<<endl;
}

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

namespace Atcoder
{
    class Atcoderrrrrr
    {
        static void Main(string[] args)
        {
            string[] s = Console.ReadLine().Split(' ');
            int N = int.Parse(s[0]);
            int A = int.Parse(s[1]);
            int B = int.Parse(s[2]);
            int max = 0;int min = 0;
            if (A > B)
            {
                max = B;
            }
            else
            {
                max = A;
            }
            if (N - (A + B) > 0)
            {
                min = 0;
            }
            else
            {
                min =Math.Abs(N - (A + B));
            }
            Console.WriteLine(max+" "+min);
        }
    }
}


Measured memory_bytes: 11220
using System;

namespace abc117B
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int[] L = new int[N];
            string[] str = Console.ReadLine().Split();
            for (int i = 0; i < N; i++)
            {
                L[i] = int.Parse(str[i]);
            }
            int a = L[0];
            for (int i = 0; i < N; i++)
            {
                if (a >= L[i])
                {
                    a = a;
                }
                else
                {
                    a = L[i];
                }
            }
            int b = 0;
            for (int i = 0; i < N; i++)
            {
                b = b + L[i];
            }
            if (a < (b - a))
                Console.WriteLine("Yes");
            else
                Console.WriteLine("No");
        }
    }
}


Measured memory_bytes: 13140
//#include <bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<string>
#include<vector>
#include<iostream>
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
const ll INF=1000000000000005;
const ll maxn=1e6+5;
const int mod=998244353;
ll n,m,p;
ll x,y;
ll in[maxn/100];
int work()
{
    for(int i=1;i<=n;i++) if(in[i]>4||in[i]<=1) return 0;
    int a=0,b=0,c=0;//2 3 4
    for(int i=1;i<=n;i++)
    {
        if(in[i]==4) c++;
        else if(in[i]==3) b++;
        else a++;
    }
    if(a!=4) return 0;
    for(int i=1;i*i<=c;i++)
    {
        if(c%i==0)
        {
            int temp=c/i;
            if((temp+i)*2==b) return 1;
        }
    }
    return 0;
}
ll num[maxn];
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&num[i]);
    ll minl=INF;
    ll res=0;
    for(int i=1;i<=n;i++)
    {
        minl=min(minl,num[i]);
        if(minl==num[i]) res++;
    }
    printf("%lld\n",res);
    return 0;
}
/***
***/


Measured memory_bytes: 1792
import Data.Char  -- digitToInt

bottommost xs = head $ iterate nextline xs !! (length xs - 1)

nextline (x : y : xs) = ((x + y) `mod` 10) : nextline (y : xs)
nextline _ = []

main = do
  s <- getContents
  putStr . unlines . map (show . bottommost . map digitToInt) . lines $ s

Measured memory_bytes: 3696
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    n, m = map(int, input().split())
    a_list = map(int, input().split())

    r = n - sum(a_list)
    print(r if r >= 0 else -1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9660
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
#define double long double
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef vector<pii> VP;
typedef vector<string> VS;
typedef priority_queue<int> PQ;
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
#define eps 1e-12 
//priority_queue<int,vector<int>, greater<int> > q2;

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

	int N;
	cin >> N;
	int ans = 0;
	REP(i, N)ans += (i + 1)*(N - i);
	REP(i, N - 1) {
		int a, b; cin >> a >> b;
		a--; b--;
		if (a > b)swap(a, b);
		ans -= (a + 1)*(N - b);
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 3652
S = ["3", "5", "7"]

def ans(n, s)
  ret = (s.include?("3") && s.include?("5") && s.include?("7")) ? 1 : 0

  S.each do |e|
    nx = e + s
    if nx.to_i <= n
      ret += ans(n, nx)
    end
  end

  ret
end

n = gets.chomp.to_i

puts ans(n, "")


Measured memory_bytes: 1788
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<algorithm>
#include<bitset>
#define rep(i,n) for(int i=0;i<(n);++i)
using ll = long long;
#define _GLIBCXX_DEBUG

using namespace std;

int main() {
	int x;
	cin >> x;
	vector<int> v1;
	v1.push_back(2);
	if (x == 2) {
		cout << x << endl; return 0;
	}
	for (int i = 3; i < x; i++) {
		bool ans = false;
		for (int j = 0; j < v1.size(); j++) {
			if (i % v1[j] == 0) {
				break;
			}
			if (j == v1.size() - 1) {
				v1.push_back(i);
				break;
			}
		}
	}
	for (int i = x; i <= 100003; i++) {
		for (int j = 0; j < v1.size(); j++) {
			if (i % v1[j] == 0) {
				break;
			}
			if (j == v1.size() - 1) {
				cout << i << endl;
				return 0;
			}
		}
	}
	
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i < (n); i++)
#define lower(s) transform(s.begin(), s.end(), s.begin(), ::tolower)
using namespace std;
using ll = long long;
int INF = 1001001001;

int n, m, q;
int ans = 0;
vector<int> a, b, c, d;

void dfs(vector<int> A) {
  if(A.size() == n+1) {
    int sum = 0;
    rep(i, q) {
      if(A[b[i]]-A[a[i]] == c[i]) {
        sum += d[i];
      }
    }
    ans = max(sum, ans);
    return;
  }
  A.push_back(A.back());
  while(A.back() <= m) {
    dfs(A);
    A.back()++;
  }
}

int main() {
  cin >> n >> m >> q;
  a = b = c = d = vector<int>(q);
  rep(i, q) {
    cin >> a[i] >> b[i] >> c[i] >> d[i];
  }  
  dfs(vector<int>(1,1));
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3612
use proconio::*;

#[fastout]
fn main() {
    input! {
        a: i32,
        b: i32,
        h: i32,
        m: i32
    }
    let ratio = (h * 60 + m) as f64 / 720.0;
    let tyou = (2.0 * std::f64::consts::PI) * (m as f64 / 60.0);
    let tan = (2.0 * std::f64::consts::PI) * ratio;
    let (x, y) = (a as f64 * tan.cos(), a as f64 * tan.sin());
    let (xx, yy) = (b as f64 * tyou.cos(), b as f64 * tyou.sin());
    let ans = ((x - xx).powf(2.0) + (y - yy).powf(2.0)).sqrt();
    println!("{}", ans);
}


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

using namespace std;
typedef long long ll;

bool can_work(vector<ll> &not_work, ll day_back){
  if (not_work.empty()){
    return false;
  }
  ll p = -day_back;
  auto lb = lower_bound(not_work.begin(), not_work.end(), p);
  if (lb == not_work.end()){
    return false;
  }
  else{
    not_work.erase(lb);
    return true;
  }
}

int main(){
  ll N, M, A, B;
  cin >> N >> M;
  vector<pair<ll, ll>> jobs;
  for (ll i=0; i<N; i++){
    cin >> A >> B;
    jobs.emplace_back(pair<ll, ll>(B, A));
  }
  sort(jobs.begin(), jobs.end());
  ll rem = M;
  ll buf = 0;
  ll ans = 0;
  vector<ll> not_work;
  for (int i=0; i<M; i++) not_work.push_back(-(M - i - 1));
  while (rem > 0 && !jobs.empty()){
    pair<ll, ll> job = jobs.back();
    if (can_work(not_work, M - job.second)){
      ans += job.first;
      rem--;
    }
    jobs.pop_back();
  }

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

Measured memory_bytes: 3568
#include <bits/stdc++.h>
using namespace std;
typedef complex<double> xy_t;

xy_t P[100];

double cross_product(xy_t a, xy_t b){ //外積
    return (conj(a)*b).imag();
}
int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){ //入力
        double x, y;
        cin >> x >> y;
        P[i] = xy_t(x, y);
    }
    double ans = 0;
    for(int i = 0; i+2 < n; i++){
        xy_t a = P[0], b = P[i+1], c = P[i+2]; //各点をaだけ平行移動させる
        ans += cross_product(b-a, c-a)/2; //符号付き面積を足すと凸ではない図形でもうまく計算できる。」
    }
    cout << fixed <<  setprecision(1) << ans << endl;
}


Measured memory_bytes: 3276
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

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

    vector<int> b(a);
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()));

    vector<int> c(b.size(), 0);
    rep(i, n)
    {
        c[lower_bound(b.begin(), b.end(), a[i]) - b.begin()]++;
    }

    int result = 0;
    rep(i, c.size())
    {
        if (c[i] % 2 == 1) {
            result++;
        }
    }
    cout << result << endl;

    return 0;
}

Measured memory_bytes: 1408
def gcd(a,b):
  while(b):a,b=b,a%b
  return a

def lcm(a,b):
  return(a*b//gcd(a,b))


n=int(input())
a=[]
for i in range(n):a.append(int(input()))
a=set(a)
x=1
for i in a:
  x=lcm(x,i)
print(x)


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

int main(){
    int n,k,m;
    cin >> n >> k;
    if(1<=n && n<=50 && 1<=k && k<=n){
        char S[n];
        cin >> S;
        for(int i=0; i<=n-1; i++){
            if(S[i]!='A' && S[i]!='B' && S[i]!='C'){
                m++;
            }else if(i==k-1){
                switch(S[i]){
                    case 'A':
                        S[i] = 'a';
                    break;
                    case 'B':
                        S[i] = 'b';
                    break;
                    case 'C':
                        S[i] = 'c';
                    break;
                }
            }
        }
        if(m==0){
            cout << S << "\n";
        }
    }
return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
long kobai(long x,long y);
int main(){
    long A,B,C,D;
    cin >> A >> B >> C >> D;
    long num1 = B/C;
    long num2 = B/D;
    long num3;
    if(C!=D){
        num3 = B/(kobai(C,D));
    }
    else{
        num3 = B/C;
    }
    // cout << "num1 = " << num1 << " num2 = " << num2 << " num3 = " << num3 << endl;
    long bcount = B - (num1 + num2 - num3);
    num1 = (A-1)/C;
    num2 = (A-1)/D;
    if(C!=D){
        num3 = (A-1)/(kobai(C,D));
    }
    else{
        num3 = (A-1)/C;
    }
    // cout << "num1 = " << num1 << " num2 = " << num2 << " num3 = " << num3 << endl;
    long acount = A-1 - (num1 + num2 - num3);
    cout << bcount - acount << endl;
}

long kobai(long x,long y){
    long prex,prey;
    prex = x;
    prey = y;
    if(x<y){
        long tmp = x;
        x = y;
        y = tmp;
    }
    long r = x%y;
    while(r!=0){
        x = y;
        y = r;
        r = x%y;
    }
    long ret = (prex*prey)/y;
    return ret;
}

Measured memory_bytes: 256
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        s: chars,
        t: chars,
        a: usize,
        b: usize,
        u: chars,
    }

    match u == s {
        true => println!("{} {}", a-1, b),
        _ => println!("{} {}", a, b-1),
    }
}



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

Measured memory_bytes: 3092
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
int main()
{
    long long sum[60000],a,b;
    sum[0]=100;
    scanf("%lld",&a);
    for(b=1;1;b++){
    sum[b]=sum[b-1]/100+sum[b-1];
    if(sum[b]>=a) break;
    }
    printf("%lld",b);
    return 0;
}

Measured memory_bytes: 3772
C = [[int(c) for c in input().split()] for i in range(3)]

for i in range(3):
    p = min(C[i])
    for j in range(3):
        C[i][j] -= p

ans = True
for i in range(3):
    if(C[i][0]==C[i][1]==C[i][2]):
        continue
    else:
        ans = False
if(not ans):
    ans = True
    for i in range(3):
        if(C[0][i]==C[1][i]==C[2][i]):
            continue
        else:
            ans = False
print("Yes") if ans else print("No")

Measured memory_bytes: 3064
<?php
list($a, $b, $k) = ints();

$e = min($a, $k);
$a-=$e;
$k-=$e;
$f = min($b, $k);
$b-=$f;
echo "$a $b\n";


function str(){
  return trim(fgets(STDIN));
}
function ints(){
  return array_map("intval", explode(" ", trim(fgets(STDIN))));
}
function int(){
  return intval(trim(fgets(STDIN)));
}
function o(...$val){
    if(count($val)==1)$val = array_shift($val);
    $trace = debug_backtrace();
    echo $trace[0]['line'].")";
    if(is_array($val)){
        if(count($val) == 0){
            echo "empty array";
        }elseif(!is_array(current($val))){
            echo "array:";
            echo implode(" ", $val)."\n";
        }else{
            echo "array:array\n";
            foreach($val as $row){
                echo implode(" ", $row)."\n";
            }
        }
    }else{
        echo $val."\n";
    }
}

Measured memory_bytes: 4604
#include<bits/stdc++.h>
using namespace std;
int main()
{
string text,str;
int k,a;

  cin >> k >> text;
  
  a=text.size();
  
  if(a<=k)
  {
  cout << text << endl;
  }
  
  else
  {str=text.substr(0,k);
  cout << str+"..." << endl;
  }
  
return 0;
}

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

using namespace std;
struct I{
    I(){
        ios::sync_with_stdio(false);cin.tie(0);
        //cout<<fixed<<setprecision(10);
    }
}init;

typedef long long LL;
const LL MOD=1e9+7;

#define SPACE " "
template<typename T>
ostream& operator<<(ostream &os,vector<T> v){
    for(int i =0,sz=v.size();i<sz;i++)os<<(!i)+SPACE<<v[i];
    return os;
}
template<typename T>
istream& operator>>(istream &is,vector<T>& v){
    for(int i =0,sz=v.size();i<sz;i++)is>>v[i];
    return is;
}

typedef vector<int> V;
typedef vector<V> VV;
typedef VV Graph;
int dfs(int v,Graph &tree,int &res,int K){
    int D=0;
    for(auto& u:tree[v]){
        int d=dfs(u,tree,res,K);
        if(d==K&&v!=0)res++;
        else D=max(D,d);
    }
    return D+1;
}
int main(){
    int N,K,res=0;
    cin>>N>>K;
    V a(N);
    cin>>a;
    for(auto &it:a)it--;
    if(a[0]!=0)a[0]=0,res++;
    Graph tree(N);
    for(int i=1;i<N;i++)tree[a[i]].push_back(i);
    dfs(0,tree,res,K);
    cout<<res<<endl;
    return 0;
}


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

using namespace std;

class B {
	vector<string> S;
public:
	void solve()
	{
		S.resize(3);
		cin >> S[0] >> S[1] >> S[2];

		for (int i{ 0 }; i < 3; i++)
			reverse(S[i].begin(), S[i].end());

		int player{ 0 }, nextPlayer;

		while (true)
		{
			if (S[player].empty()) break;
			else
			{
				nextPlayer = S[player].back() - 'a';
				S[player].pop_back();
				player = nextPlayer;
			}
		}

		cout << (char)(player + 'A') << endl;
	}
};


int main()
{
	B solution;
	solution.solve();

	return 0;
}

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

using ll = long long;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define ALL(c) (c).begin(), (c).end()
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
const int MOD = 1000000007;

class Combination {     
    vector<ll> factorial;
    vector<ll> fact_inverse;
    vector<ll> inverse;
    int mod;                    
                 
    void init(int size) {
        factorial[0] = 1;
        factorial[1] = 1;         
        fact_inverse[0] = 1;
        fact_inverse[1] = 1;         
        inverse[1] = 1;         
         
        for (int i = 2; i < size; i++) {
            factorial[i] = factorial[i - 1] * i % mod;
            inverse[i] = mod - inverse[mod % i] * (mod / i) % mod;
            fact_inverse[i] = fact_inverse[i - 1] * inverse[i] % mod;
        }            
    }                                                
 
    public:
        Combination(int size, int m) {
           factorial = vector<ll>(size);
           fact_inverse = vector<ll>(size);
           inverse = vector<ll>(size);
           mod = m;                    
           init(size);                        
        }      
                                                
        ll calc(int n, int k) {
            if (n < k) {                        
                return 0;
            }    
            if (n < 0 || k < 0) {
                return 0;
            }
            return factorial[n] * (fact_inverse[k] * fact_inverse[n - k] % mod) % mod;
        } 
};             

int main() {
    int n;
    cin >> n;
 
    vector<int> a(n + 1);
    set<int> s;
    int l = -1;
    int r = -1;
    REP(i, n + 1) {
        cin >> a[i];
        if (l == r) {
            if (s.count(a[i]) == 1) {
                l = (int)distance(a.begin(), find(ALL(a), a[i]));
                r = i;
            } else {
                s.insert(a[i]);
            }
        }
    }

    Combination cmb = Combination(200000, MOD);
    
    REP1(i, n + 1) {
        ll ans = cmb.calc(n + 1, i) - cmb.calc(l + n - r, i - 1);
        while (ans < 0) ans += MOD;
        cout << ans << endl;
    }
}


Measured memory_bytes: 11008
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
#define FOR(i, a, b) for(LL i=(LL)(a);i<(LL)(b);i++)
#define REP(i,x) for(LL i=0;i<(LL)(x);i++)

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    // cout << fixed << setprecision(10);
    LL n;
    cin >> n;
    unordered_map<string, int> m_ret;
    REP(i, n)
    {
        string temp;
        cin >> temp;
        m_ret[temp] = 1;
    }

    cout << m_ret.size() << endl;
    return 0;
}

Measured memory_bytes: 17712
n = input()
op_cnt = len(n) - 1
for i in range(2 ** op_cnt):
    op = ["-"] * op_cnt
    for j in range(op_cnt):
        if ((i >> j) & 1) :
            op[op_cnt - j - 1] = "+"
    # print(op)
    ans = n[0]
    for l in range(op_cnt):
        ans += op[l] + n[l + 1]
    if eval(ans) == 7:
        print(ans + "=7")
        exit(0)


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

int n, k, mx, g;

int main(){
	scanf("%d%d", &n, &k);
	for(int x; n--; ){
		scanf("%d", &x);
		mx = max(mx, x);
		g = __gcd(g, x);
	}
	if(k > mx || k % g) printf("IM");
	puts("POSSIBLE");
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    string s,t;
    cin>>s>>t;
    int n=s.size();
    int m=t.size();
    int arr[n+1][m+1];
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            if(i==0||j==0)
            {
                arr[i][j]=0;
            }
            else
            {
                if(s[i-1]==t[j-1])
                {
                    arr[i][j]=arr[i-1][j-1]+1;
                }
                else
                if(arr[i-1][j]>arr[i][j-1])
                {
                    arr[i][j]=arr[i-1][j];
                }
                else
                {
                    arr[i][j]=arr[i][j-1];
                }
            }
        }
    }
    string ans;
    int l=n;
    int r=m;
    while(l>0 and r>0)
    {
       
        
    
        if(arr[l][r]==arr[l-1][r])
        {
            l--;
        }
        else
        if(arr[l][r]==arr[l][r-1])
        {
            r--;
        }
        else
        if(arr[l][r]==arr[l-1][r-1]+1)
        {   ans+=s[l-1];
            l--;
            r--;
        }
    }
   
    reverse(ans.begin(),ans.end());
    cout<<ans<<"\n";
}

Measured memory_bytes: 35456
def get_i() #空白区切の入力を数値(整数)の配列で返す
  return gets.chomp.split(" ").map(&:to_i)
end
def get_f() #空白区切の入力を数値(実数)の配列で返す
  return gets.chomp.split(" ").map(&:to_f)
end
def get() #空白区切の入力を文字列の配列で返す
  return gets.chomp.split(" ")
end
def get_nsp() #入力されたものを一文字ずつに区切った文字列の配列で返す
  return gets.chomp.split("")
end
def yn_judge(bool,y="Yes",n="No") #boolに真偽を投げることで、trueならy、falseならnの値を出力する
  return bool ? y : n 
end
def array(size1,init=nil,size2=-1) #size2に二次元配列時の最初の要素数、size1に次の配列の大きさ、initに初期値を投げることでその配列を返す
  if size2==-1
    return Array.new(size1){init}
  else
    return Array.new(size2){Array.new(size1){init}}
  end
end

N,x=get_i
A=get_i.sort
ans=0
A.each do|a|
    if x>=a
        x-=a
        ans+=1
    else
        x=0
        break
    end
end
if x>0
    ans-=1
end
puts ans

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

int main(){
    int n,m;
    cin >> n >>m;
    int ans = (2<<(m-1))*(100*(n-m) + 1900*m);
    //cout <<fixed<<setprecision(16)<< << endl;
    cout << ans << endl;
    //if(flag==1)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define lli long long int
#define timesave ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;


void solve()
{
    int n;
    cin >> n;

    int arr[n+5];
    map<int,int> mp;

    for(int i = 1; i <= n; i++) {cin >> arr[i]; mp[arr[i]]++;}
    
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        int val = arr[i], flag = 0;
        for(int j = 1; j*j <= val; j++){
            if((val%j) == 0){
                int d = val/j;
                if(j == val && mp[j] > 1) flag = 1;
                if(j != val && mp[j]) flag = 1;
                if(d != val && mp[d]) flag = 1;
                if(d == val && mp[d] > 1) flag = 1;
            }
        }
        if(!flag) cnt++;
    }
    
    cout << cnt << "\n";
}


int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    timesave; 
    
    int tc = 1;
    //cin >> tc;
    while(tc--) solve();

    return 0;
}

Measured memory_bytes: 33308
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>

using namespace std;

#define int long long

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

   	int n;
   	cin >> n;
   	vector<int> p(n);
   	for (auto &t : p) {
   		cin >> t;
   		t--;
   	}
   	vector<int> wr(n, -1);
   	for (int i = 0; i < n; i++) {
   		wr[p[i]] = i;
   	}
   	set<int> hv;
   	hv.insert(-1);
   	hv.insert(n);
   	//b..b...x....b...b
   	//b..b...x......b
   	//b....x...b...b
   	int ans = 0;
   	for (int i = n - 1; i >= 0; i--) {
   		auto it = hv.lower_bound(wr[i]);
   		if (*it != n) {
   			int f = wr[i] - *prev(it);
   			int s = *next(it) - *it;
   			ans += (i + 1) * f * s;
   		}
   		if (*prev(it) != -1) {
   			auto pr = prev(it);
   			int f = *pr - *prev(pr);
   			int s = *it - wr[i];
   			ans += (i + 1) * f * s;
   		}
   		hv.insert(wr[i]);
   	}
   	cout << ans << endl;
}

Measured memory_bytes: 6528
#!/usr/bin/env python
def main():
    N, M = map(int, input().split())
    ks = [list(map(int, input().split())) for _ in range(M)]
    p = list(map(int, input().split()))
    
    ans = 0

    for i in range(1<<N):
        isConflict = False

        for j in range(M):
            tmp = 0
            for k in ks[j][1:]:
                k -= 1
                tmp += (i>>k)
            if tmp%2 != p[j]:
                break
        else:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()



Measured memory_bytes: 39408
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long int;
// #define int ll
using PII = pair<int, int>;
 
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
 
template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const int MOD = 998244353;

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

  int n, k, q;
  cin >> n >> k >> q;
  vector<int> v(n);
  cin >> v;

  vector<PII> vp(n);
  REP(i, n) vp[i] = {v[i], i};
  sort(ALL(vp));

  vector<bool> able(n, true);
  int ans = INF;
  REP(i, n) {
    int cnt = 0;
    vector<vector<int>> vec(1);
    REP(j, n) {
      if(!able[j]) {
        vec.push_back({});
        cnt++;
      } else {
        vec[cnt].push_back(v[j]);
      }
    }
    // cout << able << endl;
    // cout << vec << endl;

    vector<int> v;
    for(auto i: vec) {
      if(i.size() == 0) continue;
      sort(ALL(i));
      REP(j, (int)i.size()-k+1) {
        v.push_back(i[j]);
      }
    }
    sort(ALL(v));

    able[vp[i].second] = false;

    if(v.size() < q) continue;
    chmin(ans, v[q-1] - v[0]);
  }
  cout << ans << endl;

  return 0;
}


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

int main() {
  cin.tie(0);
  cin.sync_with_stdio(0);

  int n;
  cin >> n;
  map<int,int> m;
  while(n--) {
    int x;
    cin >> x;
    m[x]++;
  }

  int ans = 0;
  for(auto const& p : m)
    ans += (p.first <= p.second ? p.second-p.first : p.second);

  cout << ans;
}

Measured memory_bytes: 4736
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<long, long> PLL;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

int mp[22][22];

int main(){
	int N,M;
	int x[]={0,1,0,-1};
	int y[]={1,0,-1,0};
	while(cin>>N){
		if(N==0)break;
		CLR(mp);
		REP(i,N){
			int tx,ty;
			cin>>tx>>ty;
			mp[tx][ty]++;
		}
		cin>>M;
		
		int nx=10,ny=10;
		int res=0;
		REP(k,M){
			
			char d;int l;
			cin>>d>>l;
			int rx,ry;
			if(d=='N'){
				rx=x[0]*l;
				ry=y[0]*l;
			}else if(d=='E'){
				rx=x[1]*l;
				ry=y[1]*l;
			}else if(d=='S'){
				rx=x[2]*l;
				ry=y[2]*l;
			}else{
				rx=x[3]*l;
				ry=y[3]*l;
			}
			if(rx<0||ry<0){
				for(int i=0;i>=rx;i--)for(int j=0;j>=ry;j--){
					if(mp[nx+i][ny+j]!=0){
						mp[nx+i][ny+j]=0;
						//cout<<"!"<<nx+i<<" "<<ny+j<<endl;
						res++;
					}
				}
			}else{
				for(int i=0;i<=rx;i++)for(int j=0;j<=ry;j++){
					if(mp[nx+i][ny+j]!=0){
						mp[nx+i][ny+j]=0;
						//cout<<"!"<<nx+i<<" "<<ny+j<<endl;
						res++;
					}
				}
			}
			nx+=rx;ny+=ry;
		}
		if(res==N)cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}

Measured memory_bytes: 1152