akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <math.h>
using namespace std;
int main() {
int long N,A,M,S;
  cin>>N;
  S=0;
  M=0;
  for(int i=0;i<N;i++){
  cin>>A;
    if(M>A){
      S+=(M-A);
    }
    M=max(M,A);
  }
  cout<<S;
}

Measured memory_bytes: 3184
#include <bits/stdc++.h>
const int MOD=1000000007;
const int INF=1000000000;
using namespace std;
typedef long long ll;
typedef tuple<ll,int,int> tup;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vp;
int main(int argc,char const* argv[])
{
  int ans=1000;
  vector<int> dishes;
  for(int i=0;i<5;i++)
    {
      int time;
      cin >> time;
      dishes.push_back(time);
    }
  sort(dishes.begin(),dishes.end());
  do{
    int tmp=0;
    for(int i=0;i<5;i++)
      {
	if(tmp%10!=0)
	  {
	    tmp=(tmp/10)*10+10;
	  }
	tmp+=dishes[i];
      }
    ans=min(ans,tmp);
  }while(next_permutation(dishes.begin(),dishes.end()));
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#include <deque>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

bool isPrime(int x) {
  if(x == 2) return true;
  else if(x % 2 == 0) return false;
  for(int i = 3; i*i <= x; i+=2) {
    if(x % i == 0) return false;
  }
  return true;
}

int main() {
  int x; cin >> x;
  for(int i = x; i <= 101000; i++) {
    if(isPrime(i)) {
      cout << i << endl;
      return 0;
    }
  }
  return 0;
}


Measured memory_bytes: 256
#!/usr/bin/ruby
require 'mathn'
h={};2.step(36){|i|h[i]=i.prime_division}
while(l=gets)!="0 0\n"
	l=l.split
	n=l[0].to_i;m=l[1].to_i(n)
	p h[n].map{|a,b|
		z=m;r=0
		while z>0 do r+=(z=z.div(a)) end
		r.div(b)
	}.min
end

Measured memory_bytes: 4000
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;


int main() {
    ll n, sum = 0;
    cin >> n;
    vector<ll> a(n, 0LL);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        sum += a[i];
    }

    if (2 * sum % (n * (n + 1)) != 0) {
        cout << "NO" << endl;
        return 0;
    }

    ll k = 2 * sum / (n * (n + 1));

    vector<ll> d(n, 0LL);
    ll cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (i == 0) d[i] = a[0] - a[n - 1] - k;
        else d[i] = a[i] - a[i - 1] - k;

        if (d[i] > 0 || d[i] % n) {
            cout << "NO" << endl;
            return 0;
        }
        cnt -= d[i] / n;
    }

    cout << (cnt == k ? "YES" : "NO") << endl;

}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#include <iomanip>
#include <iostream>
using namespace std;
using ll = long long;
const long long INF = 1LL << 60;
 
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 max(ll a, ll b){
    if(a > b) return a;
    else return b;
}
 
