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

#define                           ll                          long long
#define                           int                         ll
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<ll,ll>
#define                           clr(x)                      memset(x,0,sizeof(x));
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           show(x,y)                   cout<<x<<" : ";for(auto z:y)cout<<z<<" ";cout<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const ll inf=1e18;
const int mod=998244353;
const int M=200005;

inline ll bigmod(ll B,ll P){ll R=1;while(P>0){if(P&1){R=(R*B)%mod;}P>>=1;B=(B*B)%mod;}return R;}
inline ll ad(ll x,ll y){ll ret=(x%mod+y%mod)%mod;if(ret<0){ret+=mod,ret=ret%mod;}return ret;}
inline ll sub(ll x,ll y){ll ret=((x%mod)-(y%mod)+mod)%mod;if(ret<0){ret+=mod,ret=ret%mod;}return ret;}
inline ll gun(ll x,ll y){ll ret=((x%mod)*(y%mod))%mod;if(ret<0){ret+=mod,ret=ret%mod;}return ret;}

const int N = 2e5 + 100;
namespace Combi {
    int fact[N], inv[N];

    int bm(int b, int p, int m) {
        if(p == 0) return 1%m;
        int t = bm(b,p/2,m);
        t = (1ll*t*t)%m;
        if(p&1) return 1ll*t*b%m;
        return t;
    }

    int C(int n, int r) {
        if(n < 0 or r < 0 or r > n) return 0;
        int ret = 1ll*fact[n]*inv[r]%mod;
        return ret;
    }
    // X1 + X2 + ... + Xvar = Sum
    int no_of_eqns(int sum, int var) {
        return C(sum+var-1,var-1); // Xi >= 0
        // return C(sum-1,var-1); // Xi > 0
    }
    void init() {
        fact[0] = 1;
        for(int i = 1; i < N; i++) {
            fact[i] = 1ll*fact[i-1]*i%mod;
        }
        inv[N-1] = bm(fact[N-1], mod-2, mod);
        for(int i = N-2; i >= 0; i--) {
            inv[i] = 1ll*inv[i+1]*(i+1)%mod;
        }
    }
}
int yo(int box,int clr)
{
    if(box==1)return clr;
    int ret=clr;
    box--;
    int p=bigmod(clr-1,box);
    ret=gun(ret,p);
    return ret;
}
int sleep(int total,int valo)
{
    int bad=total-valo;
    int lob=Combi::fact[total-1];
    int hor=Combi::inv[valo-1];
    hor=gun(hor,Combi::inv[bad]);
    int ret=gun(hor,lob);
    return ret;
}
 main()

{
    fast
    Combi::init();
    int n,m,k,ses=0;
    cin>>n>>m>>k;
    for(int bad=0;bad<=k;bad++)
    {
        int nw=n-bad;
        int x=yo(nw,m);
        int y=sleep(n,nw);
        //cout<<x<<" "<<y<<endl;
        int z=gun(x,y);
       // cout<<z<<" # "<<endl;
        ses=ad(ses,z);
    }
    cout<<ses<<endl;
    return 0;

}





































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

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

  int x = 0, y = 0;
  for (int i = 1; i <= n; i++) {
    x += 800;
    if(i % 15 == 0) {
      y += 200;
    }
  }
  cout << x - y << '\n';
}


Measured memory_bytes: 3560
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=5e18;

int main() {
  ll n;
  cin >> n;
  vec a(n);
  for(ll i=0;i<n;i++) cin >> a[i];
  ll sum=0;
  ll ans1=0;
  for(ll i=0;i<n;i++) {
    sum+=a[i];
    if(i%2==0) {
      if(sum<=0) {
        ans1+=1-sum;
        sum=1;
      }
    }
    else {
      if(sum>=0) {
        ans1+=sum+1;
        sum=-1;
      }
    }
  }
  ll ans2=0;
  sum=0;
  for(ll i=0;i<n;i++) {
    sum+=a[i];
    if(i%2) {
      if(sum<=0) {
        ans2+=1-sum;
        sum=1;
      }
    }
    else {
      if(sum>=0) {
        ans2+=sum+1;
        sum=-1;
      }
    }
  }
  cout << min(ans1,ans2) << endl;
}

Measured memory_bytes: 1024
def main():
    s = set()
    n = int(input())
    for _ in range(n):
        com = input().split()
        if com[0] == 'insert':s.add(com[1])
        else :
            if com[1] in s:print('yes')
            else          :print('no')


if __name__ == '__main__':
    main()




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

using namespace std;

typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = (ll)1e9 + 7;

int main()
{
  int N; scanf("%d", &N);
  string s; cin >> s;
  int pre = 0, d = 0;
  for (int i = 0; i < N; ++i) {
    if (s[i] == '(') { ++d; }
    else if (s[i] == ')') {
      if (--d < 0) {
        d = 0;
        ++pre;
      }
    }
  }
  string ans = string(pre, '(') + s + string(d, ')');
  printf("%s\n", ans.c_str());
  return 0;
}


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

int main(){
  ll x;
  cin >> x;
  if(x>=30) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 3668
#coding: utf-8
A, B, C, K = map(int, input().split())
# li = [1 for _ in range(A)] + [0 for _ in range(B)] + [-1 for _ in range(C)]
ans = 0
li = [A, B, C]
ll = [1, 0, -1]
i = 0
while K > 0:
    if li[i] <= K:
        ans += ll[i] * li[i]
        K -= li[i]
    else:
        ans += ll[i] * K
        K = 0
    i += 1
print(ans)

Measured memory_bytes: 9156
//
// Created by 10034 on 2020/7/28.
//

#include <iostream>
using namespace std;
const int N=200010;
int u[N],v[N];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;++i){
        cin>>u[i]>>v[i];
    }
    long long res=0;
    for(int i=1;i<=n;++i){
        res=res+(long long )(n-i+1)*i;
    }
    for(int i=1;i<n;++i){
        if(u[i]>v[i]) swap(u[i],v[i]);
        res=res-(long long )u[i]*(n-v[i]+1);
    }
    cout<<res<<endl;

    return 0;
}

