akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define ll  long long int
#define pb push_back
#define ff first
#define ss second
#define mp make_pair
#define inf 10000000LL
#define fast_io	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define mod 1000000007
#define range 100001
#define lg 22
using namespace std;
int main()
{
	ll n,x,y,s=0,q;
	cin>>n;
	ll A[range]={0};
	
	for(ll i=1;i<=n;i++)
	{
		cin>>x;
		A[x]++;
		s+=x;
	}
	cin>>q;
	for(ll i=1;i<=q;i++)
	{
		cin>>x>>y;
		A[y]+=A[x];
		s+=y*A[x]-x*A[x];
		A[x]=0;
		cout<<s<<endl;
	}

//	cout<<s<<endl;
}

Measured memory_bytes: 4448
#include<stdio.h>
int main(){
  int n;
  int i;
  int j=0;
  scanf("%d",&n);
  int a[n];
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
  }
  int x,y;
  for(i=0;i<n-1;i++){
    printf("%d ",a[i]);
  }
  printf("%d",a[n-1]);
  printf("\n");
  for(i=1;i<n;i++){
    x=a[i];
    j=i-1;
    while(j>=0 && a[j]>x){
      a[j+1]=a[j];
      j--;
      a[j+1]=x;
    }
    for(y=0;y<n-1;y++){
      printf("%d ",a[y]);
    }
    printf("%d",a[n-1]);
    printf("\n");
  }
  return 0;
}



Measured memory_bytes: 2140
def getAverage(points)
  sum = 0
  points.each {|x|
    sum += x
  }
  return (sum / points.length).to_f
end

while true
  n = STDIN.gets.to_i
  if n == 0 then break end
  str = STDIN.gets.split(" ")
  point = Array.new(n) { |i|  i = str[i].to_f}

  average = getAverage(point)
  s = 0.0
  for i in 0..point.length - 1 do
    s += (point[i] - average) * (point[i] - average)
  end
  s = Math.sqrt(s / n)
  puts sprintf("%.5f", s)
end

Measured memory_bytes: 6148
#include<bits/stdc++.h>
using namespace std;
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vec             vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define inf             1e18
#define no_of_test(x)        int x; cin>>x; while(x--)
const int mod = 1e9 + 7;
int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	no_of_test(x)
	{
      int n;
	  cin>>n;
	  int a[n];
	  set<int>s;
	  for(int i=0;i<n;i++)
	  {
		  cin>>a[i];
		  s.insert(a[i]);
	  }
	  if(s.size()==n)
	  {
		  cout<<"YES"<<'\n';
	  }
	  else
	  {
		cout<<"NO"<<'\n';
	  }
	  

	}
	return 0;
}

Measured memory_bytes: 14568
function Main(input) {
  var dataList = input.split("\n");
  dataList.shift();
  dataList.pop();
  var restaurants = dataList.map((data, index) => {
    var tmp = data.split(" ")
    return { index: index + 1, city: tmp[0], score: parseInt(tmp[1]) }
  });
  restaurants.sort(function(a, b) {
    if (a.city < b.city) return -1
    if (a.city > b.city) return 1
    if (a.score < b.score) return 1
    if (a.score > b.score) return -1
  });
  restaurants.forEach(restaurant => {
    console.log(restaurant.index);
  });
}

//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7500
#include <bits/stdc++.h>
#define REP(i, N) for (int i = 0; i < (N); ++i)
#define ALL(x) (x).begin(), (x).end()
#define MOD 1000000007
#define PB push_back
#define MP make_pair
using namespace std;
typedef long long ll;
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

//++時計回り --反時計回り
// int dx[4] = {1, 0, -1, 0};
// int dy[4] = {0, 1, 0, -1};

int main() {
  int A, B;
  cin >> A >> B;
  cout << max(A + B, max(A - B, A * B)) << '\n';
}


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

using namespace std;

typedef long long ll;


int main() {
  int n;
  cin >> n;
  vector<int> la(n);
  for (int &a: la) cin >> a;
  ll ans = 0;
  ll l = 0;
  ll s1 = 0, s2 = 0;
  for (ll i = 0; i < n; ++i) {
    s1 += la[i];
    s2 ^= la[i];
    while (s1 != s2) {
      s1 -= la[l];
      s2 ^= la[l];
      ++l;
    }
    ans += i-l+1;
  }
  cout << ans << endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
typedef long long ll;
int x,y;

const int MAX = 676666;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(){
    cin>>x>>y;
    if(min(x,y)*2<max(x,y)||(x+y)%3!=0){
        cout<<0;
        return 0;
    }
    int n=(x+y)/3;
    x-=n;
    y-=n;
    COMinit();
    cout<<COM(n,x)<<endl;
}

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

typedef long long LL;

const long long INF = 1LL << 60;

using namespace std;

int main()
{
    int A, B;
    cin >> A >> B;

    cout << A * B << endl;

    return 0;
}

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

int main(){
  int64_t x, y;
  x=2;
  y=1;
  int N;
  cin>>N;
  for(int i=2;i<=N;i++){
    if(i%2==0) x=x+y;
    else y=x+y;
  }
  if(N%2==0) cout<<x<<endl;
  else cout<<y<<endl;
}


Measured memory_bytes: 3624
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
struct uf {
  vector<int> a;
  uf(int n): a(n, -1) {}
  int root(int x) {
    return a[x] < 0 ? x : a[x] = root(a[x]);
  }
  void unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) return;
    if (a[x] > a[y]) swap(x, y);
    a[x] += a[y];
    a[y] = x;
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
  int size(int x) {
    return -a[root(x)];
  }
};
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> a(m), b(m);
  for (int i = 0; i < m; i++) {
    cin >> a[i] >> b[i];
    a[i]--; b[i]--;
  }
  vector<long long> ans;
  ans.push_back(1LL * n * (n - 1) / 2);
  uf u(n);
  for (int i = m - 1; i > 0; i--) {
    ans.push_back(ans.back());
    if (u.same(a[i], b[i])) continue;
    *prev(ans.end()) -= 1LL * u.size(a[i]) * u.size(b[i]);
    u.unite(a[i], b[i]);
  }
  reverse(ans.begin(), ans.end());
  for (int i = 0; i < m; i++) {
    cout << ans[i] << endl;
  }
  return 0;	  
}

