akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  int v[] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  int K;cin >> K;
  --K;
  cout << v[K] << endl;
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

int main() {

	int H, W;
	scanf("%d %d", &H, &W);

	int A[H + 1][W + 1];
	for (int i = 1; i <= H; ++i) {
		for (int j = 1; j <= W; ++j) {
			scanf("%d", &A[i][j]);
		}
	}
	int G[H + 1][W + 1];
	for (int i = 0; i <= H; ++i) {
		G[i][0] = 0;
	}
	for (int i = 0; i <= W; ++i) {
		G[0][i] = 0;
	}

	int maxWidth = 0;
	for (int i = 1; i <= H; ++i) {
		for (int j = 1; j <= W; ++j) {
			if (A[i][j] == 1) {
				G[i][j] = 0;
			} else {
				G[i][j] = min(G[i][j - 1], min(G[i - 1][j - 1], G[i - 1][j])) + 1;
			}
			maxWidth = max(maxWidth, G[i][j]);
		}
	}
	cout << maxWidth * maxWidth << endl;
	return 0;
}

Measured memory_bytes: 18552
program PopularVote;
var
	N, M, i, count : integer;
	total : int64;
	r :real;
	a : array[1..100] of integer;
begin
	readln(N, M); count := 0; total := 0;
	
	for i := 1 to N do begin
		read(a[i]);
		total := total + a[i] ;
	end;
	
	r := total*(1 / (4 * M));
	for i := 1 to N do 
		if a[i] >= r 
			then count := count + 1;
			
	if count >= M 
		then writeln('Yes')
		else writeln('No');
end.


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

int main() {
  int H, W;
  vector<string> a(100);
  cin >> H >>W;
  for(int i =0;i<H;i++){
    cin >> a.at(i);
  }
  for(int j =0;j<W+2;j++){
    cout << '#';
  }
  cout << endl;
  for(int i =0;i<H;i++){
    cout << '#' << a.at(i) << '#' << endl;
  }
  for(int j =0;j<W+2;j++){
    cout << '#';
  }
  cout << endl;
}
 


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false);cin.tie(NULL)
using namespace std;
#define int long long
#define MOD 1000000007
typedef vector<int> vi;
typedef pair<int,int> pi;
#define inf 1e18
#define For(i,a,b) for (int i = a; i < b; i++)
#define Rep(i,a,b) for (int i = a; i <= b; i++)
#define ps(x,y) fixed << setprecision(y) << x 
#define pb push_back 
#define mp make_pair 
 
int32_t main()
{
    fast;
    int A, B, X; cin >> A >> B >> X;
    int a, b;
    a = A / X; b = B / X;
    if(A % X == 0) cout << b - a + 1;
    else cout << b-a;


    
    
    
    return 0;
}

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

using namespace std;
typedef long long ll;

const int maxn=5e5+10;
const int inf=0x3f3f3f3f;

struct edge{
    int to,nt,w;
}e[maxn];
queue<int>q;
int dis[maxn],h[maxn];
int cnt;

void add(int u,int v,int w){
     e[++cnt].to = v;
     e[cnt].nt = h[u];
     e[cnt].w=w;
     h[u]=cnt;
}

int main(int argc, char const *argv[])
{
    int k;
    scanf("%d",&k);
    cnt=0;
    for(int i=0;i<k;i++){
        add(i,(i+1)%k,1);
        add(i,(i*10)%k,0);
    }
    q.push(1);
    memset(dis,inf,sizeof(dis));
    dis[1]=0;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=h[x];i;i=e[i].nt){
            if( dis[e[i].to]>dis[x]+e[i].w){
                dis[e[i].to]=dis[x]+e[i].w;
                q.push(e[i].to);
            }
        }
    }
    printf("%d\n",dis[0]+1);
    return 0;
}

Measured memory_bytes: 7040
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<pair<int, int> > > vvp;
typedef vector<pair<int, int> > vp;
typedef vector<vector<int> > vvi;
typedef vector<int> vi;
typedef vector<vector<ll> > vvl;
typedef vector<ll> vl;
typedef vector<vector<bool> > vvb;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef pair<string, int> psi;
typedef pair<int, int> pii;
#define rep(i,s,n) for(int i = (s); i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define yn(f) (f?"yes":"no")
#define YN(f) (f?"YES":"NO")
#define Yn(f) (f?"Yes":"No")
#define puts(s) cout<<(s)<<endl
#define inf (1000000007)
#define nil -1
class disjoint_set {
public:
	vi p, rank;
	disjoint_set(int size) {
		p.resize(size, 0);
		rank.resize(size, 0);
		for (int i = 0; i < size; i++)makeSet(i);
	}
	void makeSet(int x) {
		p[x] = x;
		rank[x] = 0;
	}
	bool same(int x, int y) {
		return findSet(x) == findSet(y);
	}
	void unite(int x, int y) {
		link(findSet(x), findSet(y));
	}
	void link(int x, int y) {
		if (rank[x] < rank[y]) {
			p[x] = y;
		}
		else {
			p[y] = x;
			if (rank[x] == rank[y]) {
				rank[x]++;
			}
		}
	}
	int findSet(int x) {
		if (x != p[x]) {
			p[x] = findSet(p[x]);
		}
		return p[x];
	}
};