Measured memory_bytes: 4724
def main():
    N = int(input())
    q_list = list(map(int, input().split()))
    num = len(q_list)

    q_list.sort()

    ans = q_list[int(num / 2)] - q_list[int(num / 2 - 1)]
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 14428
#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
const int N=1000,M=1000;
int n,m;
char a[N+1][M+5];
int dp[N+1][M+1];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i]+1;
	dp[1][1]=1;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(i!=1||j!=1)
		if(a[i][j]=='.')dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
	cout<<dp[n][m];
	return 0;
}
/*1
3 4
...#
.#..
....
*/
/*2
5 2
..
#.
..
.#
..
*/
/*3
5 5
..#..
.....
#...#
.....
..#..
*/
/*4
20 20
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
*/

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


ll INF = 100100100100100100;
int main()
{
    // input
    int n, k;
    cin >> n >> k;
    vector<int> h(n);
    rep(i,n) cin >> h[i];

    // dp
    vector<ll> dp(n, INF); // the cost to get to the scaffold of index_n
    dp[0] = 0;

    rep(i,n-1) {
        for(int j=i+1; j<= min(n-1,i+k); j++){
            dp[j] = min(dp[j], dp[i] + abs(h[j] - h[i]));
        }
    }

    cout << dp[n-1] << endl;


    return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
 
using namespace std;
 
#define f0r(a, b) for (long long a = 0; a < (b); a++)
#define f1r(a, b, c) for (long long a = (b); a < (c); a++)
#define f0rd(a, b) for (long long a = (b); a >= 0; a--)
#define f1rd(a, b, c) for (long long a = (b); a >= (c); a--)
#define ms(arr, v) memset(arr, v, sizeof(arr))
#define pb push_back
#define mp make_pair
#define f first
#define s second
using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vpl = vector<pll>;
 
void fio() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); 
  cout.tie(0);
}
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const long double pi = 3.14159265358979323846;

const ll mod = 1000000007;

namespace modop {
	ll madd(ll a, ll b) {
	  return (a + b) % mod;
	}
	ll msub(ll a, ll b) {
	  return (((a - b) % mod) + mod) % mod;
	}
	ll mmul(ll a, ll b) {
	  return ((a % mod) * (b % mod)) % mod;
	}
	ll mpow(ll base, ll exp) {
	  ll res = 1;
	  while (exp) {
		if (exp % 2 == 1){
			res = (res * base) % mod;
		}
		exp >>= 1;
		base = (base * base) % mod;
	  }
	  return res;
	}
	ll minv(ll base) {
	  return mpow(base, mod - 2);
	}
	ll mdiv(ll a, ll b) {
	  return mmul(a, minv(b));
	}
}

using namespace modop;



void solve() {
  ll n; cin >> n;
  ll vals[n]; f0r(i, n) vals[i] = 0;

  ll loss = 0;
  f0r(i, n - 1) {
    ll x, y; cin >> x >> y; --x; --y;
    if (x > y) swap(x, y);
    vals[x] += n - y;
    loss += n - y;
  }

  ll ans = 0;
  f0r(i, n) {
    ans += (n - i) * (n - i + 1) / 2 - loss;
    loss -= vals[i];
  }

  cout << ans << '\n';
}
 
int main() {
  fio();
  
  int T = 1;
  // cin >> T;
  while (T--) solve();
} 

Measured memory_bytes: 5204
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true){
			int n = sc.nextInt();
			int m = sc.nextInt();
			if(n==0&&m==0) break;
			int[] nc = new int[n];
			int[] mc = new int[m];
			for(int i=0;i<n;++i){
				nc[i]=sc.nextInt();
			}
			for(int i=0;i<m;++i){
				mc[i]=sc.nextInt();
			}
			int num=1000000,ans_n=0,ans_m=0;
			boolean flag=false;
			for(int j=0;j<m;++j){
				for(int i=0;i<n;++i){
					int[] ncp = nc.clone();
					int[] mcp = mc.clone();
					int a=ncp[i];
					ncp[i]=mcp[j];
					mcp[j]=a;
					int sum_n=0,sum_m=0;
					for(int z=0;z<n;++z) sum_n+=ncp[z];
					for(int z=0;z<m;++z) sum_m+=mcp[z];
					if((sum_n==sum_m) && (ncp[i]+mcp[j]<num)){
						num=ncp[i]+mcp[j];
						ans_n=mcp[j];
						ans_m=ncp[i];
						flag=true;
					}
				}
			}
			if(flag==true) System.out.println(ans_n+" "+ans_m);
			else System.out.println("-1");
		}
	}
}


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

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define P pair<int,int>
#define Abs(a,b) max(a,b)-min(a,b)
#define YES(condition) if(condition){cout << "YES" << endl;}else{cout << "NO" << endl;}
#define Yes(condition) if(condition){cout << "Yes" << endl;}else{cout << "No" << endl;}
#define Cout(x) cout<<(x)<<endl

typedef long long ll;

using namespace std;

const int INF = 1e9,MOD = 1e9 + 7;
const ll LINF = 1e18;

//while(x!=0){
            //sum+=x%10;
           // x/=10;
        //}
        //各桁の和

//pair<int,int> p[100000];
//P r[100000];
//cin >> tmp;
//p[i]=make_pair(tmp,i);
//cout << p[i].second+1 << endl;//ペアの右側つまりiを出力

//s.find(w[i])==string::npos
//findの使い方

//for(int i=0;i<n;i++){
   // b[i]=x%2;
    //x/=2;
  //}二進数

long long int n=1,cnt=0,ans=0,a[100000],b,c,cmp,data,m,h,x,y,xcmp=0,ycmp=0,sum=0;

string s,w;

vector<int> z;

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

       cin >> n;
       rep(i,n){
           cin >> a[i];
       }
       sort(a,a+n);
       reverse(a,a+n);
       rep(i,n){
           if(i%2==0){
               b+=a[i];
           }
           else{
               c+=a[i];
           }
       }
       Cout(b-c);
