akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;

public static class Program
{
    public static void Main(string[] args)
    {
        var input = Console.ReadLine().Trim();
        long k = long.Parse(Console.ReadLine().Trim());

        long kisuCount = 0;
        long gusuCount = 0;
        char lastChar = '@';

        char gusuLast, kisuLast;
        foreach (char c in input)
        {
            if (lastChar == c)
            {
                lastChar = '@';
                kisuCount++;
            }
            else
            {
                lastChar = c;
            }
        }
        gusuLast = lastChar;
        foreach (char c in input)
        {
            if (lastChar == c)
            {
                lastChar = '@';
                gusuCount++;
            }
            else
            {
                lastChar = c;
            }
        }
        kisuLast = lastChar;
        long result;
        if (gusuLast == '@')
        {
            result = kisuCount * k;
        }
        else if(gusuLast != kisuLast)
        {
            result = kisuCount * (k - k / 2) + gusuCount * (k / 2);
        }
        else
        {
            result = kisuCount + gusuCount * (k - 1);
        }

        Console.WriteLine(result);
    }
}

Measured memory_bytes: 11220
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())

const int MAX = 510000;
const int MOD = 1000000007;

class UnionFind{
public:
    //親の番号を格納する。親だった場合は-(その集合のサイズ)
    vector<int> Parent;

    //作る時はParentの値を全て-1にする
    //こうするとずべてバラバラになる
    UnionFind(int N){
      Parent = vector<int>(N,-1);
    }

    //Aがどのグループに属しているのか調べる
    int root(int A){
      if(Parent[A]<0) return A;
      return Parent[A] = root(Parent[A]);
    }

    //自分のいるグループの頂点数を調べる
    int size(int A){
      return -Parent[root(A)];//親を取ってきたい
    }

    //AとBをくっつける
    bool connect(int A,int B){
      //AとBを直すつつなぐのではなく、root(A)にroot(B)をくっつける)
      A = root(A);
      B = root(B);
      if(A==B){
        //すでにくっついているからくっつけない
        return false;
      }
      //大きい方(A)に小さい方(B)をくっつけたい
      //大小が逆だったらひっくり返しちゃう
      if(size(A)<size(B)) swap(A,B);

      //Aのサイズを更新する
      Parent[A] += Parent[B];
      //Bの親をAに変更する
      Parent[B] = A;

      return true;
    }
  };


int main(){
  ll N,K,L; cin>>N>>K>>L;

  UnionFind s(N);
  UnionFind t(N);
  //Unionfindの入力
  rep(i,K){
    int a,b;cin>>a>>b;
    s.connect(a-1,b-1);
  }
  rep(i,L){
    int a,b;cin>>a>>b;
    t.connect(a-1,b-1);
  }

  //どちらもconnectな都市をcount
  map <P, int> m;
  rep(i,N){
    m[mp(s.root(i), t.root(i))]++;
  }
  rep(i,N){
    cout<<m[mp(s.root(i), t.root(i))]<<" ";
  }
  cout<<endl;


}


Measured memory_bytes: 13568
import numpy as np
s=input()
A=np.array([0,0,0,0])
B=np.array([0,0,0,0])
C=np.array([0,0,0,0])
t=0
for c in s:
	if c=="A":
		A[0]+=1
	if c=="B":
		B+=A
	if c=='C':
		C+=B
	if c=='?':
		C[1]+=B[0]
		C[2]+=B[1]
		C[3]+=B[2]
		B[1]+=A[0]
		B[2]+=A[1]
		A[1]+=1
		t+=1
ans=0
for i in range(4):
	ans+=pow(3,t-i)*C[i]
print(int(ans%1000000007))

Measured memory_bytes: 21652
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<functional>
#include<math.h>
using namespace std;
#define N (1000000000+7)
#define M (998244353)
#define INF 1e16
typedef long long ll;
typedef pair<int,vector<ll> > P;
typedef pair<P,ll>Q;
 

int main(void){
    string s;
    cin>>s;
    if(s=="ABC")cout<<"ARC";
    else cout<<"ABC";
    cout<<endl;
    return 0;
}

Measured memory_bytes: 3628
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<math.h>
#include<map>

#define MOD 1e9+7;
#define INF 1e17+9;
#define PI acos(-1);

using namespace std;

int main() {

	long long n,k;
	cin >> n >> k;
	vector<long long> A(n);
	map<long long,long long> mp;
	
	for(long long i=0;i<n;i++){
		cin >> A[i];
		mp[A[i]]++;
	}
	
	vector<pair <long long,long long>> pa;
	
	long long cnt=0;
	for(auto p=mp.begin();p!=mp.end();p++){
		pa.push_back({p->second,p->first});
		cnt++;
	}
	
	sort(pa.begin(),pa.end());
	
	if(cnt<=k){
		cout << "0" << endl;
	}else{
		long long r=cnt-k;
		long long ans=0;
		for(long long i=0;i<r;i++){
			ans+=pa[i].first;
		}
		cout << ans << endl;
	}
	return 0;
}


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

typedef long long int ll;

using namespace std;

