akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

int D[200000];
vector <vector <int>> vex;

void dfs(int i, int p) {
    for(int r : vex[i])
        if(r != p) {
            D[r] = D[i] + 1;
            dfs(r, i);
        }
    return ;
}

int main() {
    int n; cin >> n;
    vex.resize(n);
    int u, v;
    
    for(int i = 1; i < n; ++i) {
        cin >> u >> v;
        u -= 1; v -= 1;
        vex[u].push_back(v);
        vex[v].push_back(u);
    }
    dfs(0, 0);
    int rx = 0;
    for(int i = 0; i < n; ++i)
        if(D[i] > D[rx]) rx = i;
    
    memset(D, 0, sizeof D);
    dfs(rx, rx);
    int mx = 0;
    for(int i = 0; i < n; ++i)
        mx = max(mx, D[i]);
    
    cout << (mx % 3 == 1 ? "Second" : "First");
    return 0;
}

Measured memory_bytes: 21376
#include <bits/stdc++.h>
#define ll long long
#define res register ll
using namespace std;
ll n,num,m;
ll len[101010];
ll f[101010],sum[101010];
inline ll read()
{
  ll X=0,w=0;
  char ch=0;
  while(!isdigit(ch))
  {
    w|=ch=='-';
    ch=getchar();
  }
  while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
  return w?-X:X;
}
void work(ll x,ll base)
{
  if (x<len[1])
  {
    sum[x]+=base;
    return;
  }
  ll l=1,r=n;
  ll total;
  while (l<=r)
  {
    ll mid=(l+r)/2;
    if (len[mid]<=x)
    {
      total=mid;
      l=mid+1;
    }
    else r=mid-1;
  }
  f[total]+=base*(x/len[total]);
  x=x%len[total];
  if (x) work(x,base);
}
int main()
{
  n=read(),m=read();
  num=1;
  len[1]=n;
  ll x;
  for (res i=1; i<=m; ++i)
  {
    x=read();
    while (x<=len[num] && num)
      --num;
    ++num;
    len[num]=x;
  }
  m=n;
  n=num;
  f[n]=1;
  for (res i=n-1; i>=1; --i)
  {
    f[i]+=f[i+1]*(len[i+1]/len[i]);
    work(len[i+1]%len[i],f[i+1]);
  }
  for (res i=len[1]; i>=1; --i)
    sum[i]+=sum[i+1];
  for (res i=1; i<=len[1]; ++i)
    sum[i]+=f[1];
  for (res i=1; i<=m; ++i)
    printf("%lld\n",sum[i]);
  return 0;
}

