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

using namespace std;
typedef long long ll;

#define MOD (long long)(1e9+7)
#define INF (1LL<<60)
#define rep(i,n) for(ll i = 0; i < (n); i++)
#define rep1(i,n) for(ll i = 1; i <= (n); i++)

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;
}


// 最大公約数
ll gcd(ll a, ll b)
{
  if(b == 0) return a;
  return gcd(b, a % b);
}

// mod m におけるa の逆元
ll modinv(ll a, ll m) {
  ll b = m, u = 1, v = 0;
  while (b) {
    ll t = a / b;
    a -= t * b; swap(a, b);
    u -= t * v; swap(u, v);
  }
  u %= m;
  if (u < 0) u += m;
  return u;
}

// 素因数分解
vector<pair<ll, ll>> prim;
void pf(ll n)
{
  ll s = sqrt(n);
  ll r = 0;
  for(ll i = 2; i <= s; i++) {
    if((n % i) == 0) {
      r = 0;
      do {
	r++;
	n = n / i;
      } while((n % i) == 0);
      prim.push_back({i, r});
    }
  }
  if(n > s) {
    prim.push_back({n, 1});
  }
}


struct UnionFind {
  vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
  vector<int> cnt;
  UnionFind(int N) : par(N), cnt(N, 1) { //最初は全てが根であるとして初期化
    for(int i = 0; i < N; i++) par[i] = i;
  }
  
  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につける
    cnt[ry] += cnt[rx];
  }
  
  bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
    int rx = root(x);
    int ry = root(y);
    return rx == ry;
  }
};




void solve()
{
  ll N, M; cin >> N >> M;

  UnionFind tree(N);

  set<pair<ll, ll>> vvp;
  rep(i,M) {
    ll a, b;
    cin >> a >> b;
    a--;b--;
    tree.unite(a, b);
  }
  
  ll ans = 0;

  rep(i, N) {
    ans = max((long long)tree.cnt[i], ans);
    //    cerr << i << ":" << tree.cnt[i] << endl;
  }

  cout << ans << endl;
}


int main(void)
{
  // ll t; cin >> t; rep(i, t)
  solve();
}


Measured memory_bytes: 4760
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<map>
#include<cassert>
#include<ctime>
#include<set>
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<29
#define all(n) n.begin(),n.end()
using namespace std;
int a,b;
 
int main(){
  
  while(true){
    cin >> a >> b;
    if(a+b == 0)break;
    int ans = (1<<27);
    assert(a>=0 && b>=0);
    for(int i=1;i<=a/2+1;i++){
      if(a%i != 0)continue;
      vector<int> vec;
      //cout << "a = " << i << "," << a/i << " ";
      vec.push_back(i);vec.push_back((int)(a/i));
      for(int j=1;j<=b/2+1;j++){
    if(b%j != 0)continue;
    //cout << "b = " << j << "," << b/j << endl;
    vec.push_back(j); vec.push_back(b/j);
    sort(all(vec));
    //for(int k=0;k<4;k++){
    //cout << vec[k] << endl;
    //}
    //cout << "---" << endl;
    int sum = 0;
    sum = (vec[1]-vec[0])*(vec[1]-vec[0]) + (vec[2]-vec[1])*(vec[2]-vec[1]) + (vec[3]-vec[2])*(vec[3]-vec[2]);
    //cout << "sum -  " << sum << endl;
    ans = min(ans,sum);
    vec.clear();
    vec.push_back(i); vec.push_back(a/i);
      }
    }
 
    cout << ans << endl;
  }
   
  return 0;
}

Measured memory_bytes: 1216
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	Scanner sc = new Scanner(System.in);
	int[] dx = { 1, 0, -1, 0 };
	int[] dy = { 0, 1, 0, -1 };
	int H, W, C;
	int[][] map;
	int[][] field;
	boolean visit[][];
	int max, cnt;

	void run() {
		for (;;) {
			H = sc.nextInt();
			W = sc.nextInt();
			C = sc.nextInt();
			if ((H | W | C) == 0) {
				return;
			}
			map = new int[H][W];
			field = new int[H][W];
			max = 0;
			for (int i = 0; i < H; i++) {
				for (int j = 0; j < W; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			boolean[] use = new boolean[6];
			int[] parm = new int[5];
			makePerm(0, parm, use);
			System.out.println(max);
		}
	}

	void makePerm(int n, int[] parm, boolean use[]) {
		if (n == 4) {
			parm[n] = C;
			solve(parm);
			return;
		}
		for (int i = 1; i <= 6; i++) {
			parm[n] = i;
			makePerm(n + 1, parm, use);
		}
	}

	void solve(int parm[]) {
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				field[i][j] = map[i][j];
			}
		}
		for (int i = 0; i < 5; i++) {
			visit = new boolean[H][W];
			int first = field[0][0];
			dfs(parm[i], first, visit, 0, 0);
		}
		visit = new boolean[H][W];
		if (field[0][0] == C && !visit[0][0]) {
			cnt = 1;
			cntMap(field, visit, 0, 0);
			max = Math.max(max, cnt);
		}
	}

	void dfs(int num, int first, boolean[][] visit, int h, int w) {
		field[h][w] = num;
		visit[h][w] = true;
		for (int i = 0; i < 4; i++) {
			int nh = h + dy[i];
			int nw = w + dx[i];
			if (nh >= 0 && nh < H && nw >= 0 && nw < W && !visit[nh][nw]
					&& field[nh][nw] == first) {
				dfs(num, first, visit, nh, nw);
			}
		}
	}

	void cntMap(int[][] field, boolean[][] visitf, int h, int w) {
		visit[h][w] = true;
		for (int i = 0; i < 4; i++) {
			int nh = h + dy[i];
			int nw = w + dx[i];
			if (nh >= 0 && nh < H && nw >= 0 && nw < W && !visit[nh][nw]
					&& field[nh][nw] == C) {
				cnt++;
				cntMap(field, visit, nh, nw);
			}
		}

	}

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

Measured memory_bytes: 166780
import java.util.Scanner;
    public  class Main{
      	public static void main(String args[]){
          int A,B;
          Scanner scan = new Scanner(System.in);
          A=scan.nextInt();
          B=scan.nextInt();
          if(A==1){
          		A=14;
          }
          if( B==1){
  				B=14;
          }
          if(A < B){
            System.out.println("Bob");
          }
          if(A == B){
            	System.out.println("Draw");
           }
          if(A > B){
            	System.out.println("Alice");
          }
        }
    }