int main(void)
{
    string s;
    cin>>s;

    vector<int> v;
    for(int i = 0;i < s.size();i++)
    {
	if(s[i] == '0')
	    v.push_back(0);
	else if(s[i] == '1')
	    v.push_back(1);
	else if(s[i] == 'B' && v.size() != 0)
	    v.erase(--v.end());
    }

    for(int i = 0;i < v.size();i++)
	cout<<v[i];

    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<string> vs;
typedef vector<bool> vb;

const ll mod=1e9+7;
const ll inf=1e16;

#define rep(i,m,n) for(ll i=m;i<n;i++)
#define repr(i,m,n) for(ll i=m-1;i>=n;i--)
#define fi first
#define se second
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
#define eb(x) emplace_back(x)
#define all(x) x.begin(),x.end()
#define gll greater<ll>()

void solve(){
  double a,b,h,m;
  cin >> a >> b >> h >> m;
  
  double rad1=30.0*h+0.5*m;
  double rad2=6.0*m;
  
  double dis=abs(rad2-rad1);
  if(dis>=180.0) dis=360.0-dis;
  
  cout << setprecision(12) << sqrt(a*a+b*b-2*a*b*cos(acos(-1.0)*dis/180.0)) << endl;
  
}
int main(){
   cin.tie(nullptr);
  ios::sync_with_stdio(false);
  solve();
}  

Measured memory_bytes: 4248
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <string>

using namespace std;
typedef long long ll;
#define rep(i,s,n)for(ll i = s;i<n;i++)
#define repe(i,s,n)for(ll i = s;i<=n;i++)
static const ll maxLL = (ll)1 << 62;

double W[1000];
ll wp = 0;
double S[10000000];
ll sp = 0;

int main() {
	double A, B, C, D, E, F; cin >> A >> B >> C >> D >> E >> F;

	double maxn = 0;
	double maxws = 0;
	double maxs = 0;

	set<double> w;
	set<double> s;
	repe(a, 0, F / 100 * A) {
		repe(b, 0, F / 100 * A) {
			if (a * 100 * A + b * 100 * b <= F) {
				w.insert(a * 100 * A + b * 100 * B);
				//W[wp++] = a * 100 * A + b * 100 * b;
			}
		}
	}
	repe(c, 0, F / C) {
		repe(d, 0, F / D) {
			if (c * C + d * D <= F) {
				s.insert(c * C + d * D);
				//S[sp++] = c * C + d * D;
			}
		}
	}

	for (set<double>::iterator itw = w.begin(); itw != w.end(); itw++) {
		double W = *itw;
		for (set<double>::iterator its = s.begin(); its != s.end(); its++) {
			double S = *its;
			if (W + S <= F) {
				double T = W + S;
				if (T != 0 && (S / T) <= (E / (100 + E))) {
					double n = 100 * S / T;
					if (maxn <= n) {
						maxn = n;
						maxws = T;
						maxs = S;
					}
				}
			}
		}
	}

	cout << maxws << " " << maxs << endl;
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <limits>
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
using namespace std;
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(a > b){ a = b; return 1; } return 0; }
using ll = long long; using ld = long double;
using pi = pair<int,int>; using pl = pair<ll,ll>;
using vi = vector<int>; using vii = vector<vi>;
using vl = vector<ll>; using vll = vector<vl>;
const int inf = numeric_limits<int>::max();
const ll infll = numeric_limits<ll>::max();
//----------------------------
// 抽象化セグ木
// 二項演算と単位元を渡して使ってね
///****例****************************
//  auto f = [&](int a,int b){ return a+b;}; // 二項演算:和
//  ll id = 0; //単位元:0
//  SegTree<decltype(f),ll> seg(f,id);
//************************************
//----------------------------

template <typename F,typename T>
struct SegTree{
  // 二項演算merge,単位元identify
  T identity;
  F merge; 
  int size;
  vector<T> dat;
  
  // 二項演算fと単位元idを渡して宣言する
  SegTree(F f,T id):merge(f),identity(id){}

  // データの要素の数nを渡して初期化、sizeはnより大きい2の冪乗
  void init(int n){
    size = 1;
    while(size<=n) size *= 2;
    dat.resize(size*2-1,identity);
  }

  // 配列を渡して0(n)で初期化
  void build(vector<T> vec){
    rep(i,vec.size()) dat[size-1+i] = vec[i];
    dfs(0);
  }
  
  T dfs(int k){
    if(k>=size-1) return dat[k];
    else return dat[k] = merge(dfs(2*k+1),dfs(2*k+2));
  }

  // index kの要素をaに変更
  void update(int k,T a){
    k += size - 1;
    dat[k] = a;
    while(k > 0){
      k = (k-1)/2;
      dat[k] = merge(dat[2*k+1],dat[2*k+2]);
    }
  }
  
  // index kの要素にaを加算
  void add(int k,T a){
    k += size - 1;
    dat[k] += a;
    while(k > 0){
      k = (k-1)/2;
      dat[k] = merge(dat[2*k+1],dat[2*k+2]);
    }
  }

  // 区間[a,b)に対するクエリに答える。(k,l,r)=(0,0,size)
  T query(int a,int b,int k,int l,int r){
    if(r<=a||b<=l) return identity;
    
    if(a<=l&&r<=b) return dat[k]; 
    else return merge(query(a,b,2*k+1,l,(l+r)/2),query(a,b,2*k+2,(l+r)/2,r));
  }

  T query(int a,int b){
    return query(a,b,0,0,size);
  }
  
  // デバッグ用
  void show(){
    int index = 0;
    int num = 1;
    while(index<size){
      rep(i,num){
	if(dat[i+index]==identity) cout << "e ";
	else cout << dat[i+index] << " ";
      }
      cout << "\n";
      num *= 2;
      index = index*2+1;
    }
  }
  
  
};

int main()
{
  auto f = [&](int a,int b){ return max(a,b);}; 
  int id = 0; //単位元:0
  SegTree<decltype(f),int> seg(f,id);

  int n,k; cin >> n >> k;
  vi a(n);
  rep(i,n) cin >> a[i];

  seg.init(300010);
  
  vi dp(n);
  int res = 1;
  rep(i,n) {
    dp[i] = seg.query(max(0, a[i]-k), min(300002, a[i]+k)+1) + 1;
    seg.update(a[i], dp[i]);
    chmax(res, dp[i]);
  }
  cout << res << "\n";
  
  return 0;
}


Measured memory_bytes: 9248
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int line1 = sc.nextInt();
		int line2 = sc.nextInt();
		int line3 = sc.nextInt();
		
		if(line1 < line3 && line3 < line2 || line2 < line3 && line3 < line1) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}

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

using namespace std;

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

    int q;
    cin>>q;

    multiset<int> Set;
    while(q--)
    {
        int op,x;
        cin>>op>>x;

        if(!op)
        {
            Set.insert(x);
            cout<<Set.size()<<endl;
        }else if(op==1)
        {
            cout<<Set.count(x)<<endl;
        }else if(op==2)
        {
            Set.erase(x);
        }else if(op==3)
        {
            int l=x,r,cnt=0;
            cin>>r;
            for(auto i=Set.lower_bound(l);i!=Set.end()&&*i<=r;i++)
                cout<<*i<<endl;
        }
    }

    return 0;
}




Measured memory_bytes: 12372
#include <bits/stdc++.h>
#define INF 1e+18
#define int long long
using namespace std;

signed main(){
	int n,m,ans = 0,sum = 0;
	map<int,int> mp;
	cin >> n >> m;
	for(int i = 0;i < n;i++){
		int a;
		cin >> a;
		mp[a]++;
	}
	for(int i = 0;i < m;i++){
		int a,b;
		cin >> a >> b;
		mp[b] += a;
	}
	for(auto it = mp.rbegin();it != mp.rend();it++){
		int num = min(n - sum,(*it).second);
		sum += num;
		ans += num * (*it).first;
	}
	cout << ans << endl;
}

