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

using namespace std;
using i64 = int64_t;
// #define int i64
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
const int INF = (1 << 30);
const i64 INFL = (1LL << 62);
const i64 MOD = 1000000007;

struct UnionFindSize {
  std::vector<int> data;
  const int n;
  UnionFindSize(int num) : data(n, -1), n(num) { data.resize(n); }
  int find(int k) {
    assert(0 <= k && k < n);
    if (data[k] < 0) return k;
    return (data[k] = find(data[k]));
  }
  bool unite(int x, int y) {
    assert(0 <= x && x < n);
    assert(0 <= y && y < n);
    x = find(x), y = find(y);
    if (x == y) return false;
    if (data[x] > data[y]) std::swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return true;
  }
  int size(int k) {
    assert(0 <= k && k < n);
    return (-data[find(k)]);
  }
  bool same(int x, int y) {
    assert(0 <= x && x < n);
    assert(0 <= y && y < n);
    return find(x) == find(y);
  }
};

void print() { std::cout << std::endl; }
template <typename T, typename... A>
void print(const T& first, const A&... rest) {
  cout << sizeof...(rest) << endl;
  std::cout << first;
  if (sizeof...(rest)) std::cout << " ";
  print(rest...);
}
template <typename... A>
void print(const A&... rest) {
  print(rest...);
}
template <typename A>
void print(const std::vector<A>& v) {
  std::for_each(v.begin(), v.end(), [](A x) { std::cout << x << " "; });
  std::cout << std::endl;
}
// #undef int
int main() {
  // #define int i64
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, m, k;
  cin >> n >> m >> k;
  UnionFindSize uf(n);
  vector<vector<int>> gf(n);
  vector<vector<int>> gb(n);
  rep(i, m) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    uf.unite(a, b);
    gf[a].push_back(b);
    gf[b].push_back(a);
  }
  vector<int> d(n, 0);
  rep(i, k) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    gb[a].push_back(b);
    gb[b].push_back(a);
    if (uf.same(a, b)) {
      d[a]++;
      d[b]++;
    }
  }
  vector<int> ans(n);
  rep(i, n) { ans[i] = max(0, uf.size(i) - 1 - (int)(gf[i].size()) - d[i]); }
  rep(i, n) {
    cout << ans[i];
    if (i != n) {
      cout << " ";
    }
  }
  cout << endl;
  // cout << "f" << endl;

  // rep(i, n) { print(gf[i]); }
  // cout << "block" << endl;
  // rep(i, n) { print(gb[i]); }
  // print(uf.data);
  return 0;
}

Measured memory_bytes: 29048
N = int(input())
A = list(map(int, input().split()))

from itertools import accumulate


ans = float("inf")
if N == 4:
    ans = min(ans, (max(A) - min(A)))
else:
    cs = list(accumulate(A))
    l = 0
    r = 0
    for i in range(1, N - 2):
        while cs[i] > cs[l] + cs[l+1]:
            l += 1
        while cs[-1] + cs[i] > cs[r] + cs[r+1]:
            r += 1
        P = cs[l]
        Q = cs[i] - P
        R = cs[r] - P - Q
        S = cs[-1] - cs[r]
        ans = min(ans, (max(P, Q, R, S) - min(P, Q, R, S)))

print(ans)