Measured memory_bytes: 3444
#include <iostream>

using namespace std;

int main() {
	int A, B;
	cin >> A >> B;
	if (A <= 5) {
		cout << 0 << endl;
	} else if (A <= 12) {
		cout << B / 2 << endl;
	} else {
		cout << B << endl;
	}
}


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

int main(){
    int n,k;
    cin >> n >> k;
    string s;
    cin >> s;
    bool first_stand;
    if(s.at(0)=='1') first_stand=true;
    else first_stand = false;
    vector<int> people;
    int cnt=1;
    for(int i=1; i<n; i++){
        if(s.at(i) != s.at(i-1)){
            people.push_back(cnt);
            cnt=1;
        }
        else cnt++;
    }
    people.push_back(cnt);
    for(int i=1;i<people.size(); i++){
        people.at(i)+=people.at(i-1);
    }
    int ps=people.size();
    if(first_stand){
        int cnt=1;
        int ans = people.at(min(ps-1, 2*k));
        while(cnt<ps){
            int result;
            result = people.at(min(ps-1,cnt+2*k+1)) - people.at(cnt);
            cnt+=2;
            ans = max(ans,result);
        }
        cout << ans << endl;
    }
    else{
        int cnt=0;
        int ans=people.at(min(ps-1, 2*k-1));
        while(cnt<ps){
            int result;
            result = people.at(min(ps-1,cnt+2*k+1)) - people.at(cnt);
            cnt+=2;
            ans = max(ans,result);
        }
        cout <<ans << endl;
    }
}


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

typedef long long ll;


int main() {

    ios_base::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    string s;
    cin >> s;
    long long int q = 0;
    cin >> q;
    int temp_count = 1;
    string ans;
    deque<char> dq;
    for(int i = 0; i < s.size(); i++) {
        dq.push_back(s[i]);
    }
    while(q--) {
        int temp = 0;
        cin >> temp;
        if(temp == 1) {
            temp_count = !temp_count;
        }
        else {
            int f = 0;
            char to_insert;
            cin >> f;
            cin >> to_insert;
            if(f == 1) {
                if(temp_count) {
                    dq.push_front(to_insert);
                }
                else {
                    dq.push_back(to_insert);
                }
            }
            else {
                if(temp_count) {
                    dq.push_back(to_insert);
                }
                else {
                    dq.push_front(to_insert);
                }
            }
        }
    }

    deque<char>::iterator itr;
    if(temp_count) {
        for(itr = dq.begin(); itr != dq.end(); itr++) {
            cout << *itr;
        }
    }
    else {
        reverse(dq.begin(), dq.end());
        for(itr = dq.begin(); itr != dq.end(); itr++) {
            cout << *itr;
        }
    }


    return 0;
}


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

int main() {
  int n;
  cin >> n;
  vector<ll> p(n), q(n);
  string pstr, qstr;
  ll p_ind, q_ind = 0;
  rep(i, n) cin >> p[i];
  rep(i, n) cin >> q[i];
  vector<ll> tmp(n);
  for(int i=1; i<=n; i++) tmp[i-1] = i;
  ll count = 0;
  do {
    if (tmp == p) p_ind = count;
    if (tmp == q) q_ind = count;
    count++;
  } while (next_permutation(tmp.begin(), tmp.end()));
  cout << abs(p_ind - q_ind) << endl;
  return 0;
}

Measured memory_bytes: 256
INF = float('inf')

n, k = map(int, raw_input().strip().split())
h = map(int, raw_input().strip().split())
for i in xrange(k): h.append(INF)

dp = [INF for i in xrange(n + k)]
dp[n - 1] = 0

for i in xrange(n - 2, -1, -1):
    for j in xrange(k):
        dp[i] = min(dp[i], abs(h[i + j + 1] - h[i]) + dp[i + j + 1])

print dp[0]

Measured memory_bytes: 42348
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

L = INT()

print(L**3/27)

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

#define rep(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