Measured memory_bytes: 12800
#include<cstdio>
#include<iostream>
using namespace std;
int n;
int k,a,b;
char s[2];
int ans=0;
int sum[2010][2010][2];
int t1,t2;
int qzh(int x1,int ckw,int x2,int y2,bool p)
{
	if (x1<0||ckw<0||x2<0||y2<0) return 0;
	if (x1==0&&ckw==0) return sum[x2][y2][p];
	if (x1==0) return sum[x2][y2][p]-sum[x2][ckw-1][p];
	if (ckw==0) return sum[x2][y2][p]-sum[x1-1][y2][p];
	return sum[x2][y2][p]-sum[x2][ckw-1][p]-sum[x1-1][y2][p]+sum[x1-1][ckw-1][p];
}
int main()
{
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++)
	{
		scanf("%d%d%s",&a,&b,s);
		if (s[0]=='B') sum[a%(2*k)][b%(2*k)][1]++;
		else sum[a%(2*k)][b%(2*k)][0]++;
	}
	for (int i=1;i<2*k;i++)
	{
		sum[i][0][0]+=sum[i-1][0][0];sum[0][i][0]+=sum[0][i-1][0];
		sum[i][0][1]+=sum[i-1][0][1];sum[0][i][1]+=sum[0][i-1][1];
	}
	for (int i=1;i<2*k;i++)
		for (int j=1;j<2*k;j++)
		{
			sum[i][j][0]+=sum[i-1][j][0]+sum[i][j-1][0]-sum[i-1][j-1][0];
			sum[i][j][1]+=sum[i-1][j][1]+sum[i][j-1][1]-sum[i-1][j-1][1];
			//cout<<i<<" "<<j<<" "<<sum[i][j][0]<<" "<<sum[i][j][1]<<endl;
		}
	for (int i=0;i<k;i++)
		for (int j=0;j<k;j++)
		{
			t1=qzh(0,0,i-1,j-1,0)+qzh(i,j,i+k-1,j+k-1,0)+qzh(i+k,j+k,2*k-1,2*k-1,0)+qzh(0,j+k,i-1,2*k-1,0)+qzh(i+k,0,2*k-1,j-1,0)+qzh(i,0,i+k-1,j-1,1)+qzh(0,j,i-1,j+k-1,1)+qzh(i+k,j,2*k-1,j+k-1,1)+qzh(i,j+k,i+k-1,2*k-1,1);
			t2=qzh(0,0,i-1,j-1,1)+qzh(i,j,i+k-1,j+k-1,1)+qzh(i+k,j+k,2*k-1,2*k-1,1)+qzh(0,j+k,i-1,2*k-1,1)+qzh(i+k,0,2*k-1,j-1,1)+qzh(i,0,i+k-1,j-1,0)+qzh(0,j,i-1,j+k-1,0)+qzh(i+k,j,2*k-1,j+k-1,0)+qzh(i,j+k,i+k-1,2*k-1,0);
			ans=max(ans,max(t1,t2));
		}
	printf("%d",ans);
}

Measured memory_bytes: 31616
#include <iostream>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <map>
#include <queue>
#include <string>
#include <vector>
#include <ostream>
#include <cstring>
#include <cmath>
#include <cstdio>

using std::cin;
using std::cout;
using std::cerr;
using std::endl;

inline void init() {
  cin.tie(0);
  std::ios::sync_with_stdio(false);
}