Measured memory_bytes: 24180
#include <iostream>
using namespace std;
int main()
{
  long N;
  cin >> N;
  for (long h = 1; h <= 3500; h++)
  {
    for (long n = 1; n <= 3500; n++)
    {
      if ((4 * h * n - N * n - N * h) == 0)
        continue;
      if ((N * n * h) % (4 * h * n - N * n - N * h) == 0)
      {
        long w = (N * n * h) / (4 * h * n - N * n - N * h);
        if (1 <= w && w <= 3500)
        {
          cout << h << " " << n << " " << w << endl;
          return 0;
        }
      }
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std; 
int main(){
	int n , d , x ;
	cin >> n >> d >> x ;
	int a , c=0; 
	while(n--){
		cin >> a ;
		for (int i = 1; i <= d ; i+=a)
		{
			c++ ;
		}
	}
	cout << c+x << endl ;
	return 0 ;
}

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

using namespace std;

struct Edge {
    int source, target, distance;
};

struct Node {
    int vertex, weight;
    bool operator > (const Node& node) const {
        return weight > node.weight;
    }
};


int main()
{
    int n_vertices, n_edges, source_node;
    cin >> n_vertices >> n_edges >> source_node;
    vector< vector<Edge> > adjlist(n_vertices);

    for (int i = 0; i < n_edges; ++i) {
        int source, target, distance;
        cin >> source >> target >> distance;
        adjlist[source].emplace_back(Edge{source, target, distance});
    }

    int visited = 0;
    vector<int> closed(n_vertices, numeric_limits<int>::max());
    priority_queue<Node, vector<Node>, greater<Node> > open;

    open.push(Node{source_node, 0});
    while (visited != n_vertices && !open.empty()) {
        auto node = open.top();
        open.pop();
        if (closed[node.vertex] != numeric_limits<int>::max()) continue;
        for (auto edge : adjlist[node.vertex]) {
            int child = edge.target;
            int distance = edge.distance;
            open.push(Node{child, node.weight + distance});
        }
        closed[node.vertex] = node.weight;
        visited++;
    }

    for (auto weight : closed) {
        if (weight == numeric_limits<int>::max()) {
            cout << "INF";
        } else {
            cout << weight;
        }
        cout << endl;
    }
}





Measured memory_bytes: 16436
from bisect import bisect_left as bl
from sys import maxint as mi
A,B,Q=map(int,raw_input().split())
da=list()
for i in xrange(A):
	da.append(int(raw_input()))
db=list()
for i in xrange(B):
	db.append(int(raw_input()))
da.sort()
db.sort()

for i in xrange(Q):
	p=int(raw_input())
	a=bl(da,p)
	b=bl(db,p)
	v1,v2=mi if a>A-1 else da[a],mi if b>B-1 else db[b]
	x0=abs(v1-p)
	x0=x0+min(abs(v1-v2),mi if b+1>=B else abs(v1-db[b+1]),mi if b-1<0 else abs(v1-db[b-1]))
	x1=mi
	if a>0:
		x1=abs(da[a-1]-p)
		x1=x1+min(abs(da[a-1]-v2),mi if b+1>=B else abs(da[a-1]-db[b+1]),mi if b-1<0 else abs(da[a-1]-db[b-1]))
	x2=mi
	if a+1<A:
		x2=abs(da[a+1]-p)
		x2=x2+min(abs(da[a+1]-v2),mi if b+1>=B else abs(da[a+1]-db[b+1]),mi if b-1<0 else abs(da[a+1]-db[b-1]))
	v=min(x0,x1,x2)
	
	x0=abs(v2-p)
	x0=x0+min(abs(v1-v2),mi if a+1>=A else abs(v2-da[a+1]),mi if a-1<0 else abs(v2-da[a-1]))
	x1=mi
	if b>0:
		x1=abs(db[b-1]-p)
		x1=x1+min(abs(db[b-1]-v1),mi if a+1>=A else abs(db[b-1]-da[a+1]),mi if a-1<0 else abs(db[b-1]-da[a-1]))
	x2=mi
	if b+1<B:
		x2=abs(db[b+1]-p)
		x2=x2+min(abs(db[b+1]-v1),mi if a+1>=A else abs(db[b+1]-da[a+1]),mi if a-1<0 else abs(db[b+1]-da[a-1]))
	print min(v,x0,x1,x2)

Measured memory_bytes: 10240
#include <math.h>

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
int main() {
    string S;
    string es = "es";
    string ss = "s";
    cin >> S;
    if (S[S.size()-1] == 's')
        S = S + es;
    else
        S = S + ss;
    cout << S << endl;
}

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

const int NIL = -1;

struct chem{
	int a, b, c;
};

vector<chem> ch;

int dp[41][401][401];

int gcd(int a, int b){
	if (b == 0) return a;
	return gcd(b, a % b);
}
int N, MA, MB;

int cost(int n, int ma, int mb){
	int na = ma, nb = mb;
	int g = gcd(na, nb);
		if (g != 0){
		na /= g; nb /= g;
	}
	if (n == 0 and (na != MA or nb != MB)){
		return 40000;
	}
	if (na == MA and nb == MB){
		return 0;
	}
	int& ans = dp[n][ma][mb];
	if (ans == NIL){
		int a = cost(n - 1, ma, mb);
		int b = cost(n - 1, ma + ch[n].a, mb + ch[n].b) + ch[n].c;
		ans = min(a, b); 
	}
	return ans;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> N >> MA >> MB;	
	ch.resize(N + 1);
	memset(dp, NIL, sizeof dp);
	
	int a, b, c;
	for (int i = 1; i <= N; i++){
		cin >> a >> b >> c;
		ch[i] = {a, b, c};
	}
	//assert(gcd(MA, MB) == 1);
	
	int ans = cost(N, 0, 0);
	if (ans == 40000){
		ans = -1;
	}
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 25984
#include<cstdio>
int a[105];
inline int read() {
	register int x=0,f=1;register char s=getchar();
	while(s>'9'||s<'0') {if(s=='-') f=-1;s=getchar();}
	while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
	return x*f;
}
int main() {
	int n=read(),m=read(),cnt=0,sum=0;
	for(register int i=1;i<=n;++i) {a[i]=read();sum+=a[i];}
	for(register int i=1;i<=n;++i) {if(a[i]*1.0>=sum/(4.0*m)) ++cnt;}
	if(cnt>=m) printf("Yes\n");
	else printf("No\n");
	return 0;
}

Measured memory_bytes: 128
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7

N = i()
a = l()
b1 = []
b2 = []
for i in range(N):
    if i%2==0:
        b1.append(a[i])
    else:
        b2.append(a[i])
c1 = Counter(b1)
c2 = Counter(b2)
k1,v1 = c1.most_common()[0]
k2,v2 = c2.most_common()[0]
ans = v1+v2
v3 = 0
v4 = 0
if k1 == k2:
    if len(list(c2.values())) > 1:
        v4 = c2.most_common()[1][1]
    if len(list(c1.values())) > 1:
        v3 = c1.most_common()[1][1]
    ans = max(v1+v4,v2+v3)
print(N-ans)

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

#define __STDC_FORMAT_MACROS
#define p64 PRId64

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR (i, 0, n)
#define ALL(f, x, ...)                                                         \
    ([&] (decltype ((x)) ALL) {                                                \
        return (f) (begin (ALL), end (ALL), ##__VA_ARGS__);                    \
    }) (x)

using namespace std;
using ll = int64_t;

int main() {
    string S;
    cin >> S;
    if (S[0] == S[1] && S[1] != S[2] && S[2] == S[3])
        cout << "Yes" << endl;
    else if (S[0] == S[2] && S[1] != S[2] && S[1] == S[3])
        cout << "Yes" << endl;
    else if (S[0] == S[3] && S[0] != S[1] && S[1] == S[2])
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3600
i;char s[99];main(){for(;~scanf("%[^\n]",s);i=!puts(s))for(getchar();!strstr(s,"this")&!strstr(s,"the")&!strstr(s,"that");)for(i=0;s[i];)s[i++]=isalpha(s[i])?s[i]-122?s[i]+1:97:s[i];}

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

class UnionFindTree
{
public:
	int n;
	vector<int> par;
	vector<int> rank;
	UnionFindTree(){}
	UnionFindTree(int num){
		n = num;
		par.resize(n);
		rank.resize(n);
		for (int i = 0; i < n; ++i)
		{
			par[i] = i;
			rank[i] = 0;
		}
	}

	int find(int x){
		if(par[x] == x){
			return x;
		}else{
			return par[x] = find(par[x]);
		}
	}

	void unite(int x, int y){
		int root_x = find(x);
		int root_y = find(y);
		if(root_x == root_y) return;
		if(rank[root_x] < rank[root_y]){
			par[root_x] = root_y;
		}else{
			par[root_y] = root_x;
			if(rank[root_x] == rank[root_y]) rank[root_x]++;
		}
	}

	bool same(int x, int y){
		return find(x) == find(y);
	}
};


class Connectivity
{
public:
	int n, k, l;
	UnionFindTree uft1;
	UnionFindTree uft2;
	Connectivity();
	void exec();	
};

Connectivity::Connectivity(){
	cin >> n >> k >> l;
	uft1 = UnionFindTree(n+1);
	uft2 = UnionFindTree(n+1); 
	for (int i = 0; i < k; ++i)
	{
		int p, q;
		cin >> p >> q;
		uft1.unite(p, q);
	}
	for (int i = 0; i < l; ++i)
	{
		int r, s;
		cin >> r >> s;
		uft2.unite(r, s);
	}
}

void Connectivity::exec(){
	map<pair<int, int >, int> hash;
	for (int i = 1; i <= n; ++i)
	{
		pair<int, int> p;
		p.first = uft1.find(i);
		p.second = uft2.find(i);
		hash[p]++;
	}
	for (int i =1 ; i <= n; ++i)
	{
		pair<int, int> p;
		p.first = uft1.find(i);
		p.second = uft2.find(i);
		cout << hash[p];
		if(i < n){
			cout << " ";
		}
	}
	cout << endl;

}

int main(){
	Connectivity c = Connectivity();
	c.exec();

}


Measured memory_bytes: 15104
// SeeAlso: https://atcoder.jp/contests/abc053/tasks/abc053_a

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define MAX 100000
#define NIL -1

typedef int _loop_int;
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// 最大公約数
inline constexpr ll gcd(ll a,ll b){if(!a||!b)return 0;while(b){ll c=b;b=a%b;a=c;}return a;}
// 最小公倍数
inline constexpr ll lcm(ll a,ll b){if(!a||!b)return 0;return a*b/gcd(a,b);}

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
template<class T> void print(const T& x){cout << setprecision(12) << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }

int x;

int main() {
    
    cin >> x;
    if(x<1200) {
        print("ABC");
    } else {
        print("ARC");
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <algorithm>
#include <bitset>
#define range(i, r) for(int i=0;i<r;i++)
#define ranges(i, l, r) for(int i=l;i<r;i++)
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi std::vector<std::vector<int> >
#define vvl std::vector<std::vector<ll> >
#define MODs 1000000007;
#define MODn 1000000009;
typedef long long int ll;
using namespace std;

int main(int argc, char const *argv[]) {
  int R, G, B, N;
  ll ans=0;
  std::cin >> R >> G >> B >> N;
  for(int i=0;i*R<=N;i++){
    for(int j=0;j*G+i*R<=N;j++){
      if((N-i*R-j*G)%B==0)ans++;
    }
  }
  std::cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 888
N = gets.to_i
A = gets.to_i
B = gets.to_i
C = gets.to_i
D = gets.to_i
E = gets.to_i
min = [A, B, C, D, E].min
m = N / min
c = N % min == 0 ? m : m + 1
puts(c + 4)


Measured memory_bytes: 1788
N = int(input())
*A, = map(int, input().split())
money, stock = 1000, 0
for a, nxt in zip(A, A[1:]):
    money += stock * a
    stock = 0
    if a <= nxt:
        stock, money = divmod(money, a)
money += stock * A[-1]
print(money)

Measured memory_bytes: 9104
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {

  public static void main(String[] args) {
    new Main().run();
  }

  public void run() {
    
    try(BufferedReader in = new BufferedReader(new InputStreamReader(System.in))) {

      int n = Integer.parseInt(in.readLine());
      String line = in.readLine();

      int[] seqA = new int[n/2];
      int[] seqB = new int[n/2];

      List<Integer> listA = new ArrayList<>();
      List<Integer> listB = new ArrayList<>();
      Map<Integer,Integer> mapA = new HashMap<>();
      Map<Integer,Integer> mapB = new HashMap<>();
      int offset=0,next=0;
      char regx = ' ';
      for(int i=0, j=0; i<n; i++, j= i >> 1) {
        if((next = line.indexOf(regx,offset)) == -1)
          next = line.length();
        Integer num = Integer.parseInt(line.substring(offset, next));
        offset = ++next;

        if((i & 1) == 0) {
          seqA[j] = num;
          if(mapA.containsKey(num)) {
            mapA.replace(num, mapA.get(num) + 1);
          } else {
            mapA.put(num, 1);
            listA.add(num);
          }
        }
        else {
          seqB[j] = num;
          if(mapB.containsKey(num)) {
            mapB.replace(num, mapB.get(num) + 1);
          } else {
            mapB.put(num, 1);
            listB.add(num);
          }
        }
      }

      int vma,vmb,xa,xb;
      vma = vmb = xa = xb =0;
      for (Integer var : listA) {
        int ma = mapA.get(var);
        if(vma < ma) {
          vma = ma;
          xa = var;
        }
      }
      for (Integer var : listB) {
        int mb = mapB.get(var);
        if(vmb < mb) {
          vmb = mb;
          xb = var;
        }
      }

      int cca,ccb;
      cca = ccb = 0;
      for (int i : seqA) {
        if(i != xa) cca++;
      }
      for (int i : seqB) {
        if(i != xb) ccb++;
      }

      int vma2,vmb2,xa2,xb2;
      vma2 = vmb2= xa2 = xb2 =0;
      int cca2,ccb2;
      cca2 = ccb2 = 0;
      int ans = 0;
      if(xa == xb) {
        for (Integer var : listA) {
          int ma = mapA.get(var);
          if(var != xa && vma2 < ma) {
            vma2 = ma;
            xa2 = var;
          }
        }
        for (Integer var : listB) {
          int mb = mapB.get(var);
          if(var != xb && vmb2 < mb) {
            vmb2 = mb;
            xb2 = var;
          }
        }
      
        for (int i : seqA) {
          if(i != xa2) cca2++;
        }
        for (int i : seqB) {
          if(i != xb2) ccb2++;
        }

        ans = cca2 > ccb2 ? cca + ccb2 : cca2 + ccb;
      }
      else {
        ans = cca + ccb;
      }

      System.out.println(ans);
    }
    catch(IOException e) {
      System.err.println(e);
    }
  }
}

Measured memory_bytes: 45396
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define ld long double
#define mod 998244353
int main()
{
    ll n,k;
    cin>>n>>k;
    ll a[n+1];
    for(int x=1;x<=n;x++)
        cin>>a[x];
    bool vis[n+1];
    memset(vis,false,sizeof(vis));
    ll f=0;
    ll p=1;
    vis[p]=true;
    ll dp[n+1];
    memset(dp,0,sizeof(dp));
    while(k>0 && !vis[a[p]])
    {   ll f=dp[p];
        p=a[p];
        dp[p]=f+1;
        vis[p]=true;
        --k;
    }
    if(k==0)
        cout<<p;
    else
    {
        ll s=dp[p]-dp[a[p]]+1;
        --k;
        k%=s;
        //cout<<p<<" "<<a[p]<<" "<<k<<"\n";
        p=a[p];
    while(k>0)
    {
        p=a[p];
        --k;
    }
    cout<<p<<"\n";
    }
}


Measured memory_bytes: 6912
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define pp pair<ll,ll>
#define ppp pair<ll,pp >
#define trace(...) cout<<"Line:"<<__LINE__<<" "; __f(#__VA_ARGS__, __VA_ARGS__)
template<typename Arg1>
void __f(const char* name, Arg1&& arg1) {
	cout<<name<<" : "<<arg1<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma=strchr(names+1,',');
	cout.write(names,comma-names)<<" : "<<arg1<<" | ";
	__f(comma+1,args...);
}
typedef tree<pp,null_type,less<pp>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define ld long double
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rep(i,a,b) for(ll i=a;i<b;i+=1)
#define sz(v) (ll)(v.size())
#define hell (ll)1000000007
#define slld(x) scanf("%lld",&x)
ll t=1, tt;
const ll N=200005, inf=1e18;
vector<pair<ll,ll> > ending[N];
ll tr[4*N], lazy[4*N], dp[N];
ll combine(ll x,ll y){return min(x,y);}
void lazify(ll node,ll l,ll r){
	if(lazy[node]){
		tr[node]+=lazy[node];
		if(l!=r){
			lazy[node<<1]+=lazy[node];
			lazy[node<<1|1]+=lazy[node];
		}
	}
	lazy[node]=0;
}
void update(ll node,ll l,ll r,ll a,ll b,ll val){
	lazify(node,l,r);
	if(b<l || r<a || l>r)return;
	if(a<=l and r<=b){
		tr[node]+=val;
		if(l!=r){
			lazy[node<<1]+=val;
			lazy[node<<1|1]+=val;
		}
		return;
	}
	ll mid=(l+r)/2;
	update(node<<1,l,mid,a,b,val);
	update(node<<1|1,mid+1,r,a,b,val);
	tr[node]=combine(tr[node<<1],tr[node<<1|1]);
}
void assign(ll node,ll l,ll r,ll id,ll val){
	lazify(node,l,r);
	if(l==r){
		tr[node]=val;
		return;
	}
	ll mid=(l+r)/2;
	if(l<=id and id<=mid)
		assign(node<<1,l,mid,id,val);
	else
		assign(node<<1|1,mid+1,r,id,val);
	tr[node]=combine(tr[node<<1],tr[node<<1|1]);
}
ll query(ll node,ll l,ll r,ll a,ll b){
	lazify(node,l,r);
	if(l>b || a>r || l>r)return inf;
	if(a<=l and r<=b)return tr[node];
	ll mid=(l+r)/2;
	return combine(query(node<<1,l,mid,a,b),query(node<<1|1,mid+1,r,a,b));
}
void solve(){
	ll n, m, tot=0, x, y, ans;
	cin>>n>>m;
	rep(i,0,m){
		cin>>x>>y>>ans;
		tot+=ans;
		ending[y+1].pb({x+1,ans});
	}
	rep(i,1,N-1)assign(1,1,N-1,i,0);
	ans=inf;
	rep(i,2,n+3){
		dp[i]=query(1,1,N-1,1,i-1);
		for(auto u : ending[i]){
			update(1,1,N-1,1,u.fi-1,u.se);
		}
		assign(1,1,N-1,i,dp[i]);
		ans=min(ans,dp[i]);
	}
	cout<<tot-ans<<endl;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
   	//cin>>t;
   	tt=t;
    while(t--){
        solve();
        if(t)cout<<"\n";
    }
    return 0;
}


Measured memory_bytes: 25216
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
#define rFor(i, a, b) for(int (i)=(a)-1; (i)>=(b); (i)--)
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
using namespace std;
typedef long long lint;

bool check(lint a, lint b, lint mid){
  lint c = (mid + 1) / 2;
  return c*(mid+1-c) <= a*b-1;
}

int main(){
  int q; cin >> q;
  rep(i, q){
    lint a, b; cin >> a >> b;
    if(a == b){
      cout << 2*a - 2 << endl;
      continue;
    }
    lint high, low;
    high = 1e10;
    low = 1;
    while(high-low > 1){
      lint mid = (high + low) / 2;
      if(check(a, b, mid)) low = mid;
      else high = mid;
    }
    cout << low - 1 << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
   long long int a,b,c,d;
    while(cin>>a>>b){
    c=a+b;
    d=0;
    while(c!=0){
        d++;
        c=c/10;
    }
        cout<<d<<endl;
    }
        return 0;
}

Measured memory_bytes: 2984
#include <stdio.h>

#define FREE 0
#define NOT_FREE 1

#define N 8

typedef struct {
  int col[N];
  int dpos[2*N-1];
  int dneg[2*N-1];
  int kotei[N];
}CHECK;
  
int putQueen(int, CHECK *, int *);
void printBoard(int *);

int main()
{
  CHECK check;
  int i, j, k, r, c, row[N];

  for(i = 0; i < N; i++) {
    check.col[i] = FREE;
    row[i] = -1;
    check.kotei[i] = FREE; 
  }
  for(i = 0; i < 2*N-1; i++) {
    check.dpos[i] = FREE;
    check.dneg[i] = FREE;
  }

  
  
  scanf("%d",&k);

  for(i = 0; i < k; i++) {
    scanf("%d%d",&r,&c);
    check.kotei[r] = NOT_FREE;
    row[r] = c;
    check.col[c] = check.dpos[r+c] = check.dneg[r-c+N-1] = NOT_FREE;
  }

  putQueen(0, &check, row);

  return 0;
}

int putQueen(int i, CHECK *check, int *row)
{
  int j;
  
  if(i == N) {
    printBoard(row);
    return 1;
  }
  if(check->kotei[i] == NOT_FREE) {
    if(putQueen(i+1, check, row) == 1) return 1;
    return 0;
  }
  
  for(j = 0; j < N; j++) {   
    if(check->col[j] == NOT_FREE ||
       check->dpos[i+j] == NOT_FREE || check->dneg[i-j+N-1] == NOT_FREE) continue;
    
    //put a queen at (i, j)
    row[i] = j;
    check->col[j] = check->dpos[i+j] = check->dneg[i-j+N-1] = NOT_FREE;
    
    //try the next row
    if(putQueen(i+1, check, row) == 1) return 1;
    
    //remove the queen at (i, j) for backtracking
    check->col[j] = check->dpos[i+j] = check->dneg[i-j+N-1] = FREE;  
  }
  return 0;
}

void printBoard(int *row)
{
  int i, j;
  
  for(i = 0; i < N; i++) {
    for(j = 0; j < row[i]; j++) {
      printf(".");
    }
    printf("Q");
    for(j = row[i]+1; j < N; j++) {
      printf(".");
    }
    printf("\n");
  }
}



Measured memory_bytes: 2084
#include <memory>
#include <map>
#include <cassert>
#include <array>
#include <iterator>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <string>
#include <array>
#include <numeric>

class Solution {
public:
    void solve(std::istream& in, std::ostream& out) {
      int n;
      in >> n;
      int c = 0;
      while (n > 1)
        {
          n /= 2;
          ++c;
        }
      out << (1 << c) << '\n';
    }
};

void solve(std::istream& in, std::ostream& out)
{
    out << std::setprecision(12);
    Solution solution;
    solution.solve(in, out);
}

#include <iostream>

int main ()
{
  solve (std::cin, std::cout);
}


Measured memory_bytes: 256
N = int(input())
s = [0] * N
t = [0] * N

for i in range(N):
  s[i], t[i] = map(int, input().split())

for n in range(N):
  if s[n]==t[n] and s[n+1]==t[n+1] and s[n+2]==t[n+2]:
    print('Yes')
    break
  elif n == N - 3:
    print('No')
    break
  else:
    continue

Measured memory_bytes: 9192
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
	    Scanner scanner = new Scanner(System.in);

	    char S = scanner.next().charAt(0);
	    
	    String result = "a";
	    if (Character.isUpperCase(S)) {
	        result = "A";
	    }


	    System.out.println(result);
	}

}

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

int main() {
	int N,D,X;
  	cin >> N >> D >> X;
  
  	vector<int> vec(N);
  	for(int i = 0; i < N; i++) {
    	cin >> vec.at(i);
    }
  
 	int sum = 0; 
  
  	for(int i = 0; i < N; i++) {
      int day = 1;
  	while(day <= D) {
      day += vec.at(i);
      sum++;
     }
    }
  
  	cout << sum + X << endl;
}

Measured memory_bytes: 256
#include "stdio.h"
#include "stdlib.h"

int main(){

int n;

scanf("%d",&n);

char s[100];
char t[100];

scanf("%s %s",s,t);

char buf[n*2];

for(int i=0;i<n;i++){
    buf[i*2]=s[i];
    buf[(i*2)+1]=t[i];
}


for(int i=0;i<4;i++){
    buf[(2*n)+i]=0x00;
}
printf("%s",buf);
}


Measured memory_bytes: 128
var i,j,k,l,o,p,count,n,cautpetrea:longint;
type vector = array[1..2010] of longint;
var x:vector;
function check(a,b:longint):boolean;
begin
if a<b then check:=true
else check:=false;
end;
function cautbin(stanga,dreapta,valoari:longint):longint;
var mid,rs:longint;
begin
rs:=stanga-1;
while stanga<=dreapta do begin
  mid:=(stanga+dreapta) div 2;
  if check(x[mid],valoari) then begin
    rs:=mid;
    stanga:=mid+1;
    end
  else dreapta:=mid-1;
  end;
cautbin:=rs;
end;
  

function triunghi(a,b,c:longint):boolean;
begin
if (a+b>c) and (a+c>b) and (c+b>a) then begin
  // writeln(a,' ',b,' ',c);
   triunghi:=true;
   end
else  begin
  //writeln(a,' ',b,' ',c);
  triunghi:=false;
  end;
end;
procedure swap(var a,b:integer);
var temp:integer;
begin
temp:=a;
a:=b;
b:=temp;
end;
procedure bubleSort(var a:vector;n:longint);
var i,j:longint;
isSwapped:boolean;
begin
for i:=1 to n do begin
            isSwapped:=false;
                for j:=1 to n-i do 
                            if a[j]> a[j+1] then begin
                                              swap(a[j],a[j+1]);
                                              isSwapped:=true;
                                              end;
                if not isSwapped then break;
                end;
                        

end;
begin
read(n);
for i:=1 to n do 
  read(x[i]);
bublesort(x,n);
for i:=1 to n do
  for j:=i+1 to n do begin
    cautpetrea:=+cautbin(j,n,x[i]+x[j]);
    if cautpetrea>j then count:=count+(cautpetrea-j);
    end;
writeln(count);
end.

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0;i < n;i++)
#define rev(i, n) for(int i = n;i >= 0;i--)
#define Rep(i, m, n) for(int i = m;i < n;i++)
#define repeatrev(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999
#define itn int

using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;
typedef priority_queue<int> Pr;

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};
map<char, int> S;
int main(){
    int P [10]={0 ,0 ,0 ,0 ,0 ,0 ,1 ,1 ,1 ,2};
    int Q [10]={1 ,1 ,1 ,2 ,2 ,3 ,2 ,2 ,3 ,3};
    int R [10]={2 ,3 ,4 ,3 ,4 ,4 ,3 ,4 ,4 ,4};
    ll int n;
    cin >> n;
    ll int a[5];
    memset(a, 0, sizeof(a));
    rep(i, n){
        string s;
        cin >> s;
        if(s[0] == 'M') a[0] ++;
        else if(s[0] == 'A') a[1] ++;
        else if(s[0] == 'R') a[2] ++;
        else if(s[0] == 'C') a[3] ++;
        else if(s[0] == 'H') a[4] ++;
    }
    ll ans = 0;
    /*
    rep(i, 3){
        for(int j = i + 1; j < 4; j ++){
            for(int k = j + 1; k < 5; k ++){
                ans += a[i] * a[j] * a[k];
            }
        }
    }*/
    rep(i, 10) ans += a[P[i]] * a[Q[i]] * a[R[i]];

    cout << ans << endl;



}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;

public class AtCoderE
{
    static void Main()
    {
        long n = long.Parse(Console.ReadLine());
        if (n % 2 == 1)
        {
            Console.WriteLine(0);
            return;
        }

        long answer = 0;

        long div = 10;
        while (true)
        {
            if (div > n)
            {
                break;
            }
            answer += n / div;
            div = div * 5;
        }

        Console.WriteLine(answer);
    }
}

Measured memory_bytes: 13140
#include<bits/stdc++.h>
using namespace std;
const int MAX = 10010;
int cnt[MAX];

int main(){
  int N;
  cin >> N;
  for(int x=1; x<=110; x++){
    for(int y=1; y<=110; y++){
      for(int z=1; z<=110; z++){
        int64_t i = x*x + y*y + z*z + x*y + y*z + z*x;
        if(i > N){
          continue;
        }
        else{
          cnt[i]++;
        }
      }
    }
  }
  
  for(int i=0; i<N; i++){
    cout << cnt[i+1] << endl;
  }
}
  

Measured memory_bytes: 3664
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define pii pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
#define sz(x) ((ll)(x).size())
#define pb push_back
#define mp make_pair
#define bit(n) (1LL<<(n))
#define F first
#define S second
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll INF = 1LL<<60;
const ll mod = (int)1e9 + 7;

int main() {
    string s;
    cin >> s;
    int n=s.length();
    int cnt=0;
    rep(i,n/2){
        if(s[i]!=s[n-i-1])cnt++;
    }
    cout << cnt;


    
}

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

int main(int argc, char *argv[])
{
    int N, K;
    std::cin >> N >> K;

    int num = 1;
    for (int i = 0; i < N; i++) {
        if (num*2 >= (num+K)) {
            num += K;
        } else {
            num *= 2;
        }
    }

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

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
using namespace std;
int a, b, c, d;
int main(){
    cin >> a >> b >> c >> d;
    if (a*b > c*d)
        cout << a*b << endl;
    else if (a*b < c*d)
        cout << c*d << endl;
    else
        cout << a*b << endl;
    return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB = sorted(AB, key=lambda x: x[0])
r = 0
for a, b in AB:
    if M <= 0:
        break
    if b <= M:
        r += a*b
        M -= b
    elif b >= M:
        r += a*M
        break
print(r)


Measured memory_bytes: 24504
# Five Dishes
# https://atcoder.jp/contests/abc123/tasks/abc123_b

NUM_DISHES = 5
tt = 0
itvs = list()

for i in range(NUM_DISHES):
    st = int(input())
    tt += st
    if st % 10 == 0:
        itvs.append(0)
    else:
        itvs.append(10 - st % 10)

itvs.sort()

for interval in range(len(itvs) - 1):
    tt += itvs[interval]

print "{}".format(tt)


Measured memory_bytes: 2568
/**
DufauX-XuafuD
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define reset(x) memset(x,-1,sizeof(x))
#define CheckBit(a,b) (a&(1ll<<b))
#define SetBit(a,b) a=(a|(1ll<<b))
#define UnSetBit(a,b) a=(a&(~(1ll<<b)))
#define maxx 10000006
#define PI 2*acos(0.0)
const long long INF = 2000000000000000000LL;	// 2e18
const int inf = 0x3f3f3f3f;	// 1061109567
const long double EPS = 1e-9;
//bitset<maxx/2>vis;
//bitset<maxx>pr;
//int mobi[maxx+10];
//vector<ll>prime;
//void sieve(){
//    ll x=maxx/2, y=sqrt(maxx)/2;
//    for(ll i=1;i<=y;i++){
//        if(vis[i]==0){
//            for(ll j=(i*(i+1)*2);j<x;j+=(2*i)+1)
//                vis[j]=1;
//        }
//    }
//    prime.push_back(2);
//    for(ll i=3;i<maxx;i+=2)
//        if(vis[i/2]==0)
//        prime.push_back(i);
//}
//void generate_mobius()
//{
//    for(int i=0;i<maxx;i++)mobi[i]=1;
//    for(int i=2;i<maxx;i++){
//        if(!pr[i]){
//            mobi[i]*=-1;
//            for(int j=i+i;j<maxx;j+=i){
//                pr[j]=1;
//                mobi[j]*=(j%(i*i)?-1:0);
//            }
//        }
//    }
//}
//bool isprime(ll a)
//{
//    if(a==1)return false;
//    if(a==2)return true;
//    if(a%2==0)return false;
//    for(ll i=0;i<prime.size() && prime[i]*prime[i]<=a;i++)
//        if(a%prime[i]==0)return false;
//    return true;
//}
/* Calculate ( a*b ) %c */
inline ll mulmod(ll a, ll b, ll c) {
    ll ret = 0 , cur = a % c ;
    while(b) { if(b%2) ret=(ret+cur)%c; cur=(cur<<1)%c; b=b>>1; }
    return ret%c;
}
//Calculate (b^p)%m || modular inverse: b^-1 = bigmod(b, m-2, m)
inline ll bigmod(ll b, ll p, ll m){
    ll ret = 1, cur = b % m;
    while(p) { if(p&1) ret=(ret*cur)%m; cur=(cur*cur)%m; p=p>>1; }
    return ret;
}
inline ll modulo(ll a,ll b,ll c) { //Same as big mod, use for numbers over 1e10
    ll ret = 1 , cur = a%c ;
    while(b) { if(b%2) ret=mulmod(ret,cur,c); cur=mulmod(cur,cur,c); b=b>>1; }
    return ret%c ;
}
inline ll power(ll b, ll p){
    ll ret = 1, cur = b;
    while(p) { if(p&1) ret=(ret*cur); cur=(cur*cur); p=p>>1; }
    return ret;
}
ll lcm(ll a,ll b)
{
    return (a/__gcd(a,b))*b;
}
ll gcd(ll a,ll b)
{
    return __gcd(a,b);
}
void Dufaux()
{
    char a;
    cin>>a;
    if(a=='a' || a=='e' || a=='i' || a=='o' || a=='u'){
        cout<<"vowel"<<endl;
    }
    else{
        cout<<"consonant"<<endl;
    }
}
int main()
{
    FastIO;
	///sieve();
	///generate_mobius();
	int test=1;
	while(test--){
        Dufaux();
	}
	return 0;
}






Measured memory_bytes: 3668
#include<bits/stdc++.h>
using namespace std;
int arr[1000005];
int main()
{
    int n,a;
    cin>>n;
    for(int i=1;i<=n-1;i++){
        cin>>a;
        arr[a]++;
    }
    for(int i=1;i<=n;i++)
        cout<<arr[i]<<endl;
}

Measured memory_bytes: 4368
#include <bits/stdc++.h>
const int INF=1e9,MOD=1e9+7;
const long long LINF=1e18;
using namespace std;
#define int long long
//template
int dp[205][20005];
//main
signed main(){
  int N,W;cin>>N>>W;
  std::vector<int> v(N);
  for(int i=0;i<N;i++)cin>>v[i];
  sort(v.rbegin(),v.rend());
  memset(dp,0,sizeof(dp));
  dp[0][0]=1;
  for(int i=0;i<N;i++){
    for(int j=0;j<=10000;j++){
      dp[i+1][j]+=dp[i][j];
      dp[i+1][j+v[i]]+=dp[i][j];
      dp[i+1][j+v[i]]%=MOD;
    }
  }
  std::vector<int> w(N+1,0);
  for(int i=N-1;i>=0;i--)w[i]=w[i+1]+v[i];
  if(w[0]<=W){cout<<1<<endl;return 0;}
  if(v[N-1]>W){cout<<1<<endl;return 0;}
  int ans=0;
  for(int i=1;i<=N;i++){
    for(int j=0;j<=10000;j++){
      if(W-j-w[i+1]>=0&&W-j-w[i]<0)ans+=dp[i][j];
      ans%=MOD;
    }
  }
  cout<<ans<<endl;
}



Measured memory_bytes: 35132
f=input
from bisect import bisect_left as g, insort as h
n,s=int(f()),list(f())
d={chr(97+i):[] for i in range(26)}
for i in range(n): d[s[i]]+=[i]
for _ in range(int(f())):
  a,b,c=f().split(); b=int(b)-1
  if a>'1': print(sum(1 for l in d.values() if g(l,b)<len(l) and l[g(l,b)]<int(c)))
  elif s[b]!=c: l=d[s[b]]; l.pop(g(l,b)); s[b]=c; h(d[c],b)

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

using namespace std;

int main() {

    int n;
    cin >> n;
    vector <vector <int>> g(n);
    const long long INF = (long long) 1e10;

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

    c[0] = 1, c[n - 1] = 2;

    queue <int> q;

    q.push(0);
    q.push (n - 1);


    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int i = 0; i < g[v].size(); ++i){
            if (c[ g[v][i] ] == -1){
                c[ g[v][i] ] = c[v];
                q.push (g[v][i]);
            }
        }
    }

    int cnt1 = 0, cnt2 = 0;
    for (int i = 0; i < n; ++i)
        if (c[i] == 1)
            cnt1++;
        else
            cnt2++;

    if (cnt1 > cnt2){
        cout << "Fennec\n";
    } else
            cout << "Snuke\n";



    return 0;
}

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

int main(){
    int a,b,c,d,e,k;
    cin >> a >> b >> c >> d >> e >> k;
    if(e-a>k){
        cout << ":(" << endl;
    }else{
        cout << "Yay!" << endl;
    }
}

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

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

    S = regex_replace(S, regex("eraser"), "0"); // 使われていない文字("0")に置換
    S = regex_replace(S, regex("erase"), "0");
    S = regex_replace(S, regex("dreamer"), "0");
    S = regex_replace(S, regex("dream"), "0");
    S = regex_replace(S, regex("0"), ""); // "0"を消す
    cout << (S == "" ? "YES" : "NO") << endl;
}

Measured memory_bytes: 640
#include <cstdio>
#include <algorithm>
#include <utility>

#define NO -1

using namespace std;

int main() {
    int N, i, j;
    scanf("%d",&N);
    pair<int,int> red[N], blue[N];
    for (i=0; i<N; i++) scanf("%d %d",&red[i].first,&red[i].second);
    for (i=0; i<N; i++) scanf("%d %d",&blue[i].first,&blue[i].second);
    sort(red,red+N);
    sort(blue,blue+N);
    int count=0, max=NO, max_j;
    for (i=0; i<N; i++) {
        for (j=0; red[j].first < blue[i].first && j<N; j++) {
            if (red[j].first != NO && red[j].second < blue[i].second && red[j].second > max) {
                max = red[j].second;
                max_j = j;
            }
        }
        if (max != NO) {
            max = NO;
            red[max_j].first = NO;
            count++;
        }
    }
    printf("%d\n",count);
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int n,k,cur;
vector<pair<int,int>> a;
vector<pair<int,int>> wait;

int main(){
    scanf("%d%d",&n,&k);
    for(int i=2;i<=n;i++)
        a.push_back(make_pair(1,i));
    for(int i=2;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        wait.push_back(make_pair(i,j));
    cur=(n-2)*(n-1)/2;
    if(k>cur)return !printf("-1");
    cur-=k;
    while(cur--){
        a.push_back(wait.back());
        wait.pop_back();
    }
    printf("%d\n",(int)a.size());
    for(auto i:a){
        printf("%d %d\n",i.first,i.second);
    }
}


Measured memory_bytes: 384
/*
Author: CNYALI_LK
LANG: C++
PROG: d.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
	ll s=0,base=1;
	char c;
	while(!isdigit(c=getchar()))if(c=='-')base=-base;
	while(isdigit(c)){s=s*10+(c^48);c=getchar();}
	return s*base;
}
char WritellBuffer[1024];
template<class T>void write(T a,char end){
	ll cnt=0,fu=1;
	if(a<0){putchar('-');fu=-1;}
	do{WritellBuffer[++cnt]=fu*(a%10)+'0';a/=10;}while(a);
	while(cnt){putchar(WritellBuffer[cnt]);--cnt;}
	putchar(end);
}
ll to[433333],lst[433333],w[433333],beg[122222],e;
void add(ll x,ll y,ll z){
	to[++e]=y;
	lst[e]=beg[x];
	beg[x]=e;
	w[e]=z;
}
ll ww[122222],vis[122222];
void dfs(ll x,ll omega){
	vis[x]=1;
//	debug("OrzOrz%lld\n",x);
	ww[x]=omega;
	for(ll i=beg[x];i;i=lst[i]){
		if(!vis[to[i]])dfs(to[i],omega+w[i]);
		else{
			if(ww[to[i]]!=omega+w[i]){
				printf("No\n");
				exit(0);
			}
		}	
	}
}
int main(){
#ifdef cnyali_lk
	freopen("d.in","r",stdin);
	freopen("d.out","w",stdout);
#endif
	ll n,m,u,v,w;
	n=read();
	m=read();
	for(ll i=1;i<=m;++i){
		u=read();v=read();w=read();
		add(u,v,w);
		add(v,u,-w);
	}

//	debug("OrzOrz\n");
	for(ll i=1;i<=n;++i)if(!vis[i])dfs(i,0);
	printf("Yes\n");
	return 0;
}



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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

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

    ll N, A, B;
    cin >> N >> A >> B;

    if(N < A+B-1 || N > A*B){
    	cout << -1 << endl;
    	return 0;
    }
    vector<ll> res;
    ll hazi = 0;
    REP(i, A){
    	ll kosu;
    	if(N-(A-i) >= B-1) kosu = B;
    	else kosu = N-(A-i)+1;
    	hazi += kosu;
    	N -= kosu;
    	REP(j, kosu){
    		res.push_back(hazi-j);
    	}
    }
    REP(i, res.size()) cout << res[i] << " ";
    cout << endl;
    return 0;
}

Measured memory_bytes: 6512
<?php
  
fscanf(STDIN,"%d%d",$w,$h);



if(($w-2)>0&&($h-2)>0){
  echo ($w-2)*($h-2);
}
elseif($h == 2 || $w == 2){
      echo "0";
}
elseif(($h-2)>0){
  echo ($h-2);
}elseif(($w-2)>0){
  echo ($w-2);
}elseif($w==1 && $h==1){
  echo "1";
}
else{
  echo "0";
}




Measured memory_bytes: 4604
long long n,i,j,x;ans=0;main(){
scanf("%lld",&n);
for(i=2;i*i<n;i++){for(x=0;n%i==0;x++)n/=i;for(j=0;j*(j+1)/2<=x;j++);ans+=j-1;}
if(n-1)ans++;
printf("%d",ans);}

Measured memory_bytes: 1688
N = gets.to_i
UV = (N-1).times.map{ gets.split.map &:to_i }

ans = 1.upto(N).map{(N-_1+1)*(N-_1+2)/2}.sum

UV.each do |u,v|
    u,v = v,u if u>v
    ans -= u * (N-v+1)
end

p ans



Measured memory_bytes: 30224
# -*- coding: utf-8 -*-
"""
Created on Sun Apr 26 20:57:47 2020
"""

import sys
#import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 2019

S = input()
l = len(S)
#S = int(S)

a, b = [],[0]
s = 0
xx = [0 for _ in range(2019)]
xx[0] += 1
for i in range(l):
    s += int(S[-i-1])*pow(10,i,mod)
    s %= mod
#    b.append(s % x)
    xx[s] += 1

ans = 0
#for i in range(len(b)):
#    xx[b[i]] += 1
def a(n):
    return n*(n+1)//2 

for i in range(len(xx)):
    if xx[i] > 1:
        ans += a(xx[i] - 1)

print(ans)


Measured memory_bytes: 9244
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define rREP(i,m,n) for(ll i = (m); i >= (n); i--)
#define ALL(c) (c).begin(), (c).end()
#define print(x) cout << (x) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    int ary[n];
    rep(i,n) cin >> ary[i];
    ll ans = 1;
    int boushi[3];
    boushi[0] = 0;
    boushi[1] = 0;
    boushi[2] = 0;
    rep(i,n)
    {
        int tmpnum = ary[i];
        int cnt = 0;
        int tmpitr = -1;
        rep(j,3)
        {
            if (tmpnum == boushi[j])
            {
                cnt++;
                tmpitr = j;
            }
        }
        ans *= cnt;
        ans %= 1000000007;
        boushi[tmpitr]++;
    }
    cout << ans << endl;
    
}




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

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()

int main() {
  int N;
  int ans = 0;
  cin >> N;
  vector<int> A(N);
  vector<int> B(N);
  REP(i,N) {
    cin >> B[i];
  }
  A[0] = B[0];
  A[1] = B[0];
  FOR(i,1, N-1) {
    if (A[i] > B[i]) {
      A[i] = B[i];
    }
    A[i+1] = B[i];
  }
  REP(i,N) {
    ans += A[i];
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
/*  -*- coding: utf-8 -*-
 *
 * a.cc: 
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>

using namespace std;

/* constant */

/* typedef */

typedef long long ll;

/* global variables */

/* subroutines */

/* main */

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

  if ((a & 1) == 0 || (b & 1) == 0 || (c & 1) == 0)
    puts("0");
  else
    printf("%lld\n", min(a * b, min(b * c, c * a)));
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <algorithm>
#include <limits.h>

using namespace std;

int GetMaxOfSequence(int *pArr, int n) {
	int i,tmp, maxSum;

	maxSum = INT_MIN;
	tmp = 0;
	for (i = 0; i < n; i++) {
		if (tmp > 0) {
			tmp += pArr[i];
		}
		else {
			tmp = pArr[i];
		}
		maxSum = max(maxSum, tmp);
	}
	return maxSum;
}


int main(void) {
	int n,i, j,k, maxValue;
	int arr[101][101],tmp[101];

	while (cin >> n) {
		memset(arr, 0, sizeof(arr));
		for (i = 0; i < n; i++) {
			for (j = 0; j < n; j++) {
				cin >> arr[i][j];
			}
		}

		maxValue = INT_MIN;
		for (i = 0; i < n; i++) {
			memset(tmp, 0, sizeof(tmp));
			for (j = i; j < n; j++) {
				for (k = 0; k < n; k++) {
					tmp[k] += arr[j][k];
				}

				maxValue = max(maxValue, GetMaxOfSequence(tmp, n));
			}
		}

		cout << maxValue << endl;
	}

	return 0;
}




Measured memory_bytes: 3156
import math
def isInteger(p1, p2):
    s = sum([(p1[i] - p2[i]) ** 2 for i in range(len(p1))])
    num = math.sqrt(s)
    return num - int(num) == 0
N, D = map(int, input().split())

points = []
for i in range(N):
    p = tuple(map(int, input().split()))
    points.append(p)

cnt = 0
for i in range(N):
    for j in range(i+1, N):
        if isInteger(points[i], points[j]): cnt += 1
print(cnt)

Measured memory_bytes: 3064