akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  
#include <chrono>
#include <random>
#include <time.h>
#include <fstream>
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define endl "\n"
#define all(c) begin(c),end(c)
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}


#define LLINF 1e18+7
#define N 250000
ll MOD=998244353;
vector<vec> G;


main(){
    int n=in();
    string x;cin>>x;
    int a=0,b=0,bb=0;
    rep(i,x.size()){
      if(x[i]=='0')a++;
      else break;
    }
    rep2(i,a+1,x.size()){
      if(x[i]=='1')b++;
      else break;
    }
    if(a==0){
      rep2(i,b+1,x.size()){
        if(x[i]=='0')bb++;
      }
    }
    ll ANS=0;
    vector<ll> d(n+1);
    rep3(i,n,3){
      ll ans=0;
      int c=n/i;
      if(n%i==0&&i%2){
          string y;
          rep(j,c){
            y.pb(x[j]);
          }
          ll t=1,sum=0;
          rep(j,c){
            if(y[c-j-1]=='1')sum=(sum+t)%MOD;
            t=t*2%MOD;
          }
          ans=sum;
          string yy;
          rep(j,c){
              if(y[j]=='0')yy.pb('1');
              else yy.pb('0');
          }
          string z=y;
          rep(j,i/2){
              z+=yy;
                z+=y;
          }
          if(z<=x)ans++;
          ans-=d[c];
          ANS=(ANS+ans*(-n*2+c*2)%MOD+MOD)%MOD;
          for(int j=c*2;j<=n;j+=c){
              d[j]+=ans;
          }
          //cout<<c<<" "<<ans<<endl;
      }
    }
    //cout<<MOD-ANS<<endl;
    ll t=1;
    rep(i,n){
      if(x[n-1-i]=='1')ANS=(ANS+2*n*t)%MOD;
      t=t*2%MOD;
    }
    cout<<(ANS+n*2)%MOD<<endl;
}

Measured memory_bytes: 2644
#include<bits/stdc++.h>
using namespace std;
int main()
{
	  ios::sync_with_stdio(0);
      cin.tie(0);
     unsigned  long long int n,m,i,b;
      cin>>b;
      i=0;
      n=100;
      while(1)
      {
      	i++;
      	n=n+(n/100);
      	if(n>=b)
      	{
      		break;
		  }
	  }
	  cout<<i<<"\n";
	  return 0;
}

Measured memory_bytes: 3652
#include<iostream>
#include<math.h>
#include<string>
#include<algorithm>
using namespace std;

int main(){
	int a,b,c;
	cin>>a>>b>>c;
	if(b>=c)cout<<"delicious"<<endl;
	else if(c-b>a)cout<<"dangerous"<<endl;
	else cout<<"safe"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct Fast {
    Fast() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} fast;

long long mod = 998244353;
#define REP(i, n) for (long long i = 0; i < (n); i++)

long long modpow(long long m, long long n) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        long long t = modpow(m, n / 2);
        return t * t % mod;
    } else {
        return modpow(m, n - 1) * m % mod;
    }
}

long long moddiv(long long a, long long b) { return (a * modpow(b, mod - 2)) % mod; }

long long nCkmod(long long n, long long k) {
    long long denomi = 1;
    REP(i, n) {
        denomi *= (i + 1);
        denomi %= mod;
    }
    long long numera = 1;
    for (int i = n - k; i > 0; i--) {
        numera *= i;
        numera %= mod;
    }
    REP(i, k) {
        numera *= (i + 1);
        numera %= mod;
    }
    return moddiv(denomi, numera);
}

void print_binary(long long a) {
    for (int i = 31; i >= 0; i--) {
        cout << (a >> i & 1);
    }
    cout << endl;
}

void yes() {
    cout << "Yes" << endl;
    exit(0);
}
void no() {
    cout << "No" << endl;
    exit(0);
}

vector<int> h, memo;

// int dp(int n) {
//     if (memo[n] != -1) {
//         return memo[n];
//     }
//     if (n == 0) {
//         return 0;
//     }
//     if (n == 1) {
//         return abs(h[1] - h[0]);
//     }
//     memo[n] = min(dp(n - 1) + abs(h[n] - h[n - 1]), dp(n - 2) + abs(h[n] - h[n - 2]));
//     return min(dp(n - 1) + abs(h[n] - h[n - 1]), dp(n - 2) + abs(h[n] - h[n - 2]));
// }
signed main() {
    long long n, m, k;
    cin >> n >> m >> k;
    vector<long long> fac(n + 1);
    fac[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = fac[i - 1] * i;
        fac[i] %= mod;
    }
    long long ans = 0;
    REP(i, k + 1) {
        ans += ((m * modpow(m - 1, n - i - 1)) % mod) * moddiv(fac[n - 1], fac[n - i - 1] * fac[i] % mod) % mod;
        ans %= mod;
    }
    cout << ans << endl;
}

Measured memory_bytes: 4796
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <iostream>
#include <fstream>
#include <numeric>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <cmath>
#include <set>
#include <map>
#include <functional>
#include <bitset>
#include <iomanip>
#include <stack>
#include <list>
#include <cstdint>
#include <chrono>