int main() {
  init();

  int N, C;
  int d[31][31], c[501][501];


  cin >> N >> C;
  for (int i = 0; i < C; ++i) {
    for (int j = 0; j < C; ++j) {
      cin >> d[i][j];
    }
  }

  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      cin >> c[i][j];
      c[i][j]--;
    }
  }

  int cost[3][31];
  std::memset(cost, 0, sizeof cost);

  // mod 0, 1, 2 のマスの各色への書き換えの総コストを調べる
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      for (int color = 0; color < C; ++color) {
        cost[(i + j) % 3][color] += d[c[i][j]][color];
      }
    }
  }

  int ans = int(1e9);

  int b = (1 << 3) - 1;
  while (b < (1 << C)) {
    std::vector<int> colors(3);
    int idx = 0;

    for (int i = 0; i < C; ++i) {
      if (((b >> i & 1)) == 1) {
        colors[idx++] = i;
      }
    }

    do {
      int tmp = 0;
      for (int i = 0; i < 3; ++i) {
        tmp += cost[i][colors[i]];
      }

      ans = std::min(ans, tmp);
    } while (std::next_permutation(colors.begin(), colors.end()));

    int x = b & -b, y = b + x;
    b = ((b & ~y) / x >> 1) | y;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1280
END { load __FILE__ unless $stdin.eof? }

n = gets.to_i
part_sup = n * (n + 1) * (n + 2) / 6

edges = Array.new(n - 1) { gets.split.map!(&:to_i).sort! }
puts part_sup - edges.sum { |u, v| u * (n - v + 1) }


Measured memory_bytes: 28720
/*
[abc130] F - Minimum Bounding Box
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;

const int MAX_N = 1e5;
const int MAX_XY = 1e8;
const double INF = 1e18;

int dxy[2][4] = {{0, 1, 0, -1}, {1, 0, -1, 0}};

int N;
int xy[2][MAX_N];
int d[MAX_N];

double calc(double t) {
    double m[2][2];
    for (int c = 0; c < 2; c++) {
        m[c][0] = INF;
        m[c][1] = -INF;
        for (int i = 0; i < N; i++) {
            m[c][0] = min(m[c][0], xy[c][i] + dxy[c][d[i]] * t);
            m[c][1] = max(m[c][1], xy[c][i] + dxy[c][d[i]] * t);
        }
    }

    return (m[0][1] - m[0][0]) * (m[1][1] - m[1][0]);
}

double solve() {
    double l = 0, r = 2 * MAX_XY + 1;
    for (int i = 0; i < 200; i++) {
        double m1 = (2 * l + r) / 3.0, m2 = (l + 2 * r) / 3.0;
        if (calc(m1) < calc(m2)) {
            r = m2;
        } else {
            l = m1;
        }
    }

    return calc(l);
}

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        char d_raw;
        cin >> xy[0][i] >> xy[1][i] >> d_raw;
        switch (d_raw) {
            case 'U':
                d[i] = 0;
                break;
            case 'R':
                d[i] = 1;
                break;
            case 'D':
                d[i] = 2;
                break;
            case 'L':
                d[i] = 3;
                break;
        }
    }

    cout << setprecision(16) << fixed << solve() << endl;

    return 0;
}


Measured memory_bytes: 1408
#include <iostream>
#include <vector> 
#include <cmath>
using namespace std;

#define int long long

signed main() {
    vector<int> x(5);
    for(int i = 0; i < 5; i++) cin >> x[i];

    for(int i = 0; i < 5; i++) {
        if(x[i] == 0) {
            cout << i + 1 << endl;
            return 0;
        }
    }
}

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

int main()
{
    int n;
    cin >> n;
    int loan = 100000;
    for(int i=0; i<n; i++){
        loan = loan * 1.05;
        if(loan%1000 != 0){
            loan = loan/1000;
            loan = loan * 1000;
            loan = loan + 1000;
        }
    }

    
    cout <<loan<<endl;
    
    return 0;
}

Measured memory_bytes: 1160
(N,Y) = [int(i) for i in input().split()]
 
y10k = Y // 10000
y5k, y1k = divmod((Y%10000)/1000, 5)
 
current_inbag = y10k+y5k+y1k
diff = N - current_inbag
 
if Y > 10000*N or Y < 1000*N or diff < 0:
    print('-1 -1 -1')
    exit()
 
while y10k > 0 and diff >= 9:
    y10k -= 1
    y1k += 10
    diff -= 9

if y10k > 0 and diff >= 5:
    y10k -= 1
    y5k += 1
    y1k += 5
    diff -= 5

while y10k > 0 and diff > 0:
    y10k -= 1
    y5k += 2
    diff -= 1

if y10k == 0 and diff > 0:
    while y5k > 0 and diff >= 4:
        y5k -= 1
        y1k += 5
        diff -= 4

if diff == 0:
    print('%d %d %d' % (y10k,y5k,y1k))
    exit()

print('-1 -1 -1')

Measured memory_bytes: 3064
import sys
input = sys.stdin.readline

k, a, b = map(int, input().split())
ans = 1

if (b - a) <= 2:
    ans += k
else:
    if k < a:
        ans += k
    else:
        ans = a
        k_ = k - a + 1
        ans += (b-a)*(k_//2)
        if k_ % 2 == 1:
            ans += 1

print(ans)

Measured memory_bytes: 3060
INF = int(1e9)

def main():
    n, m = map(int, input().split())
    a = [int(i) for i in input().split()]
    a.sort()
    s = [0]
    for i in range(n):
        s.append(s[i]+a[i])
    #Xより大きい要素の数を数える
    def counter(x):
        count = 0
        for i in range(n):
            l = -1
            r = n
            while r-l>1:
                mid = (l+r)//2
                if a[i] + a[mid] > x:
                    r = mid
                else:
                    l = mid
            count += n-r
        return count
    
    #Xより大きい要素数がm個未満であるXのうち最大のものを探す
    l = 0 
    r = INF
    while r-l>1:
        mid = (l+r)//2
        if counter(mid) < m:
            r = mid
        else:
            l = mid

    #lより大きい要素の総和を求める 
    def sigma(x):
        cnt = 0
        sgm = 0
        for i in range(n):
            l = -1
            r = n
            while r-l >1:
                mid = (l+r)//2
                if a[i]+a[mid]>x:
                    r = mid
                else:
                    l = mid
            cnt += n-r
            sgm += a[i] * (n-r) + (s[n]-s[r])
        return (sgm, cnt)

    sgm, cnt = sigma(l)
    ans = sgm+(m-cnt)*r
    print(ans)
main()

Measured memory_bytes: 58624
#include <bits/stdc++.h>
   
using namespace std;
#define ll long long
#define ld long double
#define pll pair<long long,long long>
#define vll vector<long long>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define deb(x) cout << #x << "=" << x << endl
#define F(i,a,b) for(ll i=a;i<=b;i++)
#define RF(i,a,b) for(ll i=a;i>=b;i--)
#define in(a,n) F(i,0,n-1)cin>>a[i]
#define vi vector<int>
#define out(a,n) F(i,0,n-1)cout<<a[i]<<" ";cout<<endl
#define mod 998244353
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
#define int long long

const int N = 1e5 + 5;
 	int connected;
	int par[N], sz[N];
 
struct DSU
{
 
	void init(int n) 
	{
		for(int i=1;i<=n;i++)
		{
			par[i]=i;
			sz[i]=1;
		}
		connected=n;
	}
 
	int getPar(int k)
	{
		while(k!=par[k])
		{
			par[k]=par[par[k]];
			k=par[k];
		}
		return k;
	}
 
	int getSize(int k)
	{
		return sz[getPar(k)];
	}
 
	void unite(int u, int v)
	{
		int par1=getPar(u), par2=getPar(v);
 
		if(par1==par2)
			return;
 
		connected--;
 
		if(sz[par1]>sz[par2])
			swap(par1, par2);
 
		sz[par2]+=sz[par1];
		sz[par1]=0;
		par[par1]=par[par2];
	}
};
 DSU dsu;

void solve()
{   
    
    
    int n,m;
    cin>>n>>m;
    dsu.init(n);
    
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        dsu.unite(a,b);
    }
    cout<<connected-1;
    
    
}

int32_t main()
{
	ios::sync_with_stdio(false);
    cin.tie(NULL);
    
	int t=1;
//	cin>>t;
	while(t--)solve();
	    
   
}

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

int main() {
  ll mod = 1000000007;
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i,0,n) cin >> a[i];
  ll ans = 0;
  rep(i,0,60) {
    ll pop = 0;
    rep(j,0,n) {
      if (a[j] & ((ll)1 << i)) pop++;
    }
    ans += ((((((ll)1 << i) % mod) * pop) % mod) * (n-pop)) % mod;
    ans %= mod;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 5568
#include <bits/stdc++.h>
#include <boost/range/adaptor/reversed.hpp>
#include <boost/range/algorithm/sort.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using boost::irange;
using boost::sort;
using boost::adaptors::reversed;

int main() {
    int h1, m1, h2, m2, k;
    cin >> h1 >> m1 >> h2 >> m2 >> k;
    cout << h2 * 60 + m2 - k - h1 * 60 - m1 << endl;
}


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

int main() {
	int dp[1010][1010]={};
	int n,m;cin>>n>>m;
	int d[1010];
	int c[1010];
	for(int i=0;i<n;i++)cin>>d[i];
	for(int i=0;i<m;i++)cin>>c[i];
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)dp[i][j]=1<<28;
	for(int i=0;i<=m;i++)dp[n][i]=0;
	for(int i=n-1;i>=0;i--)
	{
		for(int j=m;j>=0;j--)
		{
			if(j+1<=m)dp[i][j]=min(dp[i][j+1],dp[i+1][j+1]+d[i]*c[j]);
			else if(i!=n)dp[i][j]=1<<28;
		}
	}
	cout<<dp[0][0]<<endl;
	return 0;
}

Measured memory_bytes: 7080
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=INT_MAX,MOD=1e9+7;

int n;
vector<int> a,b,c;

// indexが条件を満たすか?
bool AisOK(int index,int key){
    if(a[index]<key) return true;
    else return false;
}
bool CisOK(int index,int key){
    if(c[index]>key) return true;
    else return false;
}

// 二分探索
int Abinary_search(int key){
	// key以上の値をとるindexは全てokとする
    int ng=n; // aの左の範囲外は必ずng
    int ok=-1; // aの右の範囲外は必ずok

    while (abs(ok-ng)>1) {
        int mid=(ok+ng)/2;
        if(AisOK(mid,key)) ok=mid;
        else ng=mid;
    }
    return ok;
}
int Cbinary_search(int key){
	// key以上の値をとるindexは全てokとする
    int ng=-1; // aの左の範囲外は必ずng
    int ok=n; // aの右の範囲外は必ずok

    while (abs(ok-ng)>1) {
        int mid=(ok+ng)/2;
        if(CisOK(mid,key)) ok=mid;
        else ng=mid;
    }
    return ok;
}

int main(){
    cin>>n;
    rep(i,n) {int x;cin>>x;a.push_back(x);}
    rep(i,n) {int x;cin>>x;b.push_back(x);}
    rep(i,n) {int x;cin>>x;c.push_back(x);}
    sort(all(a));
    sort(all(b));
    sort(all(c));

    long long ans=0;
    for(auto i:b){
        long long x=Abinary_search(i)+1;
        long long y=n-Cbinary_search(i);
        // cout<<x<<" "<<y<<endl;
        ans+=x*y;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1784
#include<iostream>
using namespace std;
int main(){
  int a,b,c,d,h1,h2,k1,k2,H,K;
  cin>>h1>>h2;
  cin>>k1>>k2;
  cin>>a>>b>>c>>d;
  H=h1*a+h2*b+h1/10*c+h2/20*d;
  K=k1*a+k2*b+k1/10*c+k2/20*d;
  if(H>K)
  cout<<"hiroshi\n";
  else if(H<K)
  cout<<"kenjiro\n";
  else
  cout<<"even\n";
  return 0;
  
}

Measured memory_bytes: 3084
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <algorithm>

using namespace std;

int main (int argc, char *argv[]) 
{
    int A, B, C;
    cin >> A >> B >> C;

    int zan = A - B;
    int ans = C - zan;

    cout << max(0, ans) << endl;

    return 0;
}

Measured memory_bytes: 256
X, Y, Z, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)

comb = []
for a in range(X):
    b_max = K // (a+1)
    for b in range(min(Y, b_max)):
        c_max = K // ((a+1)*(b+1))
        for c in range(min(Z, c_max)):
            comb.append(sum([A[a], B[b], C[c]]))

comb.sort(reverse=True)

print(*comb[:K], sep='\n')


Measured memory_bytes: 7856
#include <stdio.h>
#include <stdlib.h>
#define N 1000
#define EMPTY 10000

typedef struct queue
{
    int data[N];
    int left;
    int right;
} Queue;

void initialize(Queue *queue)
{
    int i;

    queue->left = 0;
    queue->right = 0;
    for (i = 0; i < N; ++i)
    {
        queue->data[i] = 0;
    }
}
void enqueue(Queue *queue, int num)
{
    queue->right = (queue->right + 1) % N;
    if (queue->left == queue->right)
    {
        //printf("Full!!\n");
    }
    else queue->data[queue->right] = num;
}
int dequeue(Queue *queue)
{
    if (queue->left == queue->right)
    {
        //printf("Empty!!\n");
        return EMPTY;
    }
    queue->left = (queue->left + 1) % N;
    return queue->data[queue->left];
}

int main(){

    int x, y, W, H,i;
    char area[22][22];
    Queue queue;
    int count,next,position,flag;
    int direction[4];

    while(1)
    {
        scanf("%d %d", &W, &H);
        //printf("%d %d\n", H, W);
        if(W==0&&H==0){
            //getchar();
            //putchar('$');
            return 0;
        }
        direction[0] = -(W + 1); //上
        direction[1] = 1;        //右
        direction[2] = W + 1;    //下
        direction[3] = -1;       //左
        for (y = 0; y < 22; y++)
        {
            for (x = 0; x < 22; x++)
            {
                area[y][x]='#';
            }
        }
        for (y = 0; y < H; y++)
        {
            scanf("%s", area[y]);
        }
        flag = 0;
        for (y = 0; y < H; y++)
        {
            for (x = 0; x < W + 1; x++)
            {
                if (area[y][x] == '@')
                {
                    flag = 1;
                    break;
                }
                /*
                    printf("%c", area[y][x]); 
                 */
            }
            if(flag)break;
        }
        //printf("%d %d\n", x, y);
        initialize(&queue);
        //enqueue(&queue, (W + 1) * y + x);
        position = (W + 1) * y + x;
        //printf("#%d\n", position);

        count = 0;
        while(position!=EMPTY)
        {
            for (i = 0; i < 4;i++)
            {
                next = position + direction[i];
                x = next % (W + 1);
                y = (next - x) / (W + 1);
                if(area[y][x]=='.'){
                    area[y][x] = 'a';
                    enqueue(&queue,next);
                    count++;    
                    //printf("#%d %d\n",x,y);
                }
            }/*
            for (y = 0; y < H; y++)
            {
                for (x = 0; x < W + 1; x++)
                {
                    printf("%c", area[y][x]);
                }
            }
            printf("\n");
             */
            position = dequeue(&queue);
        }
        printf("%d\n", count+1);
        /*
        */
    }
    return 0;
}


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