ll gcd(ll a,ll b) {
	return a % b == 0 ? b : gcd(b,a%b);
}
ll lcs(ll a,ll b) {
	return a*b/gcd(a,b);
}
int main() {
	int n;
	cin >> n;
	vector<double> V(n);
	rep(i, 0, n)cin >> V[i];
	sort(all(V));
	double ans = V[0];
	rep(i, 1, n) {
		ans = (ans + V[i]) / 2;
	}
	puts(ans);
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
  int n,b,f,r,v,college[4][3][10]={0};
  cin>>n;
  for(int m=0;m<n;m++){
  cin>>b>>f>>r>>v;
  college[b-1][f-1][r-1]+=v;
//  if(college[b-1][f-1][r-1]>9)college[b-1][f-1][r-1]=9;
  //if(college[b-1][f-1][r-1]<0)college[b-1][f-1][r-1]=0;
  }
for(int i=0;i<4;i++){
  if(i!=0){
    for(int l=0;l<20;l++)cout<<"#";
    cout<<endl;
  }
    for (int j = 0; j <3 ; j++) {
      for (int k=0;k<10;k++){
        if(college[i][j][k]!=0)cout<<" "<<college[i][j][k];
        else{cout<<" "<<0;}
      }
      cout<<endl;
    }
}
  return 0;
}

Measured memory_bytes: 1160
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<cstdint>
#include<cstddef>
#include<algorithm>
using namespace std;
using i32 = int_fast32_t;
using i64 = int_fast64_t;
using usize = uint_fast64_t;
#define rep(i, n) for (usize i = 0; i < (usize)(n); i++)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
using P = pair<i64,i64>;

int main(){
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
i64 h,w;
cin >> h >> w;
usize ans = 1e18;
for(i32 i = 1; i < h; i++){
    usize s1 = i * w;
    usize H = h - i;
    usize s2 = H / 2 * w;
    usize s3 = h * w - s1 - s2;
    ans = min(ans,max({s1,s2,s3}) - min({s1,s2,s3}));
    usize W = w / 2;
    s2 = W * H;
    s3 = h * w - s1 - s2;
    ans = min(ans,max({s1,s2,s3}) - min({s1,s2,s3}));
}
swap(h,w);
    for(i32 i = 1; i < h; i++){
        usize s1 = i * w;
        usize H = h - i;
        usize s2 = H / 2 * w;
        usize s3 = h * w - s1 - s2;
        ans = min(ans,max({s1,s2,s3}) - min({s1,s2,s3}));
        usize W = w / 2;
        s2 = W * H;
        s3 = h * w - s1 - s2;
        ans = min(ans,max({s1,s2,s3}) - min({s1,s2,s3}));
    }
    cout << ans << endl;
}

Measured memory_bytes: 3580
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]

#####segfunc#####
def segfunc(x, y):
    return max(x,y)
#################

#####ide_ele#####
ide_ele = 0
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res
    
def main():
    N, K = MI()
    Seg = SegTree([0] * (300000+2), segfunc, ide_ele)
    
    for i in range(N):
        num = I()
        l = num - K
        r = num + K
        if l <= 0:
            l = 0
        if r >= 300000:
            r = 300000

        temp = Seg.query(l, r+1)
        Seg.update(num, temp+1)
    print(Seg.query(0, 300001))
    
if __name__ == "__main__":
    main()

Measured memory_bytes: 82216
N, *As = readlines.map(&:to_i)

m1, m2 = 0, 0
As.each do |a|
  if a > m1
    m1, m2 = a, m1
  elsif a > m2
    m2 = a
  end
end
As.each{|a| puts a == m1 ? m2 : m1}

Measured memory_bytes: 22524
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
long long mo = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<class A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}cout << "\n";}
ld PI=3.14159265358979323846;

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
    vector<int> size;
    UnionFind(int N): par(N),size(N) {

         //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++){
            par[i] = i;
            size[i] = -1;
        }
            
    }
    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
        size[ry] += size[rx];
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
    int getsize(int x){
        return -size[root(x)];
    }
    int getNunion(){//これちょっと遅い sameと組み合わせて順次数えていけば早くなりそう。
        map<int,int> m;
        rep(i,par.size()){
            m[this->root(i)]++;
        }
        return int(m.size());
    }
};

int main(){
    ll N,M;
    cin >> N >> M;
    vector<ll> A(M), B(M), C(M);
    rep(i,M){
        cin >> A[i] >> B[i];
        A[i]--;B[i]--;
    }
    UnionFind tree(N);
    ll ans = N*(N-1)/2;
    rep(i,M){
        C[M-1-i] = ans;
        if(tree.root(A[M-1-i]) != tree.root(B[M-1-i])){
            ans -= tree.getsize(A[M-1-i])*tree.getsize(B[M-1-i]);
        }
        tree.unite(A[M-1-i], B[M-1-i]);
    }
    rep(i,M){
        cout << C[i] << endl;
    }
}

Measured memory_bytes: 4480
#include<stdio.h>
#include<stdlib.h>

int prime_or_not(int x)
{
  int i;
  for(i=2;i*i<=x;i++){
    if(x%i==0) return 0;
  }
  return 1;
}

int main()
{
  int i,n,x,y;
  y=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&x);
    y=y+prime_or_not(x);
  }
  printf("%d\n",y);
  return 0;
}

Measured memory_bytes: 1800
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<algorithm>

using namespace std;