signed main() {
    ll N,K,ans=0;
    cin>>N>>K;
    rep(b,1,N+1){
        ll p = N/b;
        ll r = N-p*b;
        ans += p * max((ll)0, b-K);
        ans += max((ll)0,r-K+(ll)1);

        if (0 == K)
            ans--;
    }
    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using namespace std;

template<class T>
constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

int main() {
    int n, k;
    cin >> n >> k;
    int m = (n+1)/2;
    cout << (k <= m ? "YES" : "NO")  << "\n";
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define rrep(i, a, b) for (int i = (a); i < (b); ++i)
#define PI acos(-1)
#define pcnt __builtin_popcountll
#define rng(a) a.begin(), a.end()
#define rrng(a) a.rbegin(), a.rend()
#define sz(x) (int)(x).size()
#define v(T) vector<T>
#define vv(T) v(v(T))
#define fi first
#define se second

using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using LP = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using tl = tuple<ll, ll, ll>;

template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) {if (a > b) { a = b; return true; } return false; }

ll INF = 1001001001;
ll LINF = 1001001001001001001ll;

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

    clock_t start = clock();

    ll d; cin>>d;
    vl cs(26); cin>>cs;
    vvl ss(d, vl(26)); cin>>ss;

    std::random_device rnd;
    std::mt19937 mt(rnd());
    std::uniform_int_distribution<> rd(0, d - 1);
    std::uniform_int_distribution<> rq(0, 25);

    ll ans = 0;
    vl last(26);
    rep(i, 26) last[i] = -1;
    vl ts(d);
    rep(i, d) {
        ll m = -LINF;
        ll mi = 0;
        rep(j, 26) {
            ll temp = ans + ss[i][j];
            vl tlast(26);
            copy(rng(last), tlast.begin());
            last[j] = i;
            rep(k, 26) {
                temp -= cs[k] * (i - last[k]);
            }
            if (temp > m) {
                m = temp;
                mi = j;
            }
            else swap(last, tlast);
        }
        ans = m;
        ts[i] = mi;
    }

    clock_t end = clock();
    while (static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000.0 < 1900.0) {
        ll e = rd(mt);
        ll q = rq(mt);
        while (ts[e] == q) {
            e = rd(mt);
            q = rq(mt);
        }
        ll temp = 0;
        ll p = ts[e];
        ts[e] = q;
        vl tlast(26);
        copy(rng(last), tlast.begin());
        rep(i, d) {
            temp += ss[i][ts[i]];
            last[ts[i]] = i;
            rep(j, 26) {
                temp -= cs[j] * (i - last[j]);
            }
        }
        if (temp < ans) {
            ts[e] = p;
            swap(last, tlast);
        }
        else ans = temp;
        end = clock();
    }
    rep(i, d) cout<<ts[i] + 1<<endl;
}

Measured memory_bytes: 3784
using System;
using System.Collections.Generic;
using static Assistant.Input;
using static Assistant.Debug;
using System.Linq;
using Assistant;

namespace ABC085A
{
    class Program
    {
        static void Main(string[] args)
        {
            var S = Console.ReadLine();

            string ans = "2018/01/" + S.Substring(8, 2);

            Console.WriteLine(ans);
        }


    }


}

namespace Assistant
{
    static class Input
    {
        static List<string> line = new List<string>();
        static int index = 0;
        static String ReadNext()
        {
            if (line.Count <= index) line.AddRange(Console.ReadLine().Split());
            return line[index++];
        }
        public static int ReadInt => int.Parse(ReadNext());
        public static long ReadLong => long.Parse(ReadNext());
        public static int[] ReadInts => Console.ReadLine().Split().Select(int.Parse).ToArray();
        public static long[] ReadLongs => Console.ReadLine().Split().Select(long.Parse).ToArray();
    }

    static class Debug
    {
        static public void Draw2D(int[,] map, int mode = 1)
        {
#if DEBUG
            int W = map.GetLength(0);
            int H = map.GetLength(1);

            int[,] map2 = new int[W + 1, H + 1];
            for (int i = 0; i < W + 1; i++)
            {
                for (int j = 0; j < H + 1; j++)
                {
                    if (i == 0 && j == 0) map2[i, j] = 0;
                    else if (i == 0) map2[i, j] = j - 1;
                    else if (j == 0) map2[i, j] = i - 1;
                    else map2[i, j] = map[i - 1, j - 1];
                }
            }

            for (int i = 0; i < W + 1; i++)
            {
                for (int j = 0; j < H + 1; j++)
                {
                    if (mode == 0) Console.Write(map2[i, j] % 10);
                    if (mode == 1) Console.Write(map2[i, j] + " ");
                }
                Console.WriteLine();
            }
            Console.WriteLine();
#endif
        }

        public static void Draw1D(int[] array, int mode = 0)
        {
#if DEBUG
            Console.WriteLine(string.Join(" ", array));
#endif
        }
    }
}


Measured memory_bytes: 11092
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
#include <utility>
using namespace std;
typedef long long LL;

int main()
{
	int X, N;
	cin >> N >> X;

	vector<int> arr(N);
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	sort(arr.begin(), arr.end());

	int cnt = 0;
	for (int i = 0; i < N; i++) {
		X -= arr[i];
		if (X < 0)
			break;
		cnt++;
	}

	if (X > 0) {
		cnt += X / arr[0];
	}

	cout << cnt << endl;


	return 0;
}

Measured memory_bytes: 256
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import Counter

n = ni()
s = ns()

MOD = 10**9+7

cnt = Counter(s)
ans = 1

for key, val in cnt.items():
    ans *= (val+1)
    ans %= MOD
    
ans -= 1
if ans < 0:
    ans += MOD
    
print(ans)

Measured memory_bytes: 3956
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 1000000;
int A[MAXN + 5], F[MAXN + 5];
ll B[MAXN + 5];
int N; ll K;
bool check(ll x) {
	for(int i=1;i<=N;i++)
		B[i] = x / F[i];
	ll r = 0;
	for(int i=1;i<=N;i++)
		r += max(0ll, A[N - i + 1] - B[i]);
	return r <= K;
}
int main() {
	scanf("%d%lld", &N, &K);
	for(int i=1;i<=N;i++)
		scanf("%d", &A[i]);
	sort(A + 1, A + N + 1);
	for(int i=1;i<=N;i++)
		scanf("%d", &F[i]);
	sort(F + 1, F + N + 1);
	ll le = 0, ri = ll(1E12);
	while( le < ri ) {
		ll mid = (le + ri) >> 1;
		if( check(mid) ) ri = mid;
		else le = mid + 1;
	}
	printf("%lld\n", le);
}

Measured memory_bytes: 9856
def solve(string):
    n, k = map(int, string.split("\n")[0].split(" "))
    ins = list(map(int, string.split("\n")[1:]))
    ins.sort()
    return str(min([ins[i + k - 1] - ins[i] for i in range(len(ins) - k + 1)]))