int main(){
  int N, K, h[100010];
  cin >> N >> K;
  int friends = 0;
  
  for(int i=0;i<N;i++){
    cin >> h[i];
  }
  
  for(int i=0;i<N;i++){
    if(h[i] >= K) friends++;
  }
  
  cout << friends << endl;
  
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i < n; ++i)
#define repe(i, n) for(int i=0; i <= n; ++i)
#define repr(i, n) for(int i=n-1; i > 0; --i)
#define all(x) (x).begin(), (x).end()
#define pb(x) push_back(x)
#define eb(x,y) emplace_back(x,y)
#define PI 3.14159265359
using namespace std;
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;}
template <class T> using V=vector<T>;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1000000007;

ll modPow(ll x, ll n) {
    if(n==0) return 1;
    ll res = modPow(x*x%MOD, n/2);
    if(n&1) res=res*x%MOD;
    return res;
}

ll mul(ll l, ll r) {
    ll ret =1;
    for(int i=0; i<l-r+1; ++i) {
        ret*=i+r;
        ret%=MOD;
    }
    return ret;
}
ll com(ll n, ll k) {
    ll ret1 = mul(n,n-k+1);
    ll ret2 = mul(k,1);
    ll ret3 = modPow(ret2, MOD-2);
    return ret1*ret3%MOD;
}



