akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
using namespace std;

int main(){
    int n, d[4];
    while(cin >> n){
        if(n == 0)  break;
        
        if(n % 1111 == 0){
            cout << "NA" << endl;
        }else{
            int tmpn = n;
            for(int i = 3; i >= 0; i--){
                d[i] = tmpn%10;
                tmpn /= 10;
            }
            
            int ans = 0;
            while(n != 6174){
                ans++;
                sort(d, d+4);
                n = (1000*d[3] + 100*d[2] + 10*d[1] + d[0]) -
                        (1000*d[0] + 100*d[1] + 10*d[2] + d[3]);
                tmpn = n;
                for(int i = 3; i >= 0; i--){
                    d[i] = tmpn%10;
                    tmpn /= 10;
                }
            }
            
            cout << ans << endl;
        }
    }
    return 0;
}



Measured memory_bytes: 3144
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define REP(i, l, r) for (int i=(l); i<(r); ++i)
#define RREP(i, r, l) for (int i=(r); i>(l); --i)
#define CASET int _T; cin >> _T; REP(caset, 0, _T)
#define print(x) cout << to_string(x) << '\n'
#define vi vector<int>
#define vb vector<bool>
#define vs vector<string>
#define vvi vector<vi>
#define vvb vector<vb>
#define pii pair<int,int>
#define t3i tuple<int,int,int>
#define mii map<int,int>
#define vpii vector<pii>
#define vt3i vector<t3i>
#define sq(x) (x)*(x)
#define inv(x) powa(x, MOD-2)
 
long long INF = 1LL<<60;
long long MOD = 998244353;

string to_string(char &c) {string x(1, c); return x;}
string to_string(const char s[]) {return (string)s;}
string to_string(string &s) {return s;}
string to_string(vb &v) {string res; for (const bool &x : v) res += to_string(x) + ' '; return res;}
template <class C> string to_string(C &v) {string res; for (auto &x : v) res += to_string(x) + ' '; return res;}
template <typename A, typename B> istream &operator>>(istream &is, pair<A, B> &pr) {is >> pr.first >> pr.second; return is;}
template <typename A> istream &operator>>(istream &is, vector<A> &v) {for (auto &x : v) is >> x; return is;}
ostream &operator<<(ostream &os, char &c) {os << (char)c; return os;}
ostream &operator<<(ostream &os, const char s[]) {os << (string)s; return os;}
ostream &operator<<(ostream &os, string &s) {for (char &c : s) os << (char)c; return os;}
template <typename A, typename B> ostream &operator<<(ostream &os, pair<A, B> pr) {os << '(' << pr.first << ", " << pr.second << ')'; return os;}
ostream &operator<<(ostream &os, vb &v) {
    bool first = true;
    os << '[';
    for (const bool &x : v) {
        if (!first) os << ", ";
        first = false;
        os << x;
    }
    os << ']';
    return os;
}
template <class C> ostream &operator<<(ostream &os, C &v) {
    bool first = true;
    os << '[';
    for (auto &x : v) {
        if (!first) os << ", ";
        first = false;
        os << x;
    }
    os << ']';
    return os;
}
string bin_string(int x) {
    const int d = 32;
    string res(d, ' ');
    REP(i, 0, d) res[d-1-i] = '0'+(x>>i & 1LL);
    return res;
}
int powa(int base, int exp) {
    int res = 1;
    while (exp) {
        if (exp&1) res = res*base % MOD;
        base = base*base % MOD;
        exp >>= 1;
    }
    return res;
}

main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int n;
    cin >> n;
    
    vvi c(10, vi(10));
    REP(i, 1, n+1) {
        string istr = to_string(i);
        ++c[istr[0]-'0'][istr.back()-'0'];
    }

    int res = 0;
    REP(d, 1, 10) REP(e, 1, 10) {
        res += c[d][e]*c[e][d];
    }
    print(res);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = (s); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for(int i = (n); i >= 0; i--)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << '\n';
#define CFYN(n) cout << ( (n) ? "YES":"NO") << '\n';
#define OUT(n) cout << (n) << '\n';
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int main(void)
{
    IOS
    int n, m;
    cin >> n >> m;
    string s; cin >> s;
    int i = n;
    vector<int> ans;

    while(true) {
        if (i <= m) {
            ans.push_back(i);
            break;
        }
        bool ng = true;
        for (int j = m; j > 0;j--) {
            if (s[i-j] == '0') {
                ans.push_back(j);
                i -= j;
                ng = false;
                break;
            }
        }
        if (ng) {
            OUT(-1)
            return 0;
        }
    }

    reverse(ALL(ans));
    REP(i,ans.size()) cout << ans[i] << " ";

    return 0;
}

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

int main() {
  ll n,k;
  cin >> n >> k;
  vector<ll>a(n);
  rep(i,n){
    cin >> a[i];
  }
  rep(i,n-k){
    if(a[i]<a[k+i]){
      cout << "Yes" << endl;
    }
    else{
      cout << "No" << endl;
    }
  }
  return 0;
}



Measured memory_bytes: 4844
//
//  main.cpp
//  ervb
//
//  Created by Kanak Gautam on 21/04/20.
//  Copyright © 2020 Kanak Gautam. All rights reserved.
//
 
 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#define pb push_back