return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define N 800005
#define p 924844033
#define G POW(5)
#define int long long
using namespace std;

inline void rd(int &x){
	x=0;char ch=0;int w=0;
	while(!isdigit(ch)) ch=getchar(),w|=ch=='-';
	while( isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=w?-x:x;
}

int n,lim;
vector<int> g[N];
int A[N],B[N],c[N],r[N];
int f[N],inv[N],ans[N],sz[N];

inline int POW(int a,int b=p-2,int ans=1){
	for(;b;b>>=1,a=a*a%p)
		if(b&1) ans=ans*a%p;
	return ans;
}
void NTT(int *f,int o){
    for(int i=1;i<lim;i++)
        if(i<r[i]) swap(f[i],f[r[i]]);
    for(int len=1;len<lim;len<<=1){
        int w=POW(o,(p-1)/(len<<1));
        for(int b=1,k=0;k<lim;k+=(len<<1),b=1)
            for(int i=k;i<k+len;i++,b=b*w%p){
                int now=f[i+len]*b%p;
                f[i+len]=(f[i]-now+p)%p;f[i]=(f[i]+now)%p;
            }
    }
}
void add(int x,int y){
	g[x].push_back(y);g[y].push_back(x);
}
void mul(int *a,int *b,int n){
	for(lim=1;lim<=n+n+1;lim<<=1);	
    for(int i=1;i<lim;i++)
        r[i]=(r[i>>1]>>1)|((i&1)?lim>>1:0);
    for(int i=0;i<lim;i++)
		A[i]=a[i]*(i<=n),B[i]=b[i]*(i<=n);
    NTT(A,5);NTT(B,5);
    for(int i=0;i<lim;i++)
    	b[i]=A[i]*B[i]%p;
    NTT(b,G);int inv=POW(lim);
    for(int i=0;i<lim;i++)
    	b[i]=b[i]*inv%p;
}
void dfs(int x,int fa=0){
	sz[x]=1;
	for(int y:g[x]) if(y!=fa)
		dfs(y,x),sz[x]+=sz[y];
	c[sz[x]]++;c[n-sz[x]]++;
}
signed main(){
	rd(n);f[0]=inv[0]=ans[0]=1;
	for(int i=1;i<=n;i++)
		f[i]=f[i-1]*i%p,inv[i]=POW(f[i]);
	for(int x,y,i=1;i<n;i++)
		rd(x),rd(y),add(x,y);
	dfs(1);c[n]--;
	for(int i=1;i<=n;i++)
		c[i]=c[i]*f[i]%p,ans[i]=inv[i];
	reverse(c,c+1+n);mul(c,ans,n);reverse(ans,ans+1+n);
	for(int i=1;i<=n;i++)
		ans[i]=ans[i]*inv[i]%p;
	for(int i=1;i<=n;i++)
		printf("%lld\n",(f[n]*inv[i]%p*inv[n-i]%p*n%p+p-ans[i])%p);
}

Measured memory_bytes: 70656
#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
	x=0;int f=0;char ch=getchar();
	while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x=f?-x:x;
}
const int N=2e5+10;
int n,i,l,r;
ll a[N],sum[N],sumxor[N];
int main(){
	read(n);
	for (i=1;i<=n;i++) read(a[i]),sum[i]=sum[i-1]+a[i],sumxor[i]=sumxor[i-1]^a[i];
	ll ans=0;
	for (i=1;i<=n;i++){
		l=i,r=n;
		int res=i;
		while (l<=r){
			int mid=l+((r-l)>>1);
			if ((sum[mid]-sum[i-1])==(sumxor[mid]^sumxor[i-1])){
				res=mid;
				l=mid+1;
			}
			else r=mid-1;
		}
		ans+=res-i+1;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 4992
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)


K = int(input())
ans = 0
for a in range(1, K + 1):
    for b in range(1, K + 1):
        g1 = gcd(a, b)
        if g1 == 1:
            ans += K
        else:
            for c in range(1, K+1):
                ans += gcd(g1, c)
print(ans)


Measured memory_bytes: 9076
from collections import Counter


def calc_prime_factors(n, count=False):
    """Trial division"""
    factors = []
    # factor: 2
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    # factor: 3, 5, 7, 11, ...
    f = 3
    while f ** 2 <= n:
        if n % f == 0:
            factors.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        factors.append(n)
    if count:
        factors = Counter(factors).items()
    return factors


N, P = map(int, input().split())
factors = calc_prime_factors(P, count=True)
ans = 1
for factor in factors:
    p, cnt = factor
    q, _ = divmod(cnt, N)
    ans *= p**q
print(ans)


Measured memory_bytes: 3316
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
using ll = long long;
#define FOR(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(x) (x).begin(), (x).end()

int main() {
  ll N;
  cin >> N;
  vector<ll> A(N), B(N);
  FOR(i, N) {
    cin >> A[i];
    B[i] = A[i];
  }
  sort(all(A));
  // FOR(i, N) cout << A[i] << endl;

  vector<ll> cnt(N + 1, 0);
  FOR(i, N) {
    if (cnt[A[i]] != 0) continue;
    auto iter_upper = upper_bound(all(A), A[i]);
    ll idx_upper = distance(A.begin(), iter_upper);
    auto iter_lower = lower_bound(all(A), A[i]);
    ll idx_lower = distance(A.begin(), iter_lower);
    cnt[A[i]] = idx_upper - idx_lower;
  }
  /*
  cout << "cnt = " << endl;
  FOR(i, N) cout << cnt[i] << " ";
  cout << endl;
  */

  // N*(N-1)/2
  vector<ll> C(N + 1, 0);
  FOR(i, N) C[A[i]] = cnt[A[i]] * (cnt[A[i]] - 1) / 2;
  // (N-1)*(N-2)/2
  vector<ll> D(N + 1, 0);
  FOR(i, N) D[A[i]] = (cnt[A[i]] - 1) * (cnt[A[i]] - 2) / 2;
  ll sum = accumulate(all(C), 0LL);

  // cout << " ans = " << endl;
  FOR(i, N) {
    ll ans = sum - C[B[i]] + D[B[i]];
    cout << ans << endl;
  }
  // cout << endl;

  return 0;
}


Measured memory_bytes: 10368
let inputString = '';

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});
process.stdin.on('end', function() {
    const input = inputString.replace(/\s*$/, '')
        .split('\n')
        .map(str => str.replace(/\s*$/, ''));

    console.log(countInversions(input[1].split(' ').map(s => Number(s))));
});