if __name__ == '__main__':
    n, k = map(int, input().split(" "))
    ins = [input() for _ in range(n)]
    print(solve("{} {}\n{}".format(n, k, "\n".join(ins))))


Measured memory_bytes: 22292
function Main(input){
    input = input.split("\n");
    var n = parseInt(input[0],10);
    input[1] = input[1].split(" ");
    var h = new Array(n + 1);

    for(var i = 0;i < n;i++){
        h[i + 1] = parseInt(input[1][i],10);
    }

    for(var i = 1;i <= n;i++){
        var ans = "node " + i + ": key = " + h[i] + ", ";
        if(i > 1)
            ans += "parent key = " + h[Math.floor(i / 2)] + ", ";
        if(i * 2 <= n)
            ans += "left key = " + h[i * 2] + ", ";
        if(i * 2 + 1 <= n)
            ans += "right key = " + h[i * 2 + 1] + ", ";
        console.log(ans);
    }
}
 
Main(require("fs").readFileSync("/dev/stdin","utf8"));

Measured memory_bytes: 17016
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
typedef pair<int,int> pii;
const int NSIZ=1000010;
const int MSIZ=1000010;
const int mxint=-1u/2;
int n, m, o, re=0;
int a[NSIZ], b[NSIZ];
bool chk[NSIZ];
int main(){
	int i, j, k, l;
	scanf("%d %d", &n, &m);
	for(i=0; i<n; i++){
		scanf("%d", &a[i]);
	}
	for(i=1; i<n; i++){
		if(a[i]+a[i-1]>=m)break;
	}
	if(i==n){
		printf("Impossible\n");
		return 0;
	}
	printf("Possible\n");
	for(j=n-1; j>i; j--){
		printf("%d\n", j);
	}
	for(j=1; j<i; j++){
		printf("%d\n", j);
	}
	printf("%d\n", i);
	return 0;
}

Measured memory_bytes: 1152
// Insertion Sort
#include <stdio.h>
static const int N = 1000;

void trace(int A[], int n) {
	int i;
	for (i = 1; i <= n; i++) {
		if (i > 1) printf(" ");
		printf("%d", A[i]);
	}
	printf("\n");
}

int main(void) {
	int n, i, j, tmp;
	int A[N + 1];
	scanf("%d", &n);

	for (i = 1; i <= n; i++) {
		scanf("%d", &A[i]);
	}
	trace(A, n);

	for (j = 2; j <= n; j++) {
		int key = A[j];
		i = j - 1;
		while (i > 0 && A[i] > key) {
			tmp = A[i + 1];
			A[i + 1] = A[i];
			A[i] = tmp;
			i--;
			A[i + 1] = key;
		}
		trace(A, n);
	}

	return 0;
}

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

using namespace std;

int main(int argc, char const *argv[]) {
  int N, M, X;
  cin >> N >> M >> X;
  vector<int> A(M);
  for (int i = 0; i < M; i++) {
    cin >> A[i];
  }
  int to0 = 0;
  int toN = 0;

  for (int i = 0; i < M; i++) {
    if (A[i] < X) {
      to0++;
    } else {
      toN++;
    }
  }

  int min = to0 < toN ? to0 : toN;
  cout << min << "\n";
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int main() 
{
 int n,x,t;
 cin>>n>>x>>t;
 if(n%x==0)
 cout<<(n/x)*t<<endl;
 else
 cout<<(n/x+1)*t<<endl;
    
}


Measured memory_bytes: 3588
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"

using namespace std;

const long long int MOD = 1000000007;

long long int N, M, K, H, W, L, R;

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

	cin >> N >> K;
	map<int, int>m;
	for (int i = 0; i < N; i++) {
		cin >> M;
		m[M]++;
	}
	vector<int>v;
	for (auto i : m) {
		v.push_back(i.second);
	}
	sort(v.begin(), v.end());
	if (v.size() <= K) {
		cout << 0 << endl;
		return 0;
	}
	reverse(v.begin(), v.end());
	int ans = 0;
	for (int i = 0; i < K; i++) {
		ans += v[i];
	}
	cout << N - ans << endl;
	return 0;
}

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

bool solve();
long long gcd(long long, long long);

int main()
{
    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; i++)
    {
        if (solve()) printf("Yes\n");
        else printf("No\n");
    }

    return 0;
}

bool solve()
{
    long long a, b, c, d;
    scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
    if (a < b || d < b) return false;
    if (c >= b) return true;
    
    a %= b;
    if (a > c) return false;
    if (d % b == 0) return true;
    d %= b;
    if (c + d < b) return false;

    const long long min_delta{gcd(d, b)};
    if ((b - 1 - a) / min_delta * min_delta + a > c) return false;
    else return true;
}

