akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

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

int main()
{
    cin.tie(0); ios::sync_with_stdio(false); 
    int i,j;
    int h,w;
    cin >> h >> w;
    int ch, dh, cw, dw;
    cin >> ch >> cw >> dh >> dw;
    --ch, --cw, --dh, --dw;
    vector<string> s(h);
    rep(i,h) cin >> s.at(i);

    int INF = (1 << 30);

    vector<vector<int>> dp(h,vector<int>(w,INF));
    deque<pair<int,pair<int,int>>> deq;

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

    pair<int,int> top = make_pair(ch, cw); //開始点
    dp.at(ch).at(cw) = 0;
    deq.emplace_back(0, top);
    while(!deq.empty()){
        auto x = deq.front();
        deq.pop_front();
        int nx = x.second.first;
        int ny = x.second.second;
        int dist = x.first;
        if(dp.at(nx).at(ny) < dist) continue;

        rep(i,4){
            int x = nx + dx[i];
            int y = ny + dy[i];
            if(x < 0 || x >= h || y < 0 || y >= w) continue;
            if(s.at(x).at(y) == '#') continue;
            if(dp.at(x).at(y) > dist){
                dp.at(x).at(y) = dist;
                deq.emplace_front(dist, make_pair(x, y));
            }
        }

        int nd = dist + 1;
        for(i = -2;i < 3;++i){
            for(j = -2;j < 3;++j){
                int x = nx + i;
                int y = ny + j;
                if(x < 0 || x >= h || y < 0 || y >= w) continue;
                if(s.at(x).at(y) == '#') continue;
                if(dp.at(x).at(y) > nd){
                    dp.at(x).at(y) = nd;
                    deq.emplace_back(nd, make_pair(x, y));
                }
            }
        }
    }
    if(dp.at(dh).at(dw) == INF) cout << -1 << endl;
    else cout << dp.at(dh).at(dw) << endl;

    return 0;
}

Measured memory_bytes: 8796
#include <iostream>
#include <algorithm>
#include <utility>
using namespace	std;
int main()
{
  int N,M,d,p,j,A=0;
  pair<int,int>	PD[10010];
  while(cin>>N>>M&&N){
    for	(int i=0;i<N;i++){
      cin >> d >> p;
      PD[i]=make_pair(p,d);
      // PD[i].first ?????? i ?????±??????                                            
      // PD[i].second ?????? i ?????????                                             
    }
    sort(PD,PD+N);
    reverse(PD,PD+N);
    j=0;
    for(int i=0;i<M;i++){
      PD[j].second--;
      if(PD[j].second==0)
        j++;
    }
    A=0;
    for(int i=0;i<N;i++)
      A+=PD[i].first*PD[i].second;
    cout << A << endl;
  }
}

Measured memory_bytes: 3124
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProgramingStudying2
{
    class Program
    {
        static void Main(string[] args)
        {
            var nk = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var n = nk[0];
            var k = nk[1];
            var h = Console.ReadLine().Split().Select(int.Parse).ToList();
            var dp = new int[n];

            for(int i = 1; i < n; i++)
            {
                dp[i] = dp[i - 1] + Math.Abs(h[i] - h[i - 1]);
                for(int j = 2; j <= k && i - j >= 0; j++)
                {
                    dp[i] = Math.Min(dp[i], dp[i - j] + Math.Abs(h[i] - h[i - j]));
                }
            }
            Console.WriteLine(dp[n - 1]);
        }
    }
}

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

#define ll long long
#define endl "\n"