let count;
const countInversions = (arr) => {
  count = 0;
  mergeSort(arr, 0, arr.length);
  return count;
};

const mergeSort = (nums, leftIndex, rightIndex) => {
  if (leftIndex + 1 < rightIndex) {
    const sum = leftIndex + rightIndex;
    const mid = (sum - sum % 2) / 2;
    mergeSort(nums, leftIndex, mid);
    mergeSort(nums, mid, rightIndex);
    merge(nums, leftIndex, mid, rightIndex);
  }
};

const merge = (nums, leftIndex, midIndex, rightIndex) => {
  const leftArr = Array.from({ length: midIndex - leftIndex + 1 },(_, i) => nums[leftIndex + i]);
  leftArr[leftArr.length - 1] = Infinity;
  const rightArr = Array.from({ length: rightIndex - midIndex  + 1 }, (_, i) => nums[midIndex + i]);
  rightArr[rightArr.length - 1] = Infinity;

  let i = 0;
  let j = 0;
  for (let k=leftIndex; k<rightIndex; k++) {
    if (leftArr[i] <= rightArr[j]) {
      nums[k] = leftArr[i];
      i++;
    } else {
      nums[k] = rightArr[j];
      j++;

      count += (leftArr.length - 1 - i);
    }
  }
};


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

using int64 = long long;

int main() {
  int64 x;
  cin >> x;
  int64 c = x / 500;
  x %= 500;
  int64 v = x / 5;
  cout << c * 1000 + v * 5 << "\n";
  return 0;
}


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

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int, int> pii;
const int INF = 1<<28;


int main()
{
	
	//cin.tie(0); ios_base::sync_with_stdio(false);
	int n,m;
	cin >>n >>m;
	vector<VI> r(n, VI(n, INF));
	vector<VI> ent(m, VI(3, 0));
	rep(i,n) r[i][i]=0;
	rep(i,m){
		int a,b,c;
		cin >>a >>b >>c;
		r[a-1][b-1] = r[b-1][a-1] = c;
		ent[i] = {a-1, b-1, c};
	}
	rep(k,n) rep(i,n) rep(j,n) r[i][j] =min(r[i][j], r[i][k] + r[k][j]);

	int ans = 0;
	for(auto x: ent){
		bool use = 0;
		rep(j,n) if(r[j][x[0]] + x[2] == r[j][x[1]]) use = 1;
		if(use) ans++;
	}
	cout << m-ans <<"\n";
	
	return 0;

}


Measured memory_bytes: 384
from bisect import bisect_left

N = int(input())
L = sorted(list(map(int, input().split())))

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        a = L[i]
        b = L[j]
        idx = bisect_left(L, a + b)
        ans += idx - 1 - j
print(ans)


Measured memory_bytes: 3188
//#include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <complex>
#include <bitset>
#include <functional>
#include <stack>
#include <regex>
#include <tuple>
#include <iomanip>

#define int long long
#define REP(i,l,r) REPEAT(i,l,r,true) // [l, r)
#define rep(i,n) REP(i,0,n)           // [0, n)
#define REPEAT(i,l,r,condition) for(int i=(condition)?l:r-1;(condition)?i<r:i>=l;(condition)?++i:--i) // false<-[l, r)->true
#define all(e) e.begin(),e.end()
#define rall(e) e.rbegin(),e.rend()
#define pb push_back
#define fs first
#define sc second
#define show(...) cerr<<#__VA_ARGS__<<" = ";_DEBUG(__VA_ARGS__)
#define showlr(n,l,r) cerr<<#n<<" = ";for(int i=l;i<r;i++){cerr<<n[i]<<", ";}cerr<<endl // [l, r)

#define yes puts("Yes")
#define no puts("No")
#define case(i) printf("Case #%lld: ",i)

using namespace std;

using vi=vector<int>;
using pint=pair<int,int>;

struct io{io(){cin.tie(0);ios::sync_with_stdio(false);cout.tie(0);cout<<fixed<<setprecision(20);}}io;

template<class T> istream& operator >>(istream &is, vector<T> &v){for(T &e:v)is>>e;return is;}
template<class T> ostream& operator <<(ostream &os, vector<T> v){os<<"{";for(T &e:v)os<<e<<(v.size()-(int)(&e-&v[0])>1?", ":"");os<<"}";return os;}

void _DEBUG(){}
template<typename H,typename... T> void _DEBUG(H a,T...b){cerr<<a<<(sizeof...(b)?",":"\n");_DEBUG(b...);}

inline void in(){}
template<typename H,typename... T>void in(H &a, T&... b){cin>>a;in(b...);}
inline void out(){}
template<typename H,typename... T> void out(H a, T... b){cout<<a<<(sizeof...(b)?" ":"\n");out(b...);}

template<class T> void resz(int n,T& v){v.resize(n);}
template<class H,class... T> void resz(int n,H& a,T&... b){a.resize(n);resz(n,b...);}

const int INF=1LL<<55;
const int MOD=1000000007;
const double EPS=1e-8;

int n,a,b;
vi p;


signed main(){

    in(n,a,b);
    resz(n,p);
    in(p);
    vi x(3);
    
    for(auto e:p){
        if(e<=a) x[0]++;
        if(e>a && e<=b) x[1]++;
        if(e>b) x[2]++;
    }
    //show(x);
    int o=INF;
    for(auto e:x){
        o=min(o,e);
    }
    out(o);

    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
 
int main(void) {
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i=0;i<n;i++) cin >> a.at(i);

	int ans = -1000000000;

	for(int i=0;i<n;i++) {
		for(int j=0;j<n;j++) {
			ans = max(ans, a.at(i)-a.at(j));
		}
	}

	cout << ans << endl;
}


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