using namespace std;
#define     loop(n,i,a)     for(ll i=a;i<n;i++)
#define     loopR(n,i,a)    for(ll i=a-1;i>=n;i--)
#define     all(arr,n)      arr,arr+n
#define     allv(v)         (v).begin(),(v).end()
#define     rallv(v)        (v).rbegin(),(v).rend()
#define     m_p             make_pair
#define     ll              long long
#define     pii             pair<ll,ll>
#define     vi              vector<int>
#define     vll             vector<ll>
#define     vii             vector<pii>
#define     sz(x)           (int)x.size()
#define     pb              push_back
#define     endl            "\n"
#define     Endl            "\n"
#define     f               first
#define     s               second
#define     mem(dp,n)       memset(dp,n,sizeof dp)
int dx[] = { 1 , 0 ,-1 , 0 ,-1 ,-1 , 1 , 1 };
int dy[] = { 0 , 1 , 0 ,-1 ,-1 , 1 ,-1 , 1 };
int KnightI[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int KnightJ[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
template<typename T>
void max_self(T &a,T b){
    a=max(a,b);
}
template<typename T>
void min_self(T &a,T b){
    a=min(a,b);
}
void fast(){
    std::ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
vector<string> vec_splitter(string s) {
    s += ',';
    vector<string> res;
    while(!s.empty()) {
        res.push_back(s.substr(0, s.find(',')));
        s = s.substr(s.find(',') + 1);
    }
    return res;
}
void debug_out(
        vector<string> __attribute__ ((unused)) args,
        __attribute__ ((unused)) int idx,
        __attribute__ ((unused)) int LINE_NUM) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
    if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
    stringstream ss; ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, LINE_NUM, T...);
}
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
const ll mxN=5e5+10,oo=0x3f3f3f3f,MOD=1e9+7;
const double PI = acos(-1);

void solve(){
    double n;
    cin>>n;
    int q=n;
    n/=108;
    int x=n*100;
    int y=x+1;
    if(x*1.08-q>=0&&x*1.08-q<1)
        cout<<x<<endl;
    else if(y*1.08-q>=0&&y*1.08-q<1)
        cout<<y<<endl;
    else
        cout<<":("<<endl;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    fast();
    solve();

}


Measured memory_bytes: 3776
package main

import (
	"fmt"
	"strconv"
)

func main() {
	ans := []string{}

	for {
		var a, b int
		var op rune

		fmt.Scanf("%d %c %d", &a, &op, &b)

		if string(op) == "+" {
			ans = append(ans, strconv.Itoa(a+b))
		} else if string(op) == "-" {
			ans = append(ans, strconv.Itoa(a-b))
		} else if string(op) == "*" {
			ans = append(ans, strconv.Itoa(a*b))
		} else if string(op) == "/" {
			ans = append(ans, strconv.Itoa(a/b))
		} else if string(op) == "?" {
			break
		}
	}
	for _, v := range ans {
		fmt.Println(v)
	}
}



Measured memory_bytes: 1128
#include <bits/stdc++.h>
#define EB emplace_back

typedef long long ll;
typedef std::pair <int, int> pr;
typedef std::vector <int> vector;
const int mod = 1000000007, pmod = mod - 1;

inline void add(int &x, const int y) {x += y - mod, x += x >> 31 & mod;}
inline void sub(int &x, const int y) {x -= y, x += x >> 31 & mod;}
ll PowerMod(ll a, int n, ll c = 1) {for (n += n >> 31 & pmod; n; n >>= 1, a = a * a % mod) if (n & 1) c = c * a % mod; return c;}

pr solve(const vector &h) {
	int i, j = -1, n = h.size(), x, y = 0, P1 = 1, P2 = 1, C1, C2, W = n;
	vector S; x = *std::min_element(h.begin(), h.end());
	for (i = 0; i <= n; ++i)
		if (i == n || h[i] == x) {
			if (j + 1 == i) ++j;
			else if (j + 2 == i) ++j, P1 = PowerMod(2, h[j] - x, P1), P2 = PowerMod(2, h[j] - x, P2), ++j;
			else {
				W -= i - j - 1, S.clear(), S.reserve(i - j - 1);
				for (++y; ++j < i; S.EB(h[j] - x));
				std::tie(C1, C2) = solve(S), P1 = (ll)P1 * (C1 + C2) % mod, P2 = (ll)P2 * C2 % mod;
			}
		}
	C2 = PowerMod(2, x, P2), C1 = PowerMod(2, W, P1), sub(C1, P2), sub(C1, P2);
	return add(C1, C2), pr(C1, C2);
}

int main() {
	int i, n, x; vector h;
	scanf("%d", &n), h.reserve(n);
	for (i = 0; i < n; ++i) scanf("%d", &x), h.EB(x);
	printf("%d\n", solve(h).first);
	return 0;
}

Measured memory_bytes: 256
import math
N, D = map(int, input().split())
X = [0] * N
Y = [0] * N
for i in range(N):
    X[i], Y[i] = map(int, input().split())

ans = 0
for i in range(N):
    dis = math.sqrt(X[i]**2 + Y[i]**2)
    if dis <= D:
        ans += 1
print(ans)



Measured memory_bytes: 24724
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
    ll  k,x;
    cin>>k>>x;
    if(500*k>=x){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }

   return 0;

}


Measured memory_bytes: 3576
#include<iostream>
#include<math.h>
#include<algorithm>
#include<utility>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<unordered_map>
#include<stack>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll INF=2e18;

ll N;
ll B[100010];
int main(){
    cin>>N;
    for(ll i=0;i<N-1;i++){
        cin>>B[i];
    }
    ll ans=0;
    for(ll i=0;i<N-2;i++){
        ans+=min(B[i],B[i+1]);
    }
    cout<<ans+B[0]+B[N-2];
    return 0;
}

Measured memory_bytes: 256
# AまででのＡＣの数を0からＮまで保存して、毎回引き算すればいい？
N, Q = map(int, input().split())
S = input()
numofAC = [0] * N
for j in range(1, N):
    numofAC[j] = numofAC[j-1]
    if S[j-1: j + 1] == "AC":
        numofAC[j] += 1
for i in range(Q):
    l, r = map(int, input().split())
    print(numofAC[r-1]-numofAC[l-1])


Measured memory_bytes: 6140
#include "bits/stdc++.h"
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
typedef long long ll;

using namespace std;

// init {{{
struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if (AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


const int NM = 201001;
ll P[NM];
ll MOD = 1000000007;

void solve() {
    string S,C;
    cin >> S >> C;
	ll cnt = 0;

	REP(i,3){ if(S.at(i) == C.at(i)) cnt++; }
  
	cout << cnt;
    return;
}


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

Measured memory_bytes: 256
#include <math.h>
#include <regex>
#include "bits/stdc++.h"
#define FOR(i, s, e) for (int i = int(s); i < int(e); ++i)
#define REP(i, e) FOR(i, 0, e)
#define INF (INT_MAX / 2)
#define EPS (1.0e-8)
#define LINF (LLONG_MAX / 2)
const int MGN = 10;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vd = vector<double>;
using vs = vector<string>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using psi = pair<string, int>;

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd(b, a%b);
}