int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,a,b;
    cin >> n >> a >> b;
    ll res = modPow(2,n)-com(n,a)-com(n,b)-1;
    while(res<0) res+=MOD;
    cout << res << "\n";
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<tuple>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-15
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int sign(int A){
	return (A>0)-(A<0);
}
int main(){
	int N;
	scan(N);
	int a[100001];
	ll asum[100001]={0};
	rep(i,N){
		scan(a[i]);
		if(i!=0) asum[i]=asum[i-1]+a[i];
		else asum[i]=a[i];
	}
	ll ansmin=INFl;
	rep(pari,2){
		ll ans=0,sumplus=0;
		rep(i,N){
			int goal=(i+pari)%2*2-1;
			if(sign(asum[i]+sumplus)!=goal){
				ans+=abs(asum[i]+sumplus-goal);
				sumplus+=goal-(asum[i]+sumplus);
			}
		}
		ansmin=min(ansmin,ans);
	}
	prin(ansmin);
	return 0;
}


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

int main()
{
	int N, X;
	cin >> N >> X;
	int m[1000];
	int sum = 0;
	int min = 10000;
	for (int i = 0; i < N; i++) {
		cin >> m[i];
		sum += m[i];
		if (m[i] < min) {
			min = m[i];
		}
	}
	int M = N + (X - sum) / min;
	cout << M << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define lli long long
using namespace std ;
int main(){
    lli a , b1 ; 
    double b ;
    cin >> a >> b ;
    b += 0.001 ;
    b1 = 100*b ;
    cout << fixed << (a*b1)/100 << "\n" ;
    return 0 ;
}

Measured memory_bytes: 3724
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
typedef long long ll;

using namespace std;


//problem_B
int main(){
    ll n;
    cin >> n;
    ll a[n];
    ll sum1 = 1;
    //ll sum2 = 1;
    ll ans1 = 0;
    ll ans2 = 0;
    ll a0 = pow(10, 18);
    for (ll i=0; i<n; i++){
        cin >> a[i];
        if (a[i] == 0){
            ans2 += 1;
        }
    }
    if (ans2 == 0){
        for (ll i=0; i<n; i++){
            if (a0/sum1 < a[i]){
                ans1 += 1;
                break;
            }
            sum1 *= a[i];
        }
    }

    //cout << sum1 << endl;
    //cout << ans1 << endl;
    //cout << ans2 << endl;
    if (ans2 != 0){
        cout << 0 << endl;
    }
    else if (ans1 != 0){
        cout << -1 << endl;
    }
    else{
        printf("%lld\n",sum1);
    }
}

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

int main(){
    ll n; cin >> n;
    ll minl = 1e9, minIndex = 0;
    vector<string> s(n); rep(i,n){
        cin >> s[i];
        if(minl >= s[i].size()){
            sort(s[i].begin(), s[i].end());
            if(s[i] < s[minIndex] and minl == s[i].size()){
                minIndex = i;
            }else{
                minl = s[i].size();
                minIndex = i;
            }
        }
    }

    vector<char> ans;

    for(auto x:s[minIndex]){
        ll flag = 1;
        for(int j = 0; j < n; j++){
            ll index = s[j].find(x);
            if(string::npos == index){
                flag = 0;
                break;
            }else if(j != minIndex){
                s[j][index] = '#';
            }
        }
        if(flag) ans.push_back(x);
    }
    sort(ans.begin(), ans.end());
    for(auto x:ans) cout << x; cout << endl;
}

Measured memory_bytes: 3592
#include <stdio.h>
int main(){
	int aaa[4][3][10]={}, a, b, c, d, q, w, e, r, x, y, z, n, h, m;
	scanf ("%d", &a);
//	printf("%d\n",a);
	/*for(n = 0; n <= 4; n++){
		for(h = 0; h <= 3; h++){
			for(m = 0; m <= 10; m++){
				printf("n=%d h=%d m=%d\n",n,h,m);//test
				aaa[n][h][m] = 0;
			}
		}
	}*/
	for(d = 0; d < a; d++){
//		printf("OK\n");//test
		scanf("%d %d %d %d", &q, &w, &e, &r);
		aaa[q-1][w-1][e-1] += r;
	}
		for(x = 0; x < 4; x++){
			for(y =0; y < 3; y++){
				for(z = 0; z < 10; z++){
					printf(" %d", aaa[x][y][z]);
				}
			printf("\n");
		}
			if(x!=3)
	printf("####################\n");
}
	
	return 0;
}

Measured memory_bytes: 612
#include <bits/stdc++.h>
#define pb push_back
typedef long long ll;
typedef long double la;
using namespace std;

int main(){
    double n,m;
    ll sum = 0;
    cin >> n >> m;
    vector<int> a(n),b;
    for(int i=0;i<n;i++){
        cin >> a[i];
        sum += a[i]; 
    }
    if(n == 1 && m == 1){
        cout << "No" << endl;
        return 0;
    }
    for(int i=0;i<n;i++){
        if(a[i] >= sum*(0.25*(1/m))){
            b.pb(a[i]);
        }
    }
    if(b.size() >= m){
        cout << "Yes" << endl;
        return 0;
    }else{
        cout<< "No" << endl;
        return 0;
    }
}

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

int main()
{
  int64_t H, W, a, ans = 0;
  cin >> H >> W;
  vector<vector<int64_t>> DP(10, vector<int64_t>(10));
  for (int i = 0; i < 10; i++)
  {
    for (int j = 0; j < 10; j++)
    {
      cin >> DP.at(i).at(j);
    }
  }
  vector<int64_t> A;
  for (int i = 0; i < H; i++)
  {
    for (int j = 0; j < W; j++)
    {
      cin >> a;
      if (a != -1)
        A.push_back(a);
    }
  }
  for (int k = 0; k < 10; k++)
  {
    for (int i = 0; i < 10; i++)
    {
      for (int j = 0; j < 10; j++)
      {
        DP.at(i).at(j) = min(DP.at(i).at(j), DP.at(i).at(k) + DP.at(k).at(j));
      }
    }
  }
  for (int i = 0; i < A.size(); i++)
  {
    ans += DP.at(A.at(i)).at(1);
  }
  cout << ans << endl;
}

Measured memory_bytes: 896
package main

import "fmt"

const mod = 1e9 + 7

var fact, invFact []int

func powmod(a, m int) int {
	b := 1
	for m > 0 {
		if m&1 != 0 {
			b = b * a % mod
		}
		a = a * a % mod
		m >>= 1
	}
	return b
}

func combmod(n, r int) int {
	c := fact[n]
	c *= invFact[n-r]
	c %= mod
	c *= invFact[r]
	c %= mod
	return c
}

func main() {
	var H, W, A, B int
	fmt.Scan(&H, &W, &A, &B)

	max := H + W + 1
	fact = make([]int, max+1)
	invFact = make([]int, max+1)
	fact[0] = 1
	invFact[0] = 1
	for i := 1; i <= max; i++ {
		fact[i] = (i * fact[i-1]) % mod
		invFact[i] = powmod(i, mod-2)
		invFact[i] = (invFact[i] * invFact[i-1]) % mod
	}

	s := 0
	for i := 0; i < H-A; i++ {
		x := combmod(i+1+B-2, i)
		y := combmod(W-B+H-i-2, H-i-1)
		z := (x * y) % mod
		s = (s + z) % mod
	}
	fmt.Println(s)
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll k, ans = 0;
    cin >> k;
    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= k; j++) {
            for (int l = 1; l <= k; l++) {
                ans += __gcd(i, __gcd(j, l));
            }
        }
    }
    cout << ans << '\n';
    return 0;
}


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

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;