typedef long long int ll;

int main()
{
    ll n, m;
    cin >> n;
    vector<ll> t(n);
    for(ll i = 0;i < n;i++){
        cin >> t[i];
    }
    cin >> m;
    vector<ll> p(m),x(m);
    for(ll i = 0;i < m;i++){
        cin >> p[i] >> x[i];
    }

    ll bans = 0;
    for(ll i =0 ;i < n;i++){
        bans += t[i];
    }
    for(ll i = 0;i < m;i++){
        ll ans = bans - (t[p[i] - 1] - x[i]);
        cout << ans << "\n";
    }

    return 0;
}

Measured memory_bytes: 256
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;
 
signed main() {
    int N, Q; cin >> N >> Q;
    // time, type, id
    vector< tuple<int, int, int> > info;
    for(int i=0; i<N; i++) {
        int s, t, x; cin >> s >> t >> x;
        info.emplace_back(s-x, -i, x);
        info.emplace_back(t-x, -i, -x);
    }
    for(int i=0; i<Q; i++) {
        int d; cin >> d;
        info.emplace_back(d, 2, i);
    }
    sort(info.begin(), info.end());

    vector<int> ans(Q);
    set< pair<int, int> > S;
    for(const auto &e : info) {
        int tm, va, vb; tie(tm, va, vb) = e;
        if(va == 2) {
            int res = (S.size() ? S.begin()->first : -1);
            ans[vb] = res;
        }
        else {
            va = -va;
            if(vb > 0) {
                S.emplace(vb, va);
            }
            else {
                vb = -vb;
                S.erase(make_pair(vb, va));
            }
        }
    }
    for(int i=0; i<Q; i++) cout << ans[i] << endl;
    return 0;
}


Measured memory_bytes: 30052
N = int(input())
MOD = 1000000007
A =  list(map(int,input().split()))
cum = [0]*(N+1)
for i in range(N):
    cum[i+1] = cum[i] + A[i]
    cum[i+1] %= MOD

ans = 0

for i in range(N-1):
    ans += A[i] * (cum[N] - cum[i+1])
    ans %= MOD

print(ans)

Measured memory_bytes: 31628
fun main(args: Array<String>) {
    val (N,K,Q) = readLine()!!.split(" ").map(String::toInt)
    var ans = IntArray(N)
    for (i in 1..Q) {
        var A = readLine()!!.toInt()
        ans[A-1]++
    }
    for (an in ans) {
        if (an > Q-K) {
            println("Yes")
        } else {
            println("No")
        }
    }
 }


Measured memory_bytes: 45888
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,a,x[100],cnt;ll dp[51][51][3000],ans;
ll dfs(int pos,int las,int sum)
{
	if(pos>n)
	{
		if(las==0&&sum==cnt*a)return 1;
		else return 0;
	}
	if(dp[pos][las][sum]!=-1)return dp[pos][las][sum];
	return dp[pos][las][sum]=dfs(pos+1,las-1,sum+x[pos])+dfs(pos+1,las,sum);
}
int main()
{
	ios::sync_with_stdio(0);
	cin>>n>>a;
	for(int i=1;i<=n;i++)
		cin>>x[i];
	for(int i=1;i<=n;i++)
		cnt=i,memset(dp,-1,sizeof dp),ans+=dfs(1,i,0);
	cout<<ans<<endl;	
}

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

int main(){
    long long n;
    cin >> n;

    long long p[n];

    for(long long i = 0; i < n; i++){
        cin >> p[i];
    }

    long long minv = 1e9;
    long long count = 0;
    for(long long i = 0; i < n; i++){
        if(minv > p[i]){
            minv = p[i];
            count++;
        }
    }

    cout << count << endl;
    return 0;
}

Measured memory_bytes: 5192
import java.io.PrintWriter
import java.util.*
import java.math.*
import java.lang.*
import kotlin.comparisons.*

val pw = PrintWriter(System.out)
val MOD: Long = (1e+9 + 7).toLong()

fun main(args: Array<String>) {
    val n = readInt()
    val k = readInt()
    val x = readInt()
    val y = readInt()

    println( Math.min(n, k) * x + Math.max(n-k, 0) * y)
    pw.flush()
}

/****** Declared Functions and Data Structures ******/
// IO
fun read() = readLine()!!
fun readInt() = read().toInt()
fun readLong() = read().toLong()
fun readDouble() = read().toDouble()
fun readListOfString() = read().split(" ")
fun readListOfInt() = readListOfString().map { it.toInt() }
fun readListOfLong() = readListOfString().map { it.toLong() }
fun readListOfDouble() = readListOfString().map { it.toDouble() }

fun Double.format(digits: Int) = String.format("%.${digits}f", this)
fun Float.format(digits: Int) = String.format("%.${digits}f", this)

fun print(value: Any) { pw.print(value) }
fun println(value : Any) { pw.println(value) }


// Extensions
fun<T> List<T>.toBuckets(bucketKeys: List<T>): Map<T, Int> {
    val buckets = bucketKeys.associate { t -> Pair(t, 0) }.toMutableMap()
    this.forEach { t ->
        buckets[t] = buckets[t]!! + 1
    }
    return buckets
}

fun <K, V> Map<K, V>.toMutableMap(): MutableMap<K, V> = HashMap(this)

// Util Functions
fun<T> permutations(src: List<T>): List<List<T>> {
    if(src.size == 1) return listOf(src)
    val perms = mutableListOf<List<T>>()
    val insertElement = src[0]
    permutations(src.drop(1)).forEach { perm ->
        for(i in 0..perm.size) {
            val newPerm = perm.toMutableList()
            newPerm.add(i, insertElement)
            perms.add(newPerm.toList())
        }
    }
    return perms
}