Measured memory_bytes: 4096
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
long long var(long long a){
    if(a>0) return a;
    return -a;
}
int main() {
    int n;
    cin>>n;
    vector<long long> a(n);
    rep(i,n) cin>>a.at(i);
    vector<long long> dp(n);
    dp.at(0)=0;
    dp.at(1)=var(a.at(1)-a.at(0));
    rep(i,n-2){
        dp.at(i+2)=min(dp.at(i)+var(a.at(i+2)-a.at(i)),dp.at(i+1)+var(a.at(i+2)-a.at(i+1)));
    }
    cout<<dp.at(n-1);
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <set>
#include <cmath>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

using namespace std;
typedef long long int lli;

int main(){
	int N,X;
	cin>>N>>X;
	int sum=0;
	int mn=10000;
	rep(i,N){
		int m;
		cin>>m;
		sum+=m;
		mn=min(mn,m);
	}
	int ans=N+(X-sum)/mn;
	cout<<ans;
}

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

#define FAST_INP  ios_base::sync_with_stdio(false);cin.tie(NULL)


int main()  
{ 
    FAST_INP;
    int t; 
    cin >> t;
    if(t>=400&&t<=599) cout << 8;
    else if(t>=600&&t<=799) cout << 7;
    else if(t>=800&&t<=999) cout << 6;
    else if(t>=1000&&t<=1199) cout << 5;
    else if(t>=1200&&t<=1399) cout << 4;
    else if(t>=1400&&t<=1599) cout << 3;
    else if(t>=1600&&t<=1799) cout << 2;
    else if(t>=1800&&t<=1999) cout << 1;
    return 0;
} 

Measured memory_bytes: 3648
#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define pb push_back
#define mp make_pair
#define sz(x) ((int)(x).size())
#define fo(i,a) for(int i=1;i<=(a.n);i++)
#define mem(x,y) memset((x),(y),sizeof(x))
#define fup(i,x,y) for(int i=(x);i<=(y);i++)
#define fdn(i,x,y) for(int i=(x);i>=(y);i--)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main()
{
    ll x,y;
    sf("%lld%lld",&x,&y);
    if(x%y==0)return !pf("-1\n");
    if(x==1)return !pf("%lld\n",y+1);
    ll z=x;
    while(z%y==0)z+=x;
    pf("%lld\n",z);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#define mod 1000000007

using namespace std;

int main(){
    string S;
    cin >> S;

    long long dp[S.length()+1][13];
    for(int i=0; i<=S.length(); i++){
        for(int j=0; j<=13; j++){
            dp[i][j] = 0;
        }
    }

    dp[0][0] = 1;

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

    int keta = 1;
    for(int i=0; i<S.length(); i++){
        if(i==0) keta = 1;
        else keta = (keta * 10) % 13;
        for(int j=0; j<13; j++){
            if(S[i] == '?'){
                for(int k=0; k<=9; k++){
                    int m = (k * keta) % 13;
                    dp[i+1][(j+m)%13] += dp[i][j];
                }
            }else{
                int d = S[i] - '0';
                int m = (d * keta) % 13;
                dp[i+1][(j+m)%13] += dp[i][j];
            }
        }
        for(int j=0; j<13; j++){
            dp[i+1][j] %= mod;
        }
    }
    
    cout << dp[S.length()][5];

    return 0;

}

Measured memory_bytes: 10624
def ii():
    return int(input())


def lii():
    return list(map(int, input().split(' ')))


def lvi(N):
    l = []
    for _ in range(N):
        l.append(ii())
    return l


def lv(N):
    l = []
    for _ in range(N):
        l.append(input())
    return l


def C():
    N = ii()
    d = {'M': 0, 'A':0, 'R':0,'C':0,'H':0}
    for _ in range(N):
        s = input()
        if s[0] in d.keys():
            d[s[0]] += 1

    from itertools import combinations

    ans = 0
    for e1, e2, e3 in combinations(d.keys(), 3):
        ans += d[e1] * d[e2] * d[e3]

    print(ans)

if __name__ == '__main__':
    C()



Measured memory_bytes: 3188
#include <iostream>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <string>
#include <functional>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <bitset>
#define pb push_back
#define YES cout<<"YES"<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define No cout<<"No"<<endl
#define rep(i,n) for(int i=0;i<n;i++)
#define INF (1<<20)
#define LLINF (1LL<<60)
#define MOD 1000000007
typedef long long ll;
using namespace std;

int main(){
    int n;
    ll a[100005], sum = 0, evensum[50005], oddsum[50005];
    cin >> n;
    rep(i, n){
        cin >> a[i];
        sum += a[i];
        if(i==0){
            evensum[0] = a[i]*2;
        }
        else if(i==1){
            oddsum[0] = a[i]*2;
        }
        else if(i%2==0){
            evensum[i / 2] = a[i]*2 + evensum[i / 2 - 1];
        }
        else{
            oddsum[i / 2] = a[i]*2 + oddsum[i / 2 - 1];
        }
    }

        rep(i, n)
        {
            ll t = 0;
            if (i == 0)
            {
                t = evensum[(n - 1) / 2];
            }
            else if (i == 1)
            {
                t = oddsum[n / 2 - 1] + evensum[0];
            }
            else if (i % 2 == 0)
            {
                t += evensum[(n - 1) / 2] - evensum[i / 2 - 1];
                t += oddsum[(n / 2 + 1) - (((n - 1) / 2) - (i / 2 - 1) + 1)];
            }
            else
            {
                t += oddsum[n / 2 - 1] - oddsum[i / 2 - 1];
                t += evensum[(n / 2 + 1) - ((n / 2 - 1) - (i / 2 - 1) + 1)];
            }
            cout << t - sum << ' ';
        }
    return 0;
}


Measured memory_bytes: 2816
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int stepX[4] = {1,-1,0,0};
int stepY[4] = {0,0,1,-1};

bool inArea(int tx, int ty, int w,int h)
{
    return (0 <= tx && tx < w && 0 <= ty && ty < h); 
}

int getFar(vector<vector<bool>> &mat, int sh, int sw, int h, int w)
{
    queue<int> que;
    vector<int> steps(h*w,h*w);
    vector<bool> checker(w*h);
    que.push(sh*w+sw);
    steps[sh*w+sw] = 0;
    checker[sh*w+sw] = true;
    int dist = 0;
    while(!que.empty())
    {
        int num = que.front();
        que.pop();
        int tx = num%w;
        int ty = num/w;
        int stp = steps[ty*w+tx];
        for(int i = 0; i < 4; ++i)
        {
            int ttx = tx+stepX[i];
            int tty = ty+stepY[i];
            if(inArea(ttx,tty,w,h)
            && mat[tty][ttx]
            && !checker[tty*w+ttx])
            {
                que.push(tty*w+ttx);
                checker[tty*w+ttx] = true;
                steps[tty*w+ttx] = stp+1;
                dist = max(dist,stp+1);
            }
        }
    }
    return dist;
}

int main()
{
    int h,w;
    cin >> h >> w;
    vector<vector<bool>> mat(h);
    for(int i = 0; i < h; ++i)
    {
        vector<bool> row(w);
        for(int j = 0; j < w; ++j)
        {
            char c;
            cin >> c;
            row[j] = c=='.';
        }
        mat[i] = row;
    }
    int ans = 0;
    for(int i = 0; i < h*w; ++i)
    {
        int tx = i%w;
        int ty = i/w;
        if(!mat[ty][tx])
        {
            continue;
        }
        ans = max(ans, getFar(mat,ty,tx,h,w));
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
// const ll MOD = 1000000007;
// const int INF = 2000000000;

ll A, B, C, K;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> A >> B >> C >> K;

  ll ans = 0;
  if (K % 2 == 0) {
    ans = A - B;
  } else {
    ans = B - A;
  }

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using vi=vector<int>;
using vvi=vector<vi>;
using vs=vector<string>;
using msi=map<string,int>;
using mii=map<int,int>;
using pii=pair<int,int>;
using vlai=valarray<int>;
using ll=long long;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1e9
#define EPS 1e-9

int main(){
	int n,c,k;
	cin>>n>>c>>k;
	vi p(n);
	rep(i,n){
	    cin>>p[i];
	}
	sort(all(p));
	int ans=0;
	rep(i,n){
	    int lt=p[i]+k;
	    int l=c;
	    for(;p[i]<=lt && l>0;i++){
	        //cout<<i<<"("<<p[i]<<")"<<",";
	        l--;
	    }
	    //cout<<endl;
	    i--;
	    ans++;
	}
	cout<<ans<<endl;
	
	return 0;
}


Measured memory_bytes: 640
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

class MainClass
{
    static void Main()
    {
        string s = ReadLine();
        bool c = false;
        bool f = false;
        for (int i = 0; i < s.Length; i++)
        {
            if (s[i] == 'C')
            {
                c = true;
            }
            if (c && s[i] == 'F')
            {
                f = true;
            }
        }
        WriteLine((c&&f)?"Yes":"No");
    }
}


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

int main()
{
    int n;
    cin >> n;
    double x;
    string u;
    double ans = 0;
    for(int i = 1; i <= n; i++){
        cin >> x >> u;
        if(u == "BTC"){
            ans += x*380000;
        }else{
            ans += x;
        }
    }
    printf("%.5f\n",ans);
}

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

sum = 0

import sys
if a < k:
  sum = 1 * a
  k = k - a
else:
  print(1 * k)
  sys.exit()
  
if b < k:
  k = k - b
else:
  print(sum)
  sys.exit()
  
print(sum - k)

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

using namespace std;

typedef long long ll;

int main()
{
    int m , k , i , j , p , q , x , y;
    scanf("%d %d",&m,&k);
    vector<int> vec;

    int lim = 1<<m;
    lim--;

    if(k == 0)
    {
        for(i = 0 ; i <= lim ; i++)
        {
            if(i)printf(" ");
            printf("%d %d",i,i);
        }
        return !printf("\n");
    }


    if(k > lim)return !printf("-1\n");
    x = 0;
    for(i = 1 ; i <= lim ; i++)
    {
        p = k^i;
        if(p > lim)
        {
            return !printf("-1\n");
        }
        else
        {
            if(i < p)
            {
                vec.push_back(i);
                vec.push_back(p);
            }
        }
    }

    lim++;
    lim = 2*lim;

    p = vec.size();

    if(p == 0)return !printf("-1\n");
    p = p*2;
    p += 4;

    if(p != lim)return !printf("-1\n");

    printf("0 %d 0 ",k);
    int l = vec.size();
    for(i = 0 ; i < l ; i++)
    {
        printf("%d ",vec[i]);
    }
    printf("%d",k);
    reverse(vec.begin(),vec.end());
    for(i = 0 ; i < l ; i++)
    {
        printf(" %d",vec[i]);
    }
    printf("\n");


    return 0;
}


Measured memory_bytes: 2424
H,W=map(int,input().split())
S=[[int(c=='#') for c in input()] for i in range(H)]
v=[[0]*W for i in range(H)]
r=0
def bfs(p,x,y,c,b):
    while 1:
        c^=1
        q=set()
        for h,w in p:
            v[h][w]=1
            if h>0 and not v[h-1][w] and S[h-1][w]==c:
                q.add((h-1,w))
            if w>0 and not v[h][w-1] and S[h][w-1]==c:
                q.add((h,w-1))
            if h<H-1 and not v[h+1][w] and S[h+1][w]==c:
                q.add((h+1,w))
            if w<W-1 and not v[h][w+1] and S[h][w+1]==c:
                q.add((h,w+1))
        if not q:
            return x*y
        if b:
            x+=len(q)
        else:
            y+=len(q)
        b^=1
        p=q
for h in range(H):
    for w in range(W):
        if v[h][w]==0:
            r+=bfs([(h,w)],1,0,S[h][w],0)
print(r)

Measured memory_bytes: 5748
#include <cstdio>
int N, K, l, r, c[1000009], a[1000009], v[1000009], p[1000009]; char ch, s[1000009][19];
int main() {
	scanf("%d %d\n", &N, &K);
	for (int i = 0; i < N; i++) {
		ch = getchar_unlocked();
		while (48 <= ch && ch <= 57) a[i] = a[i] * 10 + ch - 48, s[i][c[i]] = ch, ch = getchar_unlocked(), ++c[i];
	}
	for (int i = 0; i < K; i++) {
		while (l != r && v[r - 1] >= a[i]) r--;
		v[r] = a[i], p[r++] = i;
	}
	for (int i = K; i <= N; i++) {
		for (int j = 0; j < c[p[l]]; ++j) putchar_unlocked(s[p[l]][j]);
		putchar_unlocked(i == N ? '\n' : ' ');
		if (p[l] == i - K) l++;
		while (l != r && v[r - 1] >= a[i]) r--;
		v[r] = a[i], p[r++] = i;
	}
	return 0;
}


Measured memory_bytes: 36792
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

int main() {
  int top=0;
  int second=0;
  int third=0;
  int height;
  std::vector<int> heights;

  while(scanf("%d\n", &height) != EOF) {
    heights.push_back(height);
  }

  std::sort(heights.begin(), heights.end());

  for(int i=0;i<3;i++) {
    std::cout << heights.back() << std::endl;
    heights.pop_back();
  }
}

Measured memory_bytes: 3220
def main():
    N = input()
    hun = N[0]
    hikaku = int(hun + hun + hun)
    N = int(N)
    if(hikaku >= N):
        print(hun + hun + hun)
        return 
    
    new_hun = str(int(hun) +1)
    print(new_hun + new_hun + new_hun)

if __name__ == "__main__":
    main()

Measured memory_bytes: 3064
#include <iostream>
#include<vector>
#include<algorithm>
#define rep(i,n) for(int i = 0;i <n;i++)
using namespace std;
int main(){
	int h, a, b,cnt = 0; cin >> h >> a >> b;
	for (int i = a; i <= b; i++) {
		if (h%i == 0)cnt++;
	}cout << cnt << endl;
}


Measured memory_bytes: 3128
#include <iostream>
#include <array>
#include <vector>
#include <map>
#include <queue>
#include <string>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstdio>
using namespace std;

int main(void){
    int N,M;
    cin >> N >> M;
    vector<long int> A(N);
    vector<pair<long int, long int>> cb(M);
    long int sum=0;
    for(int i=0; i<N; i++){
        cin >> A[i];
        sum += A[i];
    }
    for(int i=0; i<M; i++){
        long int b,c;
        cin >> b >> c;
        cb[i] = make_pair(c, b);
    }
    sort(cb.begin(), cb.end());
    sort(A.begin(), A.end());
    int index = M-1;
    for(int i=0; i<N; i++){
        if(cb[index].second <= 0){
            index--;
        }
        if(index < 0){
            break;
        }
        if(A[i] < cb[index].first){
            sum += cb[index].first - A[i];
            cb[index].second--;
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 2560
#include <stdio.h>
int main(void){
	
	int m,f,r;
	
	while(1){
		scanf("%d %d %d",&m,&f,&r);
		if(m==-1 && f==-1 && r==-1)break;
		else if(m==-1 || f==-1)printf("F\n");
		else if((m+f)>=80)printf("A\n");
		else if((m+f)>=65)printf("B\n");
		else if((m+f)>=50)printf("C\n");
		else if((m+f)>=30){
			if(r>=50)printf("C\n");
			else printf("D\n");
		}else if((m+f)<30)printf("F\n");
	}
	
	return 0;
}


Measured memory_bytes: 2052
n = gets.to_i
a = []
a.push(gets.chomp)
frag = "Yes"
1.upto(n-1) do |i|
  s = gets.chomp
  0.upto(i) do |j|
    if s == a[j] 
      frag = "No"
    end
  end
  if (a[i-1].to_s)[-1] != s[0] 
    frag = "No"
  end
  a.push(s)
end
puts frag


Measured memory_bytes: 1788
#include <iostream>

typedef unsigned long long ullong;

int main( void )
{
    ullong depositAmount = 100;
    
    ullong  targetAmount;
    std::cin >> targetAmount;
    
    ullong year = 0;
    
    while ( depositAmount < targetAmount )
    {
        depositAmount += depositAmount/100;
        ++year;
    }
    
    std::cout << year << std::endl;
    return 0;
}

Measured memory_bytes: 3624
#include <stdio.h>

int main(void) {
    int N, K, d, A, b[105], x, i, j;
    scanf("%d%d", &N, &K);
    for (i=1; i<=N; i++) b[i]=1;
    for (i=1; i<=K; i++) {
        scanf("%d", &d);
        for (j=1; j<=d; j++) {
            scanf("%d", &A);
            b[A]=0;
        }
    }
    x=0;
    for (i=1; i<=N; i++) x+=b[i];
    printf("%d", x);
    return 0;
}


Measured memory_bytes: 1712
#include <iostream>
#include <vector>
using namespace std;
typedef vector<int> vi;
const int size=4000;
vi graph[size];
int lineDistances[size][size];
bool visited[size][size];
vi vertexA, vertexB;
int number, diameter;
void dfs(int root, int start, int distanceInLines)
{
	//commandsBeforeVisitRecursion.
	visited[root][start]=true;
	lineDistances[root][start]=distanceInLines;
	for(int next : graph[start])
	{
		if(!visited[root][next])
		{
			dfs(root, next, distanceInLines+1);
		}
	}
	//commandsAfterVisitRecursion.
	return;
}
void usingDFS()
{
	cin>>number>>diameter;
	int vertex0, vertex1;
	for(int i=1; i<number; ++i)
	{
		cin>>vertex0>>vertex1;
		graph[vertex0].push_back(vertex1);
		graph[vertex1].push_back(vertex0);
		vertexA.push_back(vertex0);
		vertexB.push_back(vertex1);
	}
	for(int vertex=1; vertex<=number; ++vertex)
	{
		dfs(vertex, vertex, 0);
	}
	if(diameter%2==0)
	{
		int minimum=40000;
		for(int i=1; i<=number; ++i)
		{
			int counter=0;
			for(int j=1; j<=number; ++j)
			{
				if(lineDistances[i][j]>diameter/2)
				{
					++counter;
				}
			}
			minimum=min(minimum, counter);
		}
		cout<<minimum<<endl;
	}
	else
	{
		int dotA, dotB, tempMaxDist, minimum=40000;
		for(int i=0; i<vertexA.size(); ++i)
		{
			int counter=0;
			dotA=vertexA[i];
			dotB=vertexB[i];
			for(int j=1; j<=number; ++j)
			{
				tempMaxDist=min(lineDistances[j][dotA], lineDistances[j][dotB]);
				if(tempMaxDist>diameter/2)
				{
					++counter;
				}
			}
			minimum=min(minimum, counter);
		}
		cout<<minimum<<endl;
	}
	return;
}
int main()
{
    usingDFS();
	return 0;
}

Measured memory_bytes: 42880
#include <iostream>

using namespace std;

int main()
{
    int a[104];
    int n,d,x,sum,i,j;
    cin>>n;
    cin>>d>>x;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sum=0;
    for(i=0;i<n;i++)
    {
        for(j=1;j<=d;j=j+a[i])
        {
            sum++;
        }
    }
    cout<<sum+x<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    int t = n%10;
    if(t==3){
        cout<<"bon"<<"\n";
    }   
    else if(t==0||t==1||t==6||t==8){
        cout<<"pon"<<"\n";
    }
    else{
        cout<<"hon"<<"\n";
    }
}

Measured memory_bytes: 3568
import sys
from bisect import bisect_right as bsr
from collections import Counter as cnt
from collections import defaultdict as dd
from collections import deque
from fractions import gcd
from itertools import permutations as perm
from math import ceil, factorial, floor
from operator import itemgetter as ig

sys.setrecursionlimit(1000000)

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)


def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]


def yesno(v, yes="Yes", no="No", upper=False):
    if upper:
        print([yes.upper(), no.upper()][not v])
    else:
        print([yes, no][not v])


def lcm(v1, v2):
    """最大公約数 / 最小公倍数"""
    return (v1 // gcd(v1, v2)) * v2


def main():
    """エントリーポイント"""
    A, B = input(int, int)
    print(lcm(A, B))


if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()


Measured memory_bytes: 5176
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s;
	getline(cin,s);
	int i,max=0,maxv=0;
	for(i=0;i<s.size();i++)
	{
		if(s[i]=='A'||s[i]=='C'||s[i]=='G'||s[i]=='T')  max++;
		else
		{
			if(max>maxv)  maxv=max;
			max=0;
		}
	}
	if(max>maxv)  maxv=max;
	cout<<maxv;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef vector<int> vi;
void riffle(vi &d,int c){
	vi A,B,C;
	A.insert(A.end(),d.begin()+d.size()/2,d.end()),
	B.insert(B.end(),d.begin(),d.begin()+d.size()/2);
	int a=A.size(),b=B.size();
	for(int i=0;i<a||i<b;i+=c){
		if(i<a)C.insert(C.end(),A.begin()+i,A.begin()+(i+c<a?i+c:a));
		if(i<b)C.insert(C.end(),B.begin()+i,B.begin()+(i+c<b?i+c:b));
	}
	d=C;
}
int main(){
	int n,r,c;
	while(cin>>n>>r){
		vi d(n); rep(i,n)d[i]=i;
		rep(i,r)cin>>c,riffle(d,c);
		cout<<d.back()<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include "bits/stdc++.h"

using namespace std;

void Main() {
    long long X;
    cin >> X;

    double rate = 0.01;
    double amount = 100.0;
    int year = 1;
    while (amount < X) {
        amount *= (1.0 + rate);
        amount = (double)(long long)amount;
        if (amount >= X) {
            break;
        }
        ++year;
    }
    cout << year << endl;
}

int main() {
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 3640
var toInt = x=>parseInt(x,10);
var toIntArr = arr=>arr.map(x=>toInt(x));
function min(){var rest = arguments,val=rest[0];for(var i=1;i<rest.length;i++)if(rest[i]<val)val = rest[i];return val}
function max(){var rest = arguments,val=rest[0];for(var i=1;i<rest.length;i++)if(rest[i]>val)val = rest[i];return val}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

function Main(input){
	var n = toInt(input);
	var pow = 1;
	var mod = Math.pow(10,9) + 7;
	for(var i = 1; i <= n; i++){
		pow = (pow*i)%mod;
	}
	console.log(pow);
}



Measured memory_bytes: 7500
n = gets.to_i
string = gets
arr = []
mod = n % 26
string.each_char do |st|
  val = st.ord + mod
  if val > 90
    arr.push(('A'.ord + val - 90 - 1).chr)
  else
    arr.push((st.ord + mod).chr)
  end
end

arr.pop

print arr.join('')


Measured memory_bytes: 2428
from collections import deque

N,Q=map(int,input().split())

tree=[[] for _ in range(N)]

for _ in range(N-1):
    A,B=map(int,input().split())
    tree[A-1].append(B-1)
    tree[B-1].append(A-1)

ans=[0 for _ in range(N)]
for j in range(Q):
    p,x=map(int,input().split())
    ans[p-1]+=x

#BFSで親のカウンターを子に継がせる
dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in tree[v]:
        if dist[w] > -1:
            continue
        que.append(w)
        dist[w]=d+1
        ans[w]+=ans[v]

print(*ans)

Measured memory_bytes: 62508
#pragma warning disable

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Runtime.Serialization.Formatters.Binary;
using System.Text;
using System.Text.RegularExpressions;
using System.Diagnostics;
using System.Numerics;
using System.Collections;

static class MainClass
{
    public static void Main(string[] args)
    {
        var str = Console.ReadLine();
        Console.WriteLine(700 + str.Count(x => x == 'o') * 100);
    }

    public static long f(long n,long b)
    {
        if (n < b)
        {
            return n;
        }
        else
        {
            return f((long)Math.Floor((double)n/b),b) + n % b;
        }
    }

    public static string N(long n,long b)
    {
        var sb = new StringBuilder();
        while (true)
        {
            sb.Append((n % b).ToString());
            n /= b;
            if (n < b)
            {
                sb.Append(n.ToString());
                break;
            }
        }
        return new string( sb.ToString().Reverse().ToArray() );
    }

    #region ライブラリ
    public static long ToInt64(this string str) => long.Parse(str);
    public static int ToInt32(this string str) => int.Parse(str);
    public static BigInteger ToBigInteger(this string str) => BigInteger.Parse(str);
    public static List<string> SplittedStringToList(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).ToList();
    public static List<int> SplittedStringToInt32List(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(x => int.Parse(x)).ToList();
    public static List<long> SplittedStringToInt64List(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(x => long.Parse(x)).ToList();
    public static List<BigInteger> SplittedStringToBigInteger(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(x => BigInteger.Parse(x)).ToList();
    public const int INF = int.MaxValue / 2;
    public const long LONGINF = long.MaxValue / 2;
    public const int Mod1e9 = 1000000007;
    

    public static void PrintArray(int[,] array)
    {
        for (int i = 0; i < array.GetLength(0); i++)
        {
            var sb = new StringBuilder();
            for (int j = 0; j < array.GetLength(1); j++)
            {
                sb.Append(array[i, j]).Append(" ");
            }
            Console.WriteLine(sb.ToString());
        }
    }

    #endregion
}



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

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

  if(n[0] == n[1] && n[1] == n[2] || n[1] == n[2] && n[2] == n[3] || n[0] == n[1] && n[1] == n[2] && n[2] == n[3]){
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define AC ios::sync_with_stdio(0),cin.tie(0);

int main()
{
    AC
    int n,w,r=0;
    cin>>n>>w;
    vector<ll> dp(100001,1e10);
    dp[0]=0;
    for(int i=0;i<n;i++)
    {
        int wei,val;
        cin>>wei>>val;
        for(int j=100000;j>=val;j--)
            dp[j]=min(dp[j],dp[j-val]+wei);
    }
    for(int i=1;i<dp.size();i++)
        if(dp[i]<=w) r=i;
    cout<<r<<'\n';
}

Measured memory_bytes: 3948
loop {
	n = gets.to_i
	if n == 0 then
		break
	end
	
	a = []
	n.times {
		a.push gets.to_i
	}

	m1 = -100001
	n.times { |i|
		s = 0
		m0 = -100001
		for j in i .. (n-1)
			s += a[j];
			if m0 < s then
				m0 = s
			end 
		end
		if m1 < m0 then
			m1 = m0
		end
	}
	puts m1
}

Measured memory_bytes: 6112
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const double PI2 = 8.0 * atan(1.0);

#define REP(i,n)	for(int i=0;i<(int)n;++i)
#define ALL(c)		(c).begin(),(c).end()
#define CLEAR(v)	memset(v,0,sizeof(v))
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define FOR(i,s,n)	for(int i=s;i<(int)n;++i)

int main(int argc, char **argv) {
	int n;
	string s, t;
	cin >> n >> s >> t;
	REP(i, n + 1) {
		bool f = true;
		REP(j, n - i) f &= (s[i + j] == t[j]);
		if (f) {
			cout << (n + i) << endl;
			break;
		}
	}
	return 0;
}


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

#define rep(i,a,b) for(ll i=a;i<b;i++)
#define pb push_back
#define lcm(a,b)     (a*b)/__gcd(a,b)
#define bs(v,x)      binary_search(v.begin(),v.end(),x)
#define ub(v,x)      upper_bound(v.begin(),v.end(),x)
#define lb(v,x)      lower_bound(v.begin(),v.end(),x)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(a) (a).begin(),(a).end() 
#define inp(a,n) for(ll i=0;i<n;i++) cin>>a[i];
#define trace(v) for(auto it=v.begin();it!=v.end();it++)cout<<*it<<" ";cerr<<endl;
#define printv(a,n) for(ll i=1;i<=n;i++) cout<<a[i]<<" "; cout<<"\n";
#define Pi 3.14159265
#define reset(x) memset(x,'z',sizeof(x))
#define f first
#define s second
//#define m make_pair
#define PII pair<ll, ll> 
#define pq1 priority_queue<ll>
#define pq2 priority_queue<ll, vector<ll>,greater<ll>>
typedef long long ll;
typedef vector<ll> vll;
typedef bool B;
typedef double ff;
const ll INF=1e10;
const ll N = 100005;
char en='\n';   
ll m[100001];
         void solve()
         {
            ll n,x,t;
            cin>>n>>x>>t;
            ll ans= ll(ceil(ff(n)/ff(x)))*t;
            cout<<ans;  
         } 
         int main() 
         { 
            ios_base::sync_with_stdio(false);cin.tie(NULL); 
            
            #ifndef ONLINE_JUDGE 
            freopen("input.txt", "r", stdin); 
            freopen("error.txt", "w", stderr); 
            freopen("output.txt", "w", stdout); 
            #endif 
            
            int t=1; 
            //cin>>t; 
            while(t--) 
            { 
               solve(); 
               cout<<"\n"; 
            } 
            
            cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<endl; 
            return 0; 
         }                 


Measured memory_bytes: 3916
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define repr(e,x) for(auto& e:x)
using namespace std;
typedef long long ll;
typedef long double ld;
//typedef pair<int,int> P;
//ll const INF=1001001001;
//ll const INF=1001001001001001001;
ll const MOD=1000000007;

ll N;
ll C[200001];
ll dp[200001];
ll cnt[200001];
ll last[200001];

int main(){
    cin>>N;
    repn(i,N) cin>>C[i];

    dp[0]=1;
    ll prev=-1;
    repn(i,N){
        dp[i]=dp[i-1];
        if(prev!=C[i]){
            cnt[C[i]]++;
            if(cnt[C[i]]>=2){
                dp[i]+=dp[last[C[i]]];
            }
            dp[i]%=MOD;
        }
        last[C[i]]=i;
        prev=C[i];
    }
    //repn(i,N) cout<<"i:"<<i<<" "<<dp[i]<<endl;

    cout<<dp[N]<<endl;
}

Measured memory_bytes: 9864
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<unordered_map>

using namespace std;
typedef pair<long long int, long long int> PP;

long long int INF = 1e18;
long long int MOD = 1e9 + 7;

vector<int> E[200];
int d[200] = {}, f[200] = {};

int func(int pos, int time){
  if(d[pos] > 0){
    return time;
  }
  d[pos] = time;
  time += 1;
  for(int to : E[pos]){
    time = func(to, time);
  }
  f[pos] = time;
  time += 1;
  return time;
}

int main(){
  int n;
  cin >> n;
  for(int loop = 0; loop < n; loop++){
    int u, k;
    cin >> u >> k;
    for(int i = 0; i < k; i++){
      int v;
      cin >> v;
      E[u].push_back(v);
    }
  }
  int time = 1;
  for(int i = 1; i <= n; i++){
    if(d[i] == 0){
      time = func(i, time);
    }
    cout << i << " " << d[i] << " " << f[i] << endl;
  }
  return 0;
}



Measured memory_bytes: 3164
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
typedef pair<double,double> P;

int main(){
  int N;
  P ansA=P(-1,-1),ansB=P(-1,-1);
  int F,A,T,X,Y;
  int f,a,t,x,y;
  cin>>N>>F>>A>>T>>X>>Y;
  for(int i=1;i<N;i++){
    cin>>f>>a>>t>>x>>y;
    if(T==t&&A!=a){
      P d=P( sqrt((X-x)*(X-x)+(Y-y)*(Y-y)) ,F-f);      
      if(t==0)ansA=max(ansA,d);
      else ansB=max(ansB,d);
    }
    F=f;A=a;T=t;X=x;Y=y;
  }
  if(ansA.first<0)printf("-1 -1\n");
  else printf("%.8f %.8f\n",ansA.first,-ansA.second/60.0);
  if(ansB.first<0)printf("-1 -1\n");
  else printf("%.8f %.8f\n",ansB.first,-ansB.second/60.0);
  return 0;
}

Measured memory_bytes: 1196
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
const ll INF = numeric_limits<ll>::max()/2;

struct Edge{ll from, to, cost;};
vector<Edge> es;
vector<ll> d(1111,INF);
vector<bool> negative(1111,false);
int n,m;

bool find_negative_loop(){
    d[0]=0;
    for(int j=0;j<n-1;j++){
        for(int i=0;i<m;i++){
            Edge e=es[i];
            if(d[e.from]!=INF&&d[e.to]>d[e.from]+e.cost){
                d[e.to]=d[e.from]+e.cost;
                
            }
        }
    }
    for(int j=0;j<n;j++){
        for(int i=0;i<m;i++){
            Edge e=es[i];
            if(d[e.from]!=INF&&d[e.to]>d[e.from]+e.cost){
                d[e.to]=d[e.from]+e.cost;
                negative[e.to]=true;
            }
            if(negative[e.from]) negative[e.to]=true;
        }
    }
    return negative[n-1];
}

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

    cin>>n>>m;
    for(int i=0;i<m;i++){
        ll a,b,c;cin>>a>>b>>c;
        a--; b--; c *= -1;
        es.push_back(Edge{a,b,c});
    }
    if(find_negative_loop()){
        cout<<"inf"<<endl;
        return 0;
    }
    cout<<-d[n-1]<<endl;
}


Measured memory_bytes: 384
import re
s = input()
s2 = s.replace("BC", "D")
ss = re.split("B|C", s2)
#print(ss)
r = 0
for s in ss:
  n = 0
  for c in s:
    if c == "A":
      n += 1
    if c == "D":
      r += n
print(r)


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

using namespace std;
#define all(x) (x).begin(),(x).end()

void solve(){
    int n,m;
    cin >> n >> m;
    vector<int> p(m),y(m);
    vector<vector<int>> data(n + 1);
    for (int i = 0; i < m; i++) {
        cin >> p[i] >> y[i];
        data[p[i]].push_back(y[i]);
    }

    for (int i = 0; i < n+1; i++) {
        //sort(all(v[p[i]]));
        sort(all(data[i]));
    }

    for (int i = 0; i < m; i++) {
        vector<int> &d = data[p[i]];
        int k = lower_bound(all(d), y[i]) - d.begin();

        printf("%06d%06d\n", p[i], k + 1);
    }

}

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


Measured memory_bytes: 7808
#include <stdio.h>

int isprime(int);

int main(){
  int i, n, x, count = 0;
  
  scanf("%d",&n);
  for(i = 0; i < n; i++){
    scanf("%d",&x);
    if(isprime(x) == 1){
      count++;
    }
  }
  printf("%d\n",count);
  
  return 0;
}

int isprime(int x){
  int i;
  
  if(x == 2)
    return 1;
  
  if(x < 2 || x % 2 == 0)
    return 0; 

  i = 3;
  while(i * i <= x){
    if(x % i == 0)
      return 0;
    i = i + 2;
  }
  return 1;
}




Measured memory_bytes: 2044
/**
 *
 * AtCoder Beginner Contest 100 - Problema D: Patisserie ABC (https://abc100.contest.atcoder.jp/tasks/abc100_d)
 *
 * Find the maximum number of operations that can be done in the given sequence. The multiply by
 * 3 can't be done in all elements and the results must be integers.
 *
 * Greedy solution: while there is one even number, divide it by 2 and multiply all others by 3.
 * This can be done for each factor 2 in each element (multiply by 3 don't add a new 2 factor and
 * divide by 2 eliminates one factor).
 */
#include <iostream>
#include <algorithm>

using namespace std;
using ll = long long;

const int MAX { 1010 };

ll xs[MAX], ys[MAX], zs[MAX], as[MAX];

void solve(int N, int M)
{
    ll ans = 0;

    for (int x = -1; x <= 1; x += 2)
    for (int y = -1; y <= 1; y += 2)
    for (int z = -1; z <= 1; z += 2)
    {
        for (int i = 0; i < N; ++i)
            as[i] = x*xs[i] + y*ys[i] + z*zs[i];

        sort(as, as + N, greater<ll>());

        ll sum = 0;

        for (int i = 0; i < M; ++i)
            sum += as[i];

        ans = max(ans, sum);
    }

    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false);

    int N, M;
    cin >> N >> M;

    for (int i = 0; i < N; ++i)
        cin >> xs[i] >> ys[i] >> zs[i];

    solve(N, M);

    return 0;
}


Measured memory_bytes: 256
import java.lang.reflect.Array;
import java.util.*;
public class Main{
	public static void main(String[] agrs){
		double m,h;
		Scanner sc=new Scanner(System.in);
		ArrayList<String> b=new ArrayList<String>();
		String a;double x,y,z;
		x=0.0;y=0.0;z=0.0;
		while(sc.hasNext()){	
			a=sc.next();
			if(a.equals("0,0"))break;
			String[]c=a.split(",");
			m=Double.parseDouble(c[0]);
			h=Double.parseDouble(c[1]);
			
			x+=(m*Math.sin(Math.toRadians(z)));
			y+=(m*Math.cos(Math.toRadians(z)));
			z+=h;
			}
		System.out.println((int)x);
		System.out.println((int)y);
		
			
		}
		
		
		
		
	}

Measured memory_bytes: 17124
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <algorithm>
#include <array>
#include <complex>
#include <string>
#include <utility>
#include <map>
#include <queue>
#include <list>
#include <functional>
#include <numeric>
#include <stack>
#include <tuple>

using namespace std;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
const int INF = 100000000;
const long long LINF = 1000000000000000000;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-6;
using pii = std::pair<int, int>;
using ll = long long;
using pLL = std::pair<ll, ll>;
#define SORT(v) std::sort(v.begin(), v.end())
#define RSORT(v) std::sort(v.rbegin(), v.rend())

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

    int n, x;
    cin >> n >> x;
    vector<int> L(n);
    for (int i = 0; i < n; ++i) {
        cin >> L[i];
    }
    int d = 0, dnext = 0;
    int ans = 1;
    for (int i = 1; i <= n; ++i) {
        dnext=d+L[i-1];
        if (dnext <= x)ans++;
        d = dnext;
    }
    cout << ans << endl;
    return 0;

}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	try {
    		final int N = sc.nextInt();
    		int K = sc.nextInt();
    		StringBuilder S = new StringBuilder(sc.next());
    		boolean firstTime = true;
    		int step = 1;

    		while (K > 0) {
    			StringBuilder T = new StringBuilder(S.toString());
    			T.reverse();
    			StringBuilder revU = new StringBuilder(S.toString() + T.toString());
    			revU.reverse();
    			String sDash = S.toString();
    			for (int i=N; i>=0; i-=step) {
    				String tmp = revU.substring(i, i+N);
    				if (sDash.compareTo(tmp) > 0) {
    					sDash = tmp;
    				} else {
    					if (!firstTime) {
        					break;
    					}
    				}
    			}
				if (firstTime) {
					firstTime = false;
					if (Math.pow(2, K) > N) {
						char c = sDash.charAt(0);
						for (int i=0; i<N; i++) {
							System.out.print(c);
						}
						System.out.println();
						System.exit(0);
					}
				} else {
					step += step;
				}

    			K--;
    			S = new StringBuilder(sDash);
    			S.reverse();
    		}
    		System.out.println(S.reverse());

    	} finally {
    		sc.close();
    	}
    }
/*
    public static int compareTo(String value, String anotherString, int step) {
        int len1 = value.length();
        int len2 = anotherString.length();
        int lim = Math.min(len1, len2);
        char v1[] = value.toCharArray();
        char v2[] = anotherString.toCharArray();

        int k = 0;
        while (k < lim) {
        	System.out.print(lim + " / ");
        	System.out.println(k);
            char c1 = v1[k];
            char c2 = v2[k];
            if (c1 != c2) {
                return c1 - c2;
            }
            k+=step;
        }
        return len1 - len2;
    }
    */
}



Measured memory_bytes: 49996
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
constexpr int inf=1e9+7;
constexpr ll longinf=1LL<<60 ;
constexpr ll mod=1e9+7 ;

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    vector<vector<int>> dist(n,vector<int>(n, inf));
    vector<int> a(m), b(m), c(m);
    rep(i,m){
        cin>>a[i]>>b[i]>>c[i];
        --a[i];--b[i];
        dist[a[i]][b[i]] = dist[b[i]][a[i]] = c[i];
    }
    rep(i,n)rep(j,n)rep(k,n)dist[j][k]=min(dist[j][k],dist[j][i]+dist[i][k]);
    int ans = 0;
    rep(i,m)ans += c[i] > dist[a[i]][b[i]];
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3564
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define erep(i,a,b) for(int i=a;i<=(int)(b);++i)
#define per(i,a,b) for(int i=(a);i>(b);--i)
#define eper(i,a,b) for(int i=(a);i>=b;--i)
#define pb push_back
#define mp make_pair
#define INF 100100100100
#define MOD 1000000007
#define ALL(x) begin(x),end(x)
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using vii = vector<int>;
using vll = vector<ll>;
template<class T>using vv = vector<T>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a, b)*b;}

int n, m, q, x[510][510], c[510][510];
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
    cin >> n >> m >> q;
    erep(i, 1, m) {
      int l, r; cin >> l >> r;
      x[l][r]++;
    }
    erep(i, 1, n) erep(j, 1, n) {
      c[i][j] = c[i][j-1] + x[i][j];
    }
    rep(i, 0, q) {
      int s, t;
      cin >> s >> t;
      int ans = 0;
      erep(j, s, t)
          ans += c[j][t] - c[j][s - 1];
      cout << ans << endl;
    }
    return 0;
}




Measured memory_bytes: 2944
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;

using namespace std;

const double PI = 3.14159265358979323846;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

double equal(double a, double b) {
    return fabs(a - b) < DBL_EPSILON;
}

std::istream &operator>>(std::istream &in, set<int> &o) {
    int a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
//const ll mod = 1e10;

typedef priority_queue<ll, vector<ll>, greater<ll> > PQ_ASK;

int main() {
    int n;
    cin >> n;
    vector<double> x, y;
    rep(i, n) {
        double a, b;
        cin >> a >> b;

        x.push_back(a);
        y.push_back(b);
    }

    rep(i, n) {
        vector<double> agl;
        rep(j, n) if (i != j) agl.push_back(atan2(y[j] - y[i], x[j] - x[i]));
        sort(agl.begin(), agl.end());
        agl.push_back(agl[0] + 2 * PI);
        double maxi = 0;
        for (int j = 1; j < agl.size(); j++) maxi = max(maxi, agl[j] - agl[j - 1] - PI);
        printf("%.20f\n", maxi / (2 * PI));
    }

}


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

struct edge{
    int to,weight;
    edge(int to,int weight):to(to),weight(weight){}
};
using Graph = vector<vector<int>> ;
using GraphEdge = vector<vector<int>> ;

long long modinv(long long a, long long m=MOD) {
    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;
    /*MODの割り算の際に
    a/＝b;
    を
    a *= modinv(b,MOD);
    とする。
        */
}

int jyun[100000000];
int N;
const ll maxN = 1000000001;
void list_tfs(vector<int> &G, ll tmp) {
    G.push_back(tmp);
    if(tmp*10+3<=N)list_tfs(G,(tmp*10+3));
    if(tmp*10+5<=N)list_tfs(G,(tmp*10+5));
    if(tmp*10+7<=N)list_tfs(G,(tmp*10+7));
    return;
}

int main(){
    cin >> N;
    vector<int> G;
    int num = 0;
    list_tfs(G,3);
    list_tfs(G,5);
    list_tfs(G,7);
    sort(G.begin(),G.end());
    int len = G.size();
    int count = 0;
    rep(i,len){
        int tmp = G[i];
        bool three=false, five=false, seven = false;
        while(tmp > 0){
            int tm = tmp%10;
            tmp/=10;
            if(tm==3)three=true;
            if(tm==5)five=true;
            if(tm==7)seven=true;
        }
        if(three && five && seven){
            count++;
        }
    }

    cout << count << endl;

    
    return 0;
}

Measured memory_bytes: 3704
#include <cstdio>
#include <cstring>
int main(){
 char ss[301];
 int h,w,i,j;
 while(true){
  scanf("%d %d",&h,&w);
  if((h==0)&&(w==0)) break;
  strcpy(ss,"#");
  for(i=0;i<w-2;i++)    strcat(ss,".");
  strcat(ss,"#\n");
  for(i=0;i<w;i++) printf("#");
  printf("\n");
  for(i=0;i<h-2;i++) printf(ss);
  for(i=0;i<w;i++) printf("#");
  printf("\n\n");
 }
 return 0;
}

Measured memory_bytes: 1032
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <string>
#include <random>
#include <stack>
#include <set>
#include <unordered_set>

#define bug(x) cout<<"zdongdebug: "<<x<<endl;
#define bug2(x, y) cout<<"zdongdebug: "<<x<<" "<<y<<endl;
using namespace std;
typedef long long ll;
const int maxn = 1005;

string s[maxn];
int a[maxn];
int ret[maxn];
int main() {
#ifdef suiyuan2009
  freopen("/Users/suiyuan2009/CLionProjects/icpc/input.txt", "r", stdin);
#endif
  int n;
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>s[i]>>a[i];
    ret[i]=i;
  }
  sort(ret+1,ret+n+1,[](int x,int y){
    if(s[x]!=s[y])return s[x]<s[y];
    return a[x]>a[y];
  });
  for(int i=1;i<=n;i++)cout<<ret[i]<<endl;
  return 0;
}

Measured memory_bytes: 256
//author : Yogi79

#include<bits/stdc++.h>
using namespace std;

long long n,x,m=0,p,y;

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

   cin>>n>>y;
   n--;
   long long w = n;
   
   while(n--)
   {
     cin>>x;
     
     if(x<=y)
     	p++;
     
     else
     	p = 0;
     
     if(p>m)
     	m = p;
     
     y = x;
   }
   if(w == 1)
   	cout<<0;
   else
   cout<<m;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int INF = 1e9+7;
int mod = 100000;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
signed main() {
    int N;
    cin >> N;
    vector<P>AB(N);
    for(int i = 0; i < N; i++) {
        int A,B;
        cin >> A >> B;
        AB[i].first = B;
        AB[i].second = A;
    }
    sort(AB.begin(),AB.end());
    int now = 0;
    for(int i = 0; i < N; i++) {
        now+=AB[i].second;
        if(now > AB[i].first) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}


Measured memory_bytes: 6392