long long gcd(long long a, long long b)
{
    while (a)
    {
        b %= a;
        std::swap(a, b);
    }
    return b;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long   signed int LL;
typedef long long unsigned int LU;
#define incII(i, l, r) for(int i = (l)    ; i <= (r); ++i)
#define incID(i, l, r) for(int i = (l)    ; i <  (r); ++i)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); --i)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec(i, n)  decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
template<typename T> bool setmin  (T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmax  (T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
LL mo(LL a, LL b) { assert(b > 0); a %= b; if(a < 0) { a += b; } return a; }
LL fl(LL a, LL b) { assert(b > 0); return (a > 0 ? a / b : (a - b + 1) / b); }
LL ce(LL a, LL b) { assert(b > 0); return (a < 0 ? a / b : (a + b - 1) / b); }
#define bit(b, i) (((b) >> (i)) & 1)
#define BC __builtin_popcountll
#define SC(T, v) static_cast<T>(v)
#define SI(v) SC(int, v.size())
#define SL(v) SC( LL, v.size())
#define RF(e, v) for(auto & e: v)
#define ei else if
#define UR assert(false)

// ---- ----

LL n, dp[104][4][4][4], MOD = 1e9 + 7;

bool eq(vector<int> v, string s) {
	bool f = true;
	inc(i, 4) { f &= (s[i] == '-' || v[i] == s[i] - '0'); }
	return f;
}

int main() {
	cin >> n;
	
	dp[0][3][3][3] = 1;
	inc(i, n + 3) {
		inc(a, 4) {
		inc(b, 4) {
		inc(c, 4) {
		inc(d, 4) {
			vector<int> v = { a, b, c, d };
			if(
				eq(v, "-012") ||
				eq(v, "-102") ||
				eq(v, "-021") ||
				eq(v, "0-12") ||
				eq(v, "01-2")
			) { continue; }
			
			(dp[i + 1][b][c][d] += dp[i][a][b][c]) %= MOD;
		}
		}
		}
		}
	}
	
	cout << dp[n + 3][3][3][3] << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    long long N, K;
    long long i;
    long long cnt = 0;

    cin >> N >> K;
    vector<int>H(N);

    for (i = 0; i < N; i++){
      cin >> H.at(i);
    }

    sort(H.begin(), H.end());

    if (N <= K){
      cout << 0 << endl;
    } else {
      for (i = 0; i < N - K; i++){
         cnt += H.at(i);
      }
      cout << cnt << endl;
    }
}

Measured memory_bytes: 1024
#include <stdio.h>
int main(void) {
	char cards[52] = {0}, s;
	char suits['S'+1] = {['S']=13*0, ['H']=13*1, ['C']=13*2, ['D']=13*3};
	int i, n;

	scanf("%d ", &n);
	while (n--) {
		scanf("%c %d ", &s, &i);
		cards[suits[(int)s] + i - 1] = 1;
	}
	for (i = 0; i < 52; i++) {
		if (!cards[i]) {
			printf("%c %d\n", "SHCD"[i/13], i % 13 + 1);
		}
	}
	return 0;
}

Measured memory_bytes: 600
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <numeric>
#include <cmath>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <complex>
#include <string.h>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <iomanip>
#include <sys/time.h>
#include <tuple>
#include <random>
using namespace std;

#define endl '\n'
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end())

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef complex<double> comp;
typedef vector< vector<ld> > matrix;
struct pairhash {
public:
    template<typename T, typename U>
    size_t operator()(const pair<T, U> &x) const {
	size_t seed = hash<T>()(x.first);
	return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }
};
const int inf = 1e9 + 9;
const ll mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = acos(-1);

int n;
int a[100100];
vector<int> b[100100];

int calc(int k) {
    int l = b[k].size();
    if (l == 0) return 0;
    int c[l];
    for (int i = 0; i < l; i++) c[i] = calc(b[k][i]);
    sort(c, c+l);
    int res = 0;
    for (int i = 0; i < l; i++) res = max(res, c[i]+l-i);
    return res;
}

int solve() {
    for (int i = 1; i < n; i++) {
        b[a[i]].push_back(i);
    }
    return calc(0);
}

void input() {
    cin >> n;
    int v;
    for (int i = 1; i < n; i++) {
        cin >> v;
        a[i] = v-1;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);

    input();
    cout << solve() << endl;
}


Measured memory_bytes: 15488
#include <iostream>
#include <cmath>

using namespace std;

char dna[4]={'A','T','C','G'};

int main () {
	string s;
	cin>>s;
	int br=0;
	int tr;
	int sol=0;
	for(int i=0;i<s.length();i++){
		tr=0;
		for(int j=0;j<4;j++){
			if(s[i]==dna[j]){
				tr=1;
				break;
			}
		}
		if(tr) br++;
		else br=0;
		if(br>sol) sol=br;
	}
	cout<<sol;



return 0;
}



Measured memory_bytes: 256
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define reps(i,a,b) for(int i=a;i<b;++i)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
template<typename T> inline bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T> inline bool chmin(T &a,T b){if(b<a){a=b;return 1;}return 0;}
template<typename T> vector<T> make_vec(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_vec(size_t a,Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a,make_vec<T>(ts...));}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T,U>::value>::type fill_v(U &u,const V... v){u=U(v...);}
template<typename T,typename U,typename... V>
typename enable_if<!is_same<T,U>::value>::type fill_v(U &u,const V... v){for(auto &e:u)fill_v<T>(e,v...);}

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

    int h, w;
    while (cin >> h >> w, h != 0) {
        rep(i, h) {
            rep(j, w) {
                if ((i+j) % 2 == 0) cout << '#';
                else cout << '.';
            }
            cout << endl;
        }
        cout << endl;
    }
}



Measured memory_bytes: 3164
#include<bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(int i=a;i<=(b);++i)
#define F2(i,a,b) for(int i=a;i<(b);++i)
#define dF(i,a,b) for(int i=a;i>=(b);--i)
#define MN 305
#define MM 90000
#define mod 998244353
#define inv2 499122177
int n,ans=1,p2=1,s;
int a[MN],f[MM+5],g[MM+5];
int main(){
	scanf("%d",&n);
	F(i,1,n)scanf("%d",a+i),s+=a[i],p2=2ll*p2%mod;
	f[0]=1,g[0]=p2;
	F(i,1,n)dF(j,s,0)f[j]=(f[j]+(j>=a[i]?f[j-a[i]]:0))%mod,g[j]=(g[j]+(j>=a[i]?1ll*g[j-a[i]]*inv2%mod:0))%mod;
	F(i,1,n)ans=3ll*ans%mod;
	F(j,0,s){
		if(j+j>=s)ans=(ans-3ll*g[j])%mod;
		if(j+j==s)ans=(ans+3ll*f[j])%mod;
	}
	printf("%d\n",(ans+mod)%mod);
	return 0;
}

Measured memory_bytes: 896
#include <stdio.h>
#include <math.h>
 
int main()
{
    int dice[7]={},cpy[7]={},i;
   
    for(i=1;i<=7;i++)
        scanf("%d",&dice[i]);
        
     
        char str[1000];
        scanf("%s",str);
        int n;
        n=strlen(str);
        int cnt=0;
     
     
    
     
    while(cnt<n){
        char a;
        for(i=1;i<=7;i++)
            cpy[i]=dice[i];
         
        if(str[cnt]=='E')
        {
            dice[1]=cpy[4];
            dice[2]=cpy[2];
            dice[3]=cpy[1];
            dice[4]=cpy[6];
            dice[5]=cpy[5];
            dice[6]=cpy[3];
        }
        if(str[cnt]=='W')
        {
            dice[1]=cpy[3];
            dice[2]=cpy[2];
            dice[3]=cpy[6];
            dice[4]=cpy[1];
            dice[5]=cpy[5];
            dice[6]=cpy[4];
        }if(str[cnt]=='S')
        {
            dice[1]=cpy[5];
            dice[2]=cpy[1];
            dice[3]=cpy[3];
            dice[4]=cpy[4];
            dice[5]=cpy[6];
            dice[6]=cpy[2];
        }if(str[cnt]=='N')
        {
            dice[1]=cpy[2];
            dice[2]=cpy[6];
            dice[3]=cpy[3];
            dice[4]=cpy[4];
            dice[5]=cpy[1];
            dice[6]=cpy[5];
        }
        cnt++;
    }
     
    printf("%d\n",dice[1]);
}


Measured memory_bytes: 2088
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
using ll = long long;
using namespace std;
int main()
{
    int n;
    cin >> n;
    int a[n];
    REP(i, n) cin >> a[i];
    deque<int> q;
    REP(i, n) {
        if (i % 2 == 0) {
            q.push_back(a[i]);
        } else {
            q.push_front(a[i]);
        }
    }
    if (n % 2 == 1) {
        REP(i, n - 1) cout << q[n - i - 1] << " ";
        cout << q[0] << endl;
    } else {
        REP(i, n - 1) cout << q[i] << " ";
        cout << q[n - 1] << endl;
    }
}


Measured memory_bytes: 3840
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
using namespace std;

int main()
{
    long long int n,times=1;
    int route[8]={0,1,2,3,4,5,6,7};
    double ans=0.0,temp=0.0;
    cin>>n;
    vector<pair<int,int>> mura;
    for(int i=2;i<=n;i++)
        times*=i;
    for(int i = 0;i<n;i++)
    {
        pair<int,int> tmp;
        cin>>tmp.first>>tmp.second;
        //cout<<tmp.first<<tmp.second;
        mura.push_back(tmp);
    }
    /*for(int i=0;i<n;i++)
        cout<<route[i]<<" ";
    cout<<endl;*/
    for(int i=1;i<n;i++)
        temp+=(sqrt((mura[route[i]].first-mura[route[i-1]].first)*(mura[route[i]].first-mura[route[i-1]].first)+(mura[route[i]].second-mura[route[i-1]].second)*(mura[route[i]].second-mura[route[i-1]].second) ));
    while(next_permutation(route,route+n))
    {
        /*for(int i=0;i<n;i++)
            cout<<route[i]<<" ";
        cout<<endl;*/
        for(int i=1;i<n;i++)
            temp+=(sqrt((mura[route[i]].first-mura[route[i-1]].first)*(mura[route[i]].first-mura[route[i-1]].first)+(mura[route[i]].second-mura[route[i-1]].second)*(mura[route[i]].second-mura[route[i-1]].second) ));
    }
    ans= temp/times;
    printf("%.10f\n",ans);
    return 0;
}


Measured memory_bytes: 256
# include "bits/stdc++.h"
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const double PI = acos(-1);
template<class T>constexpr T INF() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T HINF() { return INF<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { -1,0,1,0 }, dy[4] = { 0,-1,0,1 };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
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; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        (wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define REP(i,upupu)         FOR(i,0,upupu)
# define INIT                 std::ios::sync_with_stdio(false);std::cin.tie(0)
# pragma warning(disable:4996)

int n, m;
int a[1010];

int main() {
	while (cin >> n >> m&&n&&m) {
		REP(i, n)cin >> a[i];
		int ret = 0;
		REP(i, n)REP(j, n) {
			if (i == j)continue;
			if (a[i] + a[j] <= m)ret = max(a[i] + a[j], ret);
		}
		if (ret == 0) {
			cout << "NONE" << endl;
		}
		else {
			cout << ret << endl;
		}
	}
}


Measured memory_bytes: 3044
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <random>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
#define repl(i,n) for (long long i = 0; i < (n); ++i)
#define reppl(i,n,m) for (long long i = m; i < (n); ++i)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PL = pair<long long, long long>;
using Pxy = pair<double, double>;
using T = tuple<int, int, bool>;
const int INF = 1001001007;
const int mod = 1000000007;
const int MOD = 998244353;
const ll inf = 1e18;
template <typename AT>
void printvec(vector<AT> &ar){
    rep(i,ar.size()-1) cout << ar[i] << " ";
    cout << ar[ar.size()-1] << endl;
}
template <typename Q>
void printvvec(vector<vector<Q>> &ar){
    rep(i,ar.size()){
        rep(j,ar[0].size()-1) cout << ar[i][j] << " ";
        cout << ar[i][ar[0].size()-1] << endl;
    }
}
template <typename S>
bool range(S a, S b, S x){
    return (a <= x && x < b);
}

int main() {
    int n, m; cin >> n >> m;
    vector<PL> ar(n);
    rep(i,n) cin >> ar[i].first >> ar[i].second;
    sort(ar.begin(),ar.end());
    ll ans = 0;
    rep(i,n){
        if (ar[i].second >= m){
            ans += ar[i].first * m;
            break;
        }
        else {
            ans += ar[i].first * ar[i].second;
            m -= ar[i].second;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 4740
import java.util.Scanner;

class Main{
        public static void main(String[] args){
                Scanner scn=new Scanner(System.in);
                int i=(new Integer(scn.nextInt())).toString().indexOf("9");
                if(i==-1){
                        System.out.println("No");
                }else{
                        System.out.println("Yes");
                }
        }
}

Measured memory_bytes: 21460
package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	wfp := os.Stdout

	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
		if len(os.Args) > 2 {
			wfp, _ = os.Create(os.Args[2])
		}
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)

	n := getNextInt(scanner)
	k := getNextInt(scanner)

	aa := make([]int64, n)
	sum := make([]int64, n+1)
	bb := make([]int64, n*(n+1)/2)
	for i := 0; i < n; i++ {
		aa[i] = getNextInt64(scanner)
		sum[i+1] = sum[i] + aa[i]
	}

	bi := 0
	for i := 0; i < n; i++ {
		for ii := i + 1; ii < n+1; ii++ {
			bb[bi] = sum[ii] - sum[i]
			bi++
		}
	}

	for b := 60; b >= 0; b-- {
		j := 0
		for i := 0; i < bi; i++ {
			if bb[i]>>uint(b)&1 == 1 {
				bb[i], bb[j] = bb[j], bb[i]
				j++
			}
		}
		if j >= k {
			bi = j
		}
	}

	var ans int64
	ans = 1<<60 - 1
	for i := 0; i < k; i++ {
		ans &= bb[i]
	}

	fmt.Fprintln(writer, ans)

	writer.Flush()
}


Measured memory_bytes: 4736
def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations
    #from itertools import accumulate, product, permutations
    from math import floor, ceil

    #mod = 1000000007

    x,y,z = map(int, input().split())
    print((x-z)//(y+z))
        

if __name__ == '__main__':
    main()

Measured memory_bytes: 3316
#include<stdio.h>
using namespace std;

double N,D,M;

int main()
{
    scanf("%lf%lf%lf",&N,&M,&D);

    double ans = 0;
    if(D == 0)ans = N * (M - 1) / N / N;
    else ans = 2 * (N - D) * (M - 1) / N / N;
    printf("%.10lf\n",ans);
}


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

using namespace std;
int main(){
cin.tie(NULL);
ios::sync_with_stdio(false);
 int n,a[256],anss=0,j,i,ans[256]={};
 cin>>n;
 for(i=0;i<n;i++){
   cin>>a[i];
   ans[a[i]]+=a[i];
 }
 for(j=0;j<101;j++){
   if(ans[j]>0){
     anss+=1;
   }
 }
 cout<<anss<<"\n";

 return 0;
}


Measured memory_bytes: 256
using System;
class Program{
	static void Main(){
		int[] s=Array.ConvertAll(Console.ReadLine().Split(),int.Parse);
		int[,] dp=new int[s[0]+1,s[0]+1];
		int[][] arr=new int[s[1]][];
		int ans=0;

		for(int i=1;i<=s[0];i++){
			for(int j=1;j<=s[0];j++){
				if(i!=j){dp[i,j]=int.MaxValue/2;}
			}
		}
		for(int i=0;i<s[1];i++){
			arr[i]=Array.ConvertAll(Console.ReadLine().Split(),int.Parse);
			dp[arr[i][0],arr[i][1]]=arr[i][2];
			dp[arr[i][1],arr[i][0]]=arr[i][2];
		}
		for(int i=1;i<=s[0];i++){
			for(int j=1;j<=s[0];j++){
				for(int k=1;k<=s[0];k++){
					dp[j,k]=Math.Min(dp[j,k],dp[j,i]+dp[i,k]);
				}
			}
		}
		for(int i=0;i<s[1];i++){
			if(dp[arr[i][0],arr[i][1]]<arr[i][2]){ans++;}
		}
		Console.WriteLine(ans);
	}
}

Measured memory_bytes: 13352
// これは嘘解法です！！

#include <bits/stdc++.h>
using namespace std;
#define inc(i, n) for(int i = 0; i < (n); i++)

int n, m;
vector<int> g[1000];
bool vis[1000];

bool dfs(int v, int s) {
	if(vis[v]) { return false; }
	vis[v] = true;
	for(auto & e: g[v]) {
		if(e == s || dfs(e, s)) { return true; }
	}
	return false;
}

bool f(int v) {
	inc(i, n) { vis[i] = false; }
	return dfs(v, v);
}

int main() {
	cin >> n >> m;
	inc(i, m) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].push_back(b);
	}
	
	bool ans = false;
	inc(i, n) { ans |= f(i); }
	
	cout << (ans ? 0 : -1) << endl;
	
	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define scanVec(vec , n) for(int i = 0; i < n ; i++){ cin>>vec[i];}
#define printVec(vec , n) for(int i = 0; i < n ; i++){ cout<<vec[i]<<" ";}
#define S second
#define F first
const int  MOD = 1e9 + 7;
const int  N = 3005; 
string s;
ll n , dp[N][N] , sum[N][N];

//  a d f j k  l  ;
int main(){
    ios::sync_with_stdio(0);  cin.tie(0);
    cin>>n>>s;
    dp[1][1] = 1;
	sum[1][1] = 1;
	for(ll i = 2; i <= n; i++){
		for(ll j = 1; j <= i;j++){
			if(s[i-2] == '<'){
				dp[i][j] = sum[i-1][j-1];
			}else{
				dp[i][j] = ( (sum[i-1][i-1]-sum[i-1][j-1]) % MOD + MOD ) %MOD;
			}
			sum[i][j] = (sum[i][j-1] + dp[i][j]) % MOD;
		}
	}
	cout<<sum[n][n]<<endl;
    return 0;
}

Measured memory_bytes: 139648
using System;
using System.Collections.Generic;
using System.Linq;

namespace B___ATCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ');
            var n = int.Parse(input[0]);
            var t = int.Parse(input[1]);
            var a = new List<int>();
            for(var i=0; i<n; i++)
            {
                var input1 = Console.ReadLine().Split();
                var b = int.Parse(input1[1]);
                var c = int.Parse(input1[0]);
                if (t >= b)
                {
                    a.Add(c);
                }
            }
            if (a.Count() == 0)
            {
                Console.WriteLine("TLE");
            }
            else
            {
                Console.WriteLine(a.Min());
            }
        }
    }
}

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

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

    for (int i = 0; i < n; i++) {
        int tmp; cin >> tmp;
        h -= tmp;
    }

    if (h <= 0) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

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

typedef long long ll;
typedef pair<int,int> pp;
const int INF = 1e9;
const int MOD = 1000000007;
const double pi = 3.141592653589793238;

ll gcd(ll a, ll b) { return __gcd(a,b); } //最大公約数
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; } //最大公倍数