void solve(){
	int n; cin>>n;
	int a = n%10;
	int flag = 0;
	int ar[5] = {2, 4, 5, 7, 9};
	for(int i = 0; i<5; i++){
		if(a == ar[i]){
			cout<<"hon"<<endl;
			flag = 1;
			break;
		}
	}
	if(!flag){
		int ar1[4] = {0, 1, 6, 8};
		for(int i = 0; i<4; i++){
			if(a == ar1[i]){
				cout<<"pon"<<endl;
				flag = 1;
				break;
			}
		}
		if(!flag){
			cout<<"bon"<<endl;
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	//int t; cin>>t;
	//while(t--){
		solve();
	//}
	return 0;
}


Measured memory_bytes: 3648
#include<iostream>
#include<cstdlib>
#include<cstdio>

using namespace std;

struct Node {
  int data;
  Node *parent, *left, *right;
} *NIL, *root = NIL;
int in[500001], pre[500001], _in, _pre;

void insert (Node *node) {
  Node *y = NIL;
  Node *x = root;

  while (x != NIL) {
    y = x;

    if (node->data < x->data)
      x = x->left;
    else
      x = x->right;
  }

  if (y == NIL)
    root = node;
  else if (node->data < y->data)
    y->left = node;
  else
    y->right = node;

  node->parent = y;
}

void inorder (Node *node) {
  if (node == NIL)
    return;

  inorder(node->left);

  in[_in++] = node->data;

  inorder(node->right);
}

void preorder (Node *node) {
  if (node == NIL)
    return;
  
  pre[_pre++] = node->data;

  preorder(node->left);
  preorder(node->right);
}

void printArrary (int arr[], int length) {
  for (int i = 0; i < length; i++)
    cout << " " << arr[i];

  cout << endl;
}

void print () {
  _in = 0;
  _pre = 0;
  inorder(root);
  printArrary(in, _in);
  preorder(root);
  printArrary(pre, _pre);
}

Node *find (int n, bool print) {
  Node *node = root;
  bool found = false;

  while (node != NIL) {
    if (node->data == n) {
      found = true;
      break;
    }

    if (node->data > n)
      node = node->left;
    else
      node = node->right;
  }

  if (found && print)
    cout << "yes" << endl;
  if (!found && print)
    cout << "no" << endl;

  return node;
}

Node *getSuccessor (Node *node) {
  Node *result = node;
  
  while (true) {
    if (node->left == NIL) {
      result = node;
      break;
    }

    node = node->left;
  }

  return result;
}

void deleteNode (Node *z) {
  Node *y, *x;
  
  if (z->left == NIL || z->right == NIL)
    y = z;
  else
    y = getSuccessor(z->right);
  
  // cout << "y = " << y->data << endl;
  // cout << "y.parent = " << y->parent->data << endl;
  
  if (y->left != NIL)
    x = y->left;
  else
    x = y->right;

  // cout << "x == NIL " << (x == NIL) << endl;
  
  if (x != NIL)
    x->parent = y->parent;
  
  if (y->parent == NIL)
    root = x;
  else if (y->parent->left == y)
    y->parent->left = x;
  else
    y->parent->right = x;

  // cout << y->parent->right->data << endl;

  if (y->data != z->data) {
    z->data = y->data;
  }
}

int main () {
  int n, m;
  char s[100];

  scanf("%d\n", &n);

  for (int i = 0; i < n; i++) {
    cin >> s;

    if (s[0] == 'i') {
      cin >> m;

      Node *node = (Node *)malloc(sizeof(Node));

      node->left = NIL;
      node->right = NIL;
      node->parent = NIL;
      node->data = m;

      insert(node);
    } else if (s[0] == 'f') {
      cin >> m;
      
      find(m, true);
    } else if (s[0] == 'd') {
      cin >> m;
      
      Node *node = find(m, false);
      deleteNode(node);
    } else {
      print();
    }
  }

  return 0;
}


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

// vector<int> dp(100000, 1e9);

int main()
{
    // string S,T,U;
    ll N,R;
    ll ans = 0;
    cin >> N >> R;
    // scanf("%lld%lld", &A,&B);
    // cin >> U;
    if(N>=10)
        ans = R;
    else
        ans = 100*(10-N)+R;
    printf("%lld",ans);

    return 0;
}

Measured memory_bytes: 256
// eddy1021
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod7=1000000007LL;
inline LL getint(){
  LL _x=0,_tmp=1; char _tc=getchar();    
  while( (_tc<'0'||_tc>'9')&&_tc!='-' ) _tc=getchar();
  if( _tc == '-' ) _tc=getchar() , _tmp = -1;
  while(_tc>='0'&&_tc<='9') _x*=10,_x+=(_tc-'0'),_tc=getchar();
  return _x*_tmp;
}
inline LL add(LL _x, LL _y, LL _mod=mod7){
  _x+=_y;
  return _x>=_mod ? _x-_mod : _x;
}
inline LL sub(LL _x, LL _y, LL _mod=mod7){
  _x-=_y;
  return _x<0 ? _x+_mod : _x;
}
inline LL mul(LL _x, LL _y ,LL _mod=mod7){
  _x*=_y;
  return _x>=_mod ? _x%_mod : _x;
}
LL mypow(LL _a, LL _x, LL _mod){
  if(_x == 0) return 1LL;
  LL _ret = mypow(mul(_a, _a, _mod), _x>>1, _mod);
  if(_x & 1) _ret=mul(_ret, _a, _mod);
  return _ret;
}
LL mymul(LL _a, LL _x, LL _mod){
  if(_x == 0) return 0LL;
  LL _ret = mymul(add(_a, _a, _mod), _x>>1, _mod);
  if(_x & 1) _ret=add(_ret, _a, _mod);
  return _ret;
}
void sleep(double sec = 1021){
  clock_t s = clock();
  while(clock() - s < CLOCKS_PER_SEC * sec);
}
#define Bye exit(0)
int __ = 1 , _cs;
/*********default*********/
const int N=202020;
LL n, a[N]; 
void build(){

}
void init(){
  n=getint();
  for(int i=1; i<=n; i ++)
    a[i]=getint();
}
void solve(){
  unordered_map<LL,LL> M;
  LL ans=0;
  M[0]=1;
  for(int i=1; i<=n; i++){
    a[i] += a[i-1];
    ans+=M[a[i]];
    M[a[i]]++;
  }
  cout<<ans<<endl;
}
int main(){
  build();
  //__ = getint();
  while(__ --){
    init();
    solve();
  }
}


Measured memory_bytes: 10056
#include<iostream>
#include<cstring>
#include<queue>
#include<map>
#include<stack>
#include<cstdio>
#include<sstream>
#include<algorithm>
#include<unordered_map>

using namespace std;
#define read(x) scanf("%d",&x)
#define Read(x,y) scanf("%d%d",&x,&y)
#define gc(x)  scanf(" %c",&x);
#define mmt(x,y)  memset(x,y,sizeof x)
#define write(x) printf("%d\n",x)
#define INF 0x3f3f3f3f
#define ll long long
#define mod  998244353
const  int N = 1e5+5;
struct node
{
    int x,y;
}res[N];
bool cmp(node o1,node o2){
    if(o1.y != o2.y) return o1.y < o2.y;
    else return o1.x > o2.x;
}
int main(){
    int t;
    cin >> t;
    for(int i = 1;i <= t;++i){
        int a,l;
        cin >> a >> l;
        res[i].x = a - l,res[i].y = a + l;
    }
    sort(res + 1,res + t + 1,cmp);
    int sum = 1;
    int k = res[1].y;
    for(int i = 2;i <= t;++i){
        if(res[i].x >= k){
            sum ++;k = res[i].y;
        }
    }
    cout<<sum;
}

Measured memory_bytes: 1024
# ABC070 D - Transit Tree Path
import heapq
def dijkstra_heap(s):
    """
    始点sから各頂点への最短距離を返す

    Parameters
    ----------
    s : int
        視点とする頂点

    Returns
    -------
    d ：list
    始点sから各頂点への最短距離
    """
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #未使用の頂点の中から最小の距離のものを探す
        if not used[minedge[0]]:
            continue
        v = minedge[0]
        d[v] = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[0]]:
                heapq.heappush(edgelist,[e[0],e[1]+d[v]])
    return d

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

q,k=map(int,input().split())
k-=1
dist=dijkstra_heap(k)
for i in range(q):
    x,y=map(int,input().split())
    x-=1
    y-=1
    print(dist[x]+dist[y])

Measured memory_bytes: 55932
while True:
    n = int(raw_input())
    if n == 0: break
    field = [raw_input() for i in range(n)]
    large = [[0]*(n + 1) for i in range(n + 1)]
    mx = 0
    for i in range(n):
        for j in range(n):
            if field[i][j] == '.':
                large[i][j] = min(large[i][j - 1], large[i - 1][j], large[i - 1][j - 1]) + 1
    print max(map(max, large))

Measured memory_bytes: 32980
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #pragma comment(linker,"/stack:200000000")
#include <bits/stdc++.h>
using namespace std;

#define PI 2*acos(0.0)
#define print(x) return cout<<x<<endl,0
#define watch(x) cerr<<#x<<"-> "<<x<<endl
#define CLEAR(x,val) memset(x,val,sizeof(x))
// #define int long long

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

const int INF = 1000000000;
const int MOD = 1000000007; //998244353

signed main()
{	
	//freopen("","r",stdin);
	//freopen("","w",stdout);
	cin.tie(0), cout.tie(0);
	ios::sync_with_stdio(0);
	int n;
	cin >> n;
	string s;
	cin >> s;
	for(int i=0;i<s.length();i++)
	{
		string a = "";
		string b = "";
		for(int j=0;j<=i;j++)
			a+=s[j];
		for(int j=i+1;j<s.length();j++)
			b+=s[j];
		if(a==b)
			print("Yes");
	}	
	print("No");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,n,s) for(int i = s; i < (n); ++i)
#define rsrep(i,n,s) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<x<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;

int main() {
    int n, k;
    cin >> n >> k;
    vint h(n);
    rep(i, n) cin >> h[i];
    sort(all(h));
    int ans = INF;
    k--;
    rep(i, n-k) {
        ans = min(ans, h[i+k] - h[i]);
    }

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

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

constexpr long long int MOD = 1e9 + 7;
int main(){
    int n, m;
    cin >> n >> m;
    vector<long long int> a(m), b(n+1);
    for(auto& e : a) cin >> e;
    a.push_back(0);
    b[0] = 1;
    b[1] = !(a[0] == 1);
    for(int i = 1, l = (a[0] == 1);i + 1 < n + 1;i++){
        if(i + 1 != a[l]){
            b[i+1] = b[i] + b[i-1];
            b[i+1] %= MOD;
        }else{
            if(i + 2 != a[l+1]){
                b[i+1] = 0;
            }else{
                b[0] = 0;
            }
            l++;
        }
    }
    cout << b[0] * b[n] << endl;
    return 0;
}


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

class G
{
	static int[] Read() => Console.ReadLine().Split().Select(int.Parse).ToArray();
	static void Main()
	{
		var h = Read();
		var n = h[0];
		var es = new int[h[1]].Select(_ => Read()).ToArray();

		var map = Array.ConvertAll(new int[n], _ => new List<int>());
		var map_r = Array.ConvertAll(new int[n], _ => new List<int>());
		foreach (var e in es)
		{
			map[e[0]].Add(e[1]);
			map_r[e[1]].Add(e[0]);
		}

		var u = new bool[n];
		var order = new int[n];
		var c = n;
		var gs = new List<List<int>>();
		List<int> lg = null;

		void Dfs(int v)
		{
			u[v] = true;
			foreach (var nv in map[v]) if (!u[nv]) Dfs(nv);
			order[--c] = v;
		}
		for (int v = 0; v < n; v++) if (!u[v]) Dfs(v);

		void Dfs_r(int v)
		{
			u[v] = true;
			foreach (var nv in map_r[v]) if (!u[nv]) Dfs_r(nv);
			lg.Add(v);
		}
		Array.Clear(u, 0, n);
		foreach (var v in order) if (!u[v]) { gs.Add(lg = new List<int>()); Dfs_r(v); }

		Console.WriteLine(gs.Count);
		Console.WriteLine(string.Join("\n", gs.Select(g => string.Join(" ", g.Prepend(g.Count)))));
	}
}


Measured memory_bytes: 183808
#include <bits/stdc++.h>
#define fuck 2000000000
#define hell 2000000000000000000
#define ff first
#define ss second 
#define forn(i,n) for (int i=0;i<int(n);i++)
#define nfor(i,n) for (int i=int(n)-1;i>=0;i--)
#define N 100010
#define M 1000010
using namespace std;
const int MOD = 1000000007;
const double PI = acos(-1.0);
int gcd(int a,int b){return (b==0) ? a : gcd(b,a%b);}

int main(){
	
	int a,b;
	scanf("%d%d",&a,&b);
	printf("%d",max(0,a-b));
	
	return 0;
}

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

int main(){
	ll a,b,c,x,y;
	cin >> a >> b >> c >> x >> y;
	ll ans = 0;
	if(x > y){
		ans = min({a*x+b*y, 2*c*x, 2*c*y + (x-y)*a});
	}else{
		ans = min({a*x+b*y, 2*c*y, 2*c*x + (y-x)*b});
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 256
#include<stdio.h>

int main() {
	int N;
	scanf("%d", &N);
	int *X = (int *)malloc(sizeof(int)*N);
	int *Y = (int *)malloc(sizeof(int)*N);
	int *H = (int *)malloc(sizeof(int)*N);
	for (int i = 0; i < N; i++) {
		scanf("%d%d%d", &X[i], &Y[i], &H[i]);
	}

	for (int posx = 0; posx <= 100; posx++) {
		for (int posy = 0; posy <= 100; posy++) {
			int needH = -1;
			for (int i = 0; i < N; i++) {
				if (H[i] > 0) {
					int tmp = H[i] + abs(X[i] - posx) + abs(Y[i] - posy);
					if (needH == -1) {
						needH = tmp;
					}
					else if (needH != tmp) {
						needH = -2;
						break;
					}
				}
			}
			if (needH == -2) {
				continue;
			}

			for (int i = 0; i < N; i++) {
				if (H[i] == 0) {
					int tmp2 = abs(X[i] - posx) + abs(Y[i] - posy);
					if (needH > tmp2) {
						needH = -2;
						break;
					}
				}
			}
			if (needH == -2) {
				continue;
			}

			printf("%d %d %d", posx, posy, needH);
			printf("\n");
			return 0;
		}
	}
}


Measured memory_bytes: 128
import math

q = int(input())
a = [0] * q
b = [0] * q

for i in range(0, q):
    a[i], b[i] = [int(i) for i in input().split(" ")]
    
def sqrt_int(n):
    s = math.floor(n**(1/2)) - 1
    while s * s <= n:
        s += 1
    return s - 1

for i in range(0, q):
    mi = min(a[i], b[i])
    mx = max(a[i], b[i])
    p = mi * mx - 1
    s = math.floor(p**(1/2))
    c = 2 * (s - 1)
    if s == 0:
        print(0)
        continue
    if mi <= s - 1:
        c -= 1
    r = p // s
    if r > s:
        if s == mi:
            c += 1
        else:
            c += 2
    elif r == s and s != mi:
        c += 1
    print(c)

Measured memory_bytes: 3188
#include<iostream>
#include<bitset>
using namespace std;
int n,x,sum;
bitset<2000007>f;
int main(){
    cin>>n;
    f[0]=1;
    for(int i=1;i<=n;i++){
        cin>>x;
        f|=f<<x;
        sum+=x;
    }
    for(int i=(sum+1)/2;i<=sum;i++){
        if(f[i]) {cout<<i<<endl;break;}
    }
    return 0;
}

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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define ALL(a) (a).begin(), (a).end()
#define rALL(a) (a).rbegin(), (a).rend()
#define SZ(x) ((int)(x).size())
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1 << 28;
const ll INF64 = 1ll << 55;
const int mod = 1000000007;
//const int mod = 998244353;

template <class T>inline bool chmin(T &a, const T b)
{
  if (a > b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>inline bool chmax(T &a, const T b)
{
  if (a < b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>inline void line_out(const vector<T> vec) {
  int n = SZ(vec);
  rep(i, n) {
    cout << vec[i];
    if(i < n-1) cout << " ";
  }
  cout << endl;
  return;
}

struct mint
{
  ll x; // typedef long long ll;
  mint(ll 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++()
  {
    if ((x += 1) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator--()
  {
    if ((x += mod - 1) >= mod)
      x -= mod;
    return *this;
  }
  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;
  }
};

int main()
{
  int n; cin >> n;
  vector<int> l(n);
  rep(i, n) cin >> l[i];
  int max_l = *max_element(ALL(l));
  int sum = accumulate(ALL(l), 0);
  if(sum-max_l > max_l) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 3600
def main():
    import sys
    from collections import Counter
    
    N = int(input())
    A = list(map(int, sys.stdin.readline().split()))
    
    count = Counter(A)
    
    d = {}
    comb_sum = 0
    
    for i, n in count.items():
        if n == 1:
            comb = 0
            comb_ex = 0
        else:
            comb = n * (n - 1) / 2
            comb_ex = (n - 1) * (n - 2) / 2
        comb_sum += comb
        d[i] = comb_ex - comb
     
    for n in A:
        ans = int(d[n] + comb_sum)
        print(ans)

if __name__ == '__main__':
    main()

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

const int N_MAX = 100005;
int bcnum[N_MAX];
long long int totalnum[N_MAX];
long long int ans;

int main(){
    int n;
    scanf("%d", &n);
    vector<int> A, B, C;
    for(int i = 0; i < n; i++){
        int a;
        scanf("%d", &a);
        A.push_back(a);
    }
    for(int i = 0; i < n; i++){
        int b;
        scanf("%d", &b);
        B.push_back(b);
    }
    for(int i = 0; i < n; i++){
        int c;
        scanf("%d", &c);
        C.push_back(c);
    }
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    sort(C.begin(), C.end());

    ans = 0;
    for(int i = 0; i < n; i++){
        vector<int>::iterator itc;
        itc = upper_bound(C.begin(), C.end(), B[i]);
        bcnum[i] = C.end() - itc;
    }
    totalnum[n-1] = bcnum[n-1];
    for(int j = n-2; j >= 0; j--){
        totalnum[j] = totalnum[j+1] + bcnum[j];
    }
    for(int i = 0; i < n; i++){
        vector<int>::iterator itb;
        itb = upper_bound(B.begin(), B.end(), A[i]);
        int bn = itb - B.begin();
        if (bn <= n) ans += totalnum[bn];
    }
    printf("%lld", ans);
    return 0;
}

Measured memory_bytes: 2680
#include <cmath>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <vector>
#include <map>
#include<cstdio>
#include<functional>
#include <bitset>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for(int i = n; i >= 0; i--)
#define ll long long
using namespace std;
template <typename T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
template <typename T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
const ll INF = 1000000000000000000;
const ll MOD = 1e9 + 7;

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

	vector<char> c = { 'A','C', 'G', 'T' };
	int ans = 0;
	int tmp = 0;
	rep(i, s.size()) {
		bool isOK = false;
		rep(j, c.size()) {
			if (s[i] == c[j]) {
				isOK = true;
				break;
			}
		}
		if (isOK) {
			++tmp;
		}
		else{
			tmp = 0;
		}
		ans = max(ans, tmp);
	}
	cout << ans << endl;
	system("pause");
}




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

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

int main() {
    ll N;
    string S;
    cin >> N >> S;
    ll x = 0;
    ll m = 0;
    REP(i, N) {
        if (S[i] == 'I')
            x++;
        if (S[i] == 'D')
            x--;
        m = std::max(m, x);
    }
    cout << m << endl;
    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1000000009LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0; // æŒ‡æ•°

        while (N % a == 0) {
            ++ex;
            N /= a;
        }
        res.push_back({a, ex});
    }
    if (N != 1) res.push_back({N, 1});
    return res;
}

int main() {
    ll n, p; cin >> n >> p;
    vector<pll> div = prime_factorize(p);
    ll res = 1;
    for(auto d: div){
        int num = d.second / n;
        res *= pow(d.first, num);
    }
    cout << res << ln;
}


Measured memory_bytes: 256
package main

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

const (
	initialBufSize = 1024
	maxBufSize     = 1e6
)

var (
	scanner = bufio.NewScanner(os.Stdin)
)

func main() {
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, initialBufSize), maxBufSize)
	n := scanInt()
	anagrams := make(map[string]int, n)
	for i := 0; i < n; i++ {
		s := sort(scanText())
		anagrams[s]++
	}

	ans := 0
	for _, v := range anagrams {
		ans += (v * (v - 1)) / 2
	}

	fmt.Println(ans)
}

func sort(s string) string {
	len := len(s)
	b := []byte(s)
	for i := 0; i < len; i++ {
		min := i
		for j := (i + 1); j < len; j++ {
			if b[j] < b[min] {
				min = j
			}
		}
		b[i], b[min] = b[min], b[i]
	}
	return string(b)
}

func scanInt() int {
	i, _ := strconv.Atoi(scanText())
	return i
}

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

func scanFloat64() float64 {
	f, _ := strconv.ParseFloat(scanText(), 64)
	return f
}

func scanFloat64s(size int) []float64 {
	f := make([]float64, size)
	for i := 0; i < size; i++ {
		f[i] = scanFloat64()
	}
	return f
}

func scanText() string {
	scanner.Scan()
	return scanner.Text()
}

func scanTexts(size int) []string {
	s := make([]string, size)
	for i := 0; i < size; i++ {
		s[i] = scanText()
	}
	return s
}

func abs(n int) int {
	return int(math.Abs(float64(n)))
}

func pow(x, y int) int {
	return int(math.Pow(float64(x), float64(y)))
}

func min(n []int) (min, idx int) {
	min = math.MaxInt64
	for i := 0; i < len(n); i++ {
		if n[i] < min {
			min = n[i]
			idx = i
		}
	}
	return
}

func max(n []int) (max, idx int) {
	max = math.MinInt64
	for i := 0; i < len(n); i++ {
		if n[i] > max {
			max = n[i]
			idx = i
		}
	}
	return
}


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

using namespace std;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1LL<<60;

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

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

ll dp[3020][3020];

ll const MOD = 998244353;

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

  int n, s;
  cin >> n >> s;

  vector<int> a(n);
  rep(i, n) cin >> a[i];

  rep(i, 3010){
    rep(j, 3010){
      dp[i][j] = 0;
    }
  }

  dp[0][0] = 1;

  rep(i, n){
    rep(j, 3001){
      dp[i+1][j] = (dp[i+1][j] + 2 * dp[i][j]) % MOD;
      dp[i+1][min(j+a[i], 3010)] = (dp[i+1][min(j+a[i], 3010)] + dp[i][j]) % MOD;
    }
  }

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


Measured memory_bytes: 74688
#include<bits/stdc++.h>
using namespace std;
typedef		long long       ll;
typedef		vector<ll>      vll;
#define     fi              first
#define     se              second
#define		pb              push_back
#define		nn              "\n"
#define		all(p)          p.begin(),p.end()
#define		zz(v)           (ll)v.size()
#define 	S(a)            scanf("%lld",&a)
#define 	SS(a,b)         scanf("%lld %lld",&a,&b)
#define 	SSS(a,b,c)      scanf("%lld %lld %lld",&a,&b,&c)
#define		ss              ' '
#define     pii             pair<ll,ll>
const double eps = 1e-8;

ll ar[100010];
ll dp[100010];
ll n;
ll solve(ll i)
{
    if(i==n)
        return 0;
    if(i>n)
        return INT_MAX;
    if(dp[i]!=-1)
        return dp[i];
    ll l = abs(ar[i]-ar[i+1])+solve(i+1);
    ll r=INT_MAX;
    if(i+2<=n)
        r= abs(ar[i]-ar[i+2])+solve(i+2);
    return dp[i]=min(l,r);
}

int main()
{
    memset(dp,-1,sizeof(dp));
    cin>>n;
    for(ll i=1; i<=n; i++)
        cin>>ar[i];
    cout<<solve(1);

}








Measured memory_bytes: 4992
#include <bits/stdc++.h>
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rrepi(i,a,b) for(int i=((int)(b)-1);i>=(a);--i)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) rrepi(i,0,n)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define ZERO(x) memset(x,0,sizeof(x))
#define MINUS(x) memset(x,-1,sizeof(x))
#define UNIQUE(x) (x).erase(unique(ALL(x)), (x).end())
#define TOUPPER(x) transform(ALL(x), (x).begin(), ::toupper)
#define TOLOWER(x) transform(ALL(x), (x).begin(), ::tolower)
#define debug(var)  do{std::cout << #var << " : "; view(var);}while(0)
#define fi first
#define se second
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){for(const auto& v : vv){ view(v); } }
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void viewarr(T arr[], int n) { for(int i = 0; i < n; ++i) std::cout << arr[i] << " "; std::cout << std::endl; }
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; }
ll qp(ll a,ll b){ll ans=1;do{if(b&1)ans=1ll*ans*a;a=1ll*a*a;}while(b>>=1);return ans;}
ll qp(ll a,ll b,ll mo){ll ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const int INF = 1e9;
const ll INFL = 1e18;
const int MOD = 1e9 + 7;
const int MAX_N = 1e5;

int main() {
    int R; cin >> R;
    double S = 2 * R * M_PI;
    printf("%.4f\n", S);
    return 0;
}


Measured memory_bytes: 3764
#include <bits/stdc++.h>
using namespace std;
int parent[100001];
long long sz[100001];
void make_set(int i){
    parent[i] = i;
    sz[i] = 1;
}
int find_set(int v){
    if(v == parent[v])
    return v;
    return parent[v] = find_set(parent[v]);
}
void union_set(int a, int b){
    a = find_set(a);
    b = find_set(b);
    if(a != b){
    if(sz[a] < sz[b]){
        a = a + b;
        b = a - b;
        a = a - b;
    }
    sz[a] += sz[b];
    parent[b] = a;
    }
}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int n, m;
	cin >> n >> m;
    pair<int, int> edges[m];
    for(int i = 1; i <= n; i++)
    make_set(i);
    for(int i = 0; i < m; i++)
    cin >> edges[i].first >> edges[i].second;
    long long ans[m] = {0};
	ans[m-1] = ((long long)n * (n - 1)) / 2;
	for(int i = m - 1; i > 0; i--){
	    int u = find_set(edges[i].first), v = find_set(edges[i].second);
	    if(u != v)
	    ans[i-1] = ans[i] - (sz[u] * sz[v]);
	    else
	    ans[i-1] = ans[i];
	    union_set(u, v);
	}
	for(int i = 0; i < m; i++)
	cout << ans[i] << endl;
}

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

using namespace std;

const int maxn=200005;

typedef long long ll;

ll sum[maxn],a[maxn];

ll n,b,c,d,e;

ll ans=1e15+7;

char *p1, *p2, buf[100000];

#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )

int rd() {
	int x = 0, f = 1;
	char c = nc();
	while (c < 48) {
		if (c == '-')
			f = -1;
		c = nc();
	}
	while (c > 47) {
		x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();
	}
	return x * f;
}

bool check(ll x, ll y, int i) {
    if (abs((x + a[i]) - (y - a[i])) < abs(x - y)) {
    	return true;
	}
	return false;
}

int main() {
	n = rd();
    ll s = 0;
    for (int i = 0; i < n; i ++ ) {
		a[i] = rd();
        s += a[i];
        sum[i] = s;
    }
    int j = 0, k = 2;
    for (int i = 1; i < n - 2; i ++ ) {
        b = sum[j];
        c = sum[i] - sum[j];
        d = sum[k] - sum[i];
        e = sum[n - 1] - sum[k];
        while (check(b, c, j + 1) && j + 1 < i) {
            j ++ ;
            b = sum[j];
            c = sum[i] - sum[j];
        }
        while (check(d, e, k + 1) && k + 1 < n - 1)
        {
            k ++ ;
            d = sum[k] - sum[i];
            e = sum[n - 1] - sum[k];
        }
        ll test[10];
        test[0] = b;
		test[1] = c;
        test[2] = d;
		test[3] = e;
        sort(test, test + 3 + 1);
        ans = min(ans, test[3] - test[0]);
    }
	cout << ans << endl ;
    return 0;
}

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

class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		Solver solver = new Solver();
		solver.init();
		solver.readHead(in.readLine());
		for (; solver.hasNext();) {
			solver.readBody(in.readLine());
		}
		solver.solve();
	}
}

class Solver {
	int N;
	int cnt;

	public void init() {
		N = 0;
		cnt = 0;
	}

	public void readHead(String str) {
		String[] strArr = str.split(" ");
		N = Integer.parseInt(strArr[0]);
		// System.out.println(N);
		T = Integer.parseInt(strArr[1]);
	}

	int T;
	int C = 0;

	public boolean hasNext() {
		return cnt < N;
	}

	public void readBody(String str) {
		// System.out.println(str);
		cnt++;
		String[] strArr = str.split(" ");
		int c = Integer.parseInt(strArr[0]);
		int t = Integer.parseInt(strArr[1]);
		if (t <= T && (C == 0 || c < C))
			C = c;
	}

	public void solve() {
		if (C == 0)
			System.out.println("TLE");
		else
			System.out.println(C);

	}
}


Measured memory_bytes: 22612
#include <bits/stdc++.h>
#define pi 3.14159
using namespace std;
typedef long long LL;
const LL MOD = 1e9 + 7;
const int N = 1e5 + 7, M = 1e7, OO = 0x3f3f3f3f;
#define AC ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin.sync_with_stdio(0);
long long weights[N],n,prices[N],dp[100][100002];
long long  solve(long long i,long long weight){
    if(weight<weights[i]){
        return solve(i+1,weight);
    }
    if(i==n||weight==0){
        return 0;
    }
    if(dp[i][weight]!=-1){
        return dp[i][weight];
    }
    return dp[i][weight]=max(prices[i]+solve(i+1,weight-weights[i]),solve(i+1,weight));
}
int main()
{
long long weight,i;
memset(dp,-1,sizeof(dp));
scanf("%lld %lld",&n,&weight);
for(i=0;i<n;++i){
    scanf("%lld %lld",&weights[i],&prices[i]);
}
cout<<solve(0,weight)<<endl;




    return 0;
}


Measured memory_bytes: 81772
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    long long int a,b,n,i,max=0,temp=0;
    cin>>a>>b>>n;
    if(b-1<=n)
        max=floor((b-1)*a/b)-a*floor((b-1)/b);
    else
        max=floor(n*a/b)-a*floor(n/b);
    cout<<max<<endl;
    return 0;
}


Measured memory_bytes: 3588
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <map>
#include <queue>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

#define cerr if(0)cerr

using namespace std;

struct edge_t {
    int u, v, w;
};

int dfs(int n, int cur, int c,
    vector<vector<edge_t> > &graph,
    vector<int> &color) {
    color[cur] = c;
    vector<edge_t> g(graph[cur]);
    for (int i=0;i<g.size();i++) {
        edge_t &e(g[i]);
        if (color[e.v] < 0) {
            dfs(n, e.v, ((e.w & 1) ? (c==0?1:0) : c), graph, color);
        }
    }
    return 0;
}

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

    edge_t e;
    vector<vector<edge_t> > graph(n);
    vector<int> color(n,-1);

    for (int i=0;i<n-1;i++) {
        cerr << "check i=" << i << endl;
        cin >> e.u >> e.v >> e.w;
        e.u--;
        e.v--;
        graph[e.u].push_back(e);
        iter_swap(&e.u,&e.v);
        graph[e.u].push_back(e);
    }
    cerr << "check1" << endl;
    dfs(n, 0, 0, graph, color);
    cerr << "check2" << endl;
    for (int i=0;i<n;i++) {
        cout << color[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 12160
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
int main() {
	string a,b;
	cin >> a>>b;
	int c;
	c = a.size();
	char d;
	d = b.at(c);
	string e;
	e = a + d;
	if (b == e) {
		cout<<"Yes"<<endl;
	}
	else {
		cout << "No" << endl;
	}
	return (0);

}

Measured memory_bytes: 3628
# https://atcoder.jp/contests/abc122/tasks/abc122_d

import itertools
import collections
import bisect

dp = [{} for _ in range(101)]

def is_ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i-1], t[i] = t[i], t[i-1]
        if ''.join(t).count('AGC') > 0:
            return False
    return True


def solve(rest, lastt):
    if rest == 0:
        # print(lastt[2:])
        return 1
    if lastt in dp[rest]:
        return dp[rest][lastt]

    val = 0
    for c in 'AGCT':
        if is_ok(lastt + c):
            val += solve(rest - 1, lastt[1:] + c)
    dp[rest][lastt] = val
    return dp[rest][lastt]


def main():
    N = int(input())
    MOD = 10 ** 9 + 7
    print(solve(N, 'ZZZ') % MOD)


if __name__ == '__main__':
    main()


Measured memory_bytes: 4224
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define repi(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define repdi(i,a,b) for(ll i=(a)-1;i>=(b);--i)
#define repd(i,a) repdi(i,a,0)
#define itr(it,a) for( auto it = (a).begin(); it != (a).end(); ++it )
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define endl '\n'
#define debug(x) std::cerr << #x << " = " << (x) << endl;

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

constexpr ll INF = 1ll<<60;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

template<class S, class T>
std::ostream& operator<< ( std::ostream& out, const std::pair<S,T>& a )
{ std::cout << '(' << a.first << ", " << a.second << ')'; return out; }

template<class T>
std::ostream &operator<< ( std::ostream& out, const std::vector<T>& a )
{ std::cout << '['; rep( i, a.size() ){ std::cout << a[i]; if( i != a.size()-1 ) std::cout << ", "; } std::cout << ']'; return out; }

struct Trie {
  ll cnt;
  Trie *child[26];
  std::vector<ll> count_ch;

  Trie()
  : count_ch(26, 0), cnt(0)
  {
    rep( i, 26 ) {
      child[i] = nullptr;
    }
  }
};

ll insert( const std::string &s, Trie *root ) {
  ll ret = 0;
  std::vector<ll> count(27, 0);

  rep( i, s.size() )
    ++count[s[i]-'a'];

  Trie *trie = root;

  rep( i, s.size() ) {
    rep( j, 26 ) if( count[j] )
      ++trie->count_ch[j];

    if( trie->child[s[i]-'a'] == nullptr )
      trie->child[s[i]-'a'] = new Trie();

    trie = trie->child[s[i]-'a'];
    --count[s[i]-'a'];
  }

  return ret;
}

ll traverse( const std::string &s, Trie *root ) {
  Trie *trie = root;

  rep( i, s.size()-1 ) {
    trie = trie->child[s[i]-'a'];
  }

  return trie->count_ch[s[s.size()-1]-'a']-1;
}

ll N;
std::string S[200010];

int main() {
  std::cin >> N;

  Trie *trie = new Trie();

  ll ans = 0;

  rep( i, N ) {
    std::cin >> S[i];

    std::reverse( all(S[i]) );

    insert( S[i], trie );
  }

  rep( i, N ) {
    ans += traverse( S[i], trie );
  }

  std::cout << ans << endl;

  return 0;
}

Measured memory_bytes: 479332
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    let mut v2 = Vec::new();
    for _ in 0..n {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).ok();
        let v = s.trim().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect();
        v2.push(v);
    }
    v2
}

fn a174() {
    let x : isize = read();
    if x >= 30 { println!("{}", "Yes")} else { println!("{}","No")}

}

fn main() {
    a174();


}

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

int64_t f(int64_t n){
    return n*(n-1)/2;
}

int main(){
    /*
    cin.tie(0);
    ios::sync_with_stdio(false);
    */
    int n;
    cin>>n;
    
    vector<int64_t> a(n);
    rep(i,n)cin>>a[i], a[i]--;
    
    vector<int64_t> m(n,0);
    rep(i,n)m[a[i]]++;
    
    int64_t ans = 0;
    rep(i,n)ans += f(m[i]);
    
    rep(i,n){
        //cout << ans -f(m[a[i]]) + f(m[a[i]]-1) << endl;
        printf("%lld\n", ans -f(m[a[i]]) + f(m[a[i]]-1));
    }
    
    return 0;
}

Measured memory_bytes: 5760
#include<iostream>
#include<string>
#include<stdio.h>
#include <algorithm>
#include <set>
#include<math.h>
#include <vector>
#include<map>
using namespace std;

int main(){
    char in[120];
    int n;cin >> n;

  pair<pair<string,int>,int> p[110];
  for(int i = 0;i < n;i++){
      int t;
      cin >> in >> t;
      string tmp = in;

      p[i]=make_pair(make_pair(in,-t),i);
  }

  sort(p,p+n);
  for(int i = 0;i < n;i++){
      cout << p[i].second+1 << endl;
  }
}

Measured memory_bytes: 3564
from heapq import *

N, M = [int(i) for i in input().split()]
L = []
for _ in range(N):
    a, b = [int(i) for i in input().split()]
    L.append((a, -b))
L.sort()

Q = []
cur = 0
ans = 0
for i in range(1, M + 1):
    while cur < N:
        a, b = L[cur]
        if a > i:
            break
        heappush(Q, b)
        cur += 1
    if Q:
        ans -= heappop(Q)
print(ans)


Measured memory_bytes: 17664
#include<bits/stdc++.h>
typedef unsigned long long ll;
using namespace std;
const int maxn = 609;
const ll p = 31, q = 233;

int a[maxn][maxn],b[maxn][maxn];
ll hs1[maxn][maxn],hs2[maxn][maxn],fp[maxn],fq[maxn];
char str[maxn];
int n,ans;

ll calc1(int x1,int y1,int x2,int y2)
{
	return hs1[x2][y2]-hs1[x1-1][y2]*fp[x2-x1+1]-hs1[x2][y1-1]*fq[y2-y1+1]+hs1[x1-1][y1-1]*fp[x2-x1+1]*fq[y2-y1+1];
}
ll calc2(int x1,int y1,int x2,int y2)
{
	return hs2[x2][y2]-hs2[x1-1][y2]*fp[x2-x1+1]-hs2[x2][y1-1]*fq[y2-y1+1]+hs2[x1-1][y1-1]*fp[x2-x1+1]*fq[y2-y1+1];
}

bool check(int x,int y)
{
	return calc1(x-n+1,y-n+1,x,y)==calc2(y-n+1,x-n+1,y,x);
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",str+1);
		for(int j=1;j<=n;j++) a[i][j]=str[j]-'a'+1;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			b[i][j]=a[j][i];
	for(int i=1;i<=n*2;i++)
		for(int j=1;j<=n*2;j++)
		{
			int x=i>n?i-n:i,y=j>n?j-n:j;
			a[i][j]=a[x][y];
			b[i][j]=b[x][y];
		}
	for(int i=1;i<=2*n;i++)
		for(int j=1;j<=2*n;j++)
		{
			hs1[i][j]=hs1[i-1][j]*p+hs1[i][j-1]*q-hs1[i-1][j-1]*p*q+a[i][j];
			hs2[i][j]=hs2[i-1][j]*p+hs2[i][j-1]*q-hs2[i-1][j-1]*p*q+b[i][j];
		}
	fp[0]=fq[0]=1;
	for(int i=1;i<=2*n;i++) fp[i]=fp[i-1]*p,fq[i]=fq[i-1]*q;
	for(int i=n+1;i<=2*n;i++) for(int j=n+1;j<=2*n;j++) if(check(i,j)) ans++;
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 8960
n = int(input())
h = list(map(int,input().split()))

ans = 'Yes'
flag = 0

for i in range(n-1):
    if h[i] - h[i+1] >= 2:
        ans = 'No'
        break
    elif h[i] - h[i+1] == 1:
        if flag == 0:
            flag = 1
        else:
            ans = 'No'
            break
    elif flag == 1:
        if h[i+1] - h[i] >= 1:
            flag = 0
            
print(ans)

Measured memory_bytes: 14352
gets
arr = gets.split.map(&:to_i)
odds = (0...arr.size).step(2).map{|i| arr[i]}
evens = (1...arr.size).step(2).map{|i| arr[i]}

odds_count = {}
evens_count = {}
odds_count.default = 0
evens_count.default = 0

odds.each{|it| odds_count[it] += 1}
evens.each{|it| evens_count[it] += 1}

odds_count_arr = odds_count.to_a.sort_by{|it| -it[1]}
evens_count_arr = evens_count.to_a.sort_by{|it| -it[1]}
odds_count_arr.push [nil, 0]
evens_count_arr.push [nil, 0]

answer = arr.size
if odds_count_arr[0][0] == evens_count_arr[0][0]
    answer -= (odds_count_arr[0][1] + [odds_count_arr[1][1], evens_count_arr[1][1]].max)
else
    answer -= (odds_count_arr[0][1] + evens_count_arr[0][1])
end

puts answer


Measured memory_bytes: 21888
N, C = map(int, input().split())
D = [list(map(int, input().split())) for i in range(C)]
G = [list(map(int, input().split())) for i in range(N)]

cost = [[0 for j in range(C)] for i in range(3)]
for i in range(N):
    for j in range(N):
        rem = (i+j+2)%3
        x = G[i][j] -1
        for y in range(C):
            cost[rem][y] += D[x][y]
ans = float('inf')
for i in range(C):
    for j in range(C):
        if i == j:
            continue
        for k in range(C):
            if i == k or j == k:
                continue
            ans = min(ans, cost[0][i] + cost[1][j] + cost[2][k])
print(ans)

Measured memory_bytes: 75696
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
int n;
cin>>n;
int t[n+1],x[n+1],y[n+1];
for(int i =1;i<=n;i++)
{
    cin>>t[i] >>x[i]>>y[i];
}
t[0] = 0;x[0] = 0;y[0] = 0;
int flag = 0;
for(int i =1;i<=n;i++)
{
    int time = t[i] -t[i-1];
    int dist = abs(x[i]-x[i-1])+abs(y[i]-y[i-1]);
    if(dist<=time&&(dist%2==time%2)) {
        flag = 1;
    }
    else
    {
        flag =0;
        break;
    }
}
if(flag == 0) cout<<"No";
else cout<<"Yes";
return 0;
}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
#define maxn 300000
int a[maxn+5],ans[maxn+5];
int main(){
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	int n,x;scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",&x),a[x]++;
	sort(a+1,a+n+1,greater<int>());a[0]=maxn*2;
	int remain=0,l=n;
	for(int i=n;i;i--){
		l=min(l,i);
		do{
			if(a[l]==a[l-1])l--;
			if(remain>=i-l+1){
				int x=min(remain/(i-l+1),a[l-1]-a[l]);
				remain-=x*(i-l+1),a[l]+=x;
			}
		}while(a[l]==a[l-1]);
		remain+=(ans[i]=a[l]);
	}
	for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
	return 0;
} 

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

const int N = 3e3 + 5;

double p[N], dp[N][N];

double solve(int i, int heads) {
  if (i == 0 && heads == 0)
    return 1;
  if (i != 0 && heads == 0)
    return (1-p[i])*solve(i-1, 0);
  if (i == 0 && heads != 0)
    return 0;
  if (dp[i][heads] != -1)
    return dp[i][heads];
  double &x = dp[i][heads];
  x = p[i]*solve(i-1, heads-1) + (1-p[i])*solve(i-1, heads);
  return dp[i][heads];
}

int main () {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  for (int i = 0; i < N; i++)
    for (int j = 1; j < N; j++)
      dp[i][j] = -1;
  for (int i = 1; i <= n; i++)
    cin >> p[i];
  double ans = 0;
  for (int i = (n+1)/2; i <= n; i++) {
    ans += solve(n, i);
  }
  cout << fixed << setprecision(9) << ans << '\n';
  return 0;
}

Measured memory_bytes: 71040