Measured memory_bytes: 22740
#include <bits/stdc++.h>
using namespace std;
#define int long long

// rec(S_bit, v) dp[S_bit][v] を再帰的に求める
// v \in S を仮定
int rec(int S_bit, int v, vector<vector<int>> edges, vector<vector<int>>& dp, int V){
    if(dp[S_bit][v] != -1) return dp[S_bit][v];
    else{
        int INF = 1<<30;
        int ans = INF;
        for(int u=0; u<V; u++){ 
            if(u == v) continue;
            int v_bit = 1<<v;
            int u_bit = 1<<u;
            int prev_S_bit = S_bit & (~v_bit);
            if((S_bit & u_bit) == u_bit && edges[u][v] != -1){
                // u -> v の辺がある
                int d_u = rec(prev_S_bit, u, edges, dp, V);
                if(d_u == -1) continue;
                if(ans > d_u + edges[u][v]){
                    ans = d_u + edges[u][v];
                }
            }
        }
        return dp[S_bit][v] = ans;
    }
}

signed main(){
    // cout << fixed << setprecision(10) << flush;

    int V, E;
    cin >> V >> E;

    vector<vector<int>> edges(V, vector<int>(V, -1));
    for(int i=0; i<E; i++){
        int s, t, d;
        cin >> s >> t >> d;
        edges[s][t] = d;
    }

    int INF = 1<<30;

    // dp[bit][v] は bit の頂点をすべて回る経路の距離のうち、0 で始まり v で終わるものの最小値
    vector<vector<int>> dp(1<<V, vector<int>(V, -1));
    dp[1<<0][0] = 0;

    int U = (1<<V)-1, res = INF;
    for(int v=0; v<V; v++){
        // スタート は 0 としてもよい、どうせ一回は通るので
        if(edges[v][0] != -1){
            int r = rec(U, v, edges, dp, V);
            if(res > r + edges[v][0]){
                res = r + edges[v][0];
            }
        }
    }
    if(res == INF) res = -1;
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 7800
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, start = 0, n = 0;
  cin >> N;
  vector<int> h(N);
  for (int i = 0; i < N; i++) {
    cin >> h.at(i);
  }
  
  while (start != N) {
    
    if (h.at(start) != 0) {
      n += 1;
      for (int j = start; j < N; j++) {
        if (h.at(j) != 0) {
          h.at(j) -= 1;
        } else {
          break;
        }
      }
    }
    else start += 1;
  }
  cout << n << endl; 
}

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

using ll = long long;

ll JudgeHarmony(ll a, ll b, ll mid) {
	return abs(a - mid) - abs(b - mid);
}

int main() {
	ll a, b; cin >> a >> b;
	if (a < b) swap(a, b);

	ll l = 0L, r = 1000000001L;
	while (r - l > 1) {
		ll mid = (l + r) / 2L;
		ll j = JudgeHarmony(a, b, mid);
		if (j == 0) {
			cout << mid << endl;
			return 0;
		}
		else if (j > 0){
			l = mid;
		}
		else {
			r = mid;
		}
	}

	cout << "IMPOSSIBLE" << endl;
}


Measured memory_bytes: 256
n,m = map(int, input().split())
cond = []
for _ in range(m):
    s,c = map(int, input().split())
    cond.append((s,c))


for i in range(0,1000):
    num_s = str(i)
    if len(num_s) != n:
        continue

    for s,c in cond:
        if len(num_s) < s or num_s[s-1] != str(c):
            break
    else:
        print(i)
        exit()

else:
    print(-1)
    

Measured memory_bytes: 62788
#include <iostream>
#include <vector>
#include <algorithm>
#include <list>
#include <iomanip>
#include <string>
#include <cctype>
#include <cstdio>
#include <cmath>

using namespace std;

int main(){
  int N,K,A;
  cin>>N>>K;
  vector<int> much(N);
  for(int i=0;i<N;i++){
    cin>>A;
    much[i]=A;
  }
  sort(much.begin(),much.end());
  int Ans=0;
  for(int i=0;i<K;i++){
    Ans+=much[i];
  }
  cout<<Ans<<endl;
}

Measured memory_bytes: 3644
// ABC077_C
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <iterator>  // std::back_inserter()
#include <tuple>  // std::tuple std::get
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <algorithm>  // std::copy()
#include <functional>  // std::greater<T>()
#include <utility>  // std::swap()
#include <numeric>  // accumulate(ALL(vec), 0)  0 は初期値
#include <bitset>  // static_cast<std::bitset<8>>
#include <sstream>  // std::stringstream
#include <cmath>
#include <climits>  // INT_MIN
#include <cctype>  // std::isdigit()
#include <iomanip>  // std::setprecision()
using namespace std;

#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, n) for (ll i=0; i < n; i++)  // 0 ~ n-1
#define REPN(i, n) for (ll i=1; i <= n; i++)  // 1 ~ n
#define MIN(vec) min_element(ALL((vec)))  // イテレータのため、値を取り出すときは * を先頭につける
#define MAX(vec) max_element(ALL((vec)))
#define IDX(vec, element_iter) distance((vec).begin(), element_iter)
#define SUM(vec) accumulate(ALL((vec)), 0LL)  // 0 は初期値
#define COPY(vec1, vec2) copy(ALL(vec1), back_inserter(vec2))  // vec1をvec2にコピーする vec2は空にしておく必要あり
#define zero_pad(num) setfill('0') << std::right << setw(num)
#define space_pad(num) setfill(' ') << std::right << setw(num)

typedef long long ll;