// return nCr, if you want nCr, please access v[n][r]
fun combinations(n: Long): List<List<Long>> {
    val v = (0..n).map { (0..n).map{0L}.toMutableList() }.toMutableList()
    for(i in 0 until v.size) {
        v[i][0] = 1L
        v[i][i] = 1L
    }
    for(i in 0 until v.size) {
        for(j in 1 until i) {
            v[i][j] = (v[i-1][j-1] + v[i-1][j]) % MOD
        }
    }
    return v.map { it.toList() }.toList()
}

// should be a >= b
fun gcd(a: Long, b: Long): Long = 
    if(b == 0L) a else gcd(b, a % b)

// shoud be a >= b
fun lcm(a: Long, b: Long): Long = 
    a / gcd(a, b) * b

fun sumDigits(num_: Long): Long {
    var num = num_
    var rtn: Long = 0
    while(num != 0.toLong()) {
        val tmp = num % 10
        rtn += tmp
        num /= 10
    }
    return rtn
}

fun Double.isDecimal(): Boolean = ((this - Math.floor(this)) != 0.0)

// Data Structures
class Stack<T>(private var st: MutableList<T> = mutableListOf<T>()) {
    fun isEmpty() = st.isEmpty()
    fun top(): T = st.last()
    fun push(e: T) { st.add(e) }
    fun pop() { st = st.dropLast(1).toMutableList() }
}

class Queue<T>(private var que: MutableList<T> = mutableListOf<T>()) {
    fun isEmpty() = que.isEmpty()
    fun top(): T = que.first()
    fun push(e: T) { que.add(e) }
    fun pop() { que = que.drop(1).toMutableList() }
}


Measured memory_bytes: 31740
#include <bits/stdc++.h>
#include<stdio.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) begin(a),end(a)
#define MS(m,v) memset(m,v,sizeof(m))
#define D10  fixed<<setprecision(10)
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> P;
typedef long long ll;
const ll INF = 114514810;
const ll MOD = 1000000007;
const double EPS = 1e-8;
const double PI = acos(-1.0);
struct edge
{
	int from, to, cost;
	bool operator < (const edge& e) const { return cost < e.cost; }
	bool operator >(const edge& e) const { return cost > e.cost; }
};
int dx[] = { -1, 0, 0, 1 }; int dy[] = { 0, -1, 1, 0 };
bool valid(int x, int y, int h, int w) { return (x >= 0 && y >= 0 && x < h&&y < w); }
///*************************************************************************************///
///*************************************************************************************///
///*************************************************************************************///

int d[2000];
vector<vector<edge>> es;