void printV(vector<int> &v);
void printVV(vector<vector<int>> &vv);


int main() {
  string S, T = "";
  cin >> S;

  reverse(S.begin(), S.end());

  const string dream  = "maerd";
  const string dreamer = "remaerd";
  const string erase  = "esare";
  const string eraser = "resare";

  int pos = 0;
  const int size = S.size();
  while(S != T) {
    // cout << size - pos << endl; //
    if(size - pos > 6) {
      if(S.substr(pos, 7) == dreamer) {
        T = T + dreamer;
        pos += 7;
        continue;
      }
    }

    if(size - pos > 5) {
      if(S.substr(pos, 6) == eraser) {
        T = T + eraser;
        pos += 6;
        continue;
      }
    }

    if(size - pos > 4) {
      // cout << S.substr(pos, 5) << endl; //
      // cout << T << endl; //
      if(S.substr(pos, 5) == dream) {
        T = T + dream;
        pos += 5;
        continue;
      } else if(S.substr(pos, 5) == erase) {
        T = T + erase;
        pos += 5;
        continue;
      }
    }
    cout << "NO" << endl;
    return 0;
  }
  cout << "YES" << endl;

  return 0;
}


// ベクターの中身を全部出力
void printV(vector<int> &v) {
  cout << "  [ ";
  for(int i = 0; i < (int)v.size(); i++) {
    cout << v.at(i) << " ";
  }
  cout << "]" << endl;
}