const ll MOD7 = 1000000007;  // 1 000 000 007
const ll MOD9 = 1000000009;  // 1 000 000 009

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

    // input
    ll N;
    cin >> N;
    vector<ll> A(N), B(N), C(N);
    REP(i, N) cin >> A[i];
    REP(i, N) cin >> B[i];
    REP(i, N) cin >> C[i];
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    sort(C.begin(), C.end());
    
    // calculation
    ll now_B, num_A, num_C, res = 0;
    ll idx_bound_A, idx_bound_C;
    
    for (ll i = 0; i < N; ++i) {
        now_B = B[i];
        num_A = 0;
        num_C = 0;
        
        // 1 段目: now_B 未満の数を求める
        auto iter_A = lower_bound(A.begin(), A.end(), now_B);
        idx_bound_A = distance(A.begin(), iter_A);
        num_A = (iter_A == A.end())? N: (idx_bound_A + 1) - 1;
        
        // 3 段目: now_B より大きい数
        auto iter_C = upper_bound(C.begin(), C.end(), now_B);
        idx_bound_C = distance(C.begin(), iter_C);
        num_C = (iter_C == C.end())? 0: N - idx_bound_C;
        
        res += num_A*num_C;
    }
    
    cout << res << "\n";
    
    return 0;
}


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

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

    vector<int> vec(N);
    for (int i = 0; i < N; i++){
        cin >> vec.at(i);
    }

    int X = 0;
    int Y = 0;

    for (int k = 0; k < 1000; k++){
        for (int j = 0; j < N; j++){
            if (vec.at(j) % 2 == 1){
                X = 1;
                break;
            } else {
                continue;
            }
        }

        if (X == 1){
            Y = k;
            break;
        } else {
            for (int l = 0; l < N; l++){
                vec.at(l) /= 2;
            }
        }
    }

    cout << Y << endl;

}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int maxn=2005;

struct edge
{
    int v,nxt;
}e[maxn<<1];
int head[maxn],kt;
int siz[maxn],dis[maxn],n;
int dp[maxn],ans=0x3f3f3f3f;
char s[maxn+10];

inline void add(int u,int v)
{
    e[++kt]=(edge){v,head[u]};head[u]=kt;
}

void dfs(int u,int fa=0)
{
    siz[u]=s[u]-'0';
    int mxnd=0;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(v==fa) continue;
        dfs(v,u);
        dis[v]+=siz[v];siz[u]+=siz[v];dis[u]+=dis[v];
        if(dis[v]>dis[mxnd]) mxnd=v;
    }
    if(mxnd==0) {dp[u]=0;return;}
    if(dis[u]>=2*dis[mxnd]) dp[u]=dis[u]/2;
    else dp[u]=dis[u]-dis[mxnd]+min(dp[mxnd],dis[mxnd]-dis[u]/2);
}

int main()
{
    int u,v;
    scanf("%d%s",&n,s+1);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    for(int i=1;i<=n;i++)
    {
        memset(dp,0,sizeof(dp));
        memset(dis,0,sizeof(dis));
        dfs(i,0);
        if(dis[i]&1) continue;
        if(dp[i]*2==dis[i]) ans=min(ans,dp[i]);
    }
    if(ans==0x3f3f3f3f) puts("-1");
    else printf("%d\n",ans);
    return 0;
}

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

using namespace std;
typedef long long ll;
ll a,b,k;
int main()
{
    cin>>a>>b>>k;
    ll x=min(a,k);
    a-=x;
    k-=x;
    ll y=min(b,k);
    b-=y;
    k-=y;
    cout<<a<<" "<<b;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

signed main()
{
    int N; cin>>N;
    vint a(N);
    REP(i,N) cin>>a[i],a[i]--;

    int cur=0;
    for(int i=1;i<=N-1;i++){
        cur=a[cur];
        if(cur+1==2){
            cout<<i<<endl;
            return 0;
        }
    }
    cout<<-1<<endl;
 
}


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

using namespace std;

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

	string s;
	cin >> s;

	if (count(s.begin(), s.end(), '9') != 0) {
		cout << "Yes" << endl;
	}  else {
		cout << "No" << endl;
	}


	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a[200005];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1,greater<int>());
    long long res=0;
    for(int i=1;i<=n/2;i++)
        res+=a[i];
    for(int i=2;i<=(n+1)/2;i++)
        res+=a[i];
    printf("%lld\n",res);
    return 0;
}


Measured memory_bytes: 4596
H, W = STDIN.gets.chomp.split.map(&:to_i)

picture = []
H.times do
    picture.push(STDIN.gets.chomp.split)
end

sharp = ''.rjust(W + 2, "#")
puts sharp

picture.each do |p|
    puts "##{p.join()}#"
end

puts sharp

Measured memory_bytes: 1788
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
C = Counter(a)
s = sum(a)
q = int(input())

for i in range(q):
    b, c = map(int, input().split())
    m = C[b]
    s -= b*m
    s += c*m
    C[b] = 0
    C[c] += m
    print(s)


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

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s; cin >> s;
    string ans = (s=="Sunny" ? "Cloudy" : (s=="Cloudy" ? "Rainy" : "Sunny"));
    cout << ans << endl;
    return 0;
}

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

using namespace std;
typedef long long ll;
const int maxn=2e5+5;
const int INF=1e9+5;
set<int> se;
multiset<int> mse;
int dis[maxn]={0};///到第i位置的最小值
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int h,w;
    cin>>h>>w;
    for(int i=0;i<w;i++)
    {
        se.insert(i);///存目前可以到达的点 （0-w-1）
        mse.insert(0);///存到到达点的距离
    }
    for(int i=0;i<h;i++)
    {
        int l,r;
        cin>>l>>r;
        l--;
        int Min=INF;
        set<int>::iterator it=se.lower_bound(l);
        while(it!=se.end()&&*it<=r)
        {
            int x=*it;
            //cout<<x<<endl;
            Min=min(Min,dis[x]+r-x);
            it=se.erase(it);
            mse.erase(mse.find(dis[x]));
            dis[x]=INF;
        }
        if(r!=w&&Min!=INF)
        {
            dis[r]=Min;
            se.insert(r);
            mse.insert(dis[r]);
        }
        if(!se.empty())
        {
            cout<<*mse.begin()+i+1<<"\n";
        }
        else
        {
            cout<<"-1"<<"\n";
        }

    }
    return 0;
}


Measured memory_bytes: 23192
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  	int a;
	vector<int> n(5);
  	for(int i=0;i<5;i++){
    	cin >> n.at(i);
  		if(n.at(i) != i + 1) {
          a = i + 1;
			break;
        }
    }
  cout << a << endl;
}