ll min(ll a, ll b){
    if(a < b) return a;
    else return b;
}
int f(ll X){
    if(X == 0) return 0;
    return X%10 + f(X/10);
}
int main(void){
    ll N; cin >> N;
    if(N % f(N) == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#pragma warning(disable:4996)
#ifdef _MSC_VER
#  define __builtin_popcountll __popcnt
#endif
#define int long long
using namespace std;
using ll = long long;
using ld = long double;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
inline void my_io() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout << fixed << setprecision(10);
}
typedef unsigned long long ull;

struct RollingHash
{
	vector<ull> hash, pow;
	RollingHash(string s, ull _b = 1000000007)
	{
		_b = _b;
		int sz = s.length();
		hash.assign(sz + 1, 0);
		pow.assign(sz + 1, 0);

		pow[0] = 1;
		for (int i = 0; i<sz; i++) {
			pow[i + 1] = pow[i] * _b;
		}
		for (int i = 0; i<sz; i++) {
			hash[i + 1] = (hash[i] + s[i])*_b;
		}
	}
	// s[l]s[l+1]....s[r-1]のハッシュ値を取得する
	// 半開区間
	ull get(int l, int r) {
		return (hash[r] - hash[l] * pow[r - l]);
	}
};
signed main() {
	my_io();
	vector<int>ans;
	string t, s;
	cin >> t >> s;
	RollingHash t_Roll(t);
	RollingHash s_Roll(s);
	int s_hash=s_Roll.get(0, (int)s.size());
	for (int i = 0; i <=(int)t.size()-(int)s.size(); i++) {
		if (s_hash == t_Roll.get(i, i + s.size())) {
			ans.push_back(i);
		}
	}
	for (int i = 0; i < (int)ans.size(); i++) {
		cout << ans[i] << endl;
	}
	return 0;
}




Measured memory_bytes: 3248
#include<bits/stdc++.h>
using namespace std;
#define ld long double
#define ll long long int
int main()
{
	int n;
	cin>>n;
	vector<ld>v(n);
	for(int i=0;i<n;i++)
	{
		cin>>v[i];
	}
	ll k=n/2+1;
	vector<vector<ld>>dp(n,vector<ld>(n/2+1,0));
	dp[0][0]=v[0];
	dp[0][1]=1-v[0];
	for(int i=1;i<n;i++)
	{
		for(int j=0;j<k;j++)
		{
			dp[i][j]=dp[i-1][j]*v[i] + (j!=0 ? dp[i-1][j-1]*(1-v[i]) : 0);
		}
	}
	ld ans=0;
	for(int i=0;i<k;i++)
	{
		ans=ans+dp[n-1][i];
	}
	cout<<fixed<<setprecision(10)<<ans<<endl;
	return 0;
}

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

int main() {
	int p;
	int K[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
	cin >> p;
	cout << K[p-1] << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;
int main(){
  int n,i,sum = 0,now = 0,ans = 100000;cin >> n;
  int a[n];
  for(i=0;i<n;i++){
    cin >> a[i];sum += a[i];
  }
  for(i=0;i<n;i++){
    now += a[i]*2;
    ans = min(ans,abs(sum-now));
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cassert>
#include <ctime>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

#define all(x) (x).begin(), (x).end()

#ifdef LOCAL
#define dbg(x) cerr << #x " = " << x << endl;
#define idbg(x) #x " = " << x
#include "pretty_print.h"
#else
#define dbg(x)
#define idbg(x) ""
#endif

#ifdef _WIN32
#  define LLD "%I64d"
#else
#  define LLD "%lld"
#endif

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;

template <typename T> T sqr(T x) { return x * x; }
template <typename T> T abs(T x) { return x < 0? -x : x; }
template <typename T> T gcd(T a, T b) { return b? gcd(b, a % b) : a; }
template <typename T> bool chmin(T &x, const T& y) { if (x > y) { x = y; return true; } return false; }
template <typename T> bool chmax(T &x, const T& y) { if (x < y) { x = y; return true; } return false; }


vector<vector<pair<int, int>>> e;
vector<int> ans;


void dfs(int x, int p, int l) {
    int color = 0;
    for (auto& d : e[x]) {
        int y = d.first;
        int ind = d.second;
        if (p == y) {
            continue;
        }
        if (color == l) {
            ++color;
        }
        ans[ind] = color + 1;
        dfs(y, x, color);
        ++color;
    }
}



int main(int /* argc */, char** /* argv */)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifdef LOCAL
    assert(freopen("inp", "r", stdin));
    assert(freopen("out", "w", stdout));
    #endif

    int n;
    while (cin >> n) {
        e.resize(n);
        for (int i = 0; i < n; ++i) {
            e[i].clear();
        }

        ans.resize(n - 1);

        for (int i = 0; i < n - 1; ++i) {
            int u, v;
            cin >> u >> v;
            --u;
            --v;
            e[u].push_back(make_pair(v, i));
            e[v].push_back(make_pair(u, i));
        }
        dfs(0, -1, -1);
        cout << *max_element(all(ans)) << "\n";
        for (int i = 0; i < n - 1; ++i) {
            cout << ans[i] << "\n";
        }
    }

    cerr << "Time execute: " << clock() / (double)CLOCKS_PER_SEC << " sec" << endl;
    return 0;
}


Measured memory_bytes: 8320
/*

by.YXH_XianYu
   2018.6.17
 */
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LLI long long

LLI a[3];

int main(){
	//freopen("mothergoose.in","r",stdin);
	//freopen("mothergoose.out","w",stdout);

	scanf("%lld%lld%lld",&a[0],&a[1],&a[2]);
	for(int i=0;i<=2;i++)
		if(!(a[i]&1)){
			printf("0\n");
			return 0;
		}
	std::sort(a,a+3);
	printf("%lld\n",a[0]*a[1]);

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <climits>
#include <map>
#include <functional>
#include <cmath>
#include <cassert>

using namespace std;

int main()
{
    long x, y;
    cin >> x >> y;

    int i;
    for (i = 0; x < y; i++)
        x *= 2;

    cout << i + (int)(x == y) << endl;

    return 0;
}

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

int main(){
	int n, s, sum, maxs, mins, i;
	while((cin >> n), n){
		sum = maxs = 0;
		mins = 1000;
		for(i = 0; i < n; i++){
			cin >> s;
			sum += s;
			maxs = max(maxs, s);
			mins = min(mins, s);
		}
		sum = (sum - maxs - mins) / (n - 2);
		cout << sum << endl;
	}
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cassert>
#include <deque>
#include <map>
#include <queue>
#include <climits>
#include <set>
#include <stack>

using namespace std;

#define ll long long
#define MAX 100000
#define MAX1 10000
#define MAX2 100000
#define inf 1000000000
#define eps 1e-12
#define MOD 1000000007

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    int l, r, d, ans;
    cin >> l >> r >> d;
    ans = r / d;
    ans -= l / d;
    ans += l % d == 0;
    cout << ans;

    return 0;
}

Measured memory_bytes: 3192
#include <bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;
int32_t main(){
	if(fopen("input.txt", "r"))
	freopen("input.txt", "r", stdin),
	freopen("output.txt", "w", stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	int a,b,c;
	cin >> a >> b >> c;
	if(c>a+b){
		cout << a+2*b+1 << endl;
	}
	else cout << c+b << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <deque>
#include <map>
#include <iomanip>
#include <limits>
#include <map>

using namespace std;

const int CMax = 102;
const int CVMax = 31;
const int CInf = 2000000001;
const long long CMod = 1000000007;

int n, k;
int A[CMax], B[CMax], C[CMax];
int res;

long long gcd(long long a, long long b)
{
    if (b != 0) return gcd(b, a % b);
    else return a;
}



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

    for (int i = 0; i < n-1; i++) scanf("%d", &B[i]);

    res += B[0];
    for (int i = 1; i < n-1; i++) {
        res += min(B[i], B[i-1]);
    }

    res += B[n-2];

    printf("%d\n", res);

    return 0;
}


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 GetDigit(ll num){ return log10(num)+1; } //numの桁数を求める

int main()
{
    int a, b;
    cin >> a >> b;
    int ans = a + b;
    cout << ans%24<< endl;
    return 0;
}

Measured memory_bytes: 3548
#include<iostream>
#include<vector>
#define f first
#define s second
#define DIM 100005
using namespace std;
int n, m, x, y, i, nr;
int viz[DIM];
vector< pair<int, int> > v[DIM];
void dfs(int nod){
    if(nod == y){
        nr++;
        return;
    }
    for(int i = 0; i < v[nod].size(); i++){
        if(viz[ v[nod][i].s ] == 0){
            viz[ v[nod][i].s ] = 1;
            dfs(v[nod][i].f);
        }
    }
}
int main(){
    cin>> n >> m;
    for(i = 1; i <= m; i++){
        cin>> x >> y;
        v[x].push_back( make_pair(y, i) );
        v[y].push_back( make_pair(x, i) );
    }
    for(i = 1; i <= n; i++){
        if(v[i].size() % 2 == 1){
            nr = 1;
        }
    }
    if(nr == 1){
        cout<<"No";
        return 0;
    }
    for(i = 1; i <= n; i++){
        if(v[i].size() == 6){
            nr = 1;
        }
    }
    if(nr == 1){
        cout<<"Yes";
        return 0;
    }
    for(i = 1; i <= n; i++){
        if(v[i].size() == 4){
            nr++;
        }
    }
    if(nr == 2){
        nr = 0;
        x = y = 0;
        for(i = 1; i <= n; i++){
            if(v[i].size() == 4){
                if(x == 0){
                    x = i;
                }
                else{
                    y = i;
                }
            }
        }
        dfs(x);
        if(nr == 2){
            cout<<"Yes";
        }
        else{
            cout<<"No";
        }
    }
    else{
        if(nr < 2){
            cout<<"No";
        }
        else{
            cout<<"Yes";
        }
    }
    return 0;
}


Measured memory_bytes: 7680
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string S;
int p,ch[1<<8];

ll getNum(){
  ll res=0;
  while(isdigit(S[p])) res=res*10+S[p++]-'0';
  return res;
}

ll get(ll &a,ll b,char c){
  if(c=='+')a+=b;
  if(c=='-')a-=b;
  if(c=='*')a*=b;
  return a;
}

ll calc(int c){
  ll res=getNum(),t;
  if(S[p]=='(') p++,res=calc(-1),p++;
  while(ch[S[p]]>c)t=S[p++],get(res,calc(ch[t]),t);
  return res;
}

int main(){
  cin>>S; 
  
  ch[0]=ch[')']=-2;
  ll res=calc(-1);
  for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
      for(int k=0;k<3;k++) {
	ch['+']=i,ch['-']=j,ch['*']=k;
	p=0;
	res=max(res,calc(-1));
      }
  
  cout<<res<<endl;
  return 0;
}

Measured memory_bytes: 3188
import numpy as np

N=int(input())

D=[]

for i in range(N):
    D.append(np.array(input().split(" "),dtype=np.int64))

cnt=0
max_cnt=0
for i in range(N):
    if(D[i][0]==D[i][1]):
        cnt+=1
    else:
        if(cnt>max_cnt):
            max_cnt=cnt
        cnt=0

if(cnt>max_cnt):
    max_cnt=cnt

if(max_cnt>=3):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 27120
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;

int main() {
	long long Q, H, S, D;
	long long N;
	long long L1, L2;
	scanf("%lld %lld %lld %lld", &Q, &H, &S, &D);
	scanf("%lld", &N);
	
	L1 = S;
	if (H * 2 < L1) { L1 = H * 2; }
	if (Q * 4 < L1) { L1 = Q * 4; }

	L2 = D;
	if (L1 * 2 < L2) { L2 = L1 * 2; }

	printf("%lld\n", L2 * (N / 2) + L1 * (N % 2));
}

Measured memory_bytes: 128
// B.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <set>
#include <vector>

using namespace std;

int main(int argc, char* argv[]) {
	while (true) {
		int n = -1;
		cin >> n;
		if (n <= 0) break;
		vector<vector<int>> d(n, vector<int>(n));
		for (int i = 0; i < n; ++i) {
			string s;
			cin >> s;
			for (int j = 0; j < n; ++j) {
				d[i][j] = s[j] == '1' ? 1 : 1 << 29;
			}
			d[i][i] = 0;
		}
		int ans = 0;
		vector<int> color(n, -1), q(1, 0);
		color[0] = 1;
		while (!q.empty()) {
			vector<int> nx;
			for (int x : q) {
				for (int i = 0; i < n; ++i) {
					if (d[x][i] == 1) {
						if (color[i] < 0) {
							color[i] = !color[x];
							nx.push_back(i);
						} else if (color[i] != !color[x]) {
							ans = -1;
						}
					}
				}
			}
			q = nx;
		}
		if (ans >= 0) {
			for (int k = 0; k < n; ++k) {
				for (int i = 0; i < n; ++i) {
					for (int j = 0; j < n; ++j) {
						d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
					}
				}
			}
			for (int i = 0; i < n; ++i) {
				for (int j = 0; j < n; ++j) {
					if (d[i][j] < (1 << 29)) {
						ans = max(ans, d[i][j] + 1);
					}
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
const long long maxn=(1e5+10);
long long n,ans=0;
string s[maxn];
int main()
{
	cin>>n;
	for(long long i=0;i<n;i++)
	{
		cin>>s[i];
		sort(s[i].begin(),s[i].end());
	}
	sort(s,s+n);
	long long cnt=1;
	string tmp=s[0];
	for(long long i=1;i<n;i++)
	{
		if(s[i]==s[i-1])
			++cnt;
		else
		{
			ans+=(cnt*(cnt-1)/2);
			cnt=1;
		}
	}
	ans+=(cnt*(cnt-1)/2);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 7296
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
using loop = int;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(loop (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(loop (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(loop (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(loop (i)=(n);(i)>=(a);--(i))
#define each(i, a) for(auto &i : a)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
#define out(y,x) ((y) < 0 || h <= (y) || (x) < 0 || w <= (x))
#define line cout << "------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause") //comment out this on AOJ.
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
constexpr ld pi = 3.1415926535897932;
template<class T>inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; }return false; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }

int main() {
    init();

    int a, b; cin >> a >> b;
    string s; cin >> s;

    FOR(i, 0, s.length()) {
        if (i == a) {
            if (s[i] != '-') {
                cout << "No\n";
                return 0;
            }
        }
        else {
            bool ok = false;
            FOR(j, 0, 10)ok |= s[i] == char('0' + j);
            if (!ok) {
                cout << "No\n";
                return 0;
            }
        }
    }
    cout << "Yes\n";
}

Measured memory_bytes: 256
'use strict'

function main(input) {
  var hoge = input.split('\n')
  const n = ~~hoge[0].split(' ')[0]
  const k = ~~hoge[0].split(' ')[1]
  var str = hoge[1].split('')
  str[k - 1] = str[k - 1].toLocaleLowerCase()

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


Measured memory_bytes: 7372
from collections import deque

H, W = list(map(int, input().split()))
S = []
for i in range(H):
  S.append(input())

def bfs(x,y):
  d = deque()
  d.append([x,y,0])
  visited = [[False for i in range(W)] for j in range(H)]
  will_search = [[False for i in range(W)] for j in range(H)]
  maxd = -1
  while len(d) > 0:
    x,y,w = d.popleft()
    visited[x][y] = True
    next_point = []
    for dx,dy in [[1,0], [-1,0], [0,-1], [0,1]]:
      if 0 <= x + dx and x + dx < H and 0 <= y + dy and y + dy < W and S[x+dx][y+dy] == ".":
        next_point.append([x + dx, y + dy])
    for p, q in next_point:
      if visited[p][q]:
        continue
      if will_search[p][q]:
        continue
      d.append([p,q,w+1])
      will_search[p][q] = True
      maxd = max(maxd, w+1)

  return maxd

ans = -1
for X in range(H):
  for Y in range(W):
    if S[X][Y] == "#":
      continue
    ans = max(bfs(X,Y), ans)
    
print(ans)

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

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;
const ll MAX = 8;

string S[MAX];
ll x[8] = {1, 1, 1, 0, -1, -1, -1, 0};
ll y[8] = {1, 0, -1, -1, -1, 0, 1, 1};

bool dfs() {
    vector<vector<bool>> U(MAX, vector<bool>(MAX, true));
    ll cnt = 0;
    REP(h, MAX) {
        REP(w, MAX) {
            if (S[h][w] == '.')
                continue;
            cnt++;
            REP(i, 8) {
                ll mul = 0;
                while (true) {
                    ll nx = x[i] * mul + h, ny = y[i] * mul + w;
                    if (nx < 0 || ny < 0 || nx >= MAX || ny >= MAX)
                        break;
                    U[nx][ny] = false;
                    mul++;
                }
            }
        }
    }

    if (cnt == 8) {
        REP(h, MAX) {
            cout << S[h] << endl;
        }
        return true;
    }

    REP(h, MAX) {
        REP(w, MAX) {
            if (!U[h][w])
                continue;
            S[h][w] = 'Q';
            if (dfs())
                return true;
            S[h][w] = '.';
        }
    }
    return false;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    REP(i, MAX) {
        string s = "";
        REP(j, MAX) {
            s.push_back('.');
        }
        S[i] = s;
    }
    ll N;
    cin >> N;
    REP(i, N) {
        pll p;
        cin >> p.first >> p.second;
        S[p.first][p.second] = 'Q';
    }

    dfs();

    return 0;
}


Measured memory_bytes: 3236
def main():
  n,k=map(int,input().split())
  s=input()
  
  # first score
  ans=0
  x=s[0]
  for i in range(1,n):
    if x==s[i]:
      ans+=1
    else:
      x=s[i] 
  print(min(ans+2*k,n-1))

  
if __name__=='__main__':
  main()

Measured memory_bytes: 9228
#include "bits/stdc++.h"
using namespace std;

struct root {
	int to;
	int cost;
};

int N;
static int ANS[100000];
vector<root> V[100000];

void DFS(int x, int y, int cost) {
	ANS[x] = cost;
	for (root z : V[x]) {
		if (z.to != y) {
			DFS(z.to, x, cost + z.cost);
		}
	}
}

int main() {
	cin >> N;
	for (int i = 0; i < N - 1; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		u--, v--, w = w % 2;
		V[u].push_back({ v, w });
		V[v].push_back({ u, w });
	}
	DFS(0, -1, 0);
	for (int i = 0; i < N; i++) {
		cout << ANS[i] % 2 << endl;
	}
}

Measured memory_bytes: 8448
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func init() {
	const maxWord = (1 << 30)
	buf := []byte{}
	sc.Buffer(buf, maxWord)
	sc.Split(bufio.ScanWords)
}

func input() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	n, _ := strconv.Atoi(input())
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i], _ = strconv.Atoi(input())
	}

	s := make([]int, n+1)
	s[0] = 0
	for i := 1; i <= n; i++ {
		s[i] = s[i-1] + a[i-1]
	}
	m := map[int]int{}
	for i := 0; i <= n; i++ {
		m[s[i]]++
	}

	ans := 0
	for _, v := range m {
		if v >= 2 {
			ans += v * (v - 1) / 2
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 13824
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> l_l;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
const int INF=1001001000;
const int mINF=-1001001000;
const ll LINF=1010010010010010000;
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;
}
//グリッド：（典型）dp,dfs,bfs,最短経路,その他
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod){}
mint operator-() const { return mint(-x);}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
mint res(*this);
return res+=a;
}
mint operator-(const mint a) const {
mint res(*this);
return res-=a;
}
mint operator*(const mint a) const {
mint res(*this);
return res*=a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return (*this) *= a.inv();
}
mint operator/(const mint a) const {
mint res(*this);
return res/=a;
}
};
struct combination {
vector<mint> fact, ifact;
combination(int n):fact(n+1),ifact(n+1) {
assert(n < mod);
fact[0] = 1;
for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
ifact[n] = fact[n].inv();
for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
}
mint operator()(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n]*ifact[k]*ifact[n-k];
}
};
int main(){
    ll n;cin>>n;
    vl a(n),b(n);rep(i,n)cin>>a[i];rep(i,n)cin>>b[i];
    vector<vl> dp((1<<n)+1,vl(55,INF));
    dp[0][0]=0;
    for(int bit=0;bit<(1<<n);bit++){
        ll tmp=0;
        for(int i=0;i<n;i++){
            if(bit>>i&1)tmp++;
        }
        vp id;
        int it=tmp;
        for(int i=0;i<n;i++){
            if(!(bit>>i&1))id.pb({i,it++});
        }
        for(int s=0;s<=50;s++){
            if(dp[bit][s]>=INF)continue;
            for(auto p:id){
                ll ns=-1;
                if(abs(p.first-tmp)%2==0)ns=a[p.fi];
                else ns=b[p.fi];
                if(ns>=s)chmin(dp[bit|(1<<p.fi)][ns],dp[bit][s]+abs(p.se-tmp));
            }
        }
    }
    ll ans=INF;
    rep(i,51)chmin(ans,dp[(1<<n)-1][i]);
    if(ans==INF)cout<<-1<<endl;
    else cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 121088
a, b, c = map(int, input().split())

if b > c:
    b1 = c
    c1 = b
    if a > b1:
        a1 = b1
        b2 = a
        if b2 > c1:
            c2 = b2
            b3 = c1
            print(str(a1) + " " + str(b3) + " " + str(c2))
        else:
            print(str(a1) + " " + str(b2) + " " + str(c1))
    else:
        print(str(a) + " " + str(b1) + " " + str(c1))

else:
    if a > b:
        a1 = b
        b1 = a
        if b1 > c:
            c1 = b1
            b2 = c
            print(str(a1) + " " + str(b2) + " " + str(c1))
        else:
            print(str(a1) + " " + str(b1) + " " + str(c))
    else:
        print(str(a) + " " + str(b) + " " + str(c))



Measured memory_bytes: 5604
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define INF (1LL<<50)
#define MOD 1000000007

int main(){
    int N;
    cin >> N;
    vector<ll> A(N);
    ll xo;
    rep(i,N){
        cin >> A[i];
        if(i==0) xo = A[0];
        else xo ^= A[i];
    }
    rep(i,N){
        ll ans = xo^A[i];
        cout << ans << " ";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 4732
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) FOR(i, 0, (n))
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define LAR(a, b) ((a)=max((a),(b)))
#define SML(a, b) ((a)=min((a),(b)))
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;
template<typename T>
using pque = priority_queue<T, vector<T>, greater<T>>;
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define ALL(a) (a).begin(), (a).end()
#ifdef LOCAL_DEBUG
#define DEBUG(...) printf(__VA_ARGS__)
#else
#define DEBUG(...)
#endif

int main(){
	ll n, x, t; scanf("%lld%lld%lld", &n, &x, &t);
	printf("%lld\n", (n+x-1)/x * t);
}


Measured memory_bytes: 3824
#include <cstdio>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

string solve(string s)
{
    int n = s.size();
    for(int i=0; i<n-1; ++i){
        if(s[i] == s[i+1])
            return "No";
    }

    bool ok = true;
    for(int i=0; i<n; ++i){
        if(i % 2 == 0 && s[i] == 'R')
            ok = false;
        if(i % 2 == 1 && s[i] == 'L')
            ok = false;
    }
    if(ok)
        return "Yes";

    ok = true;
    for(int i=0; i<n; ++i){
        if(i % 2 == 1 && s[i] == 'R')
            ok = false;
        if(i % 2 == 0 && s[i] == 'L')
            ok = false;
    }
    if(ok)
        return "Yes";

    return "No";
}

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

    while(--d >= 0){
        string s;
        cin >> s;
        cout << solve(s) << endl;
    }

    return 0;
}

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

int main() {
	int s;
  	cin >> s;
  
  	int s1 = s /100; 
  	int s2 = ( s - s1 * 100 ) /10;
  	int s3 = s - s1 * 100 - s2 * 10;
  	int sum = s1 + s2 + s3;
  
  	cout << sum << endl;  
}

Measured memory_bytes: 256
import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

def main():
    r, c, k = ns()

    mat = [[0 for _ in range(c + 1)] for __ in range(r + 1)]
    for _ in range(k):
        x, y, v = ns()
        x, y = x - 1, y - 1
        mat[x][y] = v

    dp = [[0] * 4 for _ in range(c + 1)]

    for i in range(r):
        ndp = [[0] * 4 for _ in range(c + 1)]
        for j in range(c):
            for n in range(2, -1, -1):
                dp[j][n + 1] = max(dp[j][n + 1], dp[j][n] + mat[i][j])

            ndp[j][0] = max(dp[j])
            for n in range(4):
                dp[j + 1][n] = max(dp[j + 1][n], dp[j][n])
        dp = ndp

    print(max(dp[c - 1]))


if __name__ == '__main__':
    main()


Measured memory_bytes: 230384
const input=require('fs').readFileSync('/dev/stdin', 'utf8').split(/[\s]/);const nin=()=>{const r = input[0];input.shift();return Number(r)};const nrin=(n)=>{const a:number[]=[];rep(n,()=>a.push(nin()));return a};const sin=()=>{const r = input[0];input.shift();return String(r)};const out=(...a)=>{console.log(...a)};const floor=(a)=>{return Math.floor(a)};const abs=(a)=>{return Math.abs(a)};const min=(...a)=>{return Math.min(...a)};const max=(...a)=>{return Math.max(...a)};const rep=(n, callback)=>{for(let i = 0;i < n; i++){callback()}};const strrep=(s, i, v)=>{return s.slice(0, i)+v+s.slice(i+1);};const permutation=({result=[],pre=[],post,n=post.length})=>{if(n>0){post.forEach((_,i)=>{const rest=[...post];const elem=rest.splice(i, 1);permutation({result, pre: [...pre,...elem],post:rest,n:n-1})})}else{result.push(pre)}return result};const sw=(s,a:any[])=>{for(let i=0;i<a.length;i+=2)if(s==a[i])return a[i+1]};const or=(a,...b)=>{for(let i=0;i<b.length;i++)if(a==b[i])return true;return false};
const main = ()=>{
  out(nin()+nin()/2);
}
main();

Measured memory_bytes: 7372
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define Int int32_t
#define all(c) c.begin(), c.end()
#define FAST ios_base::sync_with_stdio(false) , cin.tie(NULL);
#define pii pair< int , int >
#define pb push_back
#define F first
#define S second
#define endl "\n"
#define bitcnt(n) __builtin_popcountll(n)
#define setpre(n) cout << fixed << setprecision(n)
#define tr(c) for(auto x : c )cout << x << " ";
#define ol(c, s, e) for(int pos=s; pos<e ; pos++) cout << c[pos] << " ";
#define PI acos(-1LL)

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

const int M = 1000000007;
const int N = 2e6 + 5;
const long long INF = 1e18 + 37;

void solve() {
    int L,R , d;
    cin >> L >> R >> d;
    cout << R/d - (L-1)/d << endl;
}

signed main(){
    FAST
    int tc = 1;
//    TODO : check for tc
//    cin >> tc;
    for (int t = 1; t <= tc; t++) {
        solve();
    }
}


Measured memory_bytes: 3604
#include<iostream>
#include<cstdlib>
#include<cmath>
#define N 100100
using namespace std;
long long  n,a,b,c[N],l,r;
bool check(int x)
{
    long long ans=0;
    for(int i=1;i<=n;i++)
        ans+=((c[i]-x*b)>0)*ceil(1.0*(c[i]-x*b)/(a-b));
    if (ans<=x) return true;
    else return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>a>>b;
    for(int i=1;i<=n;++i)
        cin>>c[i];
    l=1;r=1000000000;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if (check(mid))
            r=mid-1;
        else
            l=mid+1;
    }
    cout<<l<<endl;
     return 0;
}

Measured memory_bytes: 1024
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;

int32_t N,k;
int32_t one = 0;
int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> N>>k;
	for (size_t i = 0; i < N; i++)
	{
		int a;
		in >> a;
		if (a == 1) {
			one = i;
		}
	}

	out << ((one + k - 2) / (k - 1)) + (N - one-1 - ((k - 1) - (one % (k - 1))) % (k - 1) + (k - 2)) / (k - 1) << endl;



	return 0;
}
#endif



#if 0
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;

int32_t W, Y;
int32_t N, M, D;
int32_t A[50];
int32_t B[100000];
int32_t C[100000];

//日にち、C
std::set<std::pair<int32_t, int>> days;

int32_t func()
{



}

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> W >> Y;
	in >> N >> M >> D;
	for (int32_t i = 0; i < N; i++)
	{
		in >> A[i]; A[i]--;
		days.emplace(A[i], -1);
	}
	for (int32_t i = 0; i < M; i++)
	{
		in >> B[i] >> C[i]; --B[i]; --C[i];
		days.emplace(B[i] * W + C[i], C[i]);
	}





	for (size_t i = 1; i < W; i++)
	{




	}


	return 0;
}
#endif


Measured memory_bytes: 888
void solve();

int main() {
	solve();
	return 0;
}

//////////////////////////////////////////////////
//////////////////////////////////////////////////
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <functional>
#include <map>
#include <string>
#include <boost/multiprecision/cpp_int.hpp>
#include <limits.h>
#include <iomanip>
#include <stack>

using namespace std;
using namespace boost::multiprecision;

//重みなしのグラフのクラス
class graph {
public:
	int N;
	vector<set<int>>* E;
	graph(int);
	graph();
	void constructor(int);
	~graph();
	void addEdge(int, int);
	void removeEdge(int, int);
	bool isConnected(int, int);
};

graph::graph(int n) {
	constructor(n);
}

graph::graph() {
	N = 0;
}

graph::~graph() {
	delete E;
}

void graph::constructor(int n) {
	N = n;
	E = new vector<set<int>>;
	E->resize(N);
}

void graph::addEdge(int a, int b) {
	E->at(a).insert(b);
}

void graph::removeEdge(int a, int b) {
	auto itr = E->at(a).find(b);
	if (itr != E->at(a).end())E->at(a).erase(itr);
}

bool graph::isConnected(int a, int b) {
	return (E->at(a).find(b) != E->at(a).end());
}

int N, M;
graph G;
vector<int> res;
int m = 0;   //次の連結成分を何の数で塗るか
queue<int> q;

void solve() {
	cin >> N >> M;
	G.constructor(N);
	for (int m = 0; m < M; m++) {
		int x, y, z;
		cin >> x >> y >> z;
		x--; y--;
		G.addEdge(x, y);
		G.addEdge(y, x);
	}
	res.resize(N);
	for (int n = 0; n < N; n++)res[n] = -1;   //未決定
	for (int n = 0; n < N; n++) {
		if (res[n] != -1)continue;
		q.push(n);
		while (!q.empty()) {
			int e = q.front();
			q.pop();
			if (res[e] != -1)continue;
			res[e] = m;
			for (auto itr = G.E->at(e).begin(); itr != G.E->at(e).end(); itr++) {
				q.push(*itr);
			}
		}
		m++;
	}
	cout << m << endl;
	return;
}

Measured memory_bytes: 15360
/*************************************************************************
    > File Name: C.cpp
    > Author: PumpkinYing
    > Created Time: 2018/11/5 10:25:27
 ************************************************************************/

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <stack>
#include <cmath>
using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))
#define prii pair<int,int>
#define prdd pair<double,double>
#define rep(i,l,r) for(int i = l;i < r;i++)
#define rep_(i,l,r) for(int i = l;i <= r;i++)
typedef long long ll;

const int maxn = 100010;
char s[maxn];
int fa[maxn];

int main() {
	scanf("%s",s+1);
	int n = strlen(s+1);
	int ok = 1;
	if(s[1] == '0' || s[n] == '1') ok = 0;
	rep_(i,1,n/2) {
		if(s[i] != s[n-i]) ok = 0;
	}
	if(ok == 0) {
		printf("-1\n");
	}
	else {
		int cnt = 1;
		int l = cnt++;
		for(int i = 2;i <= n;i++) {
			if(s[i-1] == '0') {
				fa[cnt++] = l;
			}
			else {
				fa[l] = cnt;
				l = cnt++;
			}
		}
		for(int i = 1;i <= n;i++) if(fa[i] != 0) printf("%d %d\n",i,fa[i]);
	}
    return 0;
}


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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

class union_find{
	private:
	vector<int> parent,rank,gs;
    int size;
	public:
    int count_group;
    union_find()=default;
    union_find(int n){ init(n); }
    void init(int n){
		size=n;
		count_group=n;
		parent.resize(size);
		rank.assign(size,0);
        gs.assign(size,1);
		for(int i=0; i<size; ++i) parent[i]=i;
	}
	int find(int x){
		if(parent[x]==x) return x;
		else return parent[x]=find(parent[x]);
	}
	void unite(int x,int y){
		x=find(x);
		y=find(y);
		if(x==y) return;
		if(rank[x]<rank[y]){
			parent[x]=y;
            gs[y]+=gs[x];
		} else {
			parent[y]=x;
            gs[x]+=gs[y];
			if(rank[x]==rank[y]) ++rank[x];
		}
		--count_group;
	}
	bool is_same_group(int x,int y){
		return find(x)==find(y);
	}
    int group_size(int x){
        return gs[find(x)];
    };
};

struct edge{
    int from,to,cost;
    bool operator<(const edge& other)const{
        return cost<other.cost;
    }
};

void solve(){
    int n,m;
    cin >> n >> m;
    vector<edge> edges;
    rep(i,0,m){
        int a,b,c;
        cin >> a >> b >> c;
        --a;
        --b;
        edges.push_back(edge({a,b,c}));
    }
    sort(edges.begin(),edges.end());

    union_find uf(n);
    vector<bool> use(m);
    int64_t sum_cost=0;
    rep(i,0,m){
        edge &e=edges[i];
        if(uf.is_same_group(e.to,e.from)) continue;
        uf.unite(e.to,e.from);
        sum_cost+=e.cost;
        use[i]=true;
    }

    vector<vector<pair<int,int>>> graph(n);
    rep(i,0,m){
        if(!use[i]) continue;
        graph[edges[i].from].push_back(make_pair(edges[i].to,edges[i].cost));
        graph[edges[i].to].push_back(make_pair(edges[i].from,edges[i].cost));
    }

    vector<vector<int>> max_cost(n,vector<int>(n));
    vector<bool> done(n);
    function<void(int,int,int)> dfs=[&](int s,int u,int ma){
        done[u]=true;
        max_cost[s][u]=ma;
        for(auto &p:graph[u]){
            if(done[p.first]) continue;
            dfs(s,p.first,max(ma,p.second));
        }
        done[u]=false;
    };
    rep(i,0,n) dfs(i,i,0);

    int q;
    cin >> q;
    rep(i,0,q){
        int s,t;
        cin >> s >> t;
        --s;
        --t;
        cout << sum_cost-max_cost[s][t] << endl;
    }
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}


Measured memory_bytes: 69100
import sys
readline = sys.stdin.readline

def check(x):
    if x - 50*A >= 100:
        return N+1
    right = (x+A)//(1+A)
    left = 1
    res = 0
    for l in range(left, right+1):
        cl = calc(l, x-(l-1)*A)
        if res < cl:
            res = cl
    return res
    
    
def calc(k, c):
    return pow(c//k+1, c%k)*pow(c//k, k-c%k)

N, A = map(int, readline().split())


ok = N
ng = 0
while abs(ok-ng)>1:
    med = (ok+ng)//2
    if check(med) >= N:
        ok = med
    else:
        ng = med
    
print(ok)

    

Measured memory_bytes: 38256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;

const int MAX = 1000005;
ll fac[MAX], finv[MAX], inv[MAX];

void cominit()
{
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (ll i=2; i<MAX; i++) {
    fac[i] = fac[i-1] * i % mod;
    inv[i] = mod - inv[mod%i] * (mod/i) % mod;
    finv[i] = finv[i-1] * inv[i] % mod;
  }
}

ll com(ll n, ll k)
{
  if (n<k) return 0;
  if (n<0 || k<0) return 0;
  return fac[n] * (finv[k] * finv[n-k] % mod) % mod;
}

int main()
{
  cominit();
  ll X; cin >> X;
  ll Y; cin >> Y;

  if ((X+Y)%3!=0||min(X,Y)<(X+Y)/3) {
    cout << 0 << endl;
    return 0;
  }

  ll n = (X+Y)/3+1;
  ll t = (n-1)*3;
  ll i = 0;
  for (; i<=n; i++) {
    if (t-(n-1)-i==X) break;
  }
  cout << com(n-1, i) << endl;

  return 0;
}


Measured memory_bytes: 23680
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "

int main(void){
    int n,m;cin>>n>>m;
    map<int, int> sum;
    map<int, bool> AcFlag;
    int p;string s;
    rep(i,m){
        cin>>p>>s;
        if(s=="AC"&&!AcFlag[p])AcFlag[p]=true;
        else if(!AcFlag[p])sum[p]++;
    }
    for(auto itr=AcFlag.begin();itr!=AcFlag.end();++itr){
        if(!itr->second)sum.erase(itr->first);
    }
    int suc=0, pen=0;
    for(auto itr=sum.begin();itr!=sum.end();++itr){
        pen+=itr->second;
    }
    for(auto i=AcFlag.begin();i!=AcFlag.end();++i){
        if(i->second)suc++;
    }

    cosp(suc);co(pen);    
}


Measured memory_bytes: 6144
//ITNOA
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
const long long INF=1e9+10,MAX=2e5+1e4,MOD=1e9+7,MAXL=25;
typedef long long ll;
typedef pair<ll,ll> pii;
typedef pair<pii,ll> piii;
void OUT(long double o,int x){
	 cout<<fixed<<setprecision(x)<<o;
	 return;
}
ll a[MAX];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll n,t=0,x,y=0,la;
	cin>>n;
	x=n;
	la=n;
	while(x){
		la=x;
		x/=10;
		y++;
	}
	x=n;
	while(x){
		if(x%10!=9&&x/10!=0)
			return cout<<la+y*9-10,0;
		else
			t+=x%10;
		x/=10;
	}
	cout<<t;
	return 0;
}


Measured memory_bytes: 764
#include <iostream>
#include <cmath>
using namespace std;
const int Max_N=1e5+10;
int n;
int a[Max_N];
int dp[Max_N];
int main(){
    cin >> n;
    
    for(int i = 0 ; i < n ; i++){
        cin >>a[i];
    }
    dp[0]=0;
    dp[1]=abs(a[0]-a[1]);
    
    for(int i = 2; i < n ; i++){
        dp[i] = min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i-2]-a[i]));
    }
    cout << dp[n-1];
    
    return 0;
}





Measured memory_bytes: 1024
N = int(input())
H = list(map(int, input().split()))
cnts = []
cnt = 0
for i in range(1, N):
    if H[i-1] >= H[i]:
        cnt += 1
    else:
        cnts.append(cnt)
        cnt = 0
cnts.append(cnt)
print(max(cnts))

Measured memory_bytes: 14252
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
using VS = vector<string>;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);--(i))
#define each(i, a) for(auto &i : a)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
#define out(y,x) ((y) < 0 || h <= (y) || (x) < 0 || w <= (x))
#define line cout << "-----------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause")
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
constexpr ld pi = 3.1415926535897932;
template<class T>inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; }return false; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T>inline istream& operator>>(istream& is, deque<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }

int main() {
    init();

    ll x; cin >> x;
    ll n = 100;
    for (int i = 1; true; ++i) {
        n += n / 100;
        if (x <= n) {
            cout << i << "\n";
            break;
        }
    }
}

Measured memory_bytes: 3652
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,a[300005],b[300005],w[300005],f[300005],x;
bool check(int v)
{
	memset(f,0,sizeof(f));
	f[0]=1;
	x=0;
	for(int i=1;i<=n;i+=2)
	{
		if(w[i]-b[i]-x<=v)
		{
			f[i]=1;
			x=max(x,w[i+1]-b[i+1]);
		}
	}
	return f[n];
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		b[i]=b[i-1],w[i]=w[i-1];
		if(i&1)b[i]+=a[i];
		else w[i]+=a[i];
	}
	if(n%2==0)return printf("%d %d\n",max(b[n],w[n]),min(b[n],w[n])),0;
	int l=-w[n]-b[n],r=w[n]+b[n];
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid))r=mid-1;
		else l=mid+1;
	}
	printf("%d %d\n",w[n]-l,b[n]+l);
	return 0;
}

Measured memory_bytes: 4864