#define INF (1<<(4*4-1))
#define MOD 1000000007

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

   int N,M;
   cin>>N>>M;
   vector<vector<bool> >e(N,vector<bool>(N,false));
   for(int i=0;i<M;i++){
      int x,y;
      cin>>x>>y;
      x--,y--;
      e[x][y]=true;
      e[y][x]=true;
   }

   vector<int>node(N);
   for(int i=0;i<N;i++)node[i]=i;

   ll ans = 0;
   do{
      if(node[0]!=0)continue;
      bool flg=true;
      for(int i=0;i<N-1;i++){
         if(!e[node[i]][node[i+1]])flg=false;
      }
      if(flg)ans++;
   } while(next_permutation(node.begin(),node.end()));
   cout<<ans<<endl;
   return 0;
}


Measured memory_bytes: 256
def toId(i, j):
    pair = A[i][j]
    if i > pair:
        i, pair = pair, i
    return ids[i][pair]

def dfs(x):
    if dp[x] != -1:
        if done[x]:
            return dp[x]
        else:
            return -1
    dp[x] = 1
    for y in G[x]:
        res = dfs(y)
        if res == -1:
            return -1
        dp[x] = max(dp[x], dfs(y)+1)
    done[x] = True
    return dp[x]

N = int(input())
A = [list(map(lambda x: int(x)-1, input().split())) for i in range(N)]
ids = [[0]*N for i in range(N)]
num = 0
for i in range(N):
    for j in range(N):
        if i < j:
            ids[i][j] = num
            num += 1
allv = N*N
G = [[] for i in range(allv)]
for i in range(N):
    for j in range(N-2):
        G[toId(i,j+1)].append(toId(i,j))
dp = [-1 for i in range(allv)]
done = [False for i in range(allv)]
ans = 0
for i in range(allv):
    res = dfs(i)
    if res == -1:
        print(-1)
        exit()
    ans = max(ans, dfs(i))
print(ans)


Measured memory_bytes: 230972
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = [0] * 2 ;count = 0 ;pro = 1

n=int(input())
A=[int(input()) for i in range(n)]
A.sort()
# if n % 2 == 0:
# 1の処理
tmp = 0;k=0
k+=n//2-1; tmp += -2*sum(A[:k])
tmp += -1*A[k]; k += 1
tmp += (-1)**n*A[k]; k += 1
tmp += 2 * sum(A[k:])
ans[0] = tmp

# 2の処理
tmp = 0;k=0
k+=n//2-1+(n%2); tmp += -2*sum(A[:k])
# print(tmp,A[:k])
tmp += (-1)**(n+1)*A[k]; k += 1
tmp += A[k]; k += 1
tmp += 2 * sum(A[k:])
ans[1] = tmp

# print(A);print(ans)
print(max(ans))




Measured memory_bytes: 45020
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<complex>
#define INF 2147483647
#define llINF 9223372036854775807
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long

using namespace std;
int main(){
  int n,p;
  vector<int>prime;
  prime.pb(2);
  for(int i=3;i<=500000;i+=2){
    bool flag=true;
    for(int j=2;j<=sqrt(i);j++){
      if(i%j==0){flag=false;break;}
    }
    if(flag)
      prime.pb(i);
  }
  while(cin>>n>>p,n+p!=-2){
    vector<int>num;
    int po;
    for(po=0;po<prime.size();po++){
      if(n<prime[po])
	break;
    }
    for(int i=po;i<po+100;i++){
      for(int j=i;j<po+100;j++){
	num.pb(prime[i]+prime[j]);
      }
    }
    sort(num.begin(),num.end());
    cout<<num[p-1]<<endl;
  }
  return 0;
}


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

A,B,C = [int(x) for x in input().split(" ")]

ans = 0
while A % 2 == 0 and B % 2 == 0 and C % 2 == 0:
    ans += 1
    A_new = B / 2 + C / 2
    B_new = A / 2 + C / 2
    C_new = A / 2 + B / 2
    if A == A_new and B == B_new and C == C_new:
        ans = -1
        break
    A = A_new
    B = B_new
    C = C_new

print(ans)


Measured memory_bytes: 9116
/* 
   AOJ 1193
   Chain Disappearance Puzzle
*/

#include<stdio.h>
#include<string.h>
#define HEIGHT_MAX 10
#define WIDTH 5
#define CONSECUTIVE 3
int board[HEIGHT_MAX][WIDTH];