Measured memory_bytes: 3588
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define range(a) a.begin(),a.end()
#define print(A,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i];}cout<<endl;
#define pprint(A,m,n) rep(j,0,m){print(A[j],n);}
const long mod=1e9+7;
const int size=2e5;
const int INF=1e9;
int main(){
	long N,K;cin>>N>>K;
	long A[N],B[N]={},C[N]={};long temp=(K*(K-1)/2)%mod;
	rep(i,0,N){
		cin>>A[i];
		rep(j,0,i)if(A[j]>A[i]) B[i]++;
		(B[i]*=K)%=mod;
	}rep(i,0,N){
		rep(j,0,N){
		    if(A[j]>A[i]) C[i]++;
		}(C[i]*=temp)%=mod;
	}
	long b=0,c=0;
	rep(i,0,N){ (b+=B[i])%=mod;(c+=C[i])%=mod; }
	cout<<(b+c)%mod<<endl;
}

Measured memory_bytes: 256
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE TypeFamilies #-}
import           Data.Maybe
import           Data.Int
import           Data.List
import           Data.Char
-- import qualified Data.Vector.Unboxing as VU
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as VM
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import qualified Data.ByteString.Char8 as BS
import           Data.List (scanl')
import           Data.IORef
import           Control.Monad
import           Control.Monad.ST
import           Control.Monad.State.Strict
import           Control.Monad.Primitive
import           Control.Applicative
import           Debug.Trace
import           Text.Printf

main = do
  n <- getInt
  as <- getIntVector
  q <- getInt
  bcs <- VU.replicateM q $ getInt2Tuple
  solver n as q bcs

solver n as q bcs = do
  let vec = countElem n as
      s = sumVec vec
  cVec <- VU.thaw vec
  mutableS <- VUM.replicate 1 s


  forM_ [0..q-1] $ \i -> do
    let (b,c) = bcs VU.! i
    (vanishElem,num) <- numFromVec b cVec
    operation b c cVec
    VUM.modify mutableS (\n -> n + (c*num) - vanishElem) 0
    print =<< VUM.read mutableS 0


numFromVec i vec = do
  n <- VUM.read vec i
  return $ (n*i,n)

sumVec :: VU.Vector Int -> Int
sumVec vec = (\(i,e) -> e) $ VU.foldl' (\(i,e) b -> (i+1, e + (b*i))) (0,0) vec

operation b c vec = do
  temp <- VUM.read vec b
  VUM.write vec b 0
  VUM.modify vec (\n -> n+temp) c
  return ()

countElem n as = VU.create $ do
  vec <- VUM.replicate (10^5 + 1) (0 :: Int)
  forM [0..n-1] $ \i -> do
    VUM.modify vec (+1) (as VU.! i)

  return vec



readInt = BS.readInt . BS.dropWhile isSpace
getVector f = VU.unfoldr f <$> BS.getLine
getIntVector = getVector readInt
getBSVector = getVector BS.uncons
getInt = readLn :: IO Int
getInt2Tuple = (\vec -> (vec VU.! 0, vec VU.! 1)) <$> getIntVector
getInt3Tuple = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2)) <$> getIntVector


Measured memory_bytes: 13264
import java.util.*;
import java.lang.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int T = sc.nextInt();
        int c[] = new int[n];
        int t[] = new int[n];
        for(int i = 0; i < n; i++){
            c[i] = sc.nextInt();
            t[i] = sc.nextInt();
        }
        for(int i = 0; i < n; i++){
            if (t[i] > T) {
                c[i] = 1001;
            }
        }
        int min = 1001;
        for(int i = 0; i < n; i++){
            min = Math.min(min, c[i]);
        }
        if (min == 1001) {
            System.out.println("TLE");
        }else{
            System.out.println(min);
        }
    }
}


Measured memory_bytes: 21844
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<string>
#define MOD 1000000007
typedef long long ll;
using namespace std;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    string s,t; cin >>s >> t;
    t.pop_back();
    if(s == t){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

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

using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()
#define int long long
#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
#define mod 1000000007
#define INF 10e10
template <typename T>

void print(T x)
{
	std::cout << x << " ";
}
template <typename T>

void println(T x)
{
	std::cout << x << "\n";
}

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


void dfs(vector<int>A) {
	if (A.size() == n + 1) {
		int now = 0;
		rep(i, q) {
			if (A[b[i]] - A[a[i]] == c[i])now += d[i];
		}
		ans = max(ans, now);
		return;
	}
	
	A.pb(A.back());
	while (A.back() <= m) {
		dfs(A);
		A.back()++;
		//for (auto a : A)print(a);
		//println("");
	}
}

signed main(void) {
	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));
	print(ans);
}

Measured memory_bytes: 3572
import math
import sys
import collections
import bisect
readline = sys.stdin.readline


def main():
    n = int(readline().rstrip())
    a = [0] * 10100
    for i in range(1, 105):
        for j in range(1, 105):
            for k in range(1, 105):
                m = i ** 2 + j ** 2 + k ** 2 + i * j + j * k + k * i - 1
                if m < 10050:
                    a[m] += + 1
    for s in range(n):
        print(a[s])


if __name__ == '__main__':
    main()


Measured memory_bytes: 9708
#include <iostream>
#include <string>
using namespace std;
int main(void){
    int n;
    cin >> n;
    string str1, str2;
    int taro = 0;
    int hanako = 0;
    for(int i = 0; i < n; i++){
        cin >> str1 >> str2;
        if(str1 > str2)     taro += 3;
        if(str1 < str2)     hanako += 3;
        if(str1 == str2){
            taro++;
            hanako++;
        }
    }
    cout << taro << " " << hanako << endl;
    
    return 0;
}



Measured memory_bytes: 3140
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, m, n) for (int i = m; i < n; ++i)
#define FORR(i, m, n) for (int i = m; i >= n; --i)
#define ALL(v) (v).begin(),(v).end()
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; }
const ll INF=1LL<<60;
const int inf=(1<<30)-1;
const int mod=1e9+7;
int dx[8]={1,0,-1,0,-1,-1,1,1};
int dy[8]={0,1,0,-1,-1,1,-1,1};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;cin >> n;
    int ans=0;
    REP(i,n){
        int a;cin >> a;
        if(i%2==0&&a&1){
            ans++;
        }
    }
    cout << ans << endl;
}

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