void prime_factorize(map<ll,ll>& fac, ll n) {
    for(int p = 2; (ll)p*p <= n; p++) {
        //if (is_prime(p)) {
        if (n%p != 0) continue; // p is not n's devisor
        else {
            while(n%p == 0) {
              fac[p]++;
              n /= p;
            }
        }
    }
    if (n > 1) fac[n]++;
}


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

  ll A,B; cin >> A >> B;

  ll C = gcd(A, B);
  
  map<ll,ll> mp;
  prime_factorize(mp, C);

  int ans = mp.size() + 1;
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,P> PP;
int N,Ac[100010] = {0},Bc[100010] = {0},A[100010],B[100010];
ll a,b;
vector<PP> v;
int main(){
	cin >> N;
	ll ansa = 0,ansb = 0;
	for(int i=1;i<=N;i++){
		cin >> A[i] >> B[i];
		v.push_back({A[i],{0,i}});
		v.push_back({B[i],{1,i}});
		ansa += A[i]; ansb += B[i];
	}
	sort(v.begin(),v.end());
	ll ans = 0;
	for(int i=0;i<N;i++){
		ans += v[i].first;
		if(v[i].second.first==0) Ac[v[i].second.second]++;
		else Bc[v[i].second.second]++;
	}
	bool judge = false;
	for(int i=1;i<=N;i++){
		if(Ac[i]==1 && Bc[i]==1) judge = true;
	}
	if(judge){
		cout << min(min(ansa,ansb),ans) << endl;
		return 0;
	}
	ll ans2 = 1e18;
	for(int i=1;i<=N;i++){
		if(Ac[i]==1){
			if(v[N].second.second!=i) ans2 = min(ans2,ans-A[i]+v[N].first);
			else ans2 = ans2 = min(ans2,ans-A[i]+v[N+1].first);
		}else{
			if(v[N].second.second!=i) ans2 = min(ans2,ans-B[i]+v[N].first);
			else ans2 = ans2 = min(ans2,ans-B[i]+v[N+1].first);
		}
	}
	cout << min(min(ansa,ansb),ans2) << endl;
}

Measured memory_bytes: 7024
#include<iostream>
#include<vector>
#include<string>
#include<string.h>
#include<algorithm>
using namespace std;

int main(){
	int r,D,a;
	cin>>r>>D>>a;
	long long x[10];
	x[0]=a*r-D;
	for(int i=1;i<10;i++){
		x[i]=r*x[i-1]-D;
	}
	for(int i=0;i<10;i++){
		cout<<x[i]<<endl;
	}
}

Measured memory_bytes: 256
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

def main():
    x,y,z,k=MI()
    set_=set()
    A=sorted(LI(),reverse=True)
    B=sorted(LI(),reverse=True)
    C=sorted(LI(),reverse=True)
    Q=[[(A[0]+B[0]+C[0])*(-1),0,0,0]]
    heapify(Q)
    set_.add((0,0,0))
    #print(Q)
    i=0
    ans=[]
    #print(heappop(Q))
    #al=[[[-1]*x for i in range(y)] for j in range(z)]
    #al[0][0][0]=0
    xl,yl,zl=0,0,0
    al=[]
    al=[[0,0,0]]
    while i<k:
        #print(Q)
        a,u,v,w=heappop(Q)
        ans.append([-a,u,v,w])
        print(-a)
        i+=1
        if u+1<x and (u+1,v,w) not in set_:
            heappush(Q,[-A[u+1]-B[v]-C[w],u+1,v,w])
            set_.add((u+1,v,w))
            #al.append([u+1,v,w])
            
            #al[u+1][v][w]=0
        if v+1<y and (u,v+1,w) not in set_:
            heappush(Q,[-A[u]-B[v+1]-C[w],u,v+1,w])
            set_.add((u,v+1,w))
            #al.append([u,v+1,w])
            #al[u][v+1][w]=0
        if w+1<z and (u,v,w+1) not in set_:
            heappush(Q,[-A[u]-B[v]-C[w+1],u,v,w+1])
            set_.add((u,v,w+1))
            #al.append([u,v,w+1])
if __name__=="__main__":
    main()
    

    
    


Measured memory_bytes: 94988
#include <stdio.h>
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
 