#define mk make_pair
#define endl "\n"
#define mod 1000000007
using namespace std;
typedef long long int lli;
typedef long double ld;
priority_queue <lli, vector<lli>, greater<lli> > ti;
vector <lli> p[500005],g[500005],f(500005,0),b(500005,0),a(500005,0),ans(500005,0);
map <pair<lli,lli>,lli> mp;
set<pair<lli, lli> > s;
set<lli> st;
map<lli,lli> np,v;
queue<lli> qy;
lli n,q;
lli gcd(lli a, lli b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
      
}
lli bpow(lli a, lli b) {
    lli res = 1;
    while (b > 0) {
        if (b & 1)
            res = (res * a)%mod;
        a = (a * a)%mod;
        b >>= 1;
    }
    return res%mod;
}
lli fact(lli i)
{
    f[0]=1;
    for(lli k=1;k<=i;k++)
    {
        (f[k]=f[k-1]*k)%=mod;
    }
    return f[i];
}
lli isprime(lli n)
{
    if(n==1)
        return 0;
    for(lli i=2;i<=sqrt(n);i++)
        if(n%i==0)
            return 0;
    return 1;
}
bool cmp(lli i,lli j)
{
    return p[i].size()<p[j].size();
}
/*void sieve()
{
    for(lli i=2;i<=5000000;i++)
    {
        if(b[i]==0)
        {
        for(lli j=2;i*j<=5000000;j++)
        {
            b[i*j]=1;
        }
        }
    }
}*/
int main ()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    lli x,k,d;
    cin>>x>>k>>d;
    x=abs(x);
    lli m=x/d;
    lli f=m;
    lli o=m+1;
    lli g=x-d*f;
    lli h=x-d*o;
    if(k%2==f%2 && k>=f)
    {
        cout<<abs(g)<<endl;
    }
    else if(k%2 == o%2 && k>=o)
    {
        cout<<abs(h)<<endl;
    }
    else
    {
        cout<<abs(x-k*d)<<endl;
    }
}


Measured memory_bytes: 42176
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)

N, Q = map(int, input().split())
repn = [[] for i in range(N)]

for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    repn[a].append(b)
    repn[b].append(a)

count = [0] * N

## analysis of tree structure
parent = [-1] + ['nul'] * (N - 1)
child = [[] for i in range(N)]
child[0] = repn[0]

for v in child[0]:
    parent[v] = 0

deq = deque(repn[0])

while deq:
    v = deq.popleft()
    for w in repn[v]:
        if parent[v] == w:
            pass
        else:
            parent[w] = v
            child[v].append(w)
            deq.append(w)


## soltion
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    count[p] += x
    
deq = deque([0])
while deq:
    v = deq.popleft()
    for w in child[v]:
        count[w] += count[v]
        deq.append(w)



print(' '.join(map(str, count)))


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

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

int main(void){

    int N; cin >> N;
    map<int, string> cont;
    rep(i, N) cin >> cont[i];

    int ac=0, wa=0, tle=0, re=0;
    rep(i, N){
        if(cont.at(i) == "AC") ac++;
        else if(cont.at(i) == "WA") wa++;
        else if(cont.at(i) == "TLE") tle++;
        else re++;
    }

    cout << "AC x " << ac << endl;
    cout << "WA x " << wa << endl;
    cout << "TLE x " << tle << endl;
    cout << "RE x " << re << endl;

    return 0;
}

Measured memory_bytes: 11396
// Brute Force
#include <stdio.h>
#define N   20
#define Q   200

int A[N], M[Q], n;

int solve(int index, int sum) {
	if (index == n || sum == 0) {
		return sum == 0;
	} else if (sum >= A[index + 1] 
		&& solve(index + 1, sum - A[index + 1])) {
		return 1;
	} else {
		return solve(index + 1, sum);
	}
}

int main(void) {
	int i, j, q;

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

	for (i = 0; i < q; i++) {
		if (solve(-1, M[i])) {
			printf("yes\n");
		} else {
			printf("no\n");
		}
	}

	return 0;
}

Measured memory_bytes: 580
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

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

using namespace std;

typedef long long int lli;
typedef unsigned long long int ulli;

typedef map<string,int> msi; 
typedef map<int,int> mii;

typedef stack<int> si;
typedef stack<string> ss;
typedef stack<bool> sb;

typedef queue<int> qi;
typedef queue<string> qs;
typedef queue<bool> qb;

typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<bool> vb;

void f3(){

}


void f2(){

}

void f1(){

}
 

int main(){
	int a, b;
	scanf("%d%d", &a, &b);

	int cur = 1;
	int ans = 0;
	while(cur < b){
		ans++;
		cur += a-1;
	}
	printf("%d\n", ans);


	return 0;
}




Measured memory_bytes: 256
#include <iostream>