int main() {
  int N, M;
  cin >> N >> M;

  int ans = 1;
  for ( int A=1; A*A<=M; A++){
    
    if (M%A != 0) continue;
    int B = M/A;

    if ((long)A*N <=M) ans = max(ans,A);
    if ((long)B *N<=M) ans = max(ans,B);
  }
  cout << ans <<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int field[60][60];
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int dfs(int x, int y);
int main(){
  int n,m;
  while(cin >>n>>m,n||m){
    for(int i=0; i<60; i++) for(int j=0; j<60; j++) field[i][j] = 1;
    int x,y;
    string s;
    for(int i=0; i<m; i++){
      cin >>s;
      for(int j=0; j<n; j++){
	if(s[j] == '.') field[i+20][j+20] = 0;
	if(s[j] == '#') field[i+20][j+20] = 1;
	if(s[j] == '@'){
	  field[i+20][j+20] = 1;
	  x = i+20; y= j+20;
	}
      }
    }
    cout <<dfs(x,y)<<endl;
  }
  return 0;
}
int dfs(int x, int y){
  int ans = 0;
  field[x][y] = 1;
  ans++;
  for(int i=0; i<4; i++){
    if(field[x+dx[i]][y+dy[i]] == 0) ans+=dfs(x+dx[i],y+dy[i]);
  }
  return ans;
}

Measured memory_bytes: 1228
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }
    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int N = scan.nextInt();
        int M = scan.nextInt();
        long[] A = new long[N];
        for (int i = 0; i < N; i++) {
            A[i] = scan.nextLong();
        }
        long[] s = new long[N+1];
        for (int i = 0; i < N; i++) {
            s[i+1] = s[i] + A[i];
        }
        Map<Integer, Long> map = new HashMap<>();
        for (int i = 0; i <= N; i++) {
            int remain = (int) (s[i] % M);
            if (!map.containsKey(remain)) {
                map.put(remain, 0L);
            }
            long cnt = map.get(remain);
            map.put(remain, cnt+1);
        }
        long ans = 0;
        for(int x : map.keySet()) {
            long cnt = map.get(x);
            if (cnt <= 1) {
                continue;
            }
            ans += cnt * (cnt - 1) / 2;
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 62832
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
typedef long long ll;
class Binaryindextree{
  private:
    vector<ll>v;
  public:
    Binaryindextree(int n):v(n + 1){}
    ll sum(int i){
      ll res = 0;
      for(++i; i > 0; i -= i & -i)res += v[i];
      return res;
    }
    void add(int i,ll t){
      for(++i; i < v.size(); i += i & -i)v[i] += t;
      return;
    }
};
int main(){
  int n,q;
  cin >> n >> q;
  Binaryindextree BIT(n);
  rep(i,q){
    int Q;
    cin >> Q;
    if(Q){
      int num;
      cin >> num;
      cout << BIT.sum(num - 1) << endl;
    }
    else{
      int a,b,c;
      cin >> a >> b >> c;
      BIT.add(a - 1,c);
      BIT.add(b,-c);
    }
  }
  return 0;
}


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

int main(){
  int n;cin>>n;
  map<int, ll> count;
  for(int i=0;i<n;i++){
    int num;cin>>num;
    if(i==0 && num!=0){cout<<0<<endl;return 0;}
    count[num]++;
  }
  if(count[0]!=1LL){cout<<0<<endl;return 0;}
  int pre=-1;
  for(auto& e: count){
    if(pre+1!=e.first){cout<<0<<endl;return 0;}
    pre=e.first;
  }
  ll ans=1LL;
  for(int i=1;i<count.size();i++){
    ll t=count[i-1];
    if(t==1LL)continue;
  	for(int j=0;j<int(count[i]);j++){
      ans=(ans*t)%998244353;
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 6528
#include <stdio.h>
#include<string.h>
int main(void){
    unsigned long long  n,m;
    scanf("%llu%llu",&n,&m);
    if(2*n>=m)printf("%lld\n",m/2);
    else printf("%lld\n",n+(m-2*n)/4);
    return 0;
}


Measured memory_bytes: 128
from collections import deque


n,m = map(int,input().split())
tree = [[] for i in range(n)]
for i in range(m):
    tmp1, tmp2, cost = map(int, input().split())
    tmp1 -= 1
    tmp2 -= 1
    tree[tmp1].append([tmp2, cost])
    tree[tmp2].append([tmp1, -cost])

is_visited = [False]*n
pos = [0]*n
for i in range(n):
    if is_visited[i]:
        continue
    else:
        is_visited[i] = True
        q = deque()
        q.append(i)
        while q:
            here = q.popleft()
            for next, cost in tree[here]:
                if is_visited[next]:
                    if pos[next] != pos[here] + cost:
                        print("No")
                        exit()
                else:
                    is_visited[next] = True
                    pos[next] = pos[here] + cost
                    q.append(next)
print("Yes")

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

#define MAXSIZE 100100

struct Node { int parent, left, right; };

Node T[MAXSIZE];
int n, Depth[MAXSIZE];

void setDepth(int u, int depth) {
    Depth[u] = depth;
    if (T[u].right != -1) setDepth(T[u].right, depth);
    if (T[u].left != -1) setDepth(T[u].left, depth + 1);
    return;
}

void print(int u) {
    cout << "node " << u << ": parent = " << T[u].parent;
    cout << ", depth = " << Depth[u] << ", ";
    if (T[u].parent == -1) cout << "root, ";

    else if (T[u].left == -1) cout << "leaf, ";
    else cout << "internal node, ";
    
    cout << "[";
    int i = 0, child = T[u].left;
    while (child != -1) {
        if (i) cout << ", ";
        cout << child;
        child = T[child].right;
        i++;
    }
    cout << "]" << endl;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        T[i].parent = T[i].left = T[i].right = -1;
    }

    int id, k, child, left_sibling;
    for (int i = 0; i < n; i++) {
        cin >> id >> k;
        for (int j = 0; j < k; j++) {
            cin >> child;
            if (j == 0) T[id].left = child;
            else T[left_sibling].right = child;
            left_sibling = child;
            T[child].parent = id;
        }
    }

    int parent;
    for (int i = 0; i < n; i++) {
        if (T[i].parent == -1) parent = i;
    }

    setDepth(parent, 0);

    for (int i = 0; i < n; i++) print(i);
    return 0;
}


Measured memory_bytes: 7744
from itertools import combinations
from heapq import heappop, heappush
INF = 10 ** 20

def convert(s, m, n):
  if s == "H":
    return 0
  if s == "D":
    return 1
  if s[0] == "C":
    return int(s[1:]) + 1
  if s[0] == "L":
    return int(s[1:]) + m + 1

def get_cost(start, m, n, edges):
  cost = [INF] * (m + n + 2)
  cost[start] = 0
  que = []
  heappush(que, (0, start))
  while que:
    total, node = heappop(que)
    for dist, to in edges[node]:
      if cost[to] > total + dist:
        cost[to] = total + dist
        if not (2 <= to <= m + 1):
          heappush(que, (total + dist, to))
  return cost


def shortest_path(start, goal, rest, cakes_dist, dic):
  if not rest:
    return cakes_dist[start][goal]
  #if (start, rest) in dic:
  #  return dic[(start, rest)]
  
  ret = INF
  for to in rest:
    ret = min(ret, shortest_path(to, goal, tuple((i for i in rest if i != to)), cakes_dist, dic) + cakes_dist[start][to])
  dic[(start, rest)] = ret
  return ret

while True:
  m, n, k, d = map(int, input().split())
  if m == 0:
    break
  clst = list(map(int, input().split()))
  """
  Home ... 0
  D ... 1
  Cake ... 2, 3, ... m + 1
  Land ... m + 2, m + 3, ... m + n + 1
  """
  edges = [[] for _ in range(m + n + 2)]
  for _ in range(d):
    s, t, e = input().split()
    e = int(e)
    s = convert(s, m, n)
    t = convert(t, m, n)
    edges[s].append((e, t))
    edges[t].append((e, s))
  
  cakes_dist = [[INF] * (m + 2) for _ in range(m + 2)]
  for start in range(m + 2):
    cost = get_cost(start, m, n, edges)
    for to in range(m + 2):
      if to != start:
        cakes_dist[start][to] = cost[to]
  
  """
  now ... 現在いる点
  rest ... 残りのめぐる点
  dic[(now, rest)] ... 現在いる点、残りの点をまわる時の最小距離
  dic[(now, rest)] = min(cakes_dist[now][to] + dic[(to, rest - to)] for to in rest)
  """
  dic = {}
  ans = INF
  cakes = [i for i in range(2, m + 2)]
  for num in range(m + 1):
    for rest in combinations(cakes, num):
      cal = sum([clst[i - 2] for i in rest])
      ans = min(ans, shortest_path(0, 1, rest, cakes_dist, dic) * k - cal)
  print(ans)


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

int main(){
  int N;//マスの一辺
  int A;//白く塗るマスの個数
  int B;//黒く塗るマスの個数を計算する変数
  
  cin >> N >> A;
  
  B = N * N - A;
  
  cout << B << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
int main() {
	string a, b, c;
	cin >> a >> b >> c;
	int n1 = a[0]-'a';
	int n2 = b[0]-'a';
	int n3 = c[0]-'a';
	cout << char('A'+n1) << char('A'+n2) << char('A'+n3) << '\n';
}


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

int main()
{
  int64_t N, P, ans = 0;
  string S;
  cin >> N >> P >> S;
  reverse(S.begin(), S.end());
  if (P == 2 || P == 5)
  {
    for (int i = 0; i < N; i++)
    {
      int sint = S[i] - '0';
      if (sint % P == 0)
      {
        ans += N - i;
      }
    }
  }
  else
  {
    vector<int64_t> Count(10000, 0);
    Count[0]++;
    int64_t num = 1, cur = 0;
    for (int i = 1; i <= N; i++)
    {
      int sint = S[i - 1] - '0';
      cur = (cur + sint * num) % P;
      Count[cur]++;
      num *= 10;
      num %= P;
    }
    for (int64_t c : Count)
      ans += c * (c - 1) / 2;
  }
  cout << ans << endl;
}


Measured memory_bytes: 640
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 998244353

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

from bisect import bisect_left


def fact(a,M=mod):
    ans = 1
    for i in range(2,a+1):
        ans = ans*i
        ans = ans%M
    return ans

N = I()
S = str(input())

r = []
g = []
b = []

m1 = []
m2 = []
m3 = []

for i in range(3*N):
    if S[i]=='R':
        r.append(i)
    elif S[i]=='G':
        g.append(i)
    else:
        b.append(i)

for i in range(N):
    m1.append(min(r[i],g[i],b[i]))
    m2.append(sorted([r[i],g[i],b[i]])[1])
    m3.append(max(r[i],g[i],b[i]))

ans = fact(N)

for i in range(N):
    left = bisect_left(m1,m2[i])
    ans = ans*(left-i)%mod

for i in range(N)[::-1]:
    right = N-bisect_left(m3,m2[i])
    ans = ans*(right-(N-1-i))%mod

print(ans)

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


//defines...
#define ll long long
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define mp make_pair
#define in insert
#define pi 2*acos(0.0)1
#define srt(s) sort(s.begin(),s.end())
#define all(x) x.begin(),x.end()

const ll mod=1e9+7;
const ll MX=2e5+5;

//code goes from here...



int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);

    freopen("output.txt", "w", stdout);
#endif

    boost
    //---------------------------------
    int k=3, a=0,b=0;
    while(k--)
    {
        int x;
        cin >> x;
        if(x==5) a++;
        else if(x==7) b++;
    }
    if(a==2 && b==1) cout << "YES\n";
    else cout << "NO\n";
    
    //---------------------------------
    
    return 0;
}


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

#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ld long double
#define forn(low,high,i) for(i = low; i < high; i++)
#define forrev(high,low,i) for(i = high; i >= low; i--)
#define all(v) v.begin(),v.end()
#define decimal_digits cout << fixed << setprecision(15);

string to_string(string s) { return '"' + s + '"';}
string to_string(char s) { return string(1, s);}
string to_string(const char* s) { return to_string((string) s);}
string to_string(bool b) { return (b ? "true" : "false");}
template <typename A> string to_string(A);
template <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}
template <typename A> string to_string(A v) {bool f = 1; string r = "{"; for (const auto &x : v) {if (!f)r += ", "; f = 0; r += to_string(x);} return r + "}";}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {cerr << " " << to_string(H); debug_out(T...);}
#define pr(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define GOOGLE 0
#define MULTIPLE_TC 0

const int inf = 1e9;
const long long INF = 1e18;
const int mod = 1e9 + 7;
const int bit32 = log2(inf) + 3;
const int bit64 = log2(INF) + 3;

inline int add(long long a, long long b){a += b; if(a >= mod) a -= mod; return a;}
inline int sub(long long a, long long b){a -= b; if(a < 0) a += mod; return a;}
inline int mul(long long a, long long b){a %= mod; b %= mod; return (int)((long long) a * b % mod);}
inline int modexpo(long long a, long long b){int res = 1; while(b > 0){ if(b & 1) res = mul(res, a); a = mul(a, a); b /= 2;} return res;}
inline int divide(long long a, long long b){return mul(a, modexpo(b, mod - 2));}
inline int inv(long long a){return modexpo(a, mod - 2);}

clock_t time_p = clock();

void ktj(){
  time_p = clock() - time_p;
  cerr << "Time elapsed : " << (float)(time_p)/CLOCKS_PER_SEC << "\n";
}

void pre(){ // Reset each global variable (esp. for graphs)
  
}

void solve(){
  long long n, k;
  cin >> n >> k;
  long long sum = 0, mx = 0;
  vector<long long> a;
  for (int i = 0; i < n; i++) {
    long long x; cin >> x; sum += x; mx = max(mx, x);
    a.push_back(x);
  }

  long long l = 1, r = mx, ans = mx;
  while (l <= r) {
    long long md = (l + r) >> 1;
    bool poss = 1;
    poss &= (md * (n + k) >= sum);
    int cuts = 0;
    for (int i = 0; i < n; i++) {
      cuts += (a[i] - 1) / md;
    }
    poss &= (cuts <= k);
    if (poss) {
      ans = md; r = md - 1;
    } else {
      l = md + 1;
    }
  }
  cout << ans << '\n';
}

int32_t main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);cout.tie(NULL); 

  pre();

  int t = 1, T;

  if(MULTIPLE_TC)
    cin >> t;

  for(T = 1; T <= t; T++){
    if(GOOGLE)
      cout << "Case #" << T << ": ";
    solve();
  }

  ktj();
}


