akhauriyash/Code-Regression huggingface dataset:
//Following the naive approach would lead to timeout as we have to perform dfs on all the nodes... 
// resulting in O(n^2)

//better to use the build dp solution based on calculating the respective lengths of the child nodes 

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ld long double
#define pb push_back
// #define mp make_pair
#define nt _int128 
#define fir first
#define sec second
#define fast_as_levi ios_base::sync_with_stdio(false) , cin.tie(NULL);
#define debug(x) cout<<x<<"\n";
#define debug cout<<"debugged\n";
#define inf 0x3f3f3f3f
 
const ll mod = 1e9 + 7;
const ll mx = 2e6 + 5;
const ll mxi = 2e3 + 5;

int main()
{
    fast_as_levi;
    ll i,j,n,m;
    cin>>n>>m;
    char ar[n][m];
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            cin>>ar[i][j];
        }
    }
    ll dp[n+1][m+1];
    memset(dp,0,sizeof(dp));
    // just calculate the sum of total number of paths from above and left of every state 
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(ar[i-1][j-1] == '#')
            {
                dp[i][j] = 0;
                continue;
            }
            if(i==1 && j==1)
            {
                dp[i][j] = 1;
            }
            else
            {
                // if(i>0 && j>0)
                dp[i][j] = (dp[i-1][j] + dp[i][j-1])%mod;
            }
        }
    }
    // for(i=0;i<=n;i++)
    // {
    //     for(j=0;j<=m;j++)
    //     {
    //         cout<<dp[i][j]<<" ";
    //     }
    //     cout<<"\n";
    // }
    cout<<dp[n][m];
}

Measured memory_bytes: 9088
'use strict';

const inputs = require('fs').readFileSync('/dev/stdin', 'utf8').split('\n');
const sMpI = (str) => str.split(' ').map(v => parseInt(v, 10));
const pI = v => parseInt(v, 10);

const text1 = inputs.shift().split('');
const text2 = inputs.shift().split('');

let result = 0;

for (const i in text1) {
  if (text1[i] !== text2[i]) {
    ++result;
  }
}