using namespace std;
 
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int A, B;

	cin >> A >> B;

	cout << 6 - A - B << endl;


}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#define LL long long
int ans;
int g;
int main() {
	std::string S;
	std::cin >> S;
	for (auto u : S) {
		if (u == 'g') {
			if (g) {
				ans++;
				g--;
			}
			else {
				g++;
			}
		}
		else {
			if (g) {
				g--;
			}
			else {
				ans--;
				g++;
			}
		}
	}
	std::cout << ans << std::endl;
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define FOR(i,a,b)  for(int (i)=(a);(i)<(b);(i)++)
#define REP(i,n)    FOR(i,0,n)
#define RER(i,n)    FOR(i,0,(n+1))
#define pb          push_back
#define mp(a,b)     make_pair((a),(b))
#define mset(m,v)   memset(m,v,sizeof(m))
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pair<int, int> > vpii;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll,ll> pll;
typedef vector<pair<ll, ll> > vpll;
typedef vector<string> vs;
typedef long double ld;
const double EPS    = 1e-10;
const int INF       = 1e+9;
const double PI     = acos(-1);


auto main() -> int
{
    int a, b, c;
    cin >> a >> b >> c;
    if ( c >= a && c <= b ) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}



Measured memory_bytes: 256
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define PR pair
#define fi first
#define se second
#define mk make_pair
#define pb push_back
#define REP(i, x, y)   for(int i = (int)(x); i <= (int)(y); i++)
#define FOR(i, x, y)   for(int i = (int)(x); i <  (int)(y); i++)
#define PER(i ,x, y)   for(int i = (int)(x); i >= (int)(y); i--)
#define CH	         ch = getchar()
#define Exit(...)    printf(__VA_ARGS__), exit(0)
#define dln()        fprintf(stderr,"\n")
#define dprintf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef double	  db;
typedef long long LL;
typedef vector<int> VI;
typedef vector<VI > VII;
typedef PR<int,int> PII;
typedef vector<PII> VPI;
const	int inf=2e9;
const	LL Inf=1e10;
const	int P=1e9+7;
const	int N=100005;

inline LL IN(){
	LL x = 0;
	int ch = 0, f = 0;
	for (CH; ch != -1 && (ch < 48 || ch > 57); CH) f = (ch == '-');
	for (; ch >= 48 && ch <= 57; CH) x = (x << 1) + (x << 3) + ch - '0';
	return f ? (-x) : x;
}
template<typename T> inline int chkmin(T &a, const T &b){if(b < a) return a = b, 1; return 0;}
template<typename T> inline int chkmax(T &a, const T &b){if(b > a) return a = b, 1; return 0;}

void renew(int &x, const int &y){
	x += y;
	if(x >= P) x -= P;
	if(x <  0) x += P;
}

int Pow(int x, int y, int p){
	int a = 1;
	for (; y; y >>= 1, x = (LL)x * x %p) if(y & 1) a=(LL)a * x%p;
	return a;
}

int Msk[31];
int Max[N << 2], Mex[N << 2];
int n, a[N];
struct edge{
	int v, pre;
}e[N << 1]; int dex, adj[N], fa[N], dp[N];
int maxlab = 0, U;

int ans;
void dfs(int x){
	int s = 0, t = 0;
	for(int i = adj[x]; i; i = e[i].pre){
		int v = e[i].v;
		if(v == fa[x]) continue;
		fa[v] = x;
		dfs(v);
		t |= (dp[v] & s);
		s |= dp[v];
	}
	int lab = Mex[s | Max[t]];
	dp[x] = s & Msk[lab];
	dp[x] |= 1 << lab;
	ans = max(ans, lab);
}

void prebitcalc(){
	for(int m = n; m; ){
		m >>= 1;
		maxlab ++;
	}
	U = 1 << maxlab;
	U --;
	memset(Max, -1, sizeof Max);
	REP(i, 0, maxlab) Max[(1 << i) - 1] = (1 << i) - 1;
	PER(i, U, 0) if(Max[i] < 0) Max[i] = Max[i + 1];
	REP(i, 0, maxlab) Msk[i] = (U >> i) << i;
	Mex[0] = 0;
	Mex[1] = 1;
	REP(i, 1, U) if(!(i & 1)) Mex[i] = 0; else Mex[i] = Mex[i >> 1] + 1;

}

int main(){
	scanf("%d", &n);
	prebitcalc();
	REP(i, 1, n - 1){
		int x, y;
		scanf("%d%d", &x, &y);
		e[++dex] = (edge){y, adj[x]}; adj[x] = dex;
		e[++dex] = (edge){x, adj[y]}; adj[y] = dex;
	}
	dfs(1);
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
using lint     = long long;
const lint inf = 1LL << 60;
const lint mod = 1000000007;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    lint n;
    cin >> n;
    vector<lint> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<lint> as = a;
    sort(as.begin(), as.end());
    for (int i = 0; i < n; ++i) {
        if (a[i] == as[n - 1])
            cout << as[n - 2] << "\n";
        else
            cout << as[n - 1] << "\n";
    }

    return 0;
}

Measured memory_bytes: 4736
#include <iostream>
#include <vector>
#include <queue>

int bfs(int H, int W, int si, int sj,
    const std::vector<std::string> &S)
{
    std::queue<std::pair<int, int>> q;
    q.push(std::make_pair(si, sj));

    constexpr int INF = 1<<29;
    std::vector<std::vector<int>> d(H, std::vector<int>(W, INF));
    d[si][sj] = 0;

    constexpr int di[] = {0, -1, 0, 1};
    constexpr int dj[] = {-1, 0, 1, 0};

    while (!q.empty()) {
        auto curr = q.front(); q.pop();
        int ci = curr.first;
        int cj = curr.second;

        for (int i = 0; i < 4; i++) {
            int ni = ci + di[i];
            int nj = cj + dj[i];

            if (nj < 0 || nj >= W || ni < 0 || ni >= H || S[ni][nj] == '#')
                continue;

            if (d[ci][cj] + 1 < d[ni][nj]) {
                d[ni][nj] = d[ci][cj] + 1;
                q.push(std::make_pair(ni, nj));
            }
        }
    }

    int max = 0;
    for (int i = 0; i < H; i++)
        for (int j = 0; j < W; j++)
            if (d[i][j] != INF)
                max = std::max(max, d[i][j]);
                
    return max;
}

int main()
{
    int H, W;

    std::cin >> H >> W;
    std::vector<std::string> S(H);
    for (int i = 0; i < H; i++) {
        std::cin >> S[i];
    }

    int max = 0;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (S[i][j] == '#')
                continue;

            max = std::max(max, bfs(H, W, i, j, S));
        }
    }
    std::cout << max << std::endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
//#include <stdio.h>
using namespace std;

int main(){
	int a, b, answer;
	char op;
	while (1){
		cin >> a >> op >> b;
		switch (op){
		case '+':
			answer = a + b;
			break;
		case '-':
			answer = a - b;
			break;
		case '*':
			answer = a * b;
			break;
		case '/':
			answer = a / b;
			break;
		case '?':
			return 0;
			break;
		default:
			break;
		}
		cout << answer << endl;
	}
	//printf("%lf %lf\n",r * r * PI, r* 2* PI);
	return 0;
}

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

int N;
int L[400];

int comp(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}
#define min(a,b) ((a > b) ? b : a)
int main(void)
{
    int i;
    int S = 0;
    scanf("%d",&N);
    for (i = 0; i < 2*N; i++)
        scanf("%d",&L[i]);
    qsort(L, 2*N, sizeof(int), comp);
    for (i = 0; i < N; i++)
        S += min(L[2*i], L[2*i+1]);
    printf("%d\n", S);
    return 0;
}


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