Measured memory_bytes: 5308
{-# LANGUAGE BangPatterns #-}

module Main
  ( main
  )
where

import           Control.Applicative
import           Control.Monad
import           Data.Bits
import qualified Data.ByteString.Char8         as BS
import           Data.Char
import           Data.List
import           Data.Maybe
import qualified Data.Vector                   as V
import qualified Data.Vector.Mutable           as MV
import           Control.Monad.ST
import           Data.Ord
import qualified Data.Vector.Unboxed           as UV

import System.IO

parse = fst . fromJust
parseInt = parse . BS.readInt
parseInteger = parse . BS.readInteger
readInt = parseInt <$> BS.getLine
readInteger = parseInteger <$> BS.getLine
readIntList = map parseInt . BS.words <$> BS.getLine
readIntegerList = map parseInteger . BS.words <$> BS.getLine

main = do
  k <- readInt
  [a, b] <- readIntList
  putStrLn $ if k * ((a + k - 1) `div` k) <= b then "OK" else "NG"


Measured memory_bytes: 3784
%:pragma GCC optimize(2)
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int N=1000010;
int a[N],x,y,n;
bool bo[N],li[N];
vector<int>e[N];
struct cmp{bool operator ()(int x,int y){return a[x]>a[y];}};
priority_queue<int,vector<int>,cmp>q;
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;++i)
		scanf("%d",&a[i]),q.push(i),li[i]=bo[i]=0;
	for (int i=1;i<n;++i)
		scanf("%d%d",&x,&y),e[x].push_back(y),e[y].push_back(x);
	for (int i=1;i<=n;++i){
		int u=q.top(); q.pop();
		if (bo[u]) continue; bo[u]=1;
		bool flag=1;
		for (int j=0;j<e[u].size();++j) {
			int to=e[u][j];
			if (a[to]<a[u]&&!li[to]){flag=0; break;}
		}
		if (flag) li[u]=0; else li[u]=1;
		if (flag){
			for (int j=0;j<e[u].size();++j){
				int to=e[u][j]; if (a[to]>a[u]) bo[to]=1,li[to]=1;
			}
		}
	}
	for (int i=1;i<=n;++i)
		if (li[i]) printf("%d ",i);
	return 0;
}