void printVV(vector<vector<int>> &vv) {
  cout << "{" << endl;
  for(int i = 0; i < (int)vv.size(); i++) {
    cout << "  [ ";
    for(int j = 0; j < (int)vv.at(i).size(); j++) {
      cout << vv.at(i).at(j) << " ";
    }
    cout << "]," << endl;
  }
  cout << "}" << endl;
}


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


int main(){
   cin.tie(0);
   ios::sync_with_stdio(false);
   cout << fixed << setprecision(20);
   
   //int n,ans; cin >> n;
   string s,ans="Yes"; cin >> s;
   rep(i,0,s.size()){
   	if(i%2==0) {
   		if(s[i]=='L') ans="No";
   	}else{
   		if(s[i]=='R') ans="No";
   	}
   }
   

   //vector<int> a(n),b(n),c(n),d(n);

   cout << ans << endl;
}



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

#define rep(n) for(int i=0;i<n;i++)
#define repp(j, n) for(int j=0;j<n;j++)

using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> Pii;
struct edge{int from, to; ll cost;};

map<ll, ll> d;
priority_queue< Pll, vector<Pll>, greater<Pll> > que;
map<ll, vector<Pll> > edges;

void dijkstra(ll start){
    d[start] = 0;
    que.push(Pll(0, start));

    while(!que.empty()){
        Pll v = que.top(); que.pop();
        if(d.find(v.second) != d.end() && d[v.second] < v.first) continue;
        for(Pll e: edges[v.second]){
            if(d.find(e.first) == d.end() || d[e.first] > d[v.second] + e.second){
                d[e.first] = d[v.second] + e.second;
                que.push(Pll(d[e.first], e.first));
            }
        }
    }
}

int main(){
    std::ios::sync_with_stdio(0); cin.tie(0);
    int n;
    ll u, k, c, v;
    cin >> n;
    rep(n){
        cin >> u >> k;
        repp(j, k){
            cin >> v >> c;
            edges[u].emplace_back(v, c);
        }
    }

    dijkstra(0);
    repp(u, n) cout << u << " " << d[u] << endl;

}



Measured memory_bytes: 3260
N,P = map(int,input().split())
S = input()

if P in (2,5):
    ans = 0
    for i,c in enumerate(S):
        if int(c)%P==0:
            ans += i+1
    print(ans)
    exit()

a = [0]
r = 1
for c in S[::-1]:
    d = int(c)
    a.append((a[-1] + d*r) % P)
    r *= 10
    r %= P
from collections import Counter
ctr = Counter(a)
ans = 0
for v in ctr.values():
    ans += v*(v-1)//2
print(ans)

Measured memory_bytes: 12028