using namespace std;
int main(){
    string inp;
    cin >> inp;
    int a = (inp[0]-'0')*10+(inp[1]-'0') ,b =(inp[2]-'0')*10+(inp[3]-'0');
    if(a!=0 && b!=0){
        if(a<=12 && b>12){
            cout<< "MMYY";
        }
        else if(a>12 && b <=12){
            cout << "YYMM";
        }
        else if(a<=12 && b <= 12) {
            cout<< "AMBIGUOUS";
        }
        else if(a>12 && b > 12){
            cout<< "NA";
        }

    }
    else{
        if(a==0 &&b ==0){
            cout<<"NA";
        }
        else if(a==0 && b <=12){
            cout<< "YYMM";
        }
        else if(a<=12 && b==0){
            cout<< "MMYY";
        }
        
        else{
            cout<<"NA";
        }
    }
    return 0;
}


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

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

    string s;
    cin >> s;

    if (s.size() == 1 || s.size() % 2 != 0) {
        cout << "No" << endl;
        return 0;
    }

    // inspec h or i
    map<char, int> mp;
    for (auto ch : s) {
        if (!(ch == 'h' || ch == 'i')) {
            cout << "No" << endl;
            return 0;
        }

        if (mp.find(ch) != mp.end()) {
            mp[ch]++;
        } else {
            mp[ch] = 1;
        }
    }

    if (mp['h'] != mp['i']) {
        cout << "No" << endl;
        return 0;
    }

    for (int i = 0; i < s.size() / 2; i += 2) {
        if (!(s[i] == 'h' && s[i + 1] == 'i')) {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return
#define lb(v,n) lower_bound(v.begin(),v.end(),n)
#define ub(v,n) upper_bound(v.begin(),v.end(),n)
#define mae(v) max_element(v.begin(),v.end())
#define mie(v) min_element(v.begin(),v.end())
#define INF 0x7FFFFFFF
#define mod 1000000007
typedef long long ll;
////////////////////////////////////////////////////////////

int main(){
	int a;
	cin >> a;
	if( a % 2 ){
		cout << "Hello World" << endl;
	}
	else{
		int b,c;
		cin >> b >> c;
		cout << b + c << endl;
	}
	ret 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#include<cmath>
#include<cstdint>
// 多倍長整数型
/* ---------------------- ここから ---------------------- */
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;
// 任意長整数型
using Bint = mp::cpp_int;
// 仮数部が1024ビットの浮動小数点数型(TLEしたら小さくする)
using Real = mp::number<mp::cpp_dec_float<1024>>;
/* ---------------------- ここまで ---------------------- */
 
#define INF 1e9
#define LINF 1e18
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)
     
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<ll, ll>;
     
const ll MOD = 1e9 + 7;
const ll ZER = 0;


int main(){
  ll h, w;
  cin >> h >> w;
  ll res;
  if(h % 3 == 0 || w % 3 == 0){
    res = 0;
  }
  else {
    res = min(h, w);
    rep(i, h - 1){
      ll bg = w * (i + 1), sm1 = (h - i - 1) * (w / 2), sm2 = (h - i - 1) * (w - w / 2);
      chmin(res, max({bg, sm1, sm2}) - min({bg, sm1, sm2}));
    }
    rep(i, w - 1){
      ll bg = h * (i + 1), sm1 = (w - i - 1) * (h / 2), sm2 = (w - i - 1) * (h - h / 2);
      chmin(res, max({bg, sm1, sm2}) - min({bg, sm1, sm2}));
    }
  }
  cout << res << endl;
}
 

Measured memory_bytes: 3604
# coding:utf-8
while True:
    cnt = 0
    n,x = map(int, raw_input().split())
    if n == 0 and x == 0:
        break
    for i in range(1,n+1):
        for j in range(1,n+1):
            for k in range(1,n+1):
                if i < j and j < k and i + j + k == x:
                    cnt += 1
    print cnt



Measured memory_bytes: 4644
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<map>
using namespace std;
int main() {
  int n,m,a[200005]={},b[200005]={};
  cin >> n >> m;
  for(int i=0; i<m; i++) {
    int c,d;
    cin >> c >> d;
    if(c==1) {
      b[d]++;
    }
    if(d==n) {
      b[c]++;
    }
  }
  for(int i=1; i<=n; i++) {
    if(b[i]==2) {
      cout << "POSSIBLE" << endl;
      return 0;
    }
  }
  cout << "IMPOSSIBLE" << endl;
}


Measured memory_bytes: 1024
N,X=map(int, input().split())
x=list(map(int, input().split()))

def gcd(a,b):
    while b:
        a,b=b,a%b
    return a

x.append(X)
y=sorted(x)
z=[]
for i in range(N):
    z.append(y[i+1]-y[i])
Min=z[0]
for i in range(N-1):
    if Min>gcd(z[i],z[i+1]):
        Min=gcd(z[i],z[i+1])
print(Min)


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

int main(void)
{
    int N,c[3][3],a[3],b[3];
    bool flag =true;
    

    rep(i, 3){
        rep(j,3){
            cin >> c[i][j];
        }
    }

    for(int k = -100;k<=100;k++){
        a[0] = k;
        b[0] = c[0][0]-k;

        for(int i = 1;i < 3;i++){
            a[i] = c[i][0]-b[0];
        }

        
        for(int j = 1;j <3;j++){
            b[j] = c[0][j]-a[0];
        }

        for(int i = 1;i < 3;i++){
            for(int j = 1;j < 3;j++){
                if(a[i]+b[j] != c[i][j]){
                    flag = false;
                }
            }
        }
    }

    if(flag)
        cout << "Yes" << endl;

    else
        cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <cstdio>
#include <cstring>
#define N 200005
using namespace std;

int n, k, c, c1, ba, gc, a[N], gr[N], mn[N * 4], mx[N * 4];

int fmn(int p, int q) {
	int re = 1e9;
	while (p < q) {
        if (p % 2 == 1) re = min(re, mn[p]), p++;
        if (q % 2 == 0) re = min(re, mn[q]), q--;
        p /= 2, q /= 2;
	}
	if (p == q) re = min(re, mn[p]);
	return re;
}

int fmx(int p, int q) {
	int re = 0;
	while (p < q) {
        if (p % 2 == 1) re = max(re, mx[p]), p++;
        if (q % 2 == 0) re = max(re, mx[q]), q--;
        p /= 2, q /= 2;
	}
	if (p == q) re = max(re, mx[p]);
	return re;
}

int main()
{
	int i;
	cin >> n >> k;
	for (i = 0; i < n; i++) scanf("%d", &a[i]);
	gr[0] = 0;
	for (i = 1; i < n; i++) {
		if (a[i] < a[i - 1]) gc++;
		gr[i] = gc;
	}
	for (i = 0; i <= n - k; i++) {
		if (gr[i] == gr[i + k - 1]) c1++;
	}
	c1 = max(0, c1 - 1);
	c = n - k + 1;
	for (ba = 1; ba < n; ba *= 2);
	memset(mn, 0x3f, sizeof(mn));
	memset(mx, 0, sizeof(mx));
	for (i = 0; i < n; i++) mn[ba + i] = mx[ba + i] = a[i];
	for (i = ba - 1; i > 0; i--) mn[i] = min(mn[i * 2], mn[i * 2 + 1]), mx[i] = max(mx[i * 2], mx[i * 2 + 1]);
	for (i = 0; i < n - k; i++) {
		if (gr[i] != gr[i + k] && fmn(ba + i, ba + i + k - 1) == a[i] && fmx(ba + i + 1, ba + i + k) == a[i + k]) c--;
	}
    cout << c - c1 << endl;
    return 0;
}

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



int32_t main(){
    int n;cin>>n;
    vector<int> v(n);
    map<int,int> mp;
    for(int &i: v)cin>>i,mp[i]++;
    int q;cin>>q;
    int curr_sum=accumulate(v.begin(),v.end(),0ll);
    while(q--){
        int x,y;cin>>x>>y;
        if(mp.count(x)!=0){
            curr_sum-=(mp[x]*x);
            curr_sum+=(mp[x]*y);
            mp[y]+=mp[x];
            mp.erase(x);
        } 

        cout<<curr_sum<<"\n";

    }
    return 0;
}

Measured memory_bytes: 7956
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<deque>
#include<cmath>
#include<map>
#include<cstring>

using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LLINF = 1LL<<60;
#define P pair<ll, ll>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define print(x) cout << (x) << endl

class mint {
    long long x;
public:
    mint(long long x=0) : x((x%MOD+MOD)%MOD) {}
    mint operator-() const {
      return mint(-x);
    }
    mint& operator+=(const mint& a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator-=(const mint& a) {
        if ((x += MOD-a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator*=(const  mint& a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint operator+(const mint& a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint& a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint& a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    // for prime MOD
    mint inv() const {
        return pow(MOD-2);
    }
    mint& operator/=(const mint& a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint& a) const {
        mint res(*this);
        return res/=a;
    }

    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.x;
        return os;
    }
};

/* -- template -- */

int main() {
    int N, M; cin >> N >> M;
    ll H[N];
    rep(i, N) cin >> H[i];
    vector<vector<int>> G(N);
    rep(i, M) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        G[a].pb(b);
        G[b].pb(a);
    }
    int ans = 0;
    rep(i, N) {
        bool flg = true;
        for(int next : G[i]) {
            if(H[i] <= H[next]) {
                flg = false;
                break;
            }
        }
        if(flg)++ans;
    }
    cout << ans << endl;
}


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

#define ll long long

int n;
ll tab [3007];
ll dp [3][3007][3007];

int main(){
    scanf("%d",&n);
    for(int i = 1; i <= n; i++){
        scanf("%lld",&tab[i]);
        dp[0][i][i] = -tab[i];
        dp[1][i][i] = tab[i];
    }

    for(int d = 1; d <= n; d++){
        for(int i = 1; i <= n - d; i++){
            dp[0][i][i + d] = min(dp[1][i][i + d - 1] - tab[i + d], dp[1][i + 1][i + d] - tab[i]);
            dp[1][i][i + d] = max(tab[i + d] + dp[0][i][i + d - 1], tab[i] + dp[0][i + 1][i + d]);
        }
    }
    printf("%lld\n",dp[1][1][n]);
    return 0;
}


Measured memory_bytes: 141568
#include<bits/stdc++.h>
using namespace std;
#define Union(x,y) fa[Find(x)]=Find(y)//合并
int n,m,fa[200003],ans=-(1<<30),s=1,a[200003];
int Find(int x){//路径压缩
    return x==fa[x]?x:fa[x]=Find(fa[x]);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) fa[i]=i;//初始化
    while(m--){
        int a,b;scanf("%d%d",&a,&b);
        int roota=Find(a),rootb=Find(b);
        if(roota!=rootb) Union(a,b);//这样做可以避免重复的操作
    }
    for(int i=1;i<=n;i++) a[i]=Find(fa[i]);
    //因为这种写法同一个集合中的fa[]值可能不一样，所以用a[i]表示fa[i]属于哪个集合
    sort(a+1,a+1+n);//把a从小到大排序
     //for(int i=1;i<=n;i++)  cout<<a[i]<<" ";
    for(int i=2;i<=n;i++){
        if(a[i]==a[i-1]) ++s;//s表示当前集合的元素数
        else ans=max(ans,s),s=1;//ans表示最大的集合的元素数
    }
    printf("%d\n",max(ans,s));
    //这里s可能还有值，所以需要再与ans比较，取最大的输出
    return 0;
}

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

#ifdef LOCAL_DEBUG
  #include "LOCAL_DEBUG.hpp"
#endif

template <class T>
vector<vector<T>> rot_90(vector<vector<T>> cur){
  int H = cur.size();
  int W = cur[0].size();
  vector<vector<T>> rot(W,vector<T>(H));
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      rot[W-1 - j][i] = cur[i][j];
    }
  }
  return rot;
}

signed main(){

  int H,W; cin >> H >> W;
  vector<vector<char>> table(H,vector<char>(W));
  for(int i = 0; i < H; i++){
    string s; cin >> s;
    for(int j = 0; j < W; j++){
      table[i][j] = s[j];
    }
  }

  vector<vector<int>> dp(H,vector<int>(W,0));
  for(int k = 0; k < 4; k++){
    for(int i = 0; i < H; i++){
      int cnt = 0;
      for(int j = 0; j < W; j++){
        if(table[i][j] == '.') cnt++;
        else cnt = 0;
        dp[i][j] += cnt;
      }
    }
    table = rot_90(table);
    dp = rot_90(dp);
    swap(H,W);
  }

  int ans = 0;
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      ans = max(ans,dp[i][j]);
    }
  }
  cout << max(0LL,ans-3) << endl;

  return 0;
}


Measured memory_bytes: 98304
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
 int q,p,w[1000001],u[1000001],o;
 string a;
 int main()
 {
     cin>>a;
     for (int i=0;i<a.size();i++)
     {
         if (a[i]=='C') 
         {
             p++;
             u[p]=i+1;
         }
         else if (a[i]=='F')
         {
            q++;
             w[q]=i+1;
         }
     }
     if (q>=1 && p>=1)
     {
     for (int i=1;i<=p;i++)
     {
         for (int j=1;j<=q;j++)
         {
             if (u[i]<w[j])
             {
                 o=1;
             }
         }
     }
	 if (o==1) cout<<"Yes"<<endl;
     else cout<<"No"<<endl;	
     }
     else cout<<"No"<<endl;
     
     
 }

Measured memory_bytes: 2304
import java.util.*;
public class Main{
  public static void main(String[]args){
      Scanner sc = new Scanner(System.in);

      int a = sc.nextInt();
      int b = sc.nextInt();
      int c = sc.nextInt();
      int d = sc.nextInt();

      if (Math.min(b,d)-Math.max(a,c)>0) {
        System.out.println(Math.min(b,d)-Math.max(a,c));
      }else{
        System.out.println(0);
      }


  }
}


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

int main()
{

    string s = "";
    cin>>s;

    int num = 0 ;

    int len = ceil(s.length()/2.0);
    for(int i = 0 ; i<len ; i++)
    {
        if(s[i]!=s[s.length()-i-1])
            {
                num++;

            }
    }

    cout<<num<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>

#include<cstdio>

using namespace std;

int main(){

  int a,b,c,n;

  cin>>a>>b>>c;

  if(a>b){
    n=a,a=b,b=n;
      }
  if(b>c){
    n=b,b=c,c=n;
  }
  if(a>b){
    n=a,a=b,b=n;
  }

  cout<<a<<" "<<b<<" "<<c<<endl;



  return 0;
}

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

using namespace std;


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

    vector<int> dp(n+1, 0);

    dp[0] = 1, dp[1] = 1;

    for(int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }

    cout << dp[n] << endl;
	return 0;
}


Measured memory_bytes: 3080
#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>;

int64_t gcd(int64_t a, int64_t b) {
    return b ? gcd(b, a%b) : a;
}

int main() {
    int64_t n, k;
    cin >> n >> k;
    int64_t ans = min(n%k, k-n%k);
    cout << ans << endl;
}

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

int main(){
	using namespace std;
// 	ios_base::sync_with_stdio(false); 
//     cin.tie(NULL); 

// #ifndef ONLINE_JUDGE 
//     freopen("inputf.in", "r", stdin); 
//     freopen("outputf.in", "w", stdout); 
// #endif

	using ll = long long;

	int n, W;
	cin >> n;
	cin >> W;

	vector<ll> dp(W + 1);

	for(int item = 0; item < n; item++) {
		ll weight, value;
		cin >> weight;
		cin >> value;

		for(int i = W - weight; i >= 0; i--) {
			dp[i + weight] = max(dp[i + weight], dp[i] + value);
		}
	}

	ll mx = 0;
	for(int i = 0; i <= W; i++) {
		mx = max(mx, dp[i]);
	}

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


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

#define int long long int

int32_t main()
{
	int n;
	cin >> n;
	pair<int, int>a[n];

	for (int i = 0; i < n; i++)
		cin >> a[i].first >> a[i].second;
	int flag = 0;
	for (int i = 0; i + 2 < n; i++)
	{
		if (a[i].first == a[i].second && a[i + 1].first == a[i + 1].second && a[i + 2].first == a[i + 2].second)
		{
			cout << "Yes" << endl;
			flag = 1;
			break;
		}
	}
	if (flag == 0)
		cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 3636
/**OOO**/
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long ull;
using namespace std;


#define mems(arr,VAL)           memset(arr,VAL,sizeof(arr))
#define pii                     pair<int,int>
#define mk                      make_pair
#define pb                      push_back
#define ff                      first
#define ss                      second
#define PI                      acos(-1.0)

#define pf                      printf
#define sc                      scanf
//#define Mod                     1000000007
#define hiii                    1e9//1000000000
#define looo                   -1e9//-1000000000
#define NMAX                    100005




int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll n , k , sum = 0 ;
    vector<ll>h ;
    cin >> n >> k ;
    for(ll i = 0 ; i<n ; i++){
        ll x ; cin >> x ;
        h.pb(x) ;
    }
    sort(h.rbegin() , h.rend()) ;
    for(ll i = k ; i<h.size() ; i++){
        sum+=h[i] ;
    }
    cout << sum << endl ;


//cout << double( clock() - startTime ) / (double)CLOCKS_PER_SEC<< " seconds." << endl;
return 0;
}




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

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

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    int flg = 1;
    if(n == m) flg = 2;
    if(abs(n - m) > 1) cout << 0 << '\n';
    else{
        int ac = 1,bc = 1;
        for(int i=1;i<=n;i++){
            ac *= i ; 
            ac = ac % (1000000000+7);
        }
        for(int i=1;i<=m;i++){
            bc *= i;
            bc = bc % (1000000000+7);
        }
        cout << ac * bc * flg  % (1000000000+7) <<'\n';
    }   

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep0(i,n) for(ll (i) = 0; (i) < (n); ++(i))
#define rrep0(i,n) for(ll (i) = (n) - 1; (i) >= 0; --(i))
#define rep1(i,n) for(ll (i) = 1; (i) < (n); ++(i))
#define rrep1(i,n) for(ll (i) = (n) - 1; (i) >= 1; --(i))
#define nfor(i,a,b) for(ll (i) = (a); (i) < (b); ++(i))
#define ll long long
#define mod (1000000007)
#define YES cout << "YES" << endl;
#define Yes cout << "Yes" << endl;
#define yes cout << "yes" << endl;
#define NO cout << "NO" << endl;
#define No cout << "No" << endl;
#define no cout << "no" << endl;
#define all(x) (x).begin(),(x).end()

ll gcd(ll a,ll b){
    if(b == 0) return a;
    return gcd(b,a%b);
}

ll lcm(ll a,ll b){
    ll g = gcd(a,b);
    return a / g * b;
}

ll fac(ll n){
    ll t = 1;
    rep1(i, n + 1)t *= i;
    return t;
}

int main()
{
    ll n,m,a,b;
    cin >> n >> m;
    vector<bool> c(n),d(n);
    rep0(i, m){
        cin >> a >> b;
        if (a == 1) {
            c[b] = true;
        }
        if (b == n) {
            d[a] = true;
        }
    }
    rep0(i, n){
        if (c[i] && d[i]) {
            cout << "POSSIBLE" << endl;
            return 0;
        }
    }
    cout << "IMPOSSIBLE" << endl;
    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor

def main():
    #N, M = map(int, input().split())
    r, D, x = map(int, input().split())

    for i in range(10):
        x = r * x - D
        print(x)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3444
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i <= (n); ++i)
#define rrep(i, n) for (ll i = (n - 1); i >= 0; --i)
#define perm(c) sort(ALL(c));for(bool c##p=1;c##p;c##p=next_permutation(ALL(c)))
#define ALL(obj) (obj).begin(), (obj).end()
#define pb push_back
#define to_s to_string
#define len(v) (ll)v.size()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define print(x) cout << (x) << '\n'
#define debug(x) cout << #x << ": " << (x) << '\n'
using namespace std;
using ll = long long;
typedef pair<ll, ll> P;
typedef vector<ll> vec;
typedef vector<vector<ll>> vec2;
typedef vector<vector<vector<ll>>> vec3;
ll MOD = 1e9 + 7;
ll devc(ll x, ll y) { return 1 + (x - 1) / y; }
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 main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);

    string S;
    cin >> S;
    ll N = len(S);

    vec2 f(N + 1, vec(4, 0));
    f[0][0] = 1;

    rep1(i,N){
        char now = S[i - 1];
        rep(j, 4) f[i][j] = f[i - 1][j];
        if(now == 'A' || now == '?') f[i][1] += f[i - 1][0];
        if(now == 'B' || now == '?') f[i][2] += f[i - 1][1];
        if(now == 'C' || now == '?') f[i][3] += f[i - 1][2];
        if(now == '?') rep(j, 4) f[i][j] += f[i - 1][j] * 2;
        rep(j, 4) f[i][j] %= MOD;
    }

    print(f[N][3]);

    return 0;
}

Measured memory_bytes: 7376
import java.util.Scanner;

public class Main{
  public static void main(String[] args){
    Scanner scanner = new Scanner(System.in);
    int N = scanner.nextInt();
    int[] dp = new int[100010];
    dp[0] = 0;
    for (int i = 1; i < 100010; i++){
      dp[i] = i;
    }
    int[] coins = {1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049};

    for (int i = 0; i < 100010; i++){
      for (int j = 0; j < 12; j++){
        if(i-coins[j] < 0) continue;
        dp[i] = Math.min(dp[i - coins[j]] + 1, dp[i]);
      }
    }
    System.out.println(dp[N]);
  }
}

Measured memory_bytes: 23764
pre_x, pre_y, pre_z = None,None,None
for i in range(3):
  x,y,z = map(int, input().split())
  if pre_x is None:
    pre_x, pre_y, pre_z = x,y,z
  else:
    if pre_y-pre_x!=y-x or pre_z-pre_y!=z-y or x-pre_x!=y-pre_y or y-pre_y!= z-pre_z:
      print('No')
      break
else:
  print('Yes')
  

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define INF 1000000000
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repX(i, n ,x) for (int i = x; i < (int)(n); i++)
#define repM(i, n) for (int i = n; i > 0; i--)


int main() {
    int K;
    cin >> K;
    vector<ll> a;
    for(int i = 1; i <= 9; i++) a.push_back(i);
    while(true) {
        if(a.size() >= K){
            cout << a[K-1] << endl;
            return 0;
        }
        K -= a.size();
        vector<ll> old;
        swap(old,a);
        for(ll x : old){
            repX(i,2,-1){
                int last = x%10 +i;
                if(last < 0 || last > 9)continue;
                a.push_back(x*10+last);
            }
        }
    }

    return 0;
}

Measured memory_bytes: 1712
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
#define repr(i, n) for (int i = (int)n - 1; i >= 0; --i)
#define ALL(a) (a).begin(), (a).end()
using ll = long long;
// using Graph = vector<vector<int>>;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const ll LINF = 1LL << 60;

ll k, ans = 0;
queue<ll> que;

ll calc(ll k) {
  while (k > 0) {
    ll x = que.front();
    que.pop();
    k--;
    int m = x % 10;
    if (k == 0) return x;
    if (x % 10 == 0) {
      que.push(x * 10 + m);
      que.push(x * 10 + m + 1);
    } else if (x % 10 == 9) {
      que.push(x * 10 + m - 1);
      que.push(x * 10 + m);
    } else {
      que.push(x * 10 + m - 1);
      que.push(x * 10 + m);
      que.push(x * 10 + m + 1);
    }
  }
}

int main() {
  cin >> k;
  rep(i, 9) que.push(i + 1);
  cout << calc(k) << endl;
  return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <string>

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define mp make_pair
#define bg begin()
#define en end()


using namespace std;

typedef long long ll;

static const long long MOD = 1000000007;
static const long long INF = 1000000000000;

int N, M;
ll a[1005], d[1<<12];
ll dp[1005][1<<12];

int main(void) {
    scanf("%d %d", &N, &M);
    for(int i=1; i<=M; i++) {
      int b;
      scanf("%lld %d", &a[i], &b);
      for(int j=0; j<b; j++) {
        int c;
        scanf("%d", &c);
        d[i] |= 1LL<<(c-1);
      }
    }
    for(int i=0; i<1005; i++) for(int j=0; j<(1<<12); j++) {
      dp[i][j] = INF;
    }

    dp[0][0] = 0;
    for (int i=1; i<=M; i++) {
        for (int j=0; j<(1<<N); j++) dp[i][j] = dp[i-1][j];

        for (int j=0; j<(1<<N); j++) {
            dp[i][j|d[i]] = min(dp[i][j|d[i]], dp[i-1][j] + a[i]);
        }
      
    
    }
    ll ans = dp[M][(1<<N)-1];
    printf("%lld\n", ans==INF?-1 : ans);

    return 0;
}



Measured memory_bytes: 32384
#include <iostream>
using namespace std;
 
long long gcd(long long a, long long b)
{
	long long temp;
	while (a % b != 0)
	{
		temp = b;
		b = a % b;
		a = temp;
	}
	return b;
}
 
int main()
{
	long long A, B, C, D;
	cin >> A >> B >> C >> D;
 
	long long  count = 0;
	count += (B / C) - ((A-1)  / C) ;
	count += (B / D) - ((A-1)  / D) ;
	long long g = C / gcd(C, D) * D;
	count -= (B / g) - ((A-1)  / g) ;
 
	cout << (B - A + 1 - count) << endl;
	return 0;
}

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


int main(){
  int N;
  cin >>N;
  vector<int> A(N);
  vector<int> B(N);
  for(int i = 0;i<N;i++){
    cin >>A.at(i)>>B.at(i);
  }
  sort(A.begin(),A.end());
  sort(B.begin(),B.end());
  if(N%2==1){
    cout<<B.at(N/2)-A.at(N/2)+1<<endl;
  }else{
    int shita = A.at(N/2)+A.at(N/2-1);
    int ue = B.at(N/2)+B.at(N/2-1);
    int n = (ue-shita)+1;
    cout<<n<<endl;
  }
}
    

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

typedef long long ll;
typedef pair<int,int> P;
typedef map<int,int> M;
typedef vector<int> V;
typedef queue<int> Q;
typedef pair<long,long> PLL;
typedef map<long,long> MLL;
typedef vector<long> VLL;
#define INF (int)(1e9)
#define MAXX 1.1529215e+18
#define inf 999999
#define EPS (1e-7)
#define MOD (1e9+7)
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,n) for(int i=1;i<=(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n-1);i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define ALL(a)  a.begin(),a.end()
#define RALL(a) a.begin(),a.end(),greater<int>()
#define ROT(a) a.begin(),a.begin()+1,a.end()
#define RROT(a) a.begin(),a.end()-1,a.end()
#define PB push_back
#define MP make_pair
#define PI acos(-1.0)
/*--------------------------------------------*/

int main(){
    int n,t,a;cin>>n>>t>>a;
    V h(n);rep(i,n)cin>>h[i];
    int temp;
    int res=INF;
    int ans;
    int tmp;
    rep(i,n){
        temp=t*1000-h[i]*6;
        tmp=abs(temp-a*1000);
        if(res>=tmp){
            res=tmp;
            ans=i;
        }
    }
    cout<<ans+1<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
using namespace std;
#define INF 1000000000
typedef long long int lli;
typedef pair<int,int> P;

const int MAX_V=100;
int cost[MAX_V][MAX_V];
int mincost[MAX_V];
bool used[MAX_V];

int prim(int V){
    for(int i=0; i<V; ++i){
        mincost[i]=INF;
        used[i]=false;
    }
    mincost[0]=0;
    int res=0;

    while(true){
        int v=-1;
        for(int u=0; u<V; ++u){
            if(!used[u]&&(v==-1||mincost[u]<mincost[v])) v=u;
        }
        if(v==-1) break;
        used[v]=true;
        res+=mincost[v];
        for(int u=0; u<V; ++u){
            mincost[u]=min(mincost[u],cost[v][u]);
        }
    }
    return res;
}

int main(){
    int n,m;
    while(cin>>n>>m){
        if(n==0&&m==0) break;
        for(int i=0;i<n;++i)for(int j=0;j<n;++j) cost[i][j]=INF;
        for(int i=0; i<m; ++i){
            int a,b,c;
            cin >> a >> b >> c;
            cost[a][b]=cost[b][a]=c;
        }
        cout << prim(n) << "\n";
    }
    return 0;
}

Measured memory_bytes: 3120
package main

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

func main() {
	X, t := ReadInt(), ReadInt()
	ans := X - t
	if ans < 0 {
		ans = 0
	}
	fmt.Println(ans)
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int)       { Scan(&i); return }
func ReadString() (s string) { Scan(&s); return }
func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}


Measured memory_bytes: 1840
#include<bits/stdc++.h>
using namespace std;
using ll =long long;
const int MOD=1e9+7;

int func(ll a,ll b){
    b=min(b,a-b);
    ll u=1,d=1;
    for(int i=0;i<b;i++){
        u *= a-i;
        d *= d-i;
    }
    return u/d;
}

int main(){
    ll n,k;
    cin >>n>>k;
    ll ans=0,maxv=0;
    for(int i=k;i<=n+1;i++){
        ans += i*(n-i+1)+1;
    }
    cout << ans%MOD << endl;
    return 0;
}

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

#define int long long

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

string A;
int ap[26] = {};

signed main() {
    cin >> A;
    for (int i = 0; i < A.length(); i++) {
        ap[A[i] - 'a']++;
    }
    int ans = 0;
    for (int i = 0; i < 26; i++) {
        ans += ap[i] * (A.length() - ap[i]);
    }
    cout << ans / 2 + 1 << endl;
    return 0;
}


Measured memory_bytes: 640
n, m = map(int,input().split())
mod = 1000000007
stair = [True] * (n+1)
for i in range(m):
    a = int(input())
    stair[a] = False

dp = [0] * (n + 2)
dp[0] = 1
if stair[1]:
    dp[1] = 1

for i in range(2,n+1):
    if stair[i]:
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod
    else:
        dp[i] = 0

print(dp[n])

Measured memory_bytes: 7668
h, w = map(int, input().split())

cnt = 0
if h > 1 and w > 1:
    cnt += ((w+1)//2)*(h//2)
    cnt += (w//2)*(h//2)
    if h&1 == 1:
        cnt += (w+1)//2
else:
    cnt = 1

print(cnt)

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

int main() {

    string S;

    string S_tmp_5 = ""; //dream, erase
    string S_tmp_6 = ""; //eraser
    string S_tmp_7 = ""; //dreamer

    cin >> S;

    do {
        //cout << "do S: " << S << endl;

        if (S.size() == 5 || S.size() == 6|| S.size() == 7){
            if(S == "dream" || S == "erase" || S == "eraser" || S == "dreamer"){

                cout << "YES" << endl;
                return 0;

            }else{

                cout << "NO" << endl;
                return 0;
            }

        }

        S_tmp_5 = S.substr(S.size() - 5, 5);
        S_tmp_6 = S.substr(S.size() - 6, 6);
        S_tmp_7 = S.substr(S.size() - 7, 7);

        // cout << "S_tmp_5: " << S_tmp_5 << endl;
        // cout << "S_tmp_6: " << S_tmp_6 << endl;
        // cout << "S_tmp_7: " << S_tmp_7 << endl;


        if (S_tmp_5 == "dream" || S_tmp_5 == "erase"){
            S = S.substr(0, S.size() - 5);

            //cout << "5: new S: " << S << endl;

            if(S.size() == 0){
                cout << "YES" << endl;
                return 0;
            }
        }
        else if (S_tmp_6 == "eraser" ){
            S = S.substr(0, S.size() - 6);

            //cout << "6: new S: " << S << endl;

            if(S.size() == 0){
                cout << "YES" << endl;
                return 0;
            }
        }
        else if (S_tmp_7 == "dreamer" ){
            S = S.substr(0, S.size() - 7);

            //cout << "7: new S: " << S << endl;

            if(S.size() == 0){
                cout << "YES" << endl;
                return 0;
            }
        }
        else{
            cout << "NO" << endl;
            return 0;
        }


    }while (true);
    
    return 0;

}

Measured memory_bytes: 3756
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <deque>

long long mod = 1e9+7;
class Mint {
public:
  long long x;
  Mint(){}; // 引数なしでも定義できるように引数なしコンストラクタも用意しておく
  Mint(long long a){
    x = a%mod;
    while(x<0){
      x += mod;
    }
  };
  Mint& operator += (const Mint &a){
    x+=a.x;
    x%=mod;
    return *this;
  }
  Mint& operator -= (const Mint &a){
    x += (mod - a.x);
    x%=mod;
    return *this;
  }
  Mint& operator *= (const Mint &a){
    x*=a.x;
    x%=mod;
    return *this;
  }

  // a^n mod を計算する
  // Useaeg: Mint z = y.pow(y, n);
  Mint pow(Mint a, long long n) const {
    Mint y(1);
    Mint b(a);
    while (n > 0) {
      if (n & 1) y *= b;
      b *= b;
      n >>= 1;
    }
    return y;
  }

  // a^{-1} mod を計算する
  Mint modinv(const Mint &a) const {
    return pow(a, mod-2);
  }

  Mint& operator /= (const Mint &a) {
    x *= modinv(a).x;
    x %= mod;
    return *this;
  }

  Mint operator + (Mint &a) const {
    Mint y(*this);
    y += a;
    return y;
  }

  Mint operator - (Mint &a) const {
    Mint y(*this);
    y -= a;
    return y;
  }

  Mint operator * (Mint &a) const {
    Mint y(*this);
    y *= a;
    return y;
  }

  Mint operator / (Mint &a) const {
    Mint y(*this);
    y/=a;
    return y.x;
  }

  // nCk @mod を計算する
  Mint nCk(Mint &n, const long long k) const {
    Mint y = Mint(1);
    for (Mint i(0); (i.x)<k; i.x++){
      y *= (n-i);
      y /= i;
    }
    return y;
  }

  // nPk @mod を計算する
  Mint nPk(Mint &n, long long k) const {
    Mint y(1);
    for (Mint i(0); (i.x)<k; i.x++){
      y *= (n-i);
    }
    return y;
  }
};

Mint dp[2004][2004];

int main(){
  int N, M;
  std::cin >> N >> M;
  std::vector<int > S(N), T(M);
  for (int i=0; i<N; i++) {
    scanf("%d", &S[i]);
  }
  for (int i=0; i<M; i++) {
    scanf("%d", &T[i]);
  }
  dp[0][0] = 1;
  for (int i=0; i<N; i++) {
    dp[i+1][0] = 1;
  }
  for (int j=0; j<M; j++) {
    dp[0][j+1] = 1;
  }

  for (int i=0; i<N; i++) {
    for (int j=0; j<M; j++) {
      dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] - dp[i][j];
      if (S[i]==T[j]) dp[i+1][j+1] += dp[i][j];
    }
  }
  std::cout << dp[N][M].x << std::endl;
  return 0;
}

Measured memory_bytes: 34572
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int dp[20][2100];

int main(){
  int n,k;
  int g,tmp;
  vector<int> c[20],cost[20];

  cin >> n >> k;

  for(int i=0;i<n;i++){
    cin >> tmp >> g;
    c[g-1].push_back(tmp);
  }

  for(int i=0;i<10;i++){
    sort(c[i].begin(),c[i].end(),greater<int>());
    int sum = 0;
    cost[i].push_back(0);
    for(int j=0;j<(int)c[i].size();j++){
      sum += c[i][j];
      cost[i].push_back(sum + j*(j+1) );
    }
    sort(cost[i].begin(),cost[i].end());
  }

  for(int i=0;i<=10;i++){
    dp[i][0] = 0;
    for(int j=1;j<=n;j++)dp[i][j] = -1;
  }
  
  for(int i=0;i<10;i++){
    for(int j=0;j<=n;j++){
      for(int k=0;k<(int)cost[i].size();k++){
	if(dp[i][j]>=0 && j+k<=n){
	  dp[i+1][j+k] = max(dp[i+1][j+k], dp[i][j] + cost[i][k]);
	}
      }
    }
  }  
  int ans = 0;
  for(int i=0;i<=k;i++)ans = max(ans,dp[10][i]);
  cout << ans << endl;
}

Measured memory_bytes: 0
#include<iostream>
using namespace std;
int main(){
    int x[5];
    for(int i = 0; i < 5; ++i) cin >> x[i];
    int min = 10;
    int res;
    for(int i = 0; i < 5; ++i){
        if(x[i] % 10 <= min && x[i] % 10 != 0){min = x[i] % 10;
        res = i;}
    }
    int ans = 0;
    for(int i = 0; i < 5; ++i){
        if(i == res || x[i] % 10 == 0) ans += x[i];
        else ans += x[i] + 10 - x[i] % 10; 
    }
    cout << ans << endl;
}

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

int main() {
  int A,B;
  string op;
  cin >> A >> op >> B;
  
  if (op == "+") {
    cout << A + B << endl;
  } else if (op == "-") {
    cout << A - B << endl;
  }
 
  // ここにプログラムを追記
}

Measured memory_bytes: 256
let () =
  Scanf.scanf "%d" @@ fun n ->
  let p = Array.init n (fun _ -> Scanf.scanf " %d" ((+) 0)) in
  Array.sort (-) p;
  let s = Array.fold_left (+) 0 p in
  Printf.printf "%d\n" (s - p.(n-1) / 2)


Measured memory_bytes: 2432
N=int(input().split()[0])
D=[i for i in input().split()]
for i in range(N,100000):
  flag=0
  for d in D:
    for k in range(len(str(i))):
      if str(i)[k]==d:
        flag=1
      if flag==1:
        break
    if flag==1:
      break
  if flag==0:
    break
print(i)


Measured memory_bytes: 41328
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<cmath>
#include<set>
#include<stack>
#define ll long long
#define pb push_back
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
#define cls(name,x) memset(name,x,sizeof(name))
#define pos first
#define index second
#define mp make_pair
using namespace std;
const int inf=1e9+10;
const ll llinf=1e16+10;
const int maxn=2e5+10;
const int maxm=1e2+10;
const int mod=1e9+7;
int n;
ll sum[maxn];
int num[maxn];
int main()
{
    //freopen("in.txt","r",stdin);
    while(~scanf("%d",&n))
    {
        sum[0]=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&num[i]);
            sum[i]=sum[i-1]+num[i];
        }
        ll ans=llinf;
        for(int i=1;i<=n-1;i++)
        {
            ans=min(ans,abs(sum[i]-(sum[n]-sum[i])));
        }
        printf("%lld\n",ans);
    }
    return 0;
}


Measured memory_bytes: 2560