using namespace std;

int main(){
    int n,count=1;
    cin >>n;
    int p[n];
    for(auto & e:p) cin >>e;

    for(int i=0;i<n-1;i++){
        p[0] = min(p[0],p[i]);
        if(p[0]>=p[i+1]){
            //cout <<p[0]<<"/"<<p[i+1]<<endl;
            count++;
        }
    }
    cout <<count <<endl;
}

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

#define MEM(a, b) memset(a, (b), sizeof(a))
#define FOR(i, j, k, in) for (int i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (int i=j ; i>=k ; i-=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define MP make_pair
#define PB push_back
#define PI 3.1415926535897932384626433832795
typedef long long ll;
#define MOD 998244353
ll gcd(ll a,ll b){if (b == 0)return a;return gcd(b, a % b);} 
vector< pair<int,int> >v;
#define cases int t;cin>>t;while(t--)

int main()
{
ll n,m;
cin>>n>>m;
ll a[n];
ll votes  =0;
REP(i,n){
    cin>>a[i];
    votes += a[i];
}

ll ans = 0 , i=0;
for(i=0;i<n;i++){
    if(a[i] * (m * 4) >= votes){
        ans++;
    }
}

if(ans >= m)cout<<"Yes\n";
else cout<<"No\n";
}


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

int main() {
  ll x;
  cin >> x;
  vector<ll> p(401, 0);

  // 先に5乗を計算する
  for (ll i = 0; i < 201; i++) {
    p.at(i + 200) = i * i * i * i * i;
    p.at(-i + 200) = -p.at(i + 200);
  }

  // 該当の整数の組を探す
  rep(i, 401) rep(j, 401) {
    if (p.at(i) - p.at(j) == x) {
      cout << i - 200 << " " << j - 200 << endl;
      return 0;
    }
  }
  return 0;
}

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

bool isNum(char c) {
  if('0' <= c && c <= '9') { return true; }
  return false;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a, b;
  cin >> a >> b;
  string S;
  cin >> S;
  bool flag = true;
  if(S[a] != '-') flag = false;
  for(int i = 0; i < a + b + 1; i++) {
    if(i == a) continue;
    if(!isNum(S[i])) flag = false;
  }
  if(flag)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;

  return 0;
}

Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        if (hasNextByte())
            return buffer[ptr++];
        else
            return -1;
    }

    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr]))
            ptr++;
        return hasNextByte();
    }

    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext())
            throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
            throw new NumberFormatException();
        return (int) nl;
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}

public class Main {
    static int MOD = 1000000007;

    public static class Mas {
        int x;
        int y;
        int step;

        Mas(int x, int y, int step) {
            this.x = x;
            this.y = y;
            this.step = step;
        }
    }

    private static final int[] vX = { 1, 0, 0, -1 };
    private static final int[] vY = { 0, 1, -1, 0 };

    public static void main(String[] args) {

        FastScanner fs = new FastScanner();
        int n = fs.nextInt();
        int[] a = new int[n];
        int[] s = new int[n];
        for (int i = 0; i < n-1; i++) {
            a[i] = fs.nextInt()-1;
            s[a[i]]++;
        }
        for (int i = 0; i < n; i++) {
            System.out.println(s[i]);
        }

    }

}


Measured memory_bytes: 55244
N, M = map(int, input().split())
a = list(map(int, input().split()))
bc = [tuple(map(int, input().split())) for _ in range(M)]
bc.sort(key=lambda x: -x[1])
rest = N
for b, c in bc:
  a += [c] * min(rest, b)
  rest -= min(rest, b)
a.sort(reverse=True)
print(sum(a[:N]))

Measured memory_bytes: 25316
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
ts=time.time()
sys.setrecursionlimit(10**6)
#input=sys.stdin.readline().rstrip
show_flg=False
show_flg=True

ans=0
n=I()
a=[]
f=1
tmp=0
for i in range(n):
    f*=(1+i)
    x,y=LI()
    a.append((x,y))
for k in permutations(range(n)):
    for i in range(n-1):
        p,q=k[i],k[i+1]
        x,y=a[p]
        s,t=a[q]
        tmp+=((x-s)**2+(y-t)**2)**0.5

ans=tmp/f
print(ans)


Measured memory_bytes: 42600
#include<iostream>
#include<string>
using namespace std;
int main()
{
	int H,W;//行。列 
	cin>>H>>W;
	char a[H][W];
	int b[H][W];
	for(int i=0;i<H;i++)
	{
		for(int j=0;j<W;j++)
		{
			cin>>a[i][j];
		}
	}
	for(int i=0;i<H;i++)
	{
		for(int j=0;j<W;j++)
		{
			b[i][j]=0;
		}
	}
	for(int i=0;i<H;i++)
	{
		for(int j=0;j<W;j++)
		{
			if(a[i][j]=='.'){
			
			if((i-1)>=0)//上 
			{
				if(a[i-1][j]=='#')
				b[i][j]+=1;
			}
		//	a[i][j]
			if(j+1<W)//右 
			{
				if(a[i][j+1]=='#')
				b[i][j]+=1;
			}
			if((j-1)>=0)//left 
			{
				if(a[i][j-1]=='#')
				b[i][j]+=1;
			}
			
			if((i+1)<H)//down 
			{
				if(a[i+1][j]=='#')
				b[i][j]+=1;
			}
			
			if((i-1)>=0&&(j+1<W))//上 right
			{
				if(a[i-1][j+1]=='#')
				b[i][j]+=1;
			}
			
			if((j-1)>=0&&(i+1)<H)//left down
			{
				if(a[i+1][j-1]=='#')
				b[i][j]+=1;
			}
			if((j+1)<W&&(i+1)<H)//右 down
			{
				if(a[i+1][j+1]=='#')
				b[i][j]+=1;
			}
			if((j-1)>=0&&(i-1)>=0)//left down
			{
				if(a[i-1][j-1]=='#')
				b[i][j]+=1;
			}}
			else if(a[i][j]='#')
			{
				b[i][j]=9;
			}
		}
	}
	
	for(int i=0;i<H;i++)
	{
		for(int j=0;j<W;j++)
		{
			if(b[i][j]!=9)
				cout<<b[i][j];
			else
				cout<<'#';
		}
		cout<<endl;
	}
 } 

