akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define rep(i,N) for(long long i = 0; i < (long long)(N); i++)
#define repr(i,N) for(long long i = (long long)(N) - 1; i >= 0; i--)
#define rep1(i,N) for(long long i = 1; i <= (long long)(N) ; i++)
#define repr1(i,N) for(long long i = (N) ; (long long)(i) > 0 ; i--)
#define each(x,v) for(auto& x : v)
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) long long __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
using namespace std; void solve();
using ll = long long; template<class T = ll> using V = vector<T>;
using vi = V<int>; using vl = V<>; using vvi = V< V<int> >;
constexpr int inf = 1001001001; constexpr ll infLL = (1LL << 61) - 1;
struct IoSetupNya {IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7);} } iosetupnya;
template<typename T, typename U> inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; }
template<typename T, typename U> inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; }
template<typename T, typename U> ostream& operator <<(ostream& os, const pair<T, U> &p) { os << p.first << " " << p.second; return os; }
template<typename T, typename U> istream& operator >>(istream& is, pair<T, U> &p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator <<(ostream& os, const vector<T> &v) { int s = (int)v.size(); rep(i,s) os << (i ? " " : "") << v[i]; return os; }
template<typename T> istream& operator >>(istream& is, vector<T> &v) { for(auto &x : v) is >> x; return is; }
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
template<typename T>void die(T x){out(x); exit(0);}
#ifdef NyaanDebug
  #include "NyaanDebug.h"
  #define trc(...) do { cerr << #__VA_ARGS__ << " = "; dbg_out(__VA_ARGS__);} while(0)
  #define trca(v,N) do { cerr << #v << " = "; array_out(v , N);cout << endl;} while(0)
#else
  #define trc(...)
  #define trca(...)
  int main(){solve();}
#endif

#define in2(N,s,t) rep(i,N){in(s[i] , t[i]);}
#define in3(N,s,t,u) rep(i,N){in(s[i] , t[i] , u[i]);}
using vd = V<double>; using vs = V<string>; using vvl = V< V<> >;
template<typename T>using heap = priority_queue< T , V<T> , greater<T> >;

using P = pair<int,int>; using vp = V<P>;
constexpr int MOD = /** 1000000007; //*/ 998244353;
//////////////////

void solve(){
  inl(x , y);
  if(abs(x) == abs(y)){
    die(x == y ? 0 : 1);
  }
  else if(abs(x) < abs(y)){
    ll ans = 0;
    if(x < 0) {ans++; x = -x;}
    ans += abs(y) - x; x = abs(y);
    die(ans + !(x == y));
  }
  else{
    ll ans = 0;
    if(x > 0) {ans++; x = -x;}
    ans += abs(x) - abs(y); x = -abs(y);
    die(ans += !(x == y));
  }
}

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



int main(void){
  int n;
  cin >> n;
  int cnt = 0;
  int a = n;
  while (a > 0) {
    int s = a % 10;
    cnt += s;
    a /= 10;
  }
  
  if (n % cnt == 0)  cout << "Yes" << endl;
  else cout << "No" << endl;
  
}


Measured memory_bytes: 3568
import itertools
import numpy as np
n, m = map(int, input().split())
switch_comb = itertools.product((0, 1), repeat=n)
switch_arr = np.array(list(switch_comb))
res = 0
light_list = []
for i in range(m):
  s_list = list(map(int, input().split()))[1:]
  s_list = [i - 1 for i in s_list]
  light_list.append(s_list)
print()
flg_list = list(map(int, input().split()))
for j, l in enumerate(light_list):
  ans = flg_list[j]
  switch_arr = switch_arr[(switch_arr[:, l].sum(axis=1) % 2) == ans, :]
  if switch_arr.shape[0] == 0:
    break
print(switch_arr.shape[0])

Measured memory_bytes: 21460
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
ll x;
ll f(ll n){//n以下の,xの倍数の個数
    if(n==-1) return 0;
    if(n%x==0) return n/x+1;
    else{
        ll min1 = x*(n/x);
        return min1/x+1;
    }
}
int main(){
    ll a,b;
    cin>>a>>b>>x;
    //cout<<f(b)<<" "<<f(a-1)<<endl;
    cout<<f(b)-f(a-1)<<endl;
    return 0;
}

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

using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++) 
#define REP(i, n) for (int i = 0; i < (n); i++)