console.log(result);

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


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n; cin >> n;
    ll a[n]; rep(i,n) cin >> a[i];
    ll ans = 0LL;
    rep(i,n-1){
        if(a[i] - a[i+1] <= 0) continue;
        ans += a[i]-a[i+1];
        a[i+1] = a[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 5196
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;

int main(){
	int n,i;
	long long ans=0;
	cin>>n;
	for(i=1;i<=n;i++){
		if(i%3!=0&&i%5!=0) ans+=i;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 3640
import Control.Monad
import Data.Bool
import Data.List

readInt = readLn :: IO Int
readInts = map read . words <$> getLine :: IO [Int]
readNInts = flip replicateM readInts

main :: IO ()
main = do
    [n, m] <- readInts
    a <- map tail <$> readNInts n
    print $ f m a

f :: Int -> [[Int]] -> Int
f 0 _ = 0
f n xs = (if all (n `elem`) xs
            then 1
            else 0) + f (n - 1) xs


Measured memory_bytes: 1020
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
const int maxn = 200005;
typedef pair<ll, ll>par;
const ll mod = 1e9+7;

int d[maxn], p[maxn];
vector<int>g[maxn];
int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    #ifdef acm
    freopen("a.in", "r",stdin);
    #endif // acm

    int n, m, a, b;
    cin >> n >> m;

    for( int i = 1; i <= m; i++ ){
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    for( int i = 1; i <= n; i++ )
        d[i] = 1 << 30;
    queue<int>q;
    d[1] = 0;
    q.push(1);

    int nodo;
    while( !q.empty() ){
        nodo = q.front();
        q.pop();
        for( auto i : g[nodo] ){
            if( d[i] > d[nodo]+1 ){
                d[i] = d[nodo]+1;
                p[i] = nodo;
                q.push(i);
            }
        }
    }

    int ok = 1;
    for( int i = 1; i <= n; i++ )
        if( d[i] == 1 << 30 ) ok = 0;

    if( !ok ){
        cout << "No\n";
        return 0;
    }

    cout << "Yes\n";

    for( int i = 2; i <= n; i++ )
        cout << p[i] << "\n";

    return 0;
}


Measured memory_bytes: 13352
#include <iostream>
#include <queue>
using namespace std;
int main(){
  int N;
  int j;
  cin >> N;
  long long int max = 0;
  priority_queue<int, vector<int>, greater<int> > s;
  for(int i = 0; i < N; ++i){
    cin >> j;
    s.push(j);
    max = max + j;
  }

  if(max % 10 != 0){
    cout << max << endl;
    exit(0);
  }

  bool check = true;

  for(int i = 0; i < N; ++i){
    if(s.top() % 10 != 0){
      cout << max - s.top() << endl;
      check = false;
      break;
    }

    s.pop();
  }

  if(check){
  cout << '0' << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#include<queue>
#include<ctime>
#include<vector>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<memory.h>
#include<map>
#include<ctime>
#include<algorithm>
#include<ctime>
#define ll int
#define For(i,j,k)  for(ll i=j;i<=k;++i)
#define FOr(i,j,k)  for(ll i=j;i>=k;--i)
#define ld double
using namespace std;
inline ll read(){   ll x=0,f=1;char ch=getchar();   while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}  while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}  return x*f; }
inline void wrote(ll x){    if (x<0) putchar('-'),x=-x; if (x>=10) wrote(x/10);   putchar(x%10+'0');  }
inline void writeln(ll x){ wrote(x);   puts("");   }
const ll N=1010;
ll n,h,ans,fa[N],C[N],D[N],vis[N];
ll find(ll x){	return x==fa[x]?x:fa[x]=find(fa[x]);	}
int main(){
	n=read();	read();
	For(i,1,1000)	fa[i]=i;
	For(i,1,n){
		ll a=read(),b=read(),c=read(),d=read();
		a=c?-c:a;	b=d?d:-b;	a+=500;	b+=500;
		fa[find(a)]=find(b);
		D[a]++;	D[b]--;	vis[a]=1;
	}
	bool fl=1;
	For(i,1,499)	fl&=D[i]<=0;
	For(i,501,1000)	fl&=D[i]>=0;
	For(i,1,1000)	vis[find(i)]|=vis[i];
	For(i,1,1000)	if (D[i])	C[find(i)]=1;
	For(i,1,1000)	fl&=(fa[i]!=i)||C[i]||!vis[i];
	puts(fl?"YES":"NO");
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define endl "\n"
#define pb push_back
#define ll long long
#define d1(x)  cerr << #x << "--> " << x << endl
#define d2(x, y)  cerr << #x << "--> " << x << " | " << #y << "--> " << y <<endl
#define d3(x, y,z)  cerr << #x << "--> " << x << " | " << #y << "--> " << y <<" | " << #z << "--> "<< z<< endl
#define vpll vector<pair<ll,ll>>
#define F first
#define S second
#define T ll tt; cin>>tt; while(tt--)
using namespace std;
ll mode=pow(10,9)+7;
bool cmp(pair<long double ,int > x, pair<long double , int> y){ return x.F<y.F; }
const ll MAXN=1e3+5;
ll __lcm(ll a, ll b){ return (a*b)/__gcd(a,b); }
 
int main(){ 
    
//    #ifndef ONLINE_JUDGE
//  		freopen("input.txt", "r", stdin);
//    #endif
    
    ios::sync_with_stdio(0);
    cin.tie(0);
	
	ll a,b;
	cin>>a>>b;
	string s1="", s2="";
	s1=a+'0';
	for (int i=1;i<b;i++){
		s1+=a+'0';
	}
	s2=b+'0';
	for (int i=1;i<a;i++){
		s2+=b+'0';
	}
	if (s1<s2) cout<<s1<<endl;
	else cout<<s2<<endl;
	
	return 0;
}


Measured memory_bytes: 256
/*BISMILLAH
THE WHITE WOLF
NO DREAM IS TOO BIG AND NO DREAMER IS TOO SMALL*/

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<long long> vll;
typedef vector<int> vi;

#define io ios_base::sync_with_stdio(false)
#define pb push_back
#define eb emplace_back
#define mod   998244353
#define PI 2*acos(0.0)
int dirx[] = {1, -1,0, 0}, diry[] = {0, 0, 1, -1};

ll bigmod(ll x, ll p)
{
    ll res = 1;
    while(p)
    {
        if(p&1)
            res = (res*x)%mod;
        x = (x*x)%mod;
        p >>= 1;
    }
    return res;
}

//=============================================ASIFAZAD==============================================//


int32_t main()
{
    io;
    int a, b, c;
    cin>>a>>b>>c;
    int cnt = 0;
    for(; a <= b; a++)
        if(a%c == 0)
            cnt++;
    cout<<cnt;
    return 0;
}

Measured memory_bytes: 3604
N, P = map(int, input().split())
A = list(map(int, input().split()))
# print(N, P, A)
num_odd = 0
num_even = 0
for a in A:
    if a % 2 == 0:
        num_even += 1
    else:
        num_odd += 1
# print(num_odd, num_even)

def cmb(n, r):
    ans = 1
    for i in range(r):
        ans *= n
        n -= 1
    ans1 = 1
    for i in range(1, r + 1):
        ans1 *= i
    return ans // ans1

ans = 0

if P == 0:
    select_odd = 0
    for i in range(0, num_odd + 1, 2):
        select_odd += cmb(num_odd, i)
    for i in range(0, num_even + 1):
        ans += cmb(num_even, i) * select_odd
else:
    select_odd = 0
    for i in range(1, num_odd + 1, 2):
        select_odd += cmb(num_odd, i)
    for i in range(0, num_even + 1):
        ans += cmb(num_even, i) * select_odd
print(ans)


Measured memory_bytes: 38664
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 10010
#define ll long long
#define mod 998244353
using namespace std;
ll ksm(ll a,ll b=mod-2)
{
	if(b==0) return 1;
	if(b==1) return a;
	ll q=ksm(a,b>>1);
	if(b&1)return q*q%mod*a%mod;
	return q*q%mod;
}
ll fac[N],inv[N];
int f[N][N];
ll C(int a,int b)
{
	if(b<0 || b>a) return 0;
	if(a==b || b==0) return 1;
	return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
char s1[N],s2[N];
int main()
{
	int n,m;
	scanf("%s%s",s1,s2);
	n=strlen(s1);
	fac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
	inv[n]=ksm(fac[n],mod-2);
	for(int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
	int sum1=0,sum2=0;
	for(int i=0;i<n;i++)
	sum1+=s1[i]=='1' && s2[i]=='1';
	for(int i=0;i<n;i++)
	sum2+=s1[i]=='1' && s2[i]=='0';
	for(int i=0;i<=sum2;i++) f[0][i]=fac[i]*fac[i]%mod;
	for(int i=1;i<=sum1;i++)
        for(int j=1;j<=sum2;j++)
            f[i][j]=(1ll*f[i-1][j]*i%mod*j%mod+1ll*f[i][j-1]*j%mod*j%mod)%mod;
    ll ans=0;
    for(int i=0;i<=sum1;i++)
    ans=(ans+1ll*f[sum1-i][sum2]*fac[i]%mod*fac[i]%mod*C(sum1,i)%mod*C(sum1+sum2,i))%mod;
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 389760
#include <stdio.h>

int main(int argc, char *argv[])
{
    int i, N, x = 0, max = 0;
    char S[128];
    scanf("%d\n", &N);
    fgets(S, sizeof(S), stdin);
    for ( i = 0; i < N; i++ ){
        if ( S[i] == 'D' ){
            x--;
        } else {
            x++;
        }
        if ( x > max ){
            max = x;
        }
    }
    printf("%d\n", max);
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e3+5;
vector<pair<ll,ll> >v(N);
ll dp[N][N];
int n;
ll fun(int l,int r){
	if(l>r) return 0;
	if(dp[l][r]) return dp[l][r];
	int i=n-(r-l+1);
	return dp[l][r]=max(fun(l,r-1)+v[i].first*(r-v[i].second),fun(l+1,r)+v[i].first*(v[i].second-l));
}
int main(){
	scanf("%d",&n);
	for(int i=0,x;i<n;i++)
		scanf("%d",&x),v.push_back({x,i});
	sort(v.rbegin(),v.rend());
	fun(0,n-1);
	printf("%lld\n",dp[0][n-1]);
	return 0;
}

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

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

    int n;
    cin >> n;
    int cnt_4 = n / 4;
    string result = "No";
    for (int i = 0; i <= cnt_4; ++i) {
        if ((n - 4 * i) % 7 == 0) {
            result = "Yes";
            break;
        }
    }

    cout << result << '\n';
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)
#define ll long long int
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int k; cin>>k;
    queue<ll>q;
    rep(i,1,9) q.push(i);
    int c=0;
    ll ans=0;
    while(c!=k)
    {
        ans=q.front();
        q.pop();
        c++; 
        if(ans%10!=0)
            q.push(10*ans+(ans%10)-1);
        q.push(10*ans+ans%10);
        if(ans%10!=9)
            q.push(10*ans+(ans%10)+1);

    }
    cout<<ans<<"\n";
    return 0;
}

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

int main() {
    int a, b, c;
    cin >> a >> b >> c;

    int i;
    for (int x = a; x <= b; x++) {
        if (c % x == 0) {
            i++;
        }
    }
    cout << i << endl;
    return 0;
}


Measured memory_bytes: 3096
using System;

namespace ABC054B
{
    static class Program
    {
        static void Main()
        {
            var n = int.Parse(Console.ReadLine());
            long power = 1;
            int mod = 1000000007;
            for (int i = 1; i <= n; i++)
                power = (power * i) % mod;
            Console.WriteLine(power);
        }
    }
}

Measured memory_bytes: 13140
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
using namespace std;
typedef pair<int, int> P;


signed main(){
    int n, m;
    while(1){
        cin >> n >> m;
        if(n + m == 0) break;
        vector<string> s(n);
        vector<int> a(n);
        rep(i, 0, n){
            cin >> s[i] >> a[i];
        }
        int ans = 0;
        rep(i, 0, m){
            string t;
            cin >> t;
            rep(j, 0, n){
                rep(k, 0, 8){
                    if(!(t[k] == s[j][k] || s[j][k] == '*')) break;
                    if(k == 7) ans += a[j];
                }
            }
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 1212
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }
    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int N = scan.nextInt();
        int[] A = new int[N];
        int[] B = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = scan.nextInt();
        }
        for (int i = 0; i < N; i++) {
            B[i] = scan.nextInt();
        }
        List<Pair> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            Pair p = new Pair();
            p.A = A[i];
            p.B = B[i];
            list.add(p);
        }
        list.sort(new PairComparator());
        long diff = 0;
        long count = 0;
        for (int i = 0; i < N; i++) {
            Pair p = list.get(i);
            if (0 <= p.diff()) {
                break;
            }
            diff += p.diff();
            if (p.diff() < 0) {
                count += 1;
            }
        }
        for (int i = N-1; 0 <= i; i--) {
            Pair p = list.get(i);
            if (p.diff() <= 0) {
                break;
            }
            if (0 <= diff) {
                break;
            }
            count += 1;
            diff += p.diff();
        }
        if (diff < 0) {
            System.out.println(-1);
        } else {
            System.out.println(count);
        }
    }
    class Pair {
        int A;
        int B;
        public int diff() {
            return A - B;
        }
    }
    class PairComparator implements Comparator<Pair> {
        @Override
        public int compare(Pair o1, Pair o2) {
            if (o1.diff() == o2.diff()) {
                return Integer.compare(o1.B, o2.B);
            }
            return Integer.compare(o1.diff(), o2.diff());
        }
    }
}


Measured memory_bytes: 81024
import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int cnt=0;
		for(int i=0;i<n;i++){
			int x=sc.nextInt();
			if(isPrime(x)){
				cnt++;
			}
		}
		System.out.println(cnt);
	}
	public static boolean isPrime(int x){
		if(x==2){
			return true;
		}
		if(x<2 || x%2==0){
			return false;
		}
		int i=3;
		while(i<=Math.sqrt(x)){
			if(x%i==0){
				return false;
			}
			i+=2;
		}
		return true;
	}
}


Measured memory_bytes: 40592
#include<iostream>
#include<math.h>
using namespace std;

int main(){
  long  n, mini;
  cin>>n;
  mini = n+2;
  for (int i=1;i<int(sqrt(n)+1);i++){
       if (n%i == 0)
         if(i + long(n/i) -2 < mini)
                   mini = i + long(n/i) -2;
    }
  cout<<mini<<endl;
  return 0;
}


Measured memory_bytes: 256
n = int(input())
t = list(map(int, input().split(' ')))
a = list(map(int, input().split(' ')))
result = 1
for i in range(n):
    h_max, h_min = min(t[i], a[i])+1, 1

    if i != 0:
        if t[i-1] < t[i]:
            h_min = t[i]
    else:
        h_min = t[0]

    if i != n-1:
        if a[i] > a[i+1]:
            h_min = a[i]
    else:
        h_min = max(a[n-1], h_min)


    result = result * max(h_max - h_min, 0) % (10**9+7)
print(result)

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

using ll = long long;
#define rep(i, n) for (long long i = 0; i < (n); ++i)
#define repr(i, a, b) for (auto i = (a); i < (b); ++i)
#define itr(x) for (auto&& v : (x))
#define updatemax(t, v) ((t) = std::max((t), (v)))
#define updatemin(t, v) ((t) = std::min((t), (v)))

#include <boost/operators.hpp>

class modint : private boost::operators<modint>, private boost::equivalent<modint> {
  modint(const long long x, const bool y)
      : x(x) {}

 public:
  static long long M;
  long long x;
  modint(const long long x = 0)
      : x((x % M + M) % M) {}
  modint operator-() const { return modint(x ? M - x : 0, true); }
  modint& operator+=(const modint& b) { return ((x += b.x) >= M ? x -= M : 0), *this; }
  modint& operator++() { return (++x >= M ? x -= M : 0), *this; }
  modint& operator-=(const modint& b) { return ((x -= b.x) < 0 ? x += M : 0), *this; }
  modint& operator--() { return (--x < 0 ? x += M : 0), *this; }
  modint& operator*=(const modint& b) { return x = x * b.x % M, *this; }
  modint& operator/=(const modint& b) { return *this *= b.pow(-1); }
  modint pow(long long b) const {
    long long r = 1, a = x;
    b = (b % (M - 1) + (M - 1)) % (M - 1);
    while (b) {
      if (b & 1) r = r * a % M;
      b = b >> 1;
      a = a * a % M;
    }
    return modint(r, true);
  }
  friend bool operator<(const modint& a, const modint& b) { return a.x < b.x; }
  friend std::istream& operator>>(std::istream& s, modint& a) { return s >> a.x, a = a.x, s; }
  friend std::ostream& operator<<(std::ostream& s, const modint& a) { return s << a.x; }
};
long long modint::M = 1e9 + 7;

modint ssum[200100];
int main() {
  ll n, p;
  string s;
  cin >> n >> p >> s;
  ll result = 0;
  if (p == 2 || p == 5) {
    rep(i, n) if ((s[i] - '0') % p == 0) result += i + 1;
  } else {
    modint::M = p;
    rep(i, n) ssum[i + 1] = ssum[i] * 10 + (s[i] - '0');
    auto inv10 = modint(10).pow(-1);
    map<modint, ll> gc;
    modint p10i(1);
    rep(i, n + 1) {
      ++gc[ssum[i] * p10i];
      p10i *= inv10;
    }
    itr(gc) result += v.second * (v.second - 1) / 2;
  }
  cout << result << endl;
}


Measured memory_bytes: 5732
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#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() {
  int n;
  cin >> n;

  map<string,ll> c;
  rep(i,n){
    string s;
    cin >> s;
    sort(s.begin(),s.end());
    c[s]++;
  }
  ll ans = 0;
  for(auto ci:c){
    ll cnt = ci.second;
    ans += cnt*(cnt-1)/2;
  }
  cout << ans << endl;
}


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

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

template<typename P, typename Q>
ostream& operator << (ostream& os, pair<P, Q> p)
{
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n;
  while (cin >> n) {
    vector<int> a(n);
    each (i, a) cin >> i;

    int bit = 0;

    int begin = 0;
    int end = 0;

    lli sum = 0;
    while (begin <= end) {
      while (end < n) {
        if (bit & a[end]) {
          break;
        }
        bit |= a[end];
        ++end;
      }

      sum += end - begin;

      bit ^= a[begin];
      ++begin;
    }

    cout << sum << endl;
  }

  return 0;
}


Measured memory_bytes: 1024
a,b,n = list(map(int, input().split()))
def f(x):
    return a*x//b - a*(x//b)

left=1
right=n
for _ in range(100):
    delta=(right-left)/3
    midl=left+delta
    midr=midl+delta
#    print(f'left={left} midl={midl} midr={midr} right={right}')
    if f(midl)>f(midr):
        right=midr
    else:
        left=midl
print(max(f(int(midl)),f(min(int(midl)+1,n))))

Measured memory_bytes: 9196
#include<iostream>
#include<vector>
#include<utility>
using namespace std;
using ll = long long;

vector<pair<ll,ll> > primeFactorize(ll x) {
  vector<pair<ll,ll> > res;
  for (ll i=2;i*i<=x;i++) {
    ll ex=0;
    while (x%i == 0) {
      ex++;
      x/=i;
    }
    res.push_back({i, ex});
  }
  if (x>1) res.push_back({x, 1});

  return res;
}

int main() {
  ll N,i,j,ans=0;
  cin>>N;
  vector<pair<ll,ll> > pF = primeFactorize(N);
  for (i=0;i<pF.size();i++) {
    for (j=1;j<=pF[i].second;j++) {
      pF[i].second -= j;
    }
    ans += (j-1);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 19340
#include<iostream>
std::string s;
long long a,x[26],i,j;
main(){
  for(std::cin>>s;i<s.size();)x[s[i++]-'a']++;
  for(;j<s.size();x[s[j++]-'a']--)a+=s.size()-j-x[s[j]-'a'];
  std::cout<<a+1<<'\n';
}


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

#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 ALL(obj) (obj).begin(), (obj).end()
#define INF 1e9
typedef long long ll;


int main() {
    int c,a,b; cin >> c >> a >> b;
    cout << a*c/2 << endl;
    return 0;
}

Measured memory_bytes: 3596
MOD = 10**9+7
N, M = map(int, input().split())
N += 1
A = set()
for _ in range(M):
    A.add(int(input()))
dp = [0]*N
dp[0] = 1
if 1 not in A:
    dp[1] = 1
for i in range(2,N):
    if i not in A:
        dp[i] += dp[i-1] + dp[i-2]
        dp[i] %=MOD
print(dp[-1])

Measured memory_bytes: 83296
function Main(input){
    input = input.split("\n");
    var total = parseInt(input[0].split(" ")[0],10);
    var shukudai = 0;
    //console.log(input[1].split(" "));
    input[1].split(" ").forEach(element => {
        //console.log(element);
        shukudai += parseInt(element, 10);
    });
    var ans = total - shukudai;
    if(ans < 0){
        ans = -1;
    }
    
    //console.log(total);
    //console.log(shukudai);
    console.log(ans);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

int main() {
  int N;
  long int ans = 1;
  cin >> N;
  for (int i = 1; i <= N; i++) {
    ans = ans * i;
    ans = fmod(ans, (pow(10, 9) + 7));
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 384
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
import java.lang.Math;

public class Main {
    public static void main(String[] args) {
        FS reader = new FS();
        // write reader
        String S = reader.next();
        if (S.equals("Sunny")) {
            System.out.println("Cloudy");
        } else if (S.equals("Cloudy")) {
            System.out.println("Rainy");
        } else {
            System.out.println("Sunny");
        }
    }
    
    public static void solver() {
        // write logic
    }
    
    // Read Class
    static class FS {
        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() { return hasNextByte() ? buffer[ptr++] : -1;}
        private boolean isPrintableChar(int c) {return 33 <= c && c <= 126;}
        private void skipUnprintable() {while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
    
        public boolean hasNext() { skipUnprintable(); 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 int nextInt() {
            return (int)nextLong();
        }
        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();
            }
        }
    }
}



Measured memory_bytes: 20948
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define REP1(i,n) for(int i=1; i<=(int)(n); i++)
#define SORT(v) sort(v.begin(), v.end())
#define REVERSE(v)  reverse(v.begin(), v.end())
using namespace std;

int main() {
  int H,W; cin>>H>>W;
  bool black = false;
  vector<bool> blackH(H);
  vector<bool> blackW(W);
  char a[H][W];
  REP(i,H) {
    REP(j,W) {
      cin>>a[i][j];
      if(a[i][j] == '#') black = true;
    }
    if(black) blackH[i] = true;
    else blackH[i] = false;
    black = false;
  }

  REP(i,W) {
    REP(j,H) {
      if(a[j][i] == '#') black = true;
    }
    if(black) blackW[i] = true;
    else blackW[i] = false;
    black = false;
  }

  REP(i,H) {
    if(blackH[i]) {
      REP(j,W) {
        if(blackW[j])
          cout<<a[i][j];
        }
      cout<<endl;
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
char s[10005];
int main() {
//	memset(hed, -1, sizeof(hed));
	cin >> n;
	cin >> (s + 1);
	if(n & 1) {
		puts("No");
		return 0;
	}	
	n >>= 1;
	int i;
	for(i = 1; i <= n; ++i) 
		if(s[i] != s[i + n]) {
			puts("No");
			return 0;
		}
	puts("Yes");	
	return 0;
}

Measured memory_bytes: 256
N, K = map(int, input().split())
MOD = 10**9+7
ans = 0

div = [set() for _ in range(K+1)]
for i in range(2, K+1):
    for j in range(2*i, K+1, i):
        div[j].add(i)

pattern = [0]*(K+1)
for x in range(2, K+1)[::-1]:
    pattern[x] = (pattern[x] + pow(K//x, N, MOD)) % MOD
    for d in div[x]:
        pattern[d] = (pattern[d] - pattern[x] % MOD) % MOD
    pattern[1] = (pattern[1] - pattern[x]) % MOD
    
    ans = (ans + (pattern[x] * x) % MOD) %MOD

ans = (ans + (pow(K, N, MOD) + pattern[1]) % MOD ) % MOD

print(ans)

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

int main() {
    string s, t;
    cin >> s >> t;
    cout << t << s << endl;
}


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 int dx[4] = { 0, -1, 1, 0 };
const int 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);
}

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

template<class T1, class T2> void chmax(T1 &a, T2 b) { if (a<b)a = b; }
template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}
////////////////////////////////////////
int main() {
	int N;
	int a[100100];
	cin >> N;
	for (int i = 0; i < N; ++i) {
		cin >> a[i];
	}
	ll sum1 = 0; ll sum2 = 0;
	ll ans1 = 0; ll ans2 = 0;
	for (int i = 0; i < N; ++i) {
		sum1 += a[i];
		if (i % 2 == 0 && sum1 <= 0) {
			ans1 += abs(sum1) + 1;
			sum1 = 1;
		}
		else if (i % 2 != 0 && sum1 >= 0) {
			ans1 += sum1 + 1;
			sum1 = -1;
		}
	}
	for (int i = 0; i < N; ++i) {
		sum2 += a[i];
		if (i % 2 == 0 && sum2 >= 0) {
			ans2 += sum2 + 1;
			sum2 = -1;
		}
		else if (i % 2 != 0 && sum2 <= 0) {
			ans2 += abs(sum2) + 1;
			sum2 = 1;
		}
	}
	cout << min(ans1, ans2) << endl;
	return 0;
}

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

using namespace std;

int main() {

  int n; cin >> n;
  vector<int> a(n), b(n);
  for (int i = 0; i < n; ++i)
    cin >> a[i];
  for (int i = 0; i < n; ++i)
    cin >> b[i];

  vector<int> oa(n), ob(n);
  for (int i = 0; i < n; ++i) {
    oa[i] = ob[i] = i;
  }

  sort(ob.begin(), ob.end(), [&](int i, int j) {
    return b[i] < b[j];    
  });
  sort(oa.begin(), oa.end(), [&](int i, int j) {
    return a[i] < a[j];    
  });

  vector<int> pa(n), pb(n);
  for (int i = 0; i < n; ++i) {
    pa[oa[i]] = i;
    pb[ob[i]] = i;
  }

 
  for (int i = 0; i < n; ++i) {
    if (a[oa[i]] > b[ob[i]]) {
      cout << "No\n";
      return 0;
    }
  }
  
  if (n == 2) {
    for (int i = 0; i < n; ++i) {
      if (a[i] > b[i]) {
        cout << "No\n";
        return 0;
      }
    }
  }
  
  for (int i = 1; i < n; ++i) {
    if (a[oa[i]] <= b[ob[i - 1]]) {
      cout << "Yes\n";
      return 0;
    }
  }

  vector<int> seek(n);
  for (int i = 0; i < n; ++i) {
    seek[oa[i]] = ob[i];
  }

  int at = 0;
  int cnt = 0;
  do {
    cnt += 1;
    at = seek[at];
  } while (at);
  if (cnt == n) {
    cout << "No\n";
    return 0;
  }

  cout << "Yes\n";
  return 0;
}


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

int main(){
  int n;
  cin >> n;
  ll sum = 0;
  rep(i,n){
    ll a = i+1;
    if( a%3 == 0 || a%5 == 0 )continue;
    else sum += a;
  }
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)for(int i=0;i<(n);i++)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
using ll = long long;
using P = pair<int, int>;

int main(){
    string s; cin >> s;
    vector<char> w, b;
    int cnt = 0;
    for(int i = 0; i < s.size()-1; ++i){
        if(s[i] != s[i+1]) cnt++;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 512
//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

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

int a[100010];
signed main(void)
{
  int n;
  cin >> n;
  REP(i, n) cin >> a[i];

  VI v;
  int c = 1;
  bool f;
  if(a[0] == 0) f = true;
  else f = false;
  FOR(i, 1, n) {
    if(f) {
      if(a[i]) {
        f = false;
        c++;
      } else {
        f = true;
        v.PB(c);
        c = 1;
      }
    } else {
      if(!a[i]) {
        f = true;
        c++;
      } else {
        f = false;
        v.PB(c);
        c = 1;
      }
    }
  }
  v.PB(c);

  // for(int i: v) cout << i << " "; cout << endl;
  if(v.size() <= 3) {
    cout << n << endl;
    return 0;
  }

  int ret = 0;
  FOR(i, 1, v.size()-1) {
    ret = max(ret, v[i-1] + v[i] + v[i+1]);
  }
  cout << ret << endl;

  return 0;
}

Measured memory_bytes: 3532
using System;

namespace あっとコーダー
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            //string[] s = Console.ReadLine().Split(' ');

            int n = int.Parse(Console.ReadLine());
            int tmp = n;
            int sum = 0;

            while(n >0)
            {
                sum += n % 10;
                n = n / 10;
            }


            if (tmp % sum == 0)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }


        }
    }
}

Measured memory_bytes: 13140
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
import static java.lang.Math.*;
class bridge{
	public int a;
	public int b;
	public bridge() {
		a = b = 0;
	}
}
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int k = in.nextInt();
		bridge [] s = new bridge[k];
		for(int i = 0;i < k;i ++) {
			s[i] = new bridge();
			s[i].a = in.nextInt();
			s[i].b = in.nextInt();
		}
		Arrays.sort(s,new Comparator<bridge>() {
			public int compare(bridge x,bridge y) {
				if(x.a == x.b)return x.b - y.b;
				return x.a - y.a;
			}
		});
		int ans = 0,r = 0;
		for(int i = 0;i < k;i ++) {
			if(s[i].a >= r) {
				ans ++;
				r = s[i].b;
			}
			else if(r > s[i].b)r = s[i].b;
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 90664
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
#define all(a) (a).begin(),(a).end()
#define overload4(_1, _2, _3, _4, name, ...) name
#define rep1(n) for(ll i = 0;i < (n);i++)
#define rep2(i,n) for(ll i = 0;i < (n);i++)
#define rep3(i,a,b) for(ll i = (a);i < (b);i++)
#define rep4(i,a,b,c) for(ll i = (a);i < (b);i += (c))
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(n) for(ll i = (n)-1;i >= 0;i--)
#define rrep2(i,n) for(ll i = (n)-1;i >= 0;i--)
#define rrep3(i,a,b) for(ll i = (a)-1;i >= (b);i--)
#define rrep4(i,a,b,c) for(ll i = (a)-1;i >= (b);i -= (c))
#define rrep(...) overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define SHOW(x) cout << #x << ": " << x << endl;
template<class T> ll sumArr(const T& a){ return accumulate(all(a), 0LL);}
template<class T> auto minArr(const T& a){ return *min_element(all(a));}
template<class T> auto maxArr(const T& a){ return *max_element(all(a));}
template<class T> void DEBUG_PRINT(T tmp){cout<<tmp<<endl;}
template<class T1,class... T2> void DEBUG_PRINT(T1 tmp,T2... tmp2){cout<<tmp<<" ";DEBUG_PRINT(tmp2...);}
ll gcd(ll a, ll b){ while(b){ ll c = b; b = a % b; a = c; } return a; }
const ll INF=1e18,MOD = 1e9+7;
const int iINF = 1e9;


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

    int n,k,a,d,ans = 0;
    cin>>n>>k;
    vector<int>list(n,0);
    rep(i,k){
        cin>>d;
        rep(j,d){
            cin>>a;
            list[a - 1]++;
        }
    }
    rep(i,n)if(list[i] == 0)ans++;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3660
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <utility>
#include <functional>
#include <deque>
#include <cctype>
#include <stack>
#include <bitset>

using ll = long long;
typedef unsigned long long ull;
typedef std::pair<ll, ll>P;

ll min(ll a, ll b) {
	if (a >= b)return b;
	else return a;
}
ll max(ll a, ll b) {
	if (a >= b)return a;
	else return b;
}
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}

const ll Z = 1000000007;
const ll INF = 1 << 30;
const ll INF2 = 9000000000000000000LL;
bool flag = true;
bool fl = true;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
std::string abc = "abcdefghijklmnopqrstuvwxyz";
struct edge { ll to, cost; };

int main() {
	ll x, ans = 0;
	std::cin >> x;
	ans += x / 11 * 2;
	if (0 < x%11 && x%11 <= 6)ans++;
	else if (x%11 >= 7)ans += 2;
	std::cout << ans << std::endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,a[100005];
bool cmp(const int x,const int y)
{
	return x>y;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1,cmp);
	int id=0;
	for(int i=1;i<=n;i++)
		if(a[i]>=i) id=i;
	if(id==n||a[id]>a[id+1])
	{
		int nw=id+1;
		while(nw<n&&a[nw+1]==a[id+1]) nw++;
		if((a[id]-id)%2==1||(a[id+1]==id&&(nw-(id+1))%2==0)) printf("First\n");
		else printf("Second\n");
		return 0;
	}
	int nw=id;
	while(nw<n&&a[nw+1]==a[id]) nw++;
	if((nw-id)%2) printf("First\n");
	else printf("Second\n");
	return 0;
} 

Measured memory_bytes: 512
#include <iostream>
using namespace std;
int main()
{
  int n, count = 0;
  cin >> n;
  for(int i=1; i<n; i++)
  {
  	for(int j = 1; i*j<n; j++)
  		count++;
  }
  cout << count << "\n";
  return 0;
}


Measured memory_bytes: 3200
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
int D[1 << 17];
int P[1 << 17];
int s1[55],s2[55];
int W[1 << 17];
const int mod = 1e9 + 7;
int main(void)
{
    int n,m;
    cin>>n>>m;
    int p2 = 1;
    while (m --)
    {
        int a,b;
        cin>>a>>b;
        --a;--b;
        s1[a] |= 1 << b;
        s2[b] |= 1 << a;
        p2 = p2 * 2 % mod;
    }
    const int N = 1 << n;
    P[0] = 1;
    for (int mask = 1;mask < N;++mask)
        P[mask] = (P[mask - (mask & (-mask))] * 2) % mod;
    D[0] = 1;
    int ans = 0;
    for (int mask = 0;mask < N;++mask)
        if (D[mask])
        {
            const int rem = (N - 1) ^ mask;
            for (int sub = rem;sub;sub = (sub - 1) & rem)
            if ((sub & 1) == ((sub >> 1) & 1))
            {
                const int R = rem ^ sub;
                int coef = D[mask];
                for (int j = 0;j < n;++j)
                    if ((R >> j) & 1)
                        coef = (1ll * coef * (P[s1[j] & sub] - 1)) % mod,coef = (1ll * coef * P[s2[j] & sub]) % mod;
                D[sub | mask] = (D[sub | mask] + coef) % mod;
            }
        }
    ans = (p2 + mod - D[N - 1]) % mod;
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 640
n=int(input())
a=list(map(int,input().split()))
b=[0]*n
for i in range(n,0,-1):
    if sum(b[i-1::i])%2 == a[i-1]:
        continue
    else:
        b[i-1] = 1

b_index=[i+1 for i in range(n) if b[i]==1]
print(sum(b))
print(*b_index)

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

using namespace std;

typedef long long ll;

const int N = 2e5 + 5;
int A[N], B[N];
int n;


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

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> A[i] >> B[i];
    }
    sort(A, A + n);
    sort(B, B + n);

    if (n & 1) {
        int l = A[n / 2];
        int r = B[n / 2];
        cout << r - l + 1 << endl;
    } else {
        int l = A[n / 2 - 1] + A[n / 2];
        int r = B[n / 2 - 1] + B[n / 2];
        cout << r - l + 1 << endl;
    }

    return 0;
}



Measured memory_bytes: 5136
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<functional>
using namespace std;
int n, m, dist[200], d[200][200];
vector<pair<int, int>>x[200];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>Q;
void dijkstra(int r1) {
	for (int i = 0; i < 200; i++)dist[i] = 999999999;
	dist[r1] = 0; Q.push(make_pair(0, r1));
	while (!Q.empty()) {
		int a2 = Q.top().first, a1 = Q.top().second; Q.pop();
		for (int i = 0; i < x[a1].size(); i++) {
			int to = x[a1][i].first, cost = x[a1][i].second;
			if (dist[to] > dist[a1] + cost) {
				dist[to] = dist[a1] + cost; Q.push(make_pair(dist[to], to));
			}
		}
	}
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c; cin >> a >> b >> c;
		x[a].push_back(make_pair(b, c));
		x[b].push_back(make_pair(a, c));
	}
	for (int i = 1; i <= n; i++) {
		dijkstra(i);
		for (int j = 1; j <= n; j++)d[i][j] = dist[j];
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < x[i].size(); j++) {
			if (d[i][x[i][j].first] < x[i][j].second)cnt++;
		}
	}
	cout << cnt / 2 << endl;
	return 0;
}

Measured memory_bytes: 384
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	ans := 0
	for i := 1; i <= n; i++ {
		var x int
		fmt.Scan(&x)
		if i%2 == 1 && x%2 == 1 {
			ans++
		}
	}
	fmt.Print(ans)
}


Measured memory_bytes: 1764
#include <stdio.h>
int main(void)
{
	int a[] = {1, 3, 5, 7, 8, 10, 12};
	int b[] = {4, 6, 9, 11};
	int x, y;
	int i;
	int f = 0;
	scanf("%d %d", &x, &y);
	for (i = 0; i < 7; i++) {
		if (x == a[i]) f++;
		if (y == a[i]) f++;
	}
	if (f == 2) puts("Yes");
	if (f != 2) {
		f = 0;
		if (x == b[0]) f++;
		for (i = 1; i < 3; i++) {
			if (x == b[i]) f++;
			if (y == b[i]) f++;
		}
		if (f >= 2) puts("Yes");
		else puts("No");
	}
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 100005
#define INF 1e18
#define MOD 1000000007

using namespace std;
typedef long long int ll;
typedef pair <ll,int> P;

typedef tuple <ll,int,int> T;
struct edge{int to;ll cost;};
vector<edge> G[SIZE],M[SIZE];
bool used[SIZE];

//0_indexed
ll prim(){
  priority_queue<T,vector<T>,greater<T>> que;
  fill(used,used+SIZE,false);
  rep(i,0,SIZE) M[i].clear();
  ll res = 0;
  que.push(T(0,0,0));
  while(!que.empty()){
    T t = que.top();que.pop();
    ll l = get<0>(t);
    int v = get<1>(t);
    int from = get<2>(t);
    if(used[v])continue;
    res += l;
    used[v] = true;
    M[v].push_back((edge){from,l});
    M[from].push_back((edge){v,l});
    for(edge u : G[v]){
      if(!used[u.to])que.push(T(u.cost,u.to,v));
    }
  }
  return res;
}

void add_edge(int a,int b,ll c){
  G[a].push_back((edge){b,c});
  G[b].push_back((edge){a,c});
}

int n;
P x[SIZE],y[SIZE];

int main(){
  cin >> n;
  rep(i,0,n){
    cin >> x[i].first >> y[i].first;
    x[i].second = y[i].second = i;
  }
  sort(x,x+n);
  sort(y,y+n);
  rep(i,1,n){
    add_edge(x[i].second,x[i-1].second,x[i].first-x[i-1].first);
    add_edge(y[i].second,y[i-1].second,y[i].first-y[i-1].first);
  }
  cout << prim() << endl;

  return 0;
}


Measured memory_bytes: 23280
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
  public static void main(String[] args) throws IOException{
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    String[] str = in.readLine().split(" ");
    int h = Integer.parseInt(str[0]);
    int a = Integer.parseInt(str[1]);
    int num = 0;
    while(h>0){
      h -= a;
      num++;
    }
    System.out.println(num);
  }
}

Measured memory_bytes: 22612
import java.util.Scanner;

public class Main {

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

      int H = in.nextInt();
      int W = in.nextInt();

      char[][] S = new char[H+1][W+1];
      int[][] flag = new int[H+3][W+3];

      for(int cnth = 0; cnth < H; cnth++) {
          String str = in.next();
          for(int cntw = 0; cntw < W; cntw++) {
              S[cnth][cntw] = str.charAt(cntw);
              //flag[cnth][cntw] = 0;
          }
      }

      for(int cnth = 0; cnth < H; cnth++) {
          for(int cntw = 0; cntw < W; cntw++) {
              if(S[cnth][cntw] == '#') {
                  flag[cnth][cntw]++;
                  flag[cnth][cntw+1]++;
                  flag[cnth][cntw+2]++;
                  flag[cnth+1][cntw]++;
                  flag[cnth+1][cntw+2]++;
                  flag[cnth+2][cntw]++;
                  flag[cnth+2][cntw+1]++;
                  flag[cnth+2][cntw+2]++;
              }
          }
      }


      for(int cnth = 0; cnth < H; cnth++) {
          for(int cntw = 0; cntw < W; cntw++) {
              if(S[cnth][cntw] == '#') {
                  System.out.print(S[cnth][cntw]);
              }
              else {
                  System.out.print(flag[cnth+1][cntw+1]);
              }

          }
          System.out.println();
      }

    }
}

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

using namespace std;

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

	if(k%2==0 && k%5==0)
		cout<<-1;

	else
	{
		int cnt=1,num=7;
		while(num%k)
		{
			cnt++;
			if(cnt>10000000) break;
			num=num*10;
			num+=7;
			num%=k;
		}

		if(num%k==0) cout<<cnt;
		else cout<<-1;
	}
	return 0;
}

Measured memory_bytes: 3636
package main

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

var sc, wr = bufio.NewScanner(os.Stdin), bufio.NewWriter(os.Stdout)

func scanString() string   { sc.Scan(); return sc.Text() }
func scanRunes() []rune    { return []rune(scanString()) }
func scanInt() int         { a, _ := strconv.Atoi(scanString()); return a }
func scanInt64() int64     { a, _ := strconv.ParseInt(scanString(), 10, 64); return a }
func scanFloat64() float64 { a, _ := strconv.ParseFloat(scanString(), 64); return a }

func scanInts(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = scanInt()
	}
	return res
}

func debug(a ...interface{}) { fmt.Fprintln(os.Stderr, a...) }

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

//•*¨*•.¸¸♪main•*¨*•.¸¸♪(　-ω-)ノ　(　・ω・)
func main() {
	defer wr.Flush()
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 10000), 1001001)

	a := scanInt()
	b := scanFloat64()

	fmt.Fprintln(wr, a*int(b*100+0.5)/100)
}


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

int main(){
    int a,b,c;
    cin>>a>>b>>c;
    if (a!=b&&b!=c&&a!=c)
    {
        /* code */
        cout<<"No"<<endl;
    }
    else if(a==b&&b==c&&a==c){
        cout<<"No"<<endl;

    }
    else
    {
        cout<<"Yes"<<endl;
    }
    
    

}


Measured memory_bytes: 256