Measured memory_bytes: 256
N, K = map(int, input().split())

def ncr(n, r, p):
  num = den = 1
  for i in range(r):
    num = (num * (n - i)) % p
    den = (den * (i + 1)) % p
  return (num * pow(den, p - 2, p)) % p
p=10**9+7

for i in range(1, K+1):
  ans = (ncr(N-K+1, i, p) % p) * (ncr(K-1, i-1, p) % p) % p
  print(ans)

Measured memory_bytes: 3316
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#include<string.h>

int n,m,*arr,*mem;

int min(int x, int y)
{
    return x<y ? x :y;
}

int min_coin_change(int n) 
{
    if(n==0) return 0;
    if(mem[n] != -1) return mem[n];

    int s_rlt, rlt = INT_MAX;

    for(int i=0; i<m; i++)
    {
        if(arr[i] <= n)
        {
            s_rlt = min_coin_change(n-arr[i]);
        }

        if(s_rlt != INT_MAX) rlt = min(rlt,s_rlt+1);
    }

    return mem[n] = rlt;
    
}

int main()
{
    scanf("%d %d",&n,&m);
    arr = (int*)malloc(sizeof(int)*m);
    mem = (int*)malloc(sizeof(int)*(n+10));
    memset(mem,-1,sizeof(int)*(n+10));

    for(int i=0; i<m; i++)
    {
        scanf("%d",&arr[i]);
    }
    
    printf("%d\n",min_coin_change(n));

    free(arr);
    free(mem);
    return 0;
}


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