typedef long long ll;
int main(int argc, char const *argv[])
{
    string S; cin >> S;
    ll K; cin >> K;
    char ans = '1';
    int f = (K > S.size()) ? S.size() : K;
    REP(i, f){
        if (S[i] != '1') {
            ans = S[i];
            break;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
require 'prime'
def ans(x, y)
  case
  when x < y then
    'abundant number'
  when x == y then
    'perfect number'
  when x > y then
    'deficient number'
  end
end
def solve(x)
  return if x == 0
  sum = Prime.prime_division(x).inject(1) {|sum, a| (sum * ((a[0] ** (a[1] + 1)) - 1)) / (a[0] - 1) } - x
  puts ans(x, sum)
end
$stdin.read.split("\n").map(&:to_i).each(&method(:solve))

Measured memory_bytes: 8852
#include <bits/stdc++.h>
using namespace std;
using ll  = long long;
using vl  = vector<ll>;

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rng(i,a,b) for(int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()

int main() {
    ll N, K; cin >> N >> K;
    vl A(N);
    rep(i,N) cin >> A[i];
    sort(all(A));

    ll ng = 2e18, ok = -ng;
    while (ng - ok > 1) {
        ll x = (ok + ng) / 2, cnt = 0;
        rep(i,N) {
            if (A[i] < 0) cnt += N - (upper_bound(all(A), (long double)x/A[i]) - A.begin());
            if (A[i] > 0) cnt += lower_bound(all(A), (long double)x/A[i]) - A.begin();
            if (A[i] == 0 and x > 0) cnt += N;
            if (A[i]*A[i] < x) cnt--;
        }
        (cnt/2 < K ? ok : ng) = x;
    }
    cout << ok << endl;
    return 0;
}


Measured memory_bytes: 1792
#include<stdio.h>
#include<stdlib.h>
struct node{
  int key;
  struct node *parent;
  struct node *right;
  struct node *left;
};
typedef struct node *Node;
Node T;
#define NIL NULL;
void Insert(int);
int Find(int);
void Preorder(Node);
void Inorder(Node);
int main()
{
  int n,i,key;
  char S[7];
  
  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf("%s",S);
    if(S[0]=='i'){
      scanf("%d",&key);
      Insert(key);
    }
    else if(S[0]=='f'){
      scanf("%d",&key);
      if(Find(key))printf("yes\n");
      else printf("no\n");
    }
    else{
      Inorder(T);
      printf("\n");
      Preorder(T);
      printf("\n");

    }
  }
  return 0;
}

void Insert(int key)
{
  Node y,x,z;
  y=NIL;
  x=T;
  z=malloc(sizeof(struct node));
  z->key=key;
  z->left=NIL;
  z->right=NIL;
  while(x!=NULL){
    y=x;
    if( z->key < x->key )x=x->left;
    else x=x->right;
  }
  z->parent=y;
  if(y==NULL){
    T=z;
  }
 else if(z->key<y->key){
      y->left=z;
  }
  else{
    y->right=z;
  }
}

int Find(int key)
{
  Node TT;
  TT=T;
  while(TT!=NULL && TT->key!=key){
    if(key<TT->key)TT=TT->left;
    else TT=TT->right;
  }
  if(TT==NULL)return 0;
  else return 1;
}
void Preorder(Node T)
{
  printf(" %d",T->key);
  if(T->left!=NULL){
    Preorder(T->left);
  }
  if(T->right!=NULL){
    Preorder(T->right);
  }

}

void Inorder(Node T)
{
  if(T->left!=NULL && T->right!=NULL){
    Inorder(T->left);
    printf(" %d",T->key);
    Inorder(T->right);

  }
  if(T->left!=NULL && T->right==NULL){
   Inorder(T->left);
     printf(" %d",T->key);
  }

  if(T->right!=NULL && T->left==NULL){
  printf(" %d",T->key);
 Inorder(T->right);

  }
  if(T->left==NULL && T->right==NULL)printf(" %d",T->key);

}



Measured memory_bytes: 20452
from collections import defaultdict
N, M = map(int, input().split())
done = set()
ac = defaultdict(int)
wa = defaultdict(int)
# ACを一回以上出した問題のみ
for _ in range(M):
    p, s = map(str, input().split())
    if s == "WA":
        if p not in done:
            wa[p] += 1
    elif s == "AC":
        if p not in done:
            ac[p] += 1
            done.add(p)

a = len(ac)
w = 0
for k, v in wa.items():
    if k in done:
        w += v

print(a, w)


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

int Rs = 200001;
VI C(Rs, 0);

int main(){
    int k,n;
    cin >> n >> k;
    rep(i,n){
        int a;
        cin >> a;
        C[a]++;
    }

    sort(C.begin(), C.end());
    int uniq = 0;
    rep(i,Rs){
        if(C[i] > 0) uniq++;
        // if(i < 100) cout << C[i] << " ";
    }
    int ans=0;
    int cnt = uniq - k;
    rep(i,Rs){
        if(cnt <= 0){
            break;
        }else if(C[i] > 0){
            ans += C[i];
            cnt--;
        }else{
            continue;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1024
N = int(input())
A = [int(x) for x in input().split()]
X = [0]*N
S = sum(A)
X[0] = S - 2*sum(A[1::2])

for i in range(1, N):
  X[i] = 2*A[i-1] - X[i-1]
print(' '.join(map(str,X)))

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

#define get(n) scanf("%d",&n)
using ll = long long;

const bool DEBUG = 1;

const int mxn = 1e6+3, mod = mxn;

int Q;
int n, x, d;

ll fac[mxn], inv[mxn];
ll invv[mxn];

ll modpow(ll a, ll b) {
	return b?modpow(a*a%mod,b/2)*(b&1?a:1)%mod:1;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
#ifdef LOCAL
	if (DEBUG) freopen("input.txt", "r", stdin);
	if (DEBUG) freopen("output.txt", "w", stdout);
	clock_t start = clock();
#endif

	// init
	for (int i = 0; i < mxn; i++)
		fac[i] = i?fac[i-1]*i%mod:1;
	inv[mxn-1] = modpow(fac[mxn-1],mod-2);
	for (int i = mxn - 2; i >= 0; i--)
		inv[i] = inv[i+1]*(i+1)%mod;	
	for (int i = 0; i < mxn; i++)
		invv[i] = modpow(i,mod-2);

	get(Q);
	stringstream ss;
	for (int q = 0; q < Q; q++) {
		get(x); get(d);	get(n);

		if (x==0) ss << 0 << endl;
		else if (d==0) ss << modpow(x,n) << endl;
		else {
			ll alpha = x*invv[d]%mod;
			ll ans = 0;
			if (alpha&&(alpha+n-1< mxn))
				ans = fac[alpha+n-1]*(alpha?inv[alpha-1]:1)%mod;
			if (ans) ans = ans*modpow(d%mod,n)%mod;
			ss << ans << endl;
		}
	}

	cout << ss.str();
	


#ifdef LOCAL
	cout << setprecision(12) << (long double)(clock()-start) / CLOCKS_PER_SEC << endl;
#endif
	return 0;
}


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

using namespace std;

int main(){
	
	string s;
	
	cin >> s;
	
	int win = 0;
	for (int i=0; i<s.length(); ++i){
		if (s[i] == 'o'){
			win++;
		}
	}
	
	if (win + (15 - (int)s.length()) >= 8){
		cout << "YES" << endl;
	}else{
		cout << "NO" <<endl;
	}
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int N;
    cin >> N;
    double up;
    if (N % 2 == 0)
    {
        up = N / 2.0;
    }
    else
    {
        up = N / 2 + 1.0;
    }
    cout << up / (double)N << endl;
    return 0;
}


Measured memory_bytes: 256
n,m=map(int,input().split())
def root(x):
	if x!=parent[x]:
		x=root(parent[x])
	return x
def same(x,y):
	return root(x)==root(y)
parent=list(range(n))
rank=[0]*n
def unite(x,y):
	rx=root(x)
	ry=root(y)
	if rank[rx]>rank[ry]:
		parent[ry]=rx
	else:
		parent[rx]=ry
		if rank[rx]==rank[ry]:
			rank[ry]+=1

for i in range(m):
	x,y,z=map(int,input().split())
	unite(x-1,y-1)
ans=set()
for i in range(n):
	ans.add(root(i))
print(len(ans))

Measured memory_bytes: 16620
N = int(input())
p = list(map(float, input().split()))

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

for i in range(N):
    for j in range(i + 1):
        dp[i + 1][j + 1] += dp[i][j] * p[i]
        dp[i + 1][j] += dp[i][j] * (1 - p[i])
ans = 0
for i in range(N // 2 + 1, N + 1):
    ans += dp[N][i]

print(ans)

Measured memory_bytes: 204448
#include <iostream>
#include <vector>
#define REP(i, n) for (int i = 0; i < (n); i++)
using namespace std;

void solve(long long N, std::vector<long long> V, std::vector<long long> C){
    int ans = 0;
    REP(i, N)
        if (V[i] - C[i] > 0) ans += V[i] - C[i];
    cout << ans << '\n';
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    long long N;
    scanf("%lld",&N);
    std::vector<long long> V(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&V[i]);
    }
    std::vector<long long> C(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&C[i]);
    }
    solve(N, std::move(V), std::move(C));
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n;
int main() {
    cin >> n;
    vector<vector<int>> a(2, vector<int>(n, 0));
    int dp[4][n+2];
    for(int i = 0; i < 2; ++i) {
        for(int j = 0; j < n; ++j) {
            cin >> a.at(i).at(j);
        }
    }

    for(int i = 0; i < 4; ++i) {
        for(int j = 0; j < n+2; ++j) {
            dp[i][j] = 0;
        }
    }

    dp[0][0] = a.at(0).at(0);

    for(int i = 1; i <= 2; ++i) {
        for(int j = 1; j <= n; ++j) {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + a.at(i-1).at(j-1);
        }
    }

    cout << dp[2][n] << endl;
}


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

int main(){
    int n,k;
    cin >> n >>k;
    double ans=0,winp=0;

    for(int i=1;i<=n;i++){
        for(int j=0;;j++){
            winp=i*pow(2.0,j);
            if(winp>=k){
                ans+=(1.0/n)*pow(0.5,j);
                break;
            }
        }
    }
    cout << fixed << setprecision(12) << ans <<endl;
}

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

string divide[4] ={"dream","dreamer","erase","eraser"};

int main(){
  string S;
  cin >> S;
  
  reverse(S.begin(),S.end());
  for(int i = 0;i < 4;i++){
    reverse(divide[i].begin(),divide[i].end());
  }
  
  bool can = true;
  for(int i = 0;i < S.size();){
    bool can2 = false;
    for(int j = 0;j < 4;j++){
      string d = divide[j];
      if(S.substr(i,d.size())  == d){
        can2 = true;
        i += d.size();
      }
    }
    if(!can2){
      can = false;
      break;
    }
  }
  
  if(can) cout << "YES" << endl;
  else cout << "NO" << endl;
}

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

int main(){
    string s;
    cin>>s;
    for (int i = 0; i < 3; ++i) {
        if(s[i]=='7'){
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 3620
N, M = map(int, input().split())

INF = 2 << 40
G, dist = [None for i in range(M)], [INF for j in range(N)]


class Edge:
    def __init__(self, f, t, cost):
        self.f = f
        self.t = t
        self.cost = cost


def bellman_ford(s):
    dist[s] = 0
    for i in range(2*N):
        for j in range(M):
            e = G[j]
            if dist[e.f] < INF and dist[e.f] + e.cost < dist[e.t]:
                dist[e.t] = dist[e.f] + e.cost

                if i >= N - 1 and (e.t == N - 1 or e.f == N - 1):
                    return True

    return False


def main():
    for i in range(M):
        a, b, c = map(int, input().split())
        G[i] = Edge(a-1, b-1, -c)

    c = bellman_ford(0)

    if c:
        print("inf")
    else:
        print(-dist[N-1])


if __name__ == '__main__':
    main()


Measured memory_bytes: 3572
#include <algorithm>
#include <cassert>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;

template <typename T> inline constexpr bool chmin(T &a, T b) {
  if (b < a) {
    a = b;
    return true;
  }
  return false;
}
template <typename T> inline constexpr bool chmax(T &a, T b) {
  if (b > a) {
    a = b;
    return true;
  }
  return false;
}
template <typename ite>
void print_ite(ite start, ite end, char sp = ' ', char en = '\n') {
  for (auto i = start; i != end; i++)
    cout << *i << sp;
  cout << en;
}
template <typename ite> void scan_ite(ite start, ite end) {
  for (auto i = start; i != end; i++)
    cin >> (*i);
}
inline void Yes(bool condition) { cout << (condition ? "Yes\n" : "No\n"); }

int main(){
  string s;
  cin >> s;
  Yes(s[0]=='7' || s[1] == '7' || s[2]=='7');
}


Measured memory_bytes: 3132
X = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
K = int(input())-1
print(X[K])

Measured memory_bytes: 38384
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
 
#define INF 10000000000
#define M 1000000007

#define min(a,b) (((a)<(b))?(a):(b))
#define max(a,b) (((a)>(b))?(a):(b))

int main() {
	long N, A;
	long i, j, k;
	long ans = 0;
	long x[51];
	long *dp[51][51];
	long count[2500] = {0};
	
	scanf("%ld %ld", &N, &A);
	for(i=0;i<=N;i++) {
		for(j=0;j<=N;j++) {
			dp[i][j] = (long *)malloc(sizeof(long) * 2501);
			memset(dp[i][j], 0, sizeof(long) * 2501);
		}
	}
	
	for(i=1;i<=N;i++) {
		scanf("%ld", &x[i]);
		count[x[i]]++;
	}
	
	for(i=0;i<=N;i++)
			dp[i][0][0] = 1;
	
	for(i=1;i<=N;i++)
		for(j=1;j<=i;j++)
			for(k=0;k<=2500;k++)
				dp[i][j][k] = k < x[i] ? dp[i-1][j][k] : dp[i-1][j][k] + dp[i-1][j-1][k-x[i]];
	
	for(j=1;j<=N;j++) ans += dp[N][j][A*j];
	
	printf("%ld\n", ans);
	
	for(i=1;i<=N;i++) for(j=1;j<=N;j++) free(dp[i][j]);
	
	return 0;
}

Measured memory_bytes: 50816
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define int ll
using pint = pair<int,int>;
using Graph = vector<vector<int>>;
void YN(bool flg) {cout<<(flg?"YES":"NO")<<'\n';}
void Yn(bool flg) {cout<<(flg?"Yes":"No")<<'\n';}
void yn(bool flg) {cout<<(flg?"yes":"no")<<'\n';}
#define SORT(a) sort(a.begin(),a.end())
#define REVERSE(a) reverse(a.begin(),a.end())
#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 out(n) cout << n << '\n'
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<VI> VVI;
const int MOD = 1000000007;
const long long INF = 1e10; //10^10
const double PI = acos(-1.0L);
const int dx[4] = {1, 0, -1, 0} , dy[4] = {0, 1, 0, -1};
/*mod逆元*/long long modinv(long long a, long long m) {long long b = m, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}u %= m;if (u < 0) u += m;return u;}
template< typename T >T mod_pow(T x, T n, T p=MOD) {T ret = 1;while(n > 0) {if(n & 1) (ret *= x) %= p;(x *= x) %= p;n >>= 1;}return ret;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T>auto MAX(const T& a) { return *max_element(a.begin(),a.end()); }
template<class T>auto MIN(const T& a) { return *min_element(a.begin(),a.end()); }
template<class T, class U>U SUM(const T& a, const U& v) { return accumulate(a.begin(),a.end(), v); }
template<class T, class U>U COUNT(const T& a, const U& v) { return count(a.begin(),a.end(), v); }
template<class T, class U>int LOWER(const T& a, const U& v) { return lower_bound(a.begin(),a.end(), v) - a.begin(); }
template<class T, class U>int UPPER(const T& a, const U& v) { return upper_bound(a.begin(),a.end(), v) - a.begin(); }
int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { int g = GCD(a, b); return a / g * b; }
int POW(int a, int n) { int r = 1; while (n > 0) { if (n & 1)r *= a; a *= a; n >>= 1; }return r; }
int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*素因数分解*/map< int, int >prime_factor(int n){map< int, int > ret;for(int i = 2; i * i <= n; i++) {while(n % i == 0) {ret[i]++;n /= i;}}if(n != 1) ret[n] = 1;return ret;}
/*約数列挙*/vector<int> divisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}

//----------------ライブラリとか----------------

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

    int h,w,n; cin >> h >> w  >> n;
    int a = max(h,w);
    out((n+a-1)/a);

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAX_CASE=50,MAX_N=100000;

int t;
int n[MAX_CASE],k[MAX_CASE];
int x[MAX_CASE][MAX_N];

int dist[MAX_N];

int main(){
	scanf("%d",&t);
	for (int i=0;i<t;i++){
		scanf("%d %d",n+i,k+i);
		for (int j=0;j<n[i];j++){
			scanf("%d",&x[i][j]);
		}
	}
	for (int i=0;i<t;i++){
		int N=n[i],K=k[i];
		int sum=x[i][N-1]-x[i][0];
		if (K>=N){
			printf("0\n");
			continue;
		}
		for (int j=0;j<N-1;j++){
			dist[j]=x[i][j+1]-x[i][j];
		}
		sort(dist,dist+N-1);
		//??§???????????????K?????¨???
		int sum2=0;	//??????????????????
		for (int j=0;j<K-1;j++){
			sum2+=dist[N-j-2];
		}
		printf("%d\n",sum-sum2);
	}
	return 0;
}

Measured memory_bytes: 19160
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = (int)1e7;  
using  p = pair<int,int>;
int n,m;

int main(){
   cin >> n;
   auto s = unordered_map<char,int>();
   for (int i = 0; i < n; i++)
   {
      char c;
      cin >>c;
      if(s.find(c)!=s.end()){
         s[c]++;
      }else{
         s[c]=1;
      }
   }
   int f = 0;
   for (auto i:s)
   {
     f++;
   }

   cout << (f==4?"Four":"Three");
   
}
  
  

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){

	int a;
	int b;
	int c;

	cin >> a;
	cin >> b;
	cin >> c;

	if (a == b) {
	
		cout << c << endl;
	
		return 0;
	}
	else if (a == c) {

		cout << b << endl;
		return 0;
	}
	else if(b == c){

		cout << a << endl;
		return 0;
	}
	else {

		cout << "すべて違います" << endl;
		return 0;
	}
	return 0;

}

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

typedef int64_t ll;

int main(){
    int N,M;
    int s;
    char c;
    cin >> N >> M;
    vector<pair<int,char>> vec;
    for(int i =0;i<M;i++){
        cin >> s >> c;
        vec.push_back(pair<int,char>(s,c));
    }
    int n, n_end;
    if (N==1){
        n = 0;
        n_end = 10;
    }
    if (N==2){
        n = 10;
        n_end = 100;
    }
    if (N==3){
        n = 100;
        n_end = 1000;
    } 
    string n_str;
    bool ok;
    for(;n<n_end;n++){
        ok = true;
        n_str = to_string(n);
        for (auto p: vec){
            if(n_str.at(p.first - 1) != p.second) ok = false;
        }
        if(ok) break;
    }
    if(ok) cout << n << endl;
    else cout << -1 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 2e5 + 5;
const ll LINF = 1e18 + 5;

int main()
{
 	ios::sync_with_stdio(false);
 	cin.tie(0);
 	int x, y;
 	cin >> x >> y;
	if(500*x>=y) cout << "Yes";
	else cout << "No"; 
	return 0;
}


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

result = 0
if a % 2 == 1:
    result ^= a
if b % 2 == 0:
    result ^= b

if (b + b % 2) - (a + a % 2) > 0:
    result ^= ((b + b % 2) - (a + a % 2)) // 2 % 2

print(result)

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

long long n,a,m,k,q,b,c=1,a1,a2,b1,b2;
float qq,ww,ff=2,qs;
string ss,s1,s2;
int main(){
    cin>>ss;
    for (int i=0; i<ss.size(); i++){
        if (i%2==0){
            if (ss[i]=='0'){
                a1++;
            }
            else{
                b2++;
            }
        }
        else{
            if (ss[i]=='1'){
                a2++;
            }
            else{
                b1++;
            }
        }
    }
    cout<<min(a1+a2,b2+b1);
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define QQ 100010
int main() {
    int N, M;
    cin >> N >> M;
    vector<int> H(QQ);
    vector<int> A(QQ);

    rep1(i, N){
        cin >> H.at(i);
        A.at(i) = 0;
    }
    
    rep(j, M){
        int a, b;
        cin >> a >> b;
        A.at(a) = max(A.at(a), H.at(b));
        A.at(b) = max(A.at(b), H.at(a));
    }
    
    int ans = 0;
    
    rep1(i, N){
        ans += H.at(i) > A.at(i);
    }
    
    cout << ans << endl;
    
}

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

int main()
{
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	while(1)
	{		
		c-=b;
		if(c<=0)
		{
			cout<<"Yes";
			return 0;
		}
		a-=d;
		if(a<=0)
		{
			cout<<"No";
			return 0;
		}
	}
}

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

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

    int ans = 0;
    int total = 1;
    for(int i = 1; total < b; i++){
        total = (a - 1) * i + 1;
        ans = i; 
    }
    
    cout << ans << endl;

    return 0;

}



Measured memory_bytes: 256
#pragma GCC optimize("Ofast", "unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double

int main() {
	int N; cin >> N;
	ll res = 0;
	for (int i = 1; i <= N; ++i) {
		if ((i % 3) && (i % 5)) {
			res += i;
		}
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 3624
#include <cstdlib>
#include <iostream>
#include <set>
#include <vector>
using namespace std;

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

	for(int n; cin >> n && n;) {
		vector<int> h(n + 1);
		for(auto &e : h) cin >> e;

		for(int i = 0; i <= n; ++i) {
			set<int> S;

			int curr = (i ? 0 : 1);
			while(true) {
				int next = curr + 1;
				if(next == i) ++next;
				if(next > n) break;
				S.insert(h[next] - h[curr]);
				curr = next;
			}

			if(S.size() == 1) {
				cout << h[i] << endl;
				break;
			}
		}


	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1200
#include<atcoder/all>
using namespace atcoder;

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

int RMQ_op(int a, int b) { return max(a, b); }
int RMQ_e() { return -1; }
struct RMQ_cmp { int tg; bool operator()(int v) const { return v < tg; } };

int main() {
    int N, Q; scanf("%d%d", &N, &Q);
    vector<int> A(N); rep(i, N) { int a; scanf("%d", &a); A[i] = a; }
    segtree<int, RMQ_op, RMQ_e> G(A);

    rep(q, Q) {
        int c; scanf("%d", &c);
        if (c == 1) {
            int x, v; scanf("%d%d", &x, &v); x--;
            G.set(x, v);
        }
        if (c == 2) {
            int l, r; scanf("%d%d", &l, &r); l--;
            printf("%d\n", G.prod(l, r));
        }
        if (c == 3) {
            int x, v; scanf("%d%d", &x, &v); x--;
            auto cmp = [v](int x)->bool { return x < v; };
            printf("%d\n", G.max_right(x, cmp) + 1);
        }
    }

    return 0;
}

Measured memory_bytes: 6204
#include <iostream>
#include <string>

using namespace std;

void replace(string& str, const string& from, const string& to);

int main()
{
    string str;
    getline(cin, str);

    replace(str, "apple", "xxxxx");
    replace(str, "peach", "apple");
    replace(str, "xxxxx", "peach");

    cout << str << endl;
}

void replace(string& str, const string& from, const string& to)
{
    string::size_type pos = 0;
    while ((pos = str.find(from, pos)) != string::npos) {
        str.replace(pos, from.size(), to);
    }
}

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

using namespace std;

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

    vector<int> l[N];
    int sum[N];
    bool comp[N];
    for(int i=0; i<N; i++){
        sum[i] = 0;
        comp[i] = false;
    }

    for(int i=0; i<N-1; i++){
        int a, b;
        cin >> a >> b;
        l[a-1].push_back(b-1);
        l[b-1].push_back(a-1);
    }
    
    for(int i=0; i<Q; i++){
        int x, p;
        cin >> p >> x;
        sum[p-1] += x;
    }

    queue<int> q;
    q.push(0);
    comp[0] = true;
    while(!q.empty()){
        int n = q.front();
        q.pop();
        for(int i=0; i<l[n].size(); i++){
            if(!comp[l[n][i]]){
                sum[l[n][i]] += sum[n];
                comp[l[n][i]] = true;
                q.push(l[n][i]);
            }
        }
    }

    for(int i=0; i<N; i++){
        cout << sum[i] << " ";
    }

    return 0;
}

Measured memory_bytes: 15732
import math
X = int(input())
i_max = math.floor(math.sqrt(X))

result = 1
for i in range(2,i_max+1,1):
    for j in range(2,X):
        n = (i**j)
        if (n > X):
            break
        else:
            result = max(result, n)

print(result)


Measured memory_bytes: 3068
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
#include <cstdarg>
#include <sys/time.h>
#include <fstream>
//#include "cout.h"

using namespace std;

#define SZ(x) ((int)x.size())
#define MSET(x,a) memset(x, a, (int)sizeof(x))
#define PB push_back
#define VI vector < int >
#define PII pair < int, int >
#define LL long long
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(), (v).end()
#define FIT(it,v) for (__typeof((v).begin()) it = (v).begin(); it != (v).end(); it++)
#define OUT(A) cout << #A << " = "<< (A) << endl
#define OUT2(A, B) cout << "(" << #A << ", " << #B << ") = (" << (A) << ", "<< (B) << ")" << endl
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }

#define present(c, e) ((c).find((e)) != (c).end())
#define cpresent(c, e) (find(ALL(c), (e)) != (c).end())

int n, i;

void init() {

}

void input() {
	cin >> n >> i;
}

void solve() {
	cout << n-i+1 << endl;
}

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


Measured memory_bytes: 256
#include <bits/stdc++.h> 
#include <cstring>
using namespace std;
//typedef
typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
//define
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)

int main(){
    int k,x;
    cin >> k >> x;
    rep(i,2*k-1) cout << x-k+i+1 << endl;  

 return 0;
}


Measured memory_bytes: 256
#include <cmath>
#include <cstdio>

#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <numeric>
#include <string>
#include <array>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(x) x.begin(), x.end()

using namespace std;
typedef long long int ll;

int main() {
  ll a, b, c, x, y;
  cin >> a >> b >> c >> x >> y;
  ll sum=0;
  if(a + b > c*2) {
    ll minxy = min(x, y);
    sum = 2 * c * minxy;
    x -= minxy;
    y -= minxy;
  }
  if(a > c*2) sum += x*c*2;
  else sum += a*x;
  if(b > c*2) sum += y*c*2;
  else sum += b*y;

  cout << sum << endl;


  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int main() {
	int X, A; cin >> X >> A;
	if (X < A) cout << "0" << endl;
	else cout << "10" << endl;
	return 0;
}

Measured memory_bytes: 3608
#include <array>
#include <iostream>

using namespace std;

template <size_t N> constexpr array<int32_t, N + 1> solve() {
  array<bool, N> is_prime{};
  for (size_t i = 0; i < N; i++) {
    is_prime[i] = true;
  }
  is_prime[0] = false;
  is_prime[1] = false;
  for (size_t p = 2; p < N; p++) {
    if (!is_prime[p]) {
      continue;
    }
    for (size_t cur = p * 2; cur < N; cur += p) {
      is_prime[cur] = false;
    }
  }

  array<bool, N> is_liked{};
  for (size_t n = 3; n < N; n++) {
    if (n % 2 == 1 && is_prime[n] && is_prime[(n + 1) / 2]) {
      is_liked[n] = true;
    }
  }

  array<int32_t, N + 1> sum{};
  for (size_t i = 0; i <= N; i++) {
    sum[i + 1] = sum[i];
    if (is_liked[i]) {
      sum[i + 1] += 1;
    }
  }
  return sum;
}

int main() {
  /* constexpr */ array<int32_t, 10000001> sum = solve<10000000>();
  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    int l, r;
    cin >> l >> r;
    cout << (sum[r + 1] - sum[l]) << endl;
  }
}

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

typedef long long int LL;
typedef unsigned long long uLL;
typedef pair< int,int > ii;
typedef pair< int,ii > iii;
const int inf = 1e9;
const LL INF = 1e18;
const int N = 100005;
const int MOD = 1e9+7;
const double EPS = 1e-6;
const double PI = acos(-1.0);

int n;
int ara[ 5 ][ 105 ];
int dp[ 5 ][ 105 ];

int solve( int x , int y ) {
    if( x == 2 && y == n ) return ara[x][y];
    if( x > 2 || x > n || y > n ) return 0;
    int ans = 0 , op1 = 0 , op2 = 0;
    if( dp[x][y] != -1 ) return dp[x][y];
    op1 = solve( x+1 , y )+ara[x][y];
    op2 = solve( x , y+1 )+ara[x][y];
    ans = max( op1 , op2 );
    return dp[x][y] = ans;
}
int main( int argc, char const *argv[] ) {
    cin >> n;
    for( int i = 1; i <= 2; i++ ) {
        for( int j = 1; j <= n; j++ ) {
            cin >> ara[i][j];
        }
    }
    memset( dp , -1 , sizeof(dp) );
    cout << solve( 1 , 1 ) << endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define rep1(i, n) for (int i = 1; i < int(n); ++i)
#define repx(i, x, n) for (int i = int(x); i < int(n); ++i)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; --i)
#define ALL(n) begin(n), end(n)
#define IN(a, x, b) ((a) <= (x) && (x) < (b))
#define OUT(a, x, b) ((x) < (a) || (x) < (b))
typedef long long ll;
typedef long double ld;
const ll INF = 1e18;
const ll MOD = 1000000007;

int main()
{
    string s;
    cin >> s;
    set<char> S;
    rep(i, s.size())
    {
        S.insert(s[i]);
    }
    if (s.size() == S.size())
    {
        cout << "yes" << endl;
    }
    else
    {
        cout << "no" << endl;
    }

    return 0;
}


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

#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

int main() {
    int64_t k, q;
    cin >> k >> q;

    vector<int64_t> d(k);
    for (auto&& dd : d) {
        cin >> dd;
    }

    for (auto _ : irange(0L, q)) {
        int64_t n, x, m;
        cin >> n >> x >> m;

        int64_t s = 0;
        for (auto dd : d) {
            s += (m - 1 + dd) % m + 1;
        }

        s *= (n - 1) / k;

        for (auto i : irange(0L, (n - 1) % k)) {
            s += (m - 1 + d[i]) % m + 1;
        }

        s += x;

        cout << (n - 1) - (s / m - x / m) << "\n";
    }
}

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

using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

bool g[55][55];
bool c[55];

void bfs(int p) {
    if (c[p]) {
        return;
    } else {
        c[p] = true;
    }

    for (int i = 0; i < 55; ++i) {
        if (g[p][i]) {
            bfs(i);
        }
    }
}

int main() {

    int n, m; cin >> n >> m;

    vector<int> a(m);
    vector<int> b(m);

    for (int i = 0; i < 55; ++i) {
        for (int j = 0; j < 55; ++j) {
            //隣接行列を一度全てfalseにする
            g[i][j] = false;
        }
    }

    for (int i = 0; i < m; ++i) {
        cin >> a[i] >> b[i];

        --a[i]; --b[i];

        //隣接行列
        g[a[i]][b[i]] = true;
        g[b[i]][a[i]] = true;
    }

    int ans = 0;

    //橋かどうか調べる
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < 55; ++j) {
            c[j] = false;
        }

        g[a[i]][b[i]] = false;
        g[b[i]][a[i]] = false;

        //bfsを使って調べる
        bfs(a[i]);

        if (!c[b[i]]) {
            ++ans;
        }

        //元に戻す
        g[a[i]][b[i]] = true;
        g[b[i]][a[i]] = true;
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <set>

#define ll long long
#define pll pair<ll, ll>

#define reps(i, f, n) for (int i = (f); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

const int INF = 1111111111;
const double EPS = 1e-9;

using namespace std;

const int N = 222222;
const int K = 222222;

int n, k;
int a[N];

void init()
{
	cin >> n >> k;
	rep(i, n) cin >> a[i];
}

void solve()
{
	rep(t, k)
	{
		int diff[N];
		rep(i, N) diff[i] = 0;

		rep(i, n)
		{
			diff[max(0, i - a[i])]++;
			diff[min(n, i + a[i] + 1)]--;
		}

		rep(i, N) a[i] = 0;
		rep(i, n)
		{
			if (i != 0)
			{
				a[i] += a[i - 1];
			}
			a[i] += diff[i];
		}

		bool allFix = true;

		rep(i, n)
		{
			if (a[i] != n)
			{
				allFix = false;
			}
		}

		if (allFix)
		{
			break;
		}
	}

	rep(i, n)
	{
		cout << a[i] << " ";
	}
	cout << endl;
}

int main()
{
	init();
	solve();
}


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

#define LL long long
#define RG register

using namespace std;
template<class T> inline void read(T &x) {
	x = 0; RG char c = getchar(); bool f = 0;
	while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') c = getchar(), f = 1;
	while (c >= '0' && c <= '9') x = x*10+c-48, c = getchar();
	x = f ? -x : x;
	return ;
}
template<class T> inline void write(T x) {
	if (!x) {putchar(48);return ;}
	if (x < 0) x = -x, putchar('-');
	int len = -1, z[20]; while (x > 0) z[++len] = x%10, x /= 10;
	for (RG int i = len; i >= 0; i--) putchar(z[i]+48);return ;
}
const int N = 200010, Mod = 1e9 + 7;
int fac[N], ifac[N], H, W, A, B;
int fpow(int a, int b) {
	int res = 1;
	for (; b; b >>= 1, a = 1ll * a * a % Mod)
		if (b & 1) res = 1ll * res * a % Mod;
	return res;
}
int C(int n, int m) {
	if (n < m) return 0;
	return 1ll * fac[n] * ifac[m] % Mod * ifac[n - m] % Mod;
}
int calc(int n, int m) {
	return C(n + m - 2, n - 1);
}
int main() {
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	read(H), read(W), read(A), read(B);
	fac[0] = 1;
	for (int i = 1; i <= 200000; i++)
		fac[i] = 1ll * fac[i - 1] * i % Mod;
	ifac[200000] = fpow(fac[200000], Mod - 2);
	for (int i = 200000; i >= 1; i--)
		ifac[i - 1] = 1ll * ifac[i] * i % Mod;
	int ans = 0;
	for (int i = B + 1; i <= W; i++)
		(ans += 1ll * calc(H - A, i) * calc(A, W - i + 1) % Mod) %= Mod;
	printf("%d\n", ans);
	return 0;
}


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

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

int main() {
  int n,k,c=0; cin>>n>>k;
  vector<int> v(n);
  rep(i,n){
    cin>>v.at(i);
    if(v.at(i)>=k){c++;}
    
  }
  cout<<c;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long int uli;
const int oo=1e9;
const int mx=123;
int g[mx][mx];
vector<tuple<int,int,int> >edges;
int main(){
  int n,m;
  scanf("%d %d",&n,&m);
  for(int i=0;i<n;i++)for(int j=0;j<n;j++)g[i][j]=oo;
  for(int i=0;i<n;i++)g[i][i]=0;
  while(m--){
    int u,v,c;
    scanf("%d %d %d",&u,&v,&c);
    --u,--v;
    edges.push_back(make_tuple(u,v,c));
    g[u][v]=g[v][u]=c;
  }
  for(int k=0;k<n;k++)
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
        g[i][j]=min(g[i][j],g[i][k]+g[k][j]);            
  sort(edges.begin(),edges.end());
  int ans=0;
  for(auto e:edges){
    int u,v,c;
    tie(u,v,c)=e;
    if(g[u][v]<c)ans++;
  }
  printf("%d\n",ans);
  return 0;
}


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

void solve(long long N, std::vector<long long> A){
    map<ll, ll> mp;
    for(auto a : A) mp[a]++;
    ll pos = 0;
    if(N % 2 == 0) pos = 1;
    ll ans = 1;
    for(ll i = pos; i <= N-1; i += 2){
        if(i == 0 && (mp[i] != 1)){
            ans = 0;
            break;
        }
        if((i > 0 && i < N-1) && mp[i] != 2){
            ans = 0;
            break;
        }
        ans *= (mp[i] % MOD);
        ans %= MOD;
    }
    cout << ans << endl;
    /*
    map<ll, ll> idealmp;
    for(ll i = 1; i < N; i++){
        ll cnt = abs((N-i) - (i-1));
        idealmp[cnt]++;
    }
    cout << "-- real --" << endl;
    for(auto itr = mp.begin(); itr != mp.end(); itr++){
        cout << itr->first << " " << itr->second << endl;
    }
    cout << "-- ideal --" << endl;
    for(auto itr = idealmp.begin(); itr != idealmp.end(); itr++){
        cout << itr->first << " " << itr->second << endl;
    }
    */
    return;
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    solve(N, std::move(A));
    return 0;
}


Measured memory_bytes: 7916
#include <iostream>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <iomanip>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <functional>
/* Data Structure */
#include <vector>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <stack>
#include <queue>

using namespace std;

#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3fLL
#define debug cerr << "======= GOT_HERE ======\n"
#define endl "\n"

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef map<int,int> mii;
typedef map<long long,long long> mll;
typedef set<int> si;
typedef set<long long> sll;

long long n,k;

const int maxn = 1e5+10;

int a,b;

struct Node{
	int x;
	int y;
	int idx;
};

int fa[maxn];

int find(int x){
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}
void unite(int x,int y){
    x=find(x);y=find(y);
    if(x==y)return;
    fa[x]=y;
}

bool cmp(vector<int>& A, vector<int>& B)
{
	return A[0]<B[0];
}

bool cmp_x(Node& A, Node& B)
{
	return A.x<B.x;
}

bool cmp_y(Node& A, Node& B)
{
	return A.y < B.y;
}

int main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin>>n;
	for(int i=0;i<n;++i)
	{
		fa[i] = i;
	}
	vector<Node> node_x;
	vector<Node> node_y;
	for(int i=0;i<n;++i)
	{
		cin>>a>>b;
		Node temp{a,b,i};
		node_x.emplace_back(temp);
		node_y.emplace_back(temp);
	}

	sort(node_x.begin(),node_x.end(),cmp_x);
	sort(node_y.begin(),node_y.end(),cmp_y);

	vector<vector<int>> diff_x, diff_y;

	for(int i=1;i<n;++i)
	{
		diff_x.emplace_back(vector<int>{node_x[i].x-node_x[i-1].x,node_x[i].idx,node_x[i-1].idx});
		diff_y.emplace_back(vector<int>{node_y[i].y-node_y[i-1].y,node_y[i].idx,node_y[i-1].idx});
	}

	sort(diff_x.begin(),diff_x.end(),cmp);
	sort(diff_y.begin(),diff_y.end(),cmp);

	ll ans = 0, cnt = 0;

	int ptr1 = 0, ptr2 = 0;
	while(cnt!=n-1)
	{
		if(diff_x[ptr1][0]<=diff_y[ptr2][0])
		{
			int a = diff_x[ptr1][1], b = diff_x[ptr1][2];
			if(find(a)==find(b)) ptr1++;
			else
			{
				ans+=diff_x[ptr1][0];
				unite(a,b);
				cnt++;
			}
		}
		else
		{
			int a = diff_y[ptr2][1], b = diff_y[ptr2][2];
			if(find(a)==find(b)) ptr2++;
			else
			{
				ans+=diff_y[ptr2][0];
				unite(a,b);
				cnt++;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 14628
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long
#define mod 1000000007

const int sz=1e5+5;
ll inf=1e15;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    // cin>>t;
    while(t--)
    {
        string s;
        cin>>s;
        int n=s.length();
        ll sum=0;
        for(int i=0;i<n;i++)
        {
            sum+=(s[i]-'0');
            sum%=9;
        }
        if(sum)
        {
            cout<<"No";
        }
        else
            cout<<"Yes";
    }

    return 0;
}

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

const int MAX_N = 30005;
int L[MAX_N], R[MAX_N], p[10];

int main() {
	int n; cin >> n;
	string s; cin >> s;
	// memset(p, 0, sizeof(p));
	// left
	set<int> temp;
	for(int i=0; i<n; i++) {
		L[i]=temp.size();
		temp.insert(s[i]-'0');
	}
	temp.clear();
	for(int i=n-1; i>=0; i--) {
		R[i]=temp.size();
		temp.insert(s[i]-'0');
	}
	// for(int i=0; i<n; i++) {
	// 	cout << L[i] << ' ' << R[i] << endl;
	// }

	int ans = 0;
	for(int i=0; i<n; i++) {
		ans += (L[i] - L[p[s[i]-'0']]) * R[i];
		p[s[i]-'0']=i;
	}

	cout << ans << endl;
    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
// Welcome to my source code!

const int MOD = 1000000007;

ll p[1001];

vector<ll> prime_factor(ll n) {
    vector<ll> pf;
    double x = sqrt(n);
    for (ll i = 2; i <= x && n; i++) {
        while (n % i == 0 && n) {
            pf.push_back(i);
            n /= i;
        }
    }
    if (n != 1) pf.push_back(n);
    return pf;
}

int main() {
    int n;
    cin >> n;
    for (int i = n; i >= 2; i--) {
        vector<ll> vec = prime_factor(i);
        for (auto x : vec) p[x]++;
    }
    ll ans = 1;
    for (int i = 2; i <= n; i++) {
        if (p[i]) ans *= (p[i] + 1);
        ans %= MOD;
    }
    cout << ans << endl;
}

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

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, int> pii;
typedef pair<ll, ld> pld;
typedef pair<pii, int> ppiii;
typedef pair<pii, ll> ppiil;
typedef pair<pll, ll> pplll;
typedef pair<pli, int> pplii;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<pll>> vvpll;
#define rep(i, a, b) for (ll i=(a); i<(b); i++)
#define rrep(i, a, b) for (ll i=(a); i>(b); i--)
#define btoe(obj) (obj).begin(), (obj).end()
#define pb push_back
#define str to_string
#define mkp make_pair
const ll INF = 1e18;
const ll MOD = 1e9 + 7;

void print(ld out) { cout << fixed << setprecision(12) << out << '\n'; }
template<typename T> void print(T out) { cout << out << '\n'; }
template<typename T1, typename T2> void print(pair<T1, T2> out) { cout << out.first << ' ' << out.second << '\n'; }
template<typename T> void print(vector<T> A) { rep(i, 0, A.size()) { cout << A[i]; cout << (i == A.size()-1 ? '\n' : ' '); } }
template<typename T> void print(set<T> S) { vector<T> A(S.begin(), S.end()); print(A); }

template<typename T> inline bool chmax(T &x, T y) { return (y > x) ? x = y, true : false; }
template<typename T> inline bool chmin(T &x, T y) { return (y < x) ? x = y, true : false; }

ll sum(vector<ll> A) { ll res = 0; for (ll a: A) res += a; return res; }
ll max(vector<ll> A) { ll res = -INF; for (ll a: A) chmax(res, a); return res; }
ll min(vector<ll> A) { ll res = INF; for (ll a: A) chmin(res, a); return res; }

ll toint(string s) { ll res = 0; for (char c : s) { res *= 10; res += (c - '0'); } return res; }
int toint(char c) { return c - '0'; }

inline ll pow(int x, ll n) { ll res = 1; rep(_, 0, n) res *= x; return res; }
inline ll pow(ll x, ll n, int mod) { ll res = 1; while (n > 0) { if (n & 1) { res = (res * x) % mod; } x = (x * x) % mod; n >>= 1; } return res; }

inline ll floor(ll a, ll b) { if (a < 0) { return (a-b+1) / b; } else { return a / b; } }
inline ll ceil(ll a, ll b) { if (a >= 0) { return (a+b-1) / b; } else { return a / b; } }

int popcount(ll S) { return __builtin_popcountll(S); }

ll N;
ll G[16][16];
ll dp[1<<16];

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

    cin >> N;
    rep(i, 0, N) rep(j, 0, N) cin >> G[i][j];
    
    rep(S, 1, 1<<N) {
        rep(i, 0, N) {
            rep(j, i+1, N) {
                if (S & (1<<i) && S & (1<<j)) {
                    dp[S] += G[i][j];
                }
            }
        }
        rep(T, 1, S) {
            if ((S | T) == S) {
                chmax(dp[S], dp[T] + dp[S^T]);
            }
        }
    }
    ll ans = dp[(1<<N)-1];
    print(ans);
    return 0;
}


Measured memory_bytes: 768