public class Main {

  public static void main(String[] args) throws IOException {
    
    try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

      String line;
      int num;
      int result;
      List<Integer> prime = new ArrayList<>(); 
      while(true) {

        if( ((line = br.readLine()) == null) || line.isEmpty() ) break;

        num = Integer.parseInt(line);
        if( num == 0 || num == 1) {
          result = 0;
          System.out.println(result);
          continue;
        }
        
        result = 0;
        prime.clear();
        for ( Integer i = 2; i <= num; i++ ) {
          if( isPrime(i,prime) ) {
            prime.add(i);
            result += 1;
          }
        }
        System.out.println(result);
      }
    }
  }

  public static boolean isPrime(Integer num,List<Integer> prime) {
    Integer k = Double.valueOf( Math.sqrt(num) ).intValue();
    for(Integer i: prime) {
      if ( num % i == 0) return false;
      if ( i > k ) return true;
    }
    return true;
  }
}


Measured memory_bytes: 155460
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define forn(b) for(int i = 0; i < b; i++)
#define rforn(b) for(int i = b - 1 ;i >= 0; i--)
#define It(m) for(auto it = m.begin(); it != m.end(); it++)
#define N 500500
#define PI 3.14159265358979323846264338327950L
#define speed ios_base :: sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
const ll mod = (ll)1e9 + 7;
    
int main() {

    int n; cin >> n;
    vi v(n);
    forn(n) cin >> v[i];
    vector<ll> sum(n);
    ll total = 0;
    for(int i = 0; i < n; i++) {
        total += v[i];
        sum[i] = total;
    }
    ll mn = LONG_LONG_MAX;
    for(int i = 0; i < n - 1; i++) {
        mn = min(mn, abs(total - sum[i] - sum[i]));
    }
    cout << mn;
    return 0;
}


Measured memory_bytes: 5596
#include<bits/stdc++.h>
using namespace std;
#define MAXN	100005
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
vector <int> a[MAXN];
vector <long long> b[MAXN];
int value[MAXN];
bool halted;
void print(int pos) {
	for (unsigned i = 0; i < b[pos].size(); i++)
		cerr << b[pos][i] << ' ';
	cerr << endl;
}
long long work(int pos, int fa) {
	if (a[pos].size() == 1) return value[pos];
	long long sum = 0;
	for (unsigned i = 0; i < a[pos].size(); i++) {
		if (a[pos][i] == fa) continue;
		b[pos].push_back(work(a[pos][i], pos));
		sum += b[pos][b[pos].size() - 1];
	}
	long long tmp = sum - value[pos];
	long long ans = value[pos] - tmp;
	if (tmp < 0 || ans < 0) {
		halted = true;
		return 0;
	}
	long long maxnum = 0;
	for (unsigned i = 0; i < b[pos].size(); i++)
		maxnum = max(maxnum, b[pos][i]);
	if (sum - maxnum >= tmp) return ans;
	else {
		halted = true;
		return 0;
	}
}
int main() {
	int n; read(n);
	for (int i = 1; i <= n; i++)
		read(value[i]);
	for (int i = 1; i < n; i++) {
		int x, y;
		read(x), read(y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	if (n == 2) {
		if (value[1] == value[2]) printf("YES\n");
		else printf("NO\n");
		return 0;
	}
	int root = 1;
	for (int i = 1; i <= n; i++)
		if (a[i].size() >= 2) {
			root = i;
			break;
		}
	if (work(root, 0) == 0 && !halted) printf("YES\n");
	else printf("NO\n");
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;

const ll LongINF=1e13+7;
const int INF=1e9+7;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};

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;}
template <class T, class Y>T GCD(T a, Y b){if(a<b){int c=a;a=b;b=c;}if (a % b == 0){return b;}return GCD(b, a % b);}
template<class T,class Y>T LCM(T a,Y b){return (a*b)/GCD(a,b);}
void clear(queue<pair<int, int>> &q){queue<pair<int, int>> empty;swap(q, empty);} //queueの中身の型は適時変更を忘れない

using vi=vector<int>;
using vii=vector<vi>;

#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define rv reverse
#define ALL(a) (a).begin(),(a).end()
#define decimal(x) fixed<<setprecision(x)


int main(){
    int X;
    cin>>X;
    int a=X%500;
    X=(X/500)*1000;
    X+=(a/5)*5;
    cout<<X<<endl;
    return 0;
}

//a=97,z=122

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <cstdlib>  // abs() for integer
#include <cmath>

using namespace std;

int main(void) {
    
    string S;
    cin >> S;
    vector<int> count(4);
    for (int j=0;j<4;j++){
    for(int i=0;i<4;i++){
        if (i!=j){
        if (S[i]==S[j])
            count[j] ++;}}}
    
    if (count[0]==1 && count[1]==1 &&count[2]==1 && count[3]==1){
        cout << "Yes";
    }
    else cout << "No";
    return 0;
}

Measured memory_bytes: 256
import java.text.DecimalFormat;
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
				Scanner sc = new Scanner(System.in);
		// 整数の入力
		int jisin_nagasa = sc.nextInt();
		int hunsin_nagasa = sc.nextInt();
		int jikan = sc.nextInt();
		int hun = sc.nextInt();

		double jisin_kakudo = (jikan * 60 + hun) * 0.5;
		double hunsin_kakudo = hun * 6;

		double kakudo_sa = 0;

		if (jisin_kakudo > hunsin_kakudo) {
			kakudo_sa = jisin_kakudo - hunsin_kakudo;
		} else {
			kakudo_sa = hunsin_kakudo - jisin_kakudo;
		}

		double b = jisin_nagasa;	//1辺目
		double c = hunsin_nagasa;	//2辺目

		double e = kakudo_sa;			//間の角度

		double r = Math.sqrt(Math.pow(b,2)+Math.pow(c,2) - 2 * b * c * Math.cos(Math.toRadians(e)));

		//この時点でoに数値が入っている
		System.out.println(r);
	}
}

Measured memory_bytes: 35964
'use strict'