int main(){
	int N;
	cin >> N;
	vector<int> P(N);
	for(auto &i:P)cin >> i;
	
	int ans=0;
	int m=9999999;
	for(int i=0;i<N;i++){
		if(P[i]<m)ans++;
		m=min(m,P[i]);
	}
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 1024
import sys,collections
n = int(sys.stdin.readline())
#A = list(map(int,sys.stdin.readline().split()))
A = [[x,int(y)] for x,y in [line.split() for line in sys.stdin.readlines()]]
d = {}
for i,p in enumerate(A):
  d[str(p)]=i
def partition(A,p,r):
  x = A[r][1] #pivod
  i = p    #high-start
  for j in range(p,r): #high-end
    if A[j][1] <= x:
      A[i],A[j] = A[j],A[i]
      i += 1
  A[i],A[r] = A[r],A[i]
  return i
def quicksort(A,p,r):
  if p < r:
    q = partition(A,p,r)
    quicksort(A,p,q-1)
    quicksort(A,q+1,r)
quicksort(A,0,len(A)-1)
for i in range(1,n):
  if A[i-1][1]==A[i][1] and d[str(A[i-1])] > d[str(A[i])]:
    print("Not stable")
    print("\n".join([p[0]+" "+str(p[1]) for p in A]))
    exit(0)
print("Stable")
print("\n".join([p[0]+" "+str(p[1]) for p in A]))


Measured memory_bytes: 40048
#include<string>
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<chrono>
#include<functional>
#include<random>
#include<unordered_set>
using namespace std;
typedef long long int llint;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
const int mod=1000000007;
const int big=1e9+10;
const long double pai=3.141592653589793238462643383279;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
llint gcd(llint a,llint b){if(b==0){return a;}return gcd(b,a%b);}//a>b
llint lcm(llint a,llint b){return (a/gcd(max(a,b),min(a,b)))*b;}
int main(void){
	int n,m,q,i,j,zyu=1,nai=0;cin>>n>>m>>q;
	vector<int>ban(q);//入力 番号
	vector<deque<int>>numlis(m+1);//どこに番号があるのだろう?
	multiset<int>las;//最後に番号入れたのいつ？
	vector<bool>mita(m+1);
	for(i=0;i<n;i++){las.ins(big);}
	for(i=0;i<q;i++){
		int in;cin>>in;
		ban[i]=in;
		numlis[in].puf(i);
	}
	for(i=q-1;i>=0;i--){
		int no=ban[i];
		if(mita[no]){continue;}//skipped
		bool mincan=false;
		while(mita[zyu]){zyu++;}
		mita[no]=true;
		mincan=(zyu==no);
		vector<int>iti;
		int x=0;
		for(j=0;j<numlis[no].size()&&x<n;j++){
			auto it=las.lower_bound(numlis[no][j]);
			if(it==las.end()){continue;}
			x++;//成功数
			iti.pub(numlis[no][j]);
			las.erase(it);
		}
		if(x<n&&(!mincan)){cout<<"No"<<endl;return 0;}
		for(;x<n-nai;x++){
			auto it=las.lower_bound(-1);
			iti.pub(-999);
			las.erase(it);
			nai++;
		}
		while(iti.size()!=0){las.ins(iti.back());iti.pob();}
		//cout<<endl<<"de i="<<i;
		//for(auto it=las.begin();it!=las.end();it++){cout<<" "<<(*it);}
	}
	cout<<"Yes"<<endl;
	return 0;
}

Measured memory_bytes: 124288
// ARC092C.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1010;

typedef long long ll;

int n, ai[MAX_N];
ll sum[2];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]), sum[i & 1] += max(0, ai[i]);
    if (max(sum[0], sum[1]) == 0)
    {
        int pos = max_element(ai + 1, ai + 1 + n) - ai;
        printf("%d\n%d\n", ai[pos], n - 1);
        for (int i = n; i > pos; i--)
            printf("%d\n", i);
        for (int i = pos - 1; i >= 1; i--)
            puts("1");
        return 0;
    }
    int parity = sum[1] >= sum[0];
    vector<int> pos, ans;
    for (int i = 1; i <= n; i++)
        if (ai[i] > 0 && i % 2 == parity)
            pos.push_back(i);
    for (int i = n; i > pos.back(); i--)
        ans.push_back(i);
    for (int i = 1; i < pos.front(); i++)
        ans.push_back(1);
    for (int i = 0, siz = pos.size(); i < siz - 1; i++)
    {
        for (int j = 0; j < ((pos[i + 1] - pos[i] - 1) >> 1); j++)
            ans.push_back(3);
        ans.push_back(2);
    }
    printf("%lld\n%lld\n", sum[parity], 1LL * ans.size());
    for (int v : ans)
        printf("%d\n", v);
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
////////////////////////////////////////
int Q;
int l[100100], r[100100];
int arr[100100];
void eratosthenes() {
	arr[0] = 0;
	arr[1] = 0;
	for (int i = 2; i <= 100010; ++i) {
		arr[i] = 1;
	}
	for (int i = 2; i <= sqrt(100100); ++i) {
		if (arr[i]) {
			for (int j = 0; i *(j+2) <= 100010; ++j) {
				arr[i*(j+2)] = 0;
			}
		}
	}
}
int main() {
	cin >> Q;
	int count[100100];
	count[0] = 0;
	count[1] = 0;
	eratosthenes();
	for (int i = 1; i < 100100; i++) {
		if (arr[i]==1 && arr[(i + 1) / 2]==1) {
			count[i] = count[i - 1] + 1;
		}
		else {
			count[i] = count[i - 1];
		}
	}
	int ans[100100];
	for (int i = 0; i < Q;++i) {
		int l, r;
		cin >> l >> r;
		ans[i] = count[r] - count[l - 1];
	}
	for (int i = 0; i < Q; ++i) {
		cout << ans[i] << endl;
	}
	return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
long long a[100001];

int ans;
long long n,m,v,p;
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>n>>m>>v>>p;
    int i,j;
    for(i=1 ; i<=n ; i++)cin>>a[i];
    sort(a+1,a+n+1);

    ans=p;
    long long s=0;
    for(i=n-p ; i>=1 ; i--){
        s+=a[i+1];
        if(a[i]+m>=a[n-p+1]){
            if(1ll*m*(i+p-1)+1ll*(n-p-i+1)*(a[i]+m)-s>=1ll*m*v)ans++;
        }

    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
using namespace std;
int dp[20][20];

void solv(int n){
	for(int k = 0;k < n;k++){
		for(int i = 0;i < n;i++){
			for(int j = 0;j < n;j++){
				if(dp[i][j] > dp[i][k] + dp[k][j]){
					dp[i][j] = dp[i][k] + dp[k][j];
				}
			}
		}
	}
}

int main(){
	int n, m, a, b, c, d;
	char s;
	fill((int*)dp, (int*)(dp+20), 100000);
	cin >> n >> m;
	for(int i = 0;i < m;i++){
		cin >> a >> s >> b >> s >> c >> s >> d;
		dp[a-1][b-1] = c;
		dp[b-1][a-1] = d;
	}
	solv(n);
	cin >> a >> s >> b >> s >> c >> s >> d;
	cout << c - d - dp[a-1][b-1] - dp[b-1][a-1] << endl;
	return 0;
}

Measured memory_bytes: 3008
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

from heapq import heappop, heappush
H, W = mapint()
Cs = [list(mapint()) for _ in range(10)]
lis = []
for h in range(H):
    lis.extend(list(mapint()))

def dijkstra(start):
    Q = [(0, start)]
    checked = [0]*10
    while Q:
        d, v = heappop(Q)
        checked[v] = 1
        if v==1:
            return d
        for i in range(10):
            if not checked[i]:
                heappush(Q, (d+Cs[v][i], i))

costs = [0]*10
for i in range(10):
    costs[i] = dijkstra(i)

from collections import Counter
c = Counter(lis)
ans = 0
for i in range(10):
    ans += costs[i]*c[i]
print(ans)
        

Measured memory_bytes: 75704
macro_rules! scan_sub {
    ( $itr:ident, $t:ty ) => {
        let mut buf = String::new();
        let $itr = {
            while buf.trim().len() == 0 {
                buf = String::new();
                std::io::stdin().read_line(&mut buf).unwrap();
            }
            buf.split_whitespace().map(|n| n.parse::<$t>().unwrap())
        };
    };
}

macro_rules! scan {
    ( $x:ident; Vec<$t:ty> ) => {
        scan_sub!(itr, $t);
        let $x = itr.collect::<Vec<_>>();
    };
    ( $( $x:ident ),*; $t:ty ) => {
        scan_sub!(itr, $t);
        let mut itr = itr;
        $(
            let $x = itr.next().unwrap();
        )*
    };
}

fn main() {
    scan!(n; usize);
    scan!(s; String);

    let mut r: usize = 0;
    let mut g: usize = 0;
    let mut b: usize = 0;

    let mut s2 = Vec::with_capacity(n);

    for c in s.chars() {
        match c {
            'R' => r += 1,
            'G' => g += 1,
            'B' => b += 1,
            _ => (),
        }
        s2.push(c);
    }

    let mut res: usize = r * g * b;
    let s = s2;

    for k in 1..n {
        for i in 0..k {
            if (k + i) % 2 == 1 { continue; }
            let j = (i + k) / 2;

            if s[i] == s[j] || s[i] == s[k] || s[j] == s[k] {
                continue;
            }

            res -= 1;
        }
    }

    println!("{}", res);
}


Measured memory_bytes: 2124
import java.util.Scanner;

class Main{
    public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	int a,b,c;
	while(sc.hasNextInt()){
	    a=sc.nextInt();
	    b=sc.nextInt();
	    c=String.valueOf(a+b).length();
	    System.out.println(c);
	}
    }
}

Measured memory_bytes: 12000
#include <iostream>
using namespace std;
int main(int n){
    int a, b;
    cin >> a >> b;
    if (a % 2 == 1){
        if(b % 2 == 1){
            cout << "Odd" << endl;
            return 0;
        }
    }
    cout << "Even" << endl;
    return 0;

}

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>
#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;
ll Cwa[2000001]={},Mwa[2000001]={};
ll MCwa[2000001]={};
int main(){
	int N;
	string S;
	int Q;
	int k[100];

	scan(N);
	scan(S);
	for(int i=N-1;i>=0;i--){
		Cwa[i]=Cwa[i+1]+(S[i]=='C');
		Mwa[i]=Mwa[i+1]+(S[i]=='M');
	}
	ll Csum=0;
	for(int i=N-1;i>=0;i--){
		MCwa[i]=MCwa[i+1];
		if(S[i]=='C') Csum++;
		else if(S[i]=='M') MCwa[i]+=Csum;
	}
	scan(Q);
	rep(q,Q){
		scan(k[q]);
		ll MCsum=0;
		ll ans=0;
		for(int i=N-1;i>=0;i--){
			if(S[i]=='D'){
				ans+=MCwa[i]-MCwa[min(N,i+k[q])]-(Cwa[min(N,i+k[q])]-Cwa[N])*(Mwa[i]-Mwa[min(N,i+k[q])]);
			}
		}
		prin(ans);
	}

	return 0;
}


Measured memory_bytes: 29956
function myout(text){console.log(text);}//standard output
function Main(input) {
	input = input.trim();
	//input = parseInt(input.trim());
	//input = input.trim().split(" ");
	//input = input.trim().split("\n");
	//input = input.trim().split(" ").map((a)=>Number(a));
	//input = input.trim().split("\n").map((a)=>Number(a));
  var good1 = ["R","U","D"];
  var good2 = ["L","U","D"];
  for(var i = 0; i < input.length; i++){
    var tmp = input.slice(i,i+1);
    if(i % 2 == 0){//奇数番目
       if(good1.indexOf(tmp) == -1){
          myout("No");
         return;
          }
       }else{
         if(good2.indexOf(tmp) == -1){
            myout("No");
         return;
            }
       }
  }
  myout("Yes");
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 21064
h,w = map(int,input().split())

if h == 1 or w == 1:
    print(1)

elif h % 2 == 0:
    print(int(h*w/2))

elif h % 2 == 1:
    if w % 2 == 0:
        print(int(h*w/2))
    else:
        print(int((h*w/2)+1))


Measured memory_bytes: 3064
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>

using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype

template <class T>
int __builtin_popcount(T n) { return n ? 1 + __builtin_popcount(n & (n - 1)) : 0; }
#endif

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define popcount __builtin_popcount

const double EPS = 1e-10;
typedef long long ll;
typedef pair<int, int> pint;


int main()
{
	int n;
	while (scanf("%d", &n), n)
	{
		int b[31];
		memset(b, 0, sizeof(b));
		b[0] = n;
		while (true)
		{
			int t = find(b, b+n, 0) - b;
			for (int i = 0; i < t-1; ++i)
				printf("%d ", b[i]);
			printf("%d\n", b[t-1]);

			if (t == n)
				break;

			int u;
			u = t-1;
			while (b[u] == 1)
				--u;
			--b[u];
			++u;
			fill(b+u, b+n, 0);
			int s = t - u + 1;
			while (s--)
			{
				if (b[u] == b[u-1])
					++u;
				++b[u];
			}
		}
	}
}

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

int main(){
  int n,T;
  cin >> n >> T;
  int c[110];
  int t[110];
  for(int i = 0;i < n;i++){
    cin >> c[i] >> t[i];
  }
  int ok = 0;
  int min = c[0];
  for(int i = 0;i < n;i++){
    if(t[i] <= T && min >= c[i]){
      min = c[i];
      ok++;
    }
  }
  if(ok > 0){
   cout << min << endl;
  }
  else{
    cout << "TLE" << endl;
  }
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define MAX 500000

int cnt = 0;

void merge(int a[], int left, int mid, int right) 
{
	int n1, n2, i, j, k;
	int L[MAX], R[MAX];
	
	n1 = mid - left + 1;
	n2 = right - mid;

	
	for (i = 0; i < n1; i++) {
		L[i] = a[left + i];
		cnt++;
	}
	for (i = 0; i < n2; i++) {
		R[i] = a[mid + i +1];
		cnt++;
	}
	L[n1] = 1000000000;
	R[n2] = 1000000000;
	
	i = 0;
	j = 0;
	for (k = left; k <= right; k++) {
		if (L[i] < R[j]) {
			a[k] = L[i++];
		} else {
			a[k] = R[j++];
		}
	}
	
}


void mergeSort(int a[], int left, int right)
{
	int mid;
	
	if (left >= right) {
		return;
	}
	mid = (left + right) / 2;
	mergeSort(a, left, mid);
	mergeSort(a, mid + 1, right);
	merge(a, left, mid, right);
}
	
	
int main()
{
	int s[MAX];
	int n, i;
	
	
	scanf("%d",&n);
	for (i = 0; i < n; i++) {
		scanf("%d",&s[i]);
	}
	mergeSort(s, 0, n - 1);
	
	for (i = 0; i < n; i++) {
		if (i > 0) {
			printf(" ");
		}
		printf("%d",s[i]);
	}
	printf("\n");
	
	printf("%d\n",cnt);
	
return 0;
}	


Measured memory_bytes: 5624
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int[] nums=new int[n+1];
        for(int i=0;i<m;i++){
            nums[sc.nextInt()-1]++;
            nums[sc.nextInt()]--;
        }
        int ans=0;
        for(int i=0;i<n;i++){
            if(i!=0)nums[i]+=nums[i-1];
            if(nums[i]==m)ans++;
        }
        System.out.println(ans);
                
    }
}




Measured memory_bytes: 63476
using System;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int h, m, s;
            int time = int.Parse(Console.ReadLine());

            h = time / 3600;
            m = (time % 3600) / 60;
            s = (time % 3600) % 60;

            Console.WriteLine($"{h}:{m}:{s}");
        }
    }
}



Measured memory_bytes: 15932