void dijkstra(int s)
{
	fill(ALL(d), INF);
	d[s] = 0;
	priority_queue<P, vector<P>, greater<P>> que;
	que.push(P(0, s));
	while (!que.empty())
	{
		P p = que.top(); que.pop();
		int v = p.second;
		if (d[v] < p.first) continue;
		REP(i, es[v].size())
		{
			edge e = es[v][i];
			if (d[e.to] > d[v] + e.cost)
			{
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}

int main()
{
	int c, n, m, s, g;
	while (cin >> c >> n >> m >> s >> g, c)
	{
		s--; g--;
		es.clear();
		es.resize(c*n+n);
		REP(i, m)
		{
			int a, b, f;
			cin >> a >> b >> f;
			a--; b--;
			REP(j, c+1) es[a + j*n].push_back(edge{ a + j*n, b + j*n, f });
			REP(j, c) es[a + (j+1)*n].push_back(edge{ a + (j+1)*n, b + j*n, f/2 });
			REP(j, c + 1) es[b + j*n].push_back(edge{ b + j*n, a + j*n, f });
			REP(j, c) es[b + (j + 1)*n].push_back(edge{ b + (j + 1)*n, a + j*n, f / 2 });
		}
		dijkstra(s + c*n);
		int ans = INF;
		REP(i, c + 1) ans = min(ans, d[g + i*n]);
		cout << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 1536
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<queue>
#include <cmath>
#include<algorithm>
#include<stack>
#include<map>
#include<ctime>
//#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;

int main(){
    int N;
    cin>>N;
    long long L[N];
    long int ans=0;
    for (int i=0;i<N;i++) cin>>L[i];
    sort(L,L+N);
    for(int i=0;i<N;i++){
        for (int j=i+1;j<N;j++){
            if (L[i]==L[j]) continue;
            for (int k=j+1;k<N;k++){
                if ((L[k]==L[i])||(L[k]==L[j])) continue;
                if (L[k]<L[i]+L[j]){
                    ans++;
                   //cout<<L[i]<<" "<<L[j]<<" "<<L[k]<<" "<<i<<j<<k<<endl;
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3600
s=int(input())

memory=[0 for i in range(10**6)]
a=s
memory[s-1]=1
for i in range(10**6):
    if a%2==0:
        a=a//2
    else:
        a=a*3+1
    if memory[a-1]==1:
        break
    else:
        memory[a-1]=1

print(i+2)

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


int32_t main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	int k;cin >> k;
	int res=0;
	for(int i=1;i<=k;i++){
		for(int j=1;j<=k;j++){
			int temp = __gcd(i,j);
			if(temp==1){
				res+=k;
			}else{
				for(int l=1;l<=k;l++){
					int tt=__gcd(temp,l);
					res+=tt;
				}
			}
		}
	}
	cout << res <<endl;
	return 0;
}


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

const ll MAX = 200000;
const ll INF = 1001001001;
const ll MOD = 1000000007;
const double PI=3.1415926535897932;

ll N, ans=0, tmp=0;
vector<ll> A;
string S, T;

signed main(){
    cin >> S >> T;
    ll tlen = T.size();
    ll slen = S.size();
    for(int i=0;i<=slen-tlen;i++) {
        tmp=0;
        for(int j=0;j<tlen;j++) {
            if(S[i+j]==T[j]) tmp++;
        }
        ans = max(ans, tmp);
    }
    cout << tlen-ans << endl;
    return 0;
}

Measured memory_bytes: 3608
hw = input().split(" ");
h = int(hw[0]);
w = int(hw[1]);
pic = [['.']*(w+2) for i in range(h+2)];
can = 0;
for i in range(1,h+1) :
	s = list(input().rstrip('\n'));
	for j in range(1,w+1) :
		pic[i][j] = s[j-1];
for i in range(1,h+1) :
	for j in range(1,w+1) :
		if pic[i][j] == '#' and pic[i][j-1] == '.' and pic[i-1][j] == '.' and pic[i][j+1] == '.' and pic[i+1][j] == '.' :
			can = can + 1;
if can == 0 :
	print('Yes');
else :
	print('No');

Measured memory_bytes: 3064
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[]$) {
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int ans = k;
        for (int i = 1; i < n; i++) {
            ans *= k - 1;
        }
        System.out.println(ans);
    }
}

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

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

    if(s.at(2) == s.at(3) && s.at(4) == s.at(5)){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
# import sys
# sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]


def solve():
    w, h, x, y = MI()

    area = w * h * 1.0 / 2
    print(area, end=' ')

    cx = w / 2
    cy = h / 2
    # print(x, y, cx, cy)
    if x == cx and y == cy:
        print(1)
    else:
        print(0)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define ll long long
using namespace std;
signed main(){
  ll n,k,mi,sum;
  cin>>n>>k;
  mi = min(1+k,2LL);
  for(ll i=0;i<n;i++){
    sum = mi;
    mi = min(sum+k,sum*2);
  }
  cout<<sum<<"\n";
  return(0);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int solve(int n,int l)
{
	if(n>0)
	{
		return solve(n-1,l+1)+l;
	}
	return 0;
}
int main(){
	
	int n,l;
	cin>>n>>l;
	int temp=solve(n,l);
	int x;
	int ans;
	int sel=999999999;
	for(x=l;x<=(n+l)-1;x++)
	{
		if(abs(temp-(temp-x))<sel)
		{
			ans=x;
			sel=abs(temp-(temp-x));
		}
	}
	cout<<temp-ans<<endl;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<deque>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define str string
#define ld long double
#define vec vector
#define vll vec<ll>
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,b,a) for(ll i=b;i>=a;i--)
#define ALL(a) a.begin(),a.end()
#define rALL(a) a.rbegin(),a.rend()
#define kai "\n"
#define yuque priority_queue
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mie min_element
#define mae max_element
#define tos to_string
#define sep setprecision
#define lob lower_bound
#define upb upper_bound
#define nep next_permutation
#define MOD 1000000007ll
#define MIN (1e-10)
#define equal(a,b) (abs((a)-(b))<MIN)
#define v2 ten
#define chokusen senbun
#define tenten senbun
#define takaku vec<ten>
using namespace std;
void solve();
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed;
	solve();
}
struct pea{
	ll f,s;
	bool operator<(const pea &p)const{
		return f!=p.f?f<p.f:s<p.s;
	};
};
struct tri{
	ll f,s,t;
	bool operator<(const tri &p)const{
		if(f!=p.f)return f<p.f;
		if(s!=p.s)return s<p.s;
		return t<p.t;
	};
};
class ten{
public:
	ld x,y;
	ten operator+(ten p){return{x+p.x,y+p.y};}
	ten operator-(ten p){return{x-p.x,y-p.y};}
	ten operator*(ld k){return{k*x,k*y};}
	ten operator/(ld k){return{x/k,y/k};}
	ld abs(){return sqrt(abs2());}
	ld abs2(){return x*x+y*y;};
	bool operator<(const ten &p)const{return x!=p.x?x<p.x:y<p.y;};
	bool operator==(const ten &p)const{return (-MIN<x-p.x)&&(x-p.x<MIN)&&(-MIN<y-p.y)&&(y-p.y<MIN);};
	ld naiseki(v2 b){return x*b.x+y*b.y;}
	ld gaiseki(v2 b){return x*b.y-y*b.x;}
};
struct senbun{ten p1,p2;};
struct en{ten o;ld r;};
//バックトラック(8クイーン問題)
bool board[8][8],retu[8],gyo[8],lurb[15],rulb[15];
void recursive(ll i){
	if(i==8){
		rep(h,0,8){
			rep(w,0,8)if(board[h][w])cout<<'Q';else cout<<'.';
			cout<<kai;
		}
		return;
	}
	if(gyo[i]){recursive(i+1);return;}
	rep(j,0,8){
		if(!retu[j]&&!lurb[i-j+7]&&!rulb[i+j]){
			board[i][j]=retu[j]=gyo[i]=lurb[i-j+7]=rulb[i+j]=true;
			recursive(i+1);
			board[i][j]=retu[j]=gyo[i]=lurb[i-j+7]=rulb[i+j]=false;
		}
	}
}
void solve(){
	rep(i,0,8)rep(j,0,8)board[i][j]=false;
	rep(i,0,8)retu[i]=gyo[i]=false;
	rep(i,0,15)lurb[i]=rulb[i]=false;
	ll n;cin>>n;
	rep(i,0,n){
		ll a,b;cin>>a>>b;
		board[a][b]=retu[b]=gyo[a]=lurb[a-b+7]=rulb[a+b]=true;
	}
	recursive(0);
}


Measured memory_bytes: 3212
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    A,B,H,M=mis()
    H = (H*60+M)/(60*12)*2*math.pi
    M = M/60*2*math.pi
    c2 = A**2 + B**2 - 2*A*B*math.cos(H-M)
    print(c2**0.5)

main()



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

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


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

using namespace std;

int main(int argc, const char *argv[]) {
  int n, t, a;
  cin >> n >> t >> a;
  vector<int> vh(n);
  for (int i = 0; i < n; ++i) {
    cin >> vh[i];
  }

  int b = 1000 * (t - a);
  int min_idx = 0, min_n = abs(b - vh.front() * 6);
  for (int i = 0; i < vh.size(); ++i) {
    int c = abs(b - vh[i] * 6);
    if (min_n > c) {
      min_n = c;
      min_idx = i;
    }
  }

  cout << min_idx + 1 << '\n';
}


Measured memory_bytes: 3624
# -*- coding: utf-8 -*-
"""
Created on Mon Jan 21 20:39:09 2019

@author: Yamazaki Kenichi
"""

N,K = map(int,input().split())
A = [list(map(int,input().split())) for i in range(N)]

A.sort(reverse = True,key=lambda x:x[1])
eat,noteat =[],[]
a = [0 for i in range(N+1)]
k = K
for i in range(N):
    if k != 0:
        if a[A[i][0]] ==0:
            a[A[i][0]] = 1
            eat.append(A[i][1])
            k -= 1
        else:
            noteat.append(A[i][1])
    else:
        noteat.append(A[i][1])
        
ans = [0 for i in range(min(K-k,len(noteat))+2)]
ans[0] = sum(eat)+ sum(noteat[:k])+ pow(K-k,2)

for i in range(1,min(K-k,len(noteat[k:])+1)):
    ans[i] = ans[i-1]-(pow(K-k-(i-1),2)+eat[-i]) +(pow(K-k-i,2)+noteat[k+i-1])

print(max(ans))


Measured memory_bytes: 31696
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
// memo  fixed  setprecision(20);
using vvll = vector<vector<ll>>;
ll mod =1000000007;
/*"itob" int to "N"base */           template<typename TypeInt> string itob(const TypeInt v, int base){static const char table[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";string ret;static numeric_limits<TypeInt> t;TypeInt n = v;if (t.is_signed) {if (v < 0) n *= -1;}while (n >= base) {ret += table[n%base];n /= base;}ret += table[n];if (t.is_signed) {if (v < 0 && base == 10) ret += '-';}reverse(ret.begin(), ret.end());return ret;}
/*"chmin" a = MAX*/                  template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
/*"chmax" a = MIN*/                  template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
/*"ctoi"  char to int*/              int ctoi(char c) {return c-'0';}
/*"gcd"   MAX Euclidean */           ll gcd(ll a,ll b){if(b==0)return a; return gcd(b,a%b);}
/*"lcm"   MIN*/                      ll lcm(ll a,ll b){ll g = gcd(a,b);return a/g*b;}
/*"primecheck"If prime,return true.*/bool primecheck(ll n){if(n < 2) return false;else{for(int i = 2; i * i <= n; i++){if(n % i == 0) return false;}return true;}}
string  reverserange(string s,ll a,ll b){reverse(s.begin()+a-1,s.begin()+b); return s;}
int main(){
      int z;
      cin >> z;
      double ans = 2*z*3.14159265;
      cout << fixed<<setprecision(20);
      cout << ans <<endl;
}
    



Measured memory_bytes: 3756
A, B, C, D = [int(i) for i in input().split()]

if A < C:
    start_time = C
else :
    start_time = A

if B > D:
    stop_time = D
else :
    stop_time = B
    

if stop_time-start_time <= 0:
    print(0)
else :
    print(stop_time-start_time)

Measured memory_bytes: 2940
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] T = new int[N];
        int a = 0;
        
        for(int i=0; i<N; i++){
            T[i] = sc.nextInt();
            a += T[i];
        }

        int M = sc.nextInt();
        int[] P = new int[M];
        int[] X = new int[M];
        int[] ans = new int[M];

        for(int i=0; i<M; i++){
            P[i] = sc.nextInt();
            X[i] = sc.nextInt();
            ans[i] = a - T[P[i] - 1] + X[i];
            System.out.println(ans[i]);
        }
    }
}

Measured memory_bytes: 21972
#include <bits/stdc++.h>
using namespace std;
int main(){
	int N; 
		cin >>N;
/*	int x,y,z;
	x = N % 2 ;
	y = N % 10;
	z = N % 100;
		
	cout << x+y+z <<endl;*/
		// 1の位10の位100の位をどう引っ張り出すか。じゃあ
		// 1の位を出すときは、２で割ったあまり、
		// 10の位を出すときは、Nを10で割った値を2で割ったあまり
		// 以下略とすれば行ける！！
	int x,y,z;
	x = N%2 ;
	y = N/10 %2;
	z = N/100 %2 ;
	cout << x+y+z <<endl;
}


Measured memory_bytes: 256
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>

/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/

using namespace std;

#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007

signed main(){
    int N;

    cin>>N;

    int md=N%1000;

    if(md==0) cout<<"0"<<endl;
    else cout<<1000-md<<endl;
}



Measured memory_bytes: 3160
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_N = 110;
const int MAX_E = 110*110;

int par[MAX_N];
int rnk[MAX_N];

void init(int n) {
	for (int i = 0; i < n; i++) {
		par[i] = i;
		rnk[i] = 0;
	}
}

int find(int x) {
	if (par[x] == x) {
		return x;
	} else {
		return par[x] = find(par[x]);
	}
}

void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y) {
		return;
	}
	if (rnk[x] < rnk[y]) {
		par[x] = y;
	} else {
		par[y] = x;
		if (rnk[x] == rnk[y]) rnk[x]++;
	}
}

bool same(int x, int y) {
	return find(x) == find(y);
}

struct edge {
	int u, v, cost;
};

bool comp(const edge& e1, const edge& e2) {
	return e1.cost < e2.cost;
}

edge es[MAX_E];
int V, E;

int kruskal(void) {
	sort(es, es+E, comp);
	init(V);
	int res = 0;
	for (int i = 0; i < E; i++) {
		edge e = es[i];
		if (!same(e.u, e.v)) {
			unite(e.u, e.v);
			res += (e.cost-100)/100;
		}
	}
	return res;
}

int main() {
	int n, m;
	while (cin >> n) {
		if (n == 0) {
			break;
		}
		cin >> m;
		V = n;
		E = m;
		int a, b, c;
		char cc;
		for (int i = 0; i < m; i++) {
			cin >> a >> cc >> b >> cc >> c;
			es[i].u = a;
			es[i].v = b;
			es[i].cost = c;
		}
		cout << kruskal() << endl;
	}
}

Measured memory_bytes: 1240