function main(input) {
  let a = input.split('\n').map(v => v.split(' ').map(v => ~~v))
  a = a.slice(0, -1)
  const n = a[0][0]
  const m = a[0][1]
  const c = a[0][2]
  const b = a[1]
  let d = a.slice(2, a.length)
  //   console.log(b)
  //   console.log(d[1])
  //   console.log(d[2])

  let cnt = 0
  for (let i = 0; i < n; i++) {
    let tmp = 0
    for (let j = 0; j < m; j++) {
      tmp += d[i][j] * b[j]
    }
    // tmp += c
    if (tmp + c > 0) cnt++
  }

  console.log(cnt)
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'))


Measured memory_bytes: 7372
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;


class DisjointSet{
public:
	vector<int> rank, p;//rank:木の高さ p:親の頂点番号
	DisjointSet(){}
	DisjointSet(int size){//頂点の数
		rank.resize(size, 0);
		p.resize(size, 0);
		rep(i, size) makeSet(i);
	}
	bool same(int x, int y){ //同じ木にあるか
		return findSet(x) == findSet(y);
	}
	void unite(int x, int y){ // 木どうしをくっつける
		link(findSet(x), findSet(y));
	}
private:
	void makeSet(int x){
		p[x] = x;
		rank[x] = 0;
	}
	int findSet(int x){ //親を探す（ルートまで）
		if(x != p[x]){
			p[x] = findSet(p[x]);
		}
		return p[x];
	}
	void link(int x, int y){ //木の高さを考慮して木どうしをくっつける
		if(rank[x] > rank[y]){
			p[y] = x;
		}else{
			p[x] = y;
			if(rank[x] == rank[y]) rank[y]++;
		}
	}
};

int N;
int x[100010], y[100010];
vector<tuple<int, int, int>> g;

int main(void) {
	cin >> N;
	rep(i, N) cin >> x[i] >> y[i];
	vector<tuple<int, int, int>> a(N), b(N);
	rep(i, N) a[i] = make_tuple(x[i], y[i], i), b[i] = make_tuple(y[i], x[i], i);
	sort(all(a)), sort(all(b));

	rep(i, N - 1){
		int u, v;
		u = get<2>(a[i]), v = get<2>(a[i + 1]);
		g.push_back(make_tuple(x[v] - x[u], u, v));
	}
	rep(i, N - 1){
		int u, v;
		u = get<2>(b[i]), v = get<2>(b[i + 1]);
		g.push_back(make_tuple(y[v] - y[u], u, v));
	}

	sort(all(g));
	DisjointSet uf(N + 10);
	ll ans = 0;

	for(auto t : g) {
		int cost, u, v;
		tie(cost, u, v) = t;
		if(!uf.same(u, v)) {
			uf.unite(u, v);
			ans += cost;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 8052
n = int(input())
sp = [list(input().split())+[i+1] for i in range(n)]
for i in range(n):
    sp[i][1] = int(sp[i][1])
sp.sort(key=lambda x:x[1],reverse=True)
sp.sort(key=lambda x:x[0])
for i in sp:
    print(i[2])

Measured memory_bytes: 38512
#include "bits/stdc++.h"

#define REP(i,n) for(ll i=0;i<n;++i)
#define RREP(i,n) for(ll i=n-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<n;++i)
#define RFOR(i,m,n) for(ll i=n-1;i>=m;--i)
#define ALL(v) (v).begin(),(v).end()
#define PB(a) push_back(a)
#define UNIQUE(v) v.erase(unique(ALL(v),v.end()));
#define DUMP(v) REP(i, (v).size()) { cout << v[i]; if (i != v.size() - 1)cout << " "; else cout << endl; }
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
///(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)///
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n;
	cin >> n;
	ll ans = INF;
	for (ll i = 1; i*i <= n; ++i) {
		if (n % i == 0) {
			ans = min(ans, ll(log10((n / i))) + 1);
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 640
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
   
        Scanner sr = new Scanner(System.in);
        int A = sr.nextInt();
        int B = sr.nextInt();
        int C = sr.nextInt();
        int D = sr.nextInt();
        
        int left = A + B;
        int right = C + D;
        
        if(left > right){
            System.out.println("Left");
        }else if(left < right){
            System.out.println("Right");
        }else if(left == right){
            System.out.println("Balanced");
        }
    }
}

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

const ll INF = 1ll << 60;
ll MOD = 998244353;

int main()
{

    int n, x;
    cin >> n >> x;
    //    vector<int> l(n);
    vector<int> d(n + 1);
    d[0] = 0;
    REP(i, n)
    {
        int t;
        cin >> t;
        d[i + 1] = d[i] + t;
    }

    int ans = 0;
    for (int i = 0; i <= n; ++i)
    {
        if (d[i] <= x)
        {
            ans++;
        }
    }
    cout << ans;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long 
#define inf 0x7fffffff
#define infll 0x7fffffffffffffff
#define clr(c) memset(c,0,sizeof(c))
using namespace std;
int mod=998244353;
const int M=1e6+10;
const int N=2e5+10;
inline ll read(){
    ll b=1,sum=0; char c=getchar();
    while(!isdigit(c)){if(c=='-') b=-1; c=getchar();}
    while(isdigit(c)){sum=sum*10+c-'0'; c=getchar();}
    return b*sum;
}
int T,n,m,t,k;
int ans;
int dp[N],a[N];
vector<int> e[N];
vector<int> s;
void dfs(int x,int _fa,int sz) {
	int i,j;
	s.push_back(inf);
	for(int y:e[x]) {
		if(y==_fa) continue;
		int loc=lower_bound(s.begin(),s.begin()+sz,a[y])-s.begin();
		if(loc==sz) {
			s[loc]=a[y];	
			dp[y]=loc+1;
			dp[y]=max(dp[y],dp[x]);
			dfs(y,x,sz+1);
		}
		else {
			int tmp=s[loc];
			s[loc]=a[y];	
			dp[y]=loc+1;
			dp[y]=max(dp[y],dp[x]);
			dfs(y,x,sz);
			s[loc]=tmp;				
		}

	}
}
int main()
{
    int i,j;
    n=read();
    for(i=1;i<=n;i++) {
    	a[i]=read();
	}
	for(i=1;i<=n-1;i++) {
		int x=read(),y=read();
		e[x].push_back(y);
		e[y].push_back(x);
	}
	s.resize(n+1);
	dp[1]=1;
	s[0]=a[1];
	dfs(1,0,1);
	
	for(i=1;i<=n;i++) {
		printf("%d\n",dp[i]);
	}
    return 0;
}


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

using namespace std;

const int N = 1e5, M = 1e6 + 6, OO = 0x3f3f3f3f;

long long n, cnt;
map<string, long long> s;
string h;
int main()
{
	cin >> n;
	while(n--)
	{
		cin >> h;
		sort(h.begin(), h.end());
		s[h]++;
	}
	for(auto v : s)
	{
		v.second--;
		cnt += (v.second * (v.second + 1) / 2);
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 11136
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>

typedef long long unsigned int ll;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

using namespace std;

int main()
{
	string ans;
	int a;
	string s;
	cin >> a;
	cin >> s;
	
	if (a >= 3200) {
		ans = s;
	}
	else {
		ans = "red";
	}
	cout << ans << endl;
}



Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main{
	static final int MAX = 1000;
	static final int VMAX = 100000;

	static int n, s;
	static int []A = new int[MAX];
	static int []B = new int[MAX];
	static int []T = new int[VMAX + 1];
	static int solve() {
		int ans = 0;
		boolean []V = new boolean[MAX];
		for(int i = 0; i < n; i++) {
			B[i] = A[i];
			V[i] = false;
		}
		Arrays.sort(B, 0, n);
		for(int i = 0; i < n; i++) {
			T[B[i]] = i;
		}
		for(int i = 0; i < n; i++) {
			if(V[i]) continue;
			int cur = i;
			int S = 0;
			int  m = VMAX;
			int an = 0;
			while(true) {
				V[cur] = true;
				an ++;
				int v = A[cur];
				m = Math.min(m, v);
				S += v;
				cur = T[v];
				if(V[cur]) {
					break;
				}

			}
			ans += Math.min(S + (an - 2) * m, m + S + (an + 1) * s);
		}
		return ans;
	}
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		s = VMAX;
		for(int i = 0; i < n; i++) {
			A[i] = scan.nextInt();
			s = Math.min(s, A[i]);
		}
		scan.close();
		int ans = solve();
		System.out.println(ans);
	}
}


Measured memory_bytes: 30672
#include<stdio.h>
#include<string.h>
typedef long long ll;
const ll inf=1e18;
void fmin(ll&a,ll b){
	b<a?a=b:0;
}
int p[5010];
ll f[5010],g[5010],tf[5010],tg[5010];
int main(){
	int n,a,b,i,j;
	ll t;
	scanf("%d%d%d",&n,&a,&b);
	for(i=1;i<=n;i++){
		scanf("%d",&j);
		p[j]=i;
	}
	for(i=1;i<=n;i++){
		t=inf;
		for(j=1;j<=n;j++){
			fmin(t,g[j-1]);
			tf[j]=t+(p[i]<j?a:(p[i]>j?b:0));
			fmin(t,f[j]);
		}
		t=inf;
		for(j=0;j<=n;j++){
			fmin(t,g[j]);
			tg[j]=t+(p[i]<=j?a:(p[i]>j?b:0));
			fmin(t,f[j+1]);
		}
		memcpy(f,tf,sizeof(tf));
		memcpy(g,tg,sizeof(tg));
	}
	t=inf;
	for(i=1;i<=n;i++)fmin(t,f[i]);
	for(i=0;i<=n;i++)fmin(t,g[i]);
	printf("%lld",t);
}

Measured memory_bytes: 384
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <numeric>

using namespace std;

typedef long long int ll;
typedef long int li;

int main(){
    ll ans=0;
    ll a,b,k,j;
    j=0;
    cin >> a >> b >> k;
    for(ll i=max(a,b);i>0;i--){
    if(a%i==0&&b%i==0)j++;
      if(j==k){ans=i;break;}
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 256
#!/usr/bin/env python3

def main():
    n, u, v = map(int, input().split())
    u -= 1
    v -= 1
    adj = [[] for i in range(n)]
    for i in range(n - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        adj[a].append(b)
        adj[b].append(a)

    # uv間経路を求める
    st = [u]
    prev = [None for i in range(n)]
    while st:
        x = st.pop()
        for y in adj[x]:
            if y == prev[x]: continue
            prev[y] = x
            st.append(y)
    path = [v]
    while path[-1] != u:
        path.append(prev[path[-1]])
    path = list(reversed(path))

    # crossからsquareを経由しない最遠ノードstarを求める（a59p22）
    l = len(path) - 1
    cross = path[(l - 1) // 2]
    square = path[(l - 1) // 2 + 1]
    st = [(cross, 0)]
    prev = [None for i in range(n)]
    dist = [-1 for i in range(n)]
    while st:
        x, d = st.pop()
        dist[x] = d
        for y in adj[x]:
            if y == prev[x]: continue
            if y == square: continue
            prev[y] = x
            st.append((y, d + 1))
    star_square = max(dist)

    if l % 2 == 1:
        res = (l - 1) // 2 + star_square
    else:
        res = (l - 1) // 2 + star_square + 1
    print(res)

if __name__ == "__main__":
    main()


Measured memory_bytes: 25724
#include<stdio.h>
 
int main(){
  int a,b,c,d,e,f;
  float x,y;
  while(scanf("%d %d %d %d %d %d",&a,&b,&c,&d,&e,&f)!=EOF){
    x = (float)(c*e-b*f)/(a*e-d*b);
    y = (float)(c*d-a*f)/(b*d-a*e);
    if(-0.0005<x && x<=0)
      x=0;
    if(-0.0005<y && y<=0)
      y=0;
    printf("%.3f %.3f\n",x,y);
  }
  return 0;
}

Measured memory_bytes: 632
# coding: utf-8
def isKaibun(kaibun):
    for i in range(len(kaibun) // 2):
        if kaibun[i] != kaibun[-i-1]:
            return False
    return True

s = input()
s_len = len(s)
flag1 = isKaibun(s)
flag2 = isKaibun(s[:(s_len-1) // 2])
flag3 = isKaibun(s[(s_len+2) // 2:])
if flag1 and flag2 and flag3:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main(){
    long n;
    cin>>n;
    vector<long long> abcde(5);
    long v=1e15;
    for(int i=0;i<5;i++){
        cin>>abcde[i];
        if(abcde[i]<v)v=abcde[i];
    } 
    printf("%ld\n",(long)ceil(n/(v*1.0))+4);
    return 0;
}


Measured memory_bytes: 256
//by yjz
#include<bits/stdc++.h>
using namespace std;
#define FF first
#define SS second
#define PB push_back
#define MP make_pair
#define bged(v) (v).begin(),(v).end()
#define foreach(it,s) for(__typeof((s).begin()) it=(s).begin();it!=(s).end();it++)
typedef long long ll;
const int Imx=2147483647;
const ll Lbig=2e18;
const int mod=1e9+7;
//My i/o stream
struct fastio
{
	char s[100000];
	int it,len;
	fastio(){it=len=0;}
	inline char get()
	{
		if(it<len)return s[it++];it=0;
		len=fread(s,1,100000,stdin);
		if(len==0)return EOF;else return s[it++];
	}
	bool notend()
	{
		char c=get();
		while(c==' '||c=='\n')c=get();
		if(it>0)it--;
		return c!=EOF;
	}
}_buff;
#define geti(x) x=getnum()
#define getii(x,y) geti(x),geti(y)
#define getiii(x,y,z) getii(x,y),geti(z)
#define puti(x) putnum(x),putchar(' ')
#define putii(x,y) puti(x),puti(y)
#define putiii(x,y,z) putii(x,y),puti(z)
#define putsi(x) putnum(x),putchar('\n')
#define putsii(x,y) puti(x),putsi(y)
#define putsiii(x,y,z) putii(x,y),putsi(z)
inline ll getnum()
{
	ll r=0;bool ng=0;char c;c=_buff.get();
	while(c!='-'&&(c<'0'||c>'9'))c=_buff.get();
	if(c=='-')ng=1,c=_buff.get();
	while(c>='0'&&c<='9')r=r*10+c-'0',c=_buff.get();
	return ng?-r:r;
}
template<class T> inline void putnum(T x)
{
	if(x<0)putchar('-'),x=-x;
	register short a[20]={},sz=0;
	while(x)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1;i>=0;i--)putchar('0'+a[i]);
}
inline char getreal(){char c=_buff.get();while(c==' '||c=='\n')c=_buff.get();return c;}
int n;
int a[11];
int main()
{
	geti(n);
	ll ans=1,tmp=1;
	for(int i=1;i<=n;i++)
	{
		ans=ans*3;
		int x;
		geti(x);
		if(x%2==0)tmp=tmp*2;
	}
	cout<<ans-tmp<<endl;
	return 0;
}


Measured memory_bytes: 384
n=int(input())
res = []
for i in range(n):
    s,p=map(str, input().split())
    res += [(s,int(p))]
res1=res
res = sorted(res, key=lambda x:(x[0],-x[1]))
for i in range(n):
    print(res1.index(res[i])+1)
 

Measured memory_bytes: 9156
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
char s[15];
int main()
{
	scanf("%s",s+1);
	int l=strlen(s+1);
	if(l<4) {
		cout<<"No";
		return 0;
	}
	if((s[1]=='Y')&&(s[2]=='A')&&(s[3]=='K')&&(s[4]=='I')) {
		cout<<"Yes";
	}
	else cout<<"No";
	return 0;
	
}
 

Measured memory_bytes: 256
N, K=map(int, input().split())
Pn=list(map(int, input().split()))
V = [0] * N
ans = [0] * K
max_v = 0
sum_v = 0
for n in range(N):
    V[n] = (0.5*Pn[n]*(Pn[n]+1))/Pn[n]
    if n < K:
        sum_v += V[n]
        max_v = sum_v
    else:
        sum_v = sum_v - V[n-K] + V[n]
        max_v = max(max_v, sum_v)
print(max_v)

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

using namespace std;

#define WA(x) #x << " = " << x << '\n'
#define FOR(i, n) for(int i = 0; i<(int) n; i++)
#define all(x) x.begin(), x.end()
#define PB push_back
#define F first
#define S second

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;

const int INF = 1e9+10;

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

	int n; cin >> n;
	FOR(i, n){
		int x; cin >> x;
		if(x%2 == 0 && !(x%3 == 0 || x%5 == 0)){
			cout << "DENIED\n";
			return 0;
		}
	}
	cout << "APPROVED\n";

	return 0;
}

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


public class Main {
    static long mod = 1000000000+7;
    static int maxn=2;
    static long[] frac, inv;
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        //BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        //String[] buf = reader.readLine().split(" ");
        int n = sc.nextInt(), m = sc.nextInt();
        int k = sc.nextInt();
        maxn = n*m;
        init();
        long ans = 0,time = comb(k-2,n*m-2);
        for(long row=1;row<=n;row++){
            for(long col=1;col<=m;col++){
                // first compute the yi part
                /*ans  = (ans + (m*row*(row-1)/2%mod)*time%mod)%mod;
                long neg = ((n-row)*(n-row+1)/2)%mod*time%mod;
                ans = (ans-neg+2*mod*/
                long pos = row*(row-1)*m%mod*time%mod;
                long neg = row*m*(n-row)%mod*time%mod;
                // then do the xi part
                pos += col*n*(col-1)%mod*time%mod;
                neg += col*n*(m-col)%mod*time%mod;
                pos %= mod; neg %=mod;
                ans = (ans+pos-neg+10*mod)%mod;
            }
        }
        System.out.println(ans);
    }
    static long comb(int m, int n){
        if(m>n) return 0;
        // we should put m<=n
        return frac[n]*inv[m]%mod*inv[n-m]%mod;
    }
    static void init(){
        frac = new long[maxn+1]; inv = new long[maxn+1];
        frac[0]=1; inv[0]=1;
        for(int i=1;i<=maxn;i++) frac[i]=frac[i-1]*i%mod;
        inv[maxn] = pow(frac[maxn],mod-2);
        for(int i=maxn-1;i>=1;i--){
            inv[i] = inv[i+1]*(i+1)%mod;
        }
    }
    static long pow(long base, long t){
        long ans = 1;
        while(t>0){
            if(t%2==1) ans = ans*base%mod;
            t /= 2;
            base = base*base%mod;
        }
        return ans;
    }
}



Measured memory_bytes: 26068