int is_consecutive(int h)
{
  int i, prev = board[h][0], cnt = 1, max = 0, consecutive_num = 0, st = 0;
  for(i = 1; i < WIDTH; i++)
    {
      if(prev == board[h][i] && prev != 0)
	{
	  cnt++;
	  if(max <= cnt)
	    {
	      max = cnt;
	      consecutive_num = prev;
	    }
	}
      else
	{
	  if(max >= CONSECUTIVE)
	    {
	      break;
	    }
	  st = i;
	  cnt = 1;
	  prev = board[h][i];
	}
    }
  if(max >= CONSECUTIVE)
    {
      return max * 100 + consecutive_num * 10 + st;
    }
  else
    {
      return 0;
    }
}

void erase_stones(int h, int start_point, int end_point)
{
  int i, j;
  for(i = h; i >= 0; i--)
    {
      if(i == 0)
	{
	  for(j = start_point; j < end_point; j++)
	    {
	      board[0][j] = 0;
	    }
	}
      else
	{
	  for(j = start_point; j < end_point; j++)
	    {
	      board[i][j] = board[i - 1][j];
	    }	  
	}
    }
}

int main(void)
{
  int height, points = 0, i, j, cnt = 0, sp = 0, consecutive_n = 0, erase_flag = 0;
  int erase_line[HEIGHT_MAX] = {0};
  while(1)
    {
      points = 0;
      memset(board, 0, sizeof(board));
      scanf("%d", &height);
      if(!height)break;
      for(i = 0; i < height; i++)
	{
	  scanf("%d%d%d%d%d", &board[i][0], &board[i][1], &board[i][2], &board[i][3], &board[i][4]);
	}
      while(1)
	{
	  erase_flag = 0;
	  memset(erase_line, 0, sizeof(erase_line));
	  for(i = 0; i < height; i++)
	    {
	      erase_line[i] = is_consecutive(i);
	    }
	  for(i = 0; i < height; i++)
	    {
	      if(erase_line[i])
		{
		  cnt = erase_line[i] / 100, consecutive_n = (erase_line[i] % 100) / 10, sp = erase_line[i] % 10;
		  points += cnt * consecutive_n;
		  erase_stones(i, sp, sp + cnt);
		  erase_flag = 1;
		}
	    }
	  if(!erase_flag)break;
	}
      printf("%d\n", points);
    }
  return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
const ll LINF=0x1fffffffffffffff;
const int INF=0x3fffffff;
const int MOD=1000000007;
#define VAR(type,...) type __VA_ARGS__;in(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);each(i, name)in(i)
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,a,b) for(int i=(a-1);i>=(b);--i)
#define each(i,v) for(auto &i:(v))
#define all(v) (v).begin(),(v).end()
#define print(...) out(__VA_ARGS__);cout<<endl
void in(){} template<class T,class... U> void in(T &t,U &...u){cin>>t;in(u...);}
void out(){} template<class T,class... U> void out(T t,U ...u){cout<<t<<" ";out(u...);}
void solve();
int main(){cin.tie(0);ios::sync_with_stdio(0);solve();}

void solve() {
  VAR(int, N, A, B);
  ll ans = 0;
  rep(i, 1, N + 1) {
    int M = i;
    int sum = 0;
    while (M) {
      sum += M % 10;
      M /= 10;
    }
    if (sum >= A && sum <= B) {
      ans += i;
    }
  }
  print(ans);
}


Measured memory_bytes: 256
#include<stdio.h>

int main(void){

  int i;
  int stack[10];
  int car;
  int num;

  num = 0;
  for(i=0;i<10;i++){
    stack[i] = 0;
  }

  while(scanf("%d ",&car)!=EOF){
    if(car){
      stack[num] = car;
      num++;
    }else{
      num--;
      printf("%d\n",stack[num]);
      stack[num] = 0;
    }
  }

  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

int a[88][88], b[88][88];
bool dp[88][88][160*160 + 1];
const int m = 160*80;

int main() {
    int h, w;
    cin >> h >> w;

    rep(i, h) {
        rep(j, w) {
            cin >> a[i][j];
        }
    }
    rep(i, h) {
        rep(j, w) {
            cin >> b[i][j];
        }
    }
    
    dp[0][0][m + a[0][0] - b[0][0]] = 1;
    dp[0][0][m + b[0][0] - a[0][0]] = 1;
    rep(i, h) {
        rep(j, w) {
            rep(k, 2*m+1) {
                if(!dp[i][j][k]) {
                    continue;
                } 
                if(i+1 < h) {
                    if(k + a[i+1][j] <= 2*m) {
                        dp[i+1][j][k + a[i+1][j] - b[i+1][j]] = 1;
                    }
                    if(k - b[i+1][j] >= 0) {
                        dp[i+1][j][k + b[i+1][j] - a[i+1][j]] = 1;
                    }
                }
                if(j+1 < w) {
                    if(k + a[i][j+1] <= 2*m) {
                        dp[i][j+1][k + a[i][j+1] - b[i][j+1]] = 1;
                    }
                    if(k - b[i][j+1] >= 0) {
                        dp[i][j+1][k + b[i][j+1] - a[i][j+1]] = 1;
                    }
                }
            }
        }
    }

    int ans = m;
    rep(k, 2*m+1) {
        if(dp[h-1][w-1][k]) {
            chmin(ans, (int)abs(k - m));
        }
    }

    out(ans);
    re0;
}

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

int n;
int m[20][20]={{}};
int inf = 10000000;
int dp[(1<<17)][17];
int k;

int rec(int s,int v){
  if(dp[s][v]>=0) return dp[s][v];

  if(s == (1<<(n+1))-1 && v == 0) return dp[s][v] = 0;

  int res = inf;
  for(int u=0;u<=n;u++){
    if(!(s>>u&1)){
      int cost = m[u][0];
      for(int i=0;i<=n;i++){
	if(s>>i&1)
	  cost= min(cost,m[u][i]);
      }
      res = min(res,rec(s | 1 << u, u)+cost);
    }
  }
  return dp[s][v] = res;
}

int main(){
  int i,j;
  
  
  cin >> n;
  while(n!=0){
    //memset(m,inf,sizeof(m));
    fill(m[0],m[19],inf);
    for(j=0;j<=n;j++) m[0][j]=0;
    for(i=1;i<=n;i++){
      for(j=0;j<=n;j++){
	cin >> m[i][j];
      }
    }
    int s=0;
    memset(dp,-1,sizeof(dp));
    cout << rec(0,0) << endl;
    cin >> n;
  }
  return 0;
}

Measured memory_bytes: 9872
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(),m = sc.nextInt();
        long ans = 100L * (n-m);
        ans += 1900L * m;
        System.out.println(ans<<m);
    }
}

Measured memory_bytes: 22996