Measured memory_bytes: 27008
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
mod = 10**9+7

max_num = 0
min_num = 0

def cmb(n, r, mod):
    if (r<0 or r>n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range(2, n+1):
    g1.append( (g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

for i in range(k-1,n):
    cmb_num = cmb(i, k-1, mod)
    max_num += cmb_num*a[i] % mod
    min_num += cmb_num*a[n-1-i] % mod
print((max_num-min_num)%mod)


Measured memory_bytes: 20304
#include <bits/stdc++.h>
#define REP(i, a, n) for (long long i = (a); i < (long long)(n); ++i)
#define REPC(i, a, n) for (long long i = (a); i <= (long long)(n); ++i)
#define ALL(t) t.begin(), t.end()
#define RALL(t) t.rbegin(), t.rend()
#define MATINIT(type, row, col, init) \
  vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
template <class T>
using VEC = std::vector<T>;
template <class T>
using MAT = std::vector<std::vector<T>>;
void DUMP() { cerr << endl; }
template <class Head, class... Tail>
void DUMP(Head &&head, Tail &&... tail) {
  cerr << head << ", ";
  DUMP(std::move(tail)...);
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &vec) {
  os << "{";
  for (auto v : vec) os << v << ",";
  os << "}";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, set<T> &s) {
  os << "{";
  for (auto p : s) os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, map<T1, T2> &m) {
  os << "{";
  for (auto p : m) os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> p) {
  os << "[" << p.first << " " << p.second << "]";
  return os;
}

int main() {
  LL M, K;
  cin >> M >> K;
  if (K >= (1 << M)) {
    cout << -1 << endl;
    return 0;
  }
  if (M == 0) {
    cout << "0 0"<< endl;
    return 0;
  }
  if (M == 1) {
    if (K == 0) {
      cout << "0 0 1 1" << endl;
    } else {
      cout << -1 << endl;
    }
    return 0;
  }
  LL lim = (1 << M);
  VEC<LL> A;
  REP(i, 0, lim) {
    if (i != K) {
      A.push_back(i);
    }
  }
  A.push_back(K);
  for (LL i = lim - 1; i >= 0; i--) {
    if (i != K) {
      A.push_back(i);
    }
  }
  A.push_back(K);
  REP(i, 0, A.size()) {
    cout << A[i];
    if (i < A.size() - 1) cout << " ";
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 3952
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
#include<stdio.h>
#include<string.h>
#include <bitset>
#include<assert.h>

using namespace std;
#define int long long

#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
// #define MOD 1000000007

#define MEM_SIZE 10000
#define DEBUG_OUT true
#define ALL(x) (x).begin(), (x).end()

template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return; std::cout << e <<" ";}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){std::cout<< e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T,class... Ts> void DEBUG(T d, Ts... e){if(DEBUG_OUT == false)return;DEBUG(d);DEBUG(e...);}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; abort();}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }


void solve(void)
{
  int N;
  cin>>N;
  vector<int> A (N,0);
  vector<int> B (N,0);
  for (int i = 0; i < N; i++)
  {
    cin>>A[i]>>B[i];
  }
  sort(ALL(A));
  sort(ALL(B));
  if(N%2 == 1)
  {
    cout<<B[N/2] - A[N/2]+1<<endl;
  }
  else
  {
    cout<< B[N/2-1] + B[N/2] - A[N/2-1] - A[N/2] + 1<<endl;
  }

  
  

  
}
int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  std::cout << std::fixed;
  std::cout << std::setprecision(11);
  solve();

  return 0;
}


Measured memory_bytes: 6368
#include<bits/stdc++.h>
typedef long long ll;
#define m 1000000007
using namespace std;
/*ll mod(ll x,ll y)
{ ll ans=1;

    while(y>0)
    {
        if(y&1)
            ans=ans*x %m;
        y/=2;
        x=(x*x) %m;

    }
    return ans;
}*/
int main()
{
 /*ll a,b,c,d,m,n,res=0;
 cin>>a>>b>>c>>d;
 cout<<max(max(a*c,b*d),max(a*d,b*c))<<endl;*/

 /*ll n;
 cin>>n;
 ll ans= (mod(10,n)-(mod(9,n)*2-mod(8,n)))%m;
 //ll ans=mod(8,n);
 if(ans<0)
    ans+=m;
 cout<<ans<<endl;*/
 ll s;
 cin>>s;
 vector<ll> v(s+1);
 v[0]=1;
 for(int i=3;i<=s;i++)
 {

     for(int j=0;j<=i-3;j++)
     {
         v[i]+=v[j];
         v[i]%=m;

     }
 }
 cout<<v[s]<<endl;
return 0;
}


Measured memory_bytes: 3592
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<numeric>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i = m; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a)  (a).rbegin(),(a).rend()
#define dup(x,y) (((x)+(y)-1) / (y)); //整数型のまま切り上げ演算する
#define PI 3.14159265359
#define MOD 1000000007
typedef long long LL;
template<class T> inline void chmax(T & a, T b) { if (a < b) { a = b; } }
template<class T> inline void chmin(T& a, T b) { if (a > b) { a = b; } }
template<class T> T gcd(T x, T y) { if (y == 0) { return x; } else if (x == 0) { return y; }return gcd(y, x % y); }
template<class T> void print_vector(vector<T> vec) { for (int i = 0; i < vec.size(); i++) { cout << vec[i] << " "; }cout << endl; }
const LL LLINF = 1LL << 60;

int main(void) {
	LL N;
	string S;
	cin >> N >> S;

	vector<LL> E_ruiseki(N), W_ruiseki(N);
	if (S[N - 1] == 'E') E_ruiseki[N - 1]++;
	if (S[0] == 'W') W_ruiseki[0]++;


	for (int i = 1; i < N; i++) {
		if (S[i] == 'E') {
			W_ruiseki[i] = W_ruiseki[i - 1];
		}
		else {
			W_ruiseki[i] = W_ruiseki[i - 1] + 1;
		}
	}
	for (int i = N - 2; i >= 0; i--) {
		if (S[i] == 'E') {
			E_ruiseki[i] = E_ruiseki[i + 1] + 1;
		}
		else {
			E_ruiseki[i] = E_ruiseki[i + 1];
		}
	}

	LL ans = LLINF;
	for (int i = 0; i < N; i++) {
		LL tmp = E_ruiseki[i] + W_ruiseki[i] - 1;
		chmin(ans,tmp);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 5380
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const long long infll = (long long) 1.01e18;
const ld eps = 1e-9;
const ld pi = acos((ld) -1);

#ifdef DEBUG
mt19937 mrand(300); 
#else
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count()); 
#endif

int rnd(int x) {
  return mrand() % x;
}

void precalc() {
}

const int maxn = (int) 2e6 + 5;
int n;
string s, t;
char tmp[maxn];

bool read() {
  if (scanf("%d", &n) < 1) {
    return false;
  }
  scanf("%s", tmp);
  s = tmp;
  scanf("%s", tmp);
  t = tmp;
  return true;
}

int toadd[maxn];

bool check(int h) {
  memset(toadd, 0, sizeof(toadd));
  int val = 0;
  int pos = 0;
  for (int i = 0, k = 0; i < n;) {
    int j = i;
    while (j < n && t[j] == t[i]) {
      j++;
    }
    while (k <= i && (s[k] != t[i] || val + 1 > h)) {
      k++;
      pos++;
      val += toadd[pos];
    }
    if (k > i) {
      return false;
    }
    val++;
    k++;
    toadd[pos + j - k]--;
    if (j == k) {
      val--;
    }
    i = j;
  }
  return true;
}

void solve() {
  if (s == t) {
    printf("0\n");
    return;
  }
  if (!check(n)) {
    printf("-1\n");
    return;
  }
  int l = 0, r = n;
  while (l < r - 1) {
    int m = (l + r) / 2;
    if (check(m)) {
      r = m;
    } else {
      l = m;
    }
  }
  printf("%d\n", r);
}

int main() {
  precalc();
#ifdef DEBUG
  assert(freopen(TASK ".in", "r", stdin));
  assert(freopen(TASK ".out", "w", stdout));
#endif
  while (read()) {
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}


Measured memory_bytes: 11008
#include <iostream>
using namespace std;
int main() {
    int a,b,c;
    cin >> a >> b;
    int array[3] = {0,0,0};
    array[a-1] = 1;
    array[b-1] = 1;
    for (int i = 0; i < 3; i++) {
        if (array[i] != 1) {
            cout << i+1 << endl;
        }
    }
    return 0;
}  


Measured memory_bytes: 256
#include <iostream>

int main(){
    int a,b,c,d,e,f,g;
    std::cin>>a>>b>>c>>d>>e>>f;
    g=a*1+b*5+c*10+d*50+e*100+f*500;
         if(g<1000){
    std::cout <<0<< std::endl;
        }
          else if(g>1000){
    std::cout <<1<< std::endl;
            }
    else if(g=1000){
    std::cout <<1<< std::endl;
            }
}

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


typedef long long ll;
template<int um> class UF { // from kmjp
public:
	vector<int> par;
	UF() { par = vector<int>(um, 0); rep(i, 0, um) par[i] = i; }
	int operator[](int x) { return par[x] == x ? x : par[x] = operator[](par[x]); }
	void operator()(int x, int y)
	{
		x = operator[](x); y = operator[](y);
		if (x != y) par[x] = y;
	}
};
//-----------------------------------------------------------------
ll N, M;
vector<int> E[101010];
UF<101010> uf;
//-----------------------------------------------------------------
map<int, vector<int>> divide() {
	map<int, vector<int>> m;
	rep(i, 1, N + 1) m[uf[i]].push_back(i);
	return m;
}
//-----------------------------------------------------------------
int C[101010];
int dfs(int cu, int c = 1) {
	C[cu] = c;

	int nc = 3 - c;
	int rs = 0;
	for (int to : E[cu]) {
		if (C[to] == 0) rs += dfs(to, nc);
		if (C[cu] == C[to]) return 1;
	}
	return rs;
}
//-----------------------------------------------------------------
ll calc(vector<int> v) {
	int res = dfs(v[0]);
	if (res == 0) return 2;
	return 1;
}
//-----------------------------------------------------------------
int main() {
	cin >> N >> M;
	rep(i, 0, M) {
		int u, v; scanf("%d%d", &u, &v);
		E[u].push_back(v); E[v].push_back(u);
		uf(u, v);
	}

	auto m = divide();
	ll cnt[3];
	cnt[0] = cnt[1] = cnt[2] = 0;
	for (auto p : m) {
		auto v = p.second;
		if (v.size() == 1) {
			cnt[0]++;
			continue;
		}

		if (calc(v) == 1) cnt[1]++;
		else cnt[2]++;
	}

	ll ans = 1LL * N * N - 1LL * (N - cnt[0]) * (N - cnt[0]);
	ans += 1LL * (cnt[2] + cnt[1]) * (cnt[2] + cnt[1]);
	ans += 1LL * cnt[2] * cnt[2];

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

Measured memory_bytes: 14336
<?php
$s = trim(fgets(STDIN));
$cs = str_split($s);
$res = 0;
$prev = '';
$i=0;
$tmp=0;
foreach ($cs as $c) {
  $i++;
  if ($prev != '' && $c != $prev) {
    if ($c == '>') {
      $tmp = $i - 1;
    } else {
      if ($tmp) {
        if ($tmp < $i - 1) {
          $res -= $tmp;
        } else {
          $res -= $i - 1;
        }
        $tmp = 0;
      }
    }
    $i = 1;
  }
  $res += $i;
  $prev = $c;
}
if ($tmp) {
  if ($tmp < $i) {
    $res -= $tmp;
  } else {
    $res -= $i;
  }
}
echo $res;

Measured memory_bytes: 90500
#include <iostream>
#include <vector>
#include <queue>
#include <sstream>
#include <algorithm>
#include <bitset>
#include <limits>
#include <map>
#include <set>
#include <iomanip>
#include <cmath>

using namespace std;

typedef long long int ll;
typedef std::numeric_limits<double> dbl;
const long long int LL_INF=1LL<<60;

vector<string> split(const string& input, char delimiter)
{
    stringstream stream(input);
    
    string field;
    vector<string> result;
    while (getline(stream, field, delimiter)) {
        result.push_back(field);
    }
    return result;
}

//#define DEBUG

ll A, B, M, N, D, K, L, Q, W, H, T, X, Y, S;

int main()
{
    cin >> N >> L;
    vector<string> in(N);
    for (auto& i : in)
        cin >> i;
    
    sort(in.begin(), in.end());

    for (auto i : in)
        cout << i;
    cout << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return 1;
    }
    return 0;
}
typedef long long int ll;

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define endl "\n"
const double EPS = 1e-7;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
const double PI = acos(-1);
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for(int x = 1; x <= 50000; x++) {
        int y = (int)((double)x * 1.08);
        if(y == n) {
            cout << x << endl;
            return 0;
        }
    }
    cout << ":(" << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
typedef long long ll;

int main(void) {
  ll i, j, k, a, b, a1, a2, b1, b2;
  scanf("%lld%lld", &a, &b);
  a1 = (a * 100 + 4) / 8, a2 = (a * 100 + 96) / 8;
  b1 = b * 10, b2 = b * 10 + 9;
  if(a2 < b1 || b2 < a1) printf("-1");
  else printf("%lld", a1 < b1 ? b1 : a1);
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int N,ac=0,wa=0,tle=0,re=0;
	cin>>N;
	string S;
	for(int i=0;i<N;i++)
	{
		cin>>S;
		if(S.compare("AC")==0)
			ac++;
		else if(S.compare("WA")==0)
			wa++;
		else if(S.compare("TLE")==0)
			tle++;
		else
			re++;

	}
	cout<<"AC x "<<ac<<endl;
	cout<<"WA x "<<wa<<endl;
	cout<<"TLE x "<<tle<<endl;
	cout<<"RE x "<<re<<endl;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
const int64_t INF=9999999999999999;
int main() {
 string S;
 cin>>S;
 for(int i=0;i<S.size();i++){
    if(i%2==0){if(S[i]=='L'){cout<<"No"<<endl;return 0;}}
    else{if(S[i]=='R'){cout<<"No"<<endl;return 0;}}
 }
 cout<<"Yes"<<endl;
 return 0;}

Measured memory_bytes: 384
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
        double a = sc.nextInt();
        double b = sc.nextInt();
        double x = sc.nextInt();
        double res;
        
        if(x>a*a*b/2){
            res = Math.toDegrees(Math.atan(a*a*a/(2*a*a*b-2*x)));
        }else{
            res = Math.toDegrees(Math.atan(2*x/(a*b*b)));
        }
        System.out.println(90-res);
	}
}

Measured memory_bytes: 35972
def main():
    N = int(input())
    N_len = len(str(N))
    if N_len < 3:
        return print(0)
    from itertools import product
    ans_set = set()
    for k in range(3, N_len+1):
        ans_set = ans_set.union({s for s in product("753", repeat=k)
                                 if int("".join(s)) <= N and
                                 len(set(s) & set("753")) == 3})
    print(len(ans_set))


if __name__ == '__main__':
    main()


Measured memory_bytes: 49884
#include <stdio.h>

int main(void) {
	int n, m, i;
	char t[256];
	char dmy[256];
	while(1){
		for(i = 0;i < 256;i++){
			t[i] = (char)i;
		}
		scanf("%d",&n);
		if(n == 0){
			break;
		}
		gets(dmy);
		for(i = 0;i < n;i++){
			char ch1, ch2;
			ch1 = getchar();
			getchar();
			ch2 = getchar();
			gets(dmy);
			t[ch1] = ch2;
		}
		scanf("%d",&m);
		gets(dmy);
		for(i = 0;i < m;i++){
			char ch;
			ch = getchar();
			gets(dmy);
			printf("%c",t[ch]);
		}
		printf("\n");
	}
	return 0;
}

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

int main()
{
    long long int n,m,x,y,l,i,j;
    string s;
    cin >> s;
    l=s.length();
    x=(l-1)/2-1;
    y=(l+3)/2-1;
    j=l-1;
    i=0;
    while(j!=i)
        {
            if(s[i]!=s[j])
                {
                    cout << "No";
                    exit(0);
                }
            j--;i++;
        }
    i=0;
    j=x;
    while(i<x+1)
        {
            if(s[i]!=s[j])
                {
                    cout << "No";
                    exit(0);
                }
            i++;
            j--;
        }
    i=y;
    j=l-1;
    while(i<l)
        {
            if(s[i]!=s[j])
                { 
                    cout << "No";
                    exit(0);
                }
            i++;
            j--;
        }
    cout << "Yes";
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main { 
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[] C = new int[N];
    int[] S = new int[N];
    int[] F = new int[N];
    for (int i =0; i<N-1; i++) {
      C[i] = sc.nextInt();
      S[i] = sc.nextInt();
      F[i] = sc.nextInt();
    }
    
    for (int i =0; i<N-1; i++) {
      int t =0;
      for (int j =i; j<N-1; j++) {
        if (t <= S[j]) {
          t = S[j];
        } else { 
          while (t % F[j] != 0) {
          t++;
          }
        }
        t += C[j];
      }
      System.out.println(t);
    }
    System.out.println(0);
  }
}    

Measured memory_bytes: 27068
#include<iostream>
#include<string>


int main() {
	int N = 0;
	int M = 0;
	//int K[30] = {};
	std::cin >> N;
	std::cin >> M;
	int count = 0;
	int *K = new int[N];
	int *A = new int[M];
	int *count1 = new int[M];

	for (int i = 0; i < M; i++) {
		A[i] = i;
		count1[i] = 0;
	}

	for (int i = 0; i < N; i++) {
		std::cin >> K[i];
		for (int j = 0; j < K[i]; j++) {
			int x = 0;
			std::cin >> x;
			for (int k = 0; k < M; k++) {
				if ((x - 1) == A[k]) {
					count1[k]++;
					//std::cout << k << std::endl;
				}
			}

		}
	}

	for (int i = 0; i < M; i++) {
		if (count1[i] == N) {
			count++;
		}
	}


	std::cout << count << std::endl;
}

Measured memory_bytes: 256