akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int N,K;
vi Rank,Tmp;

bool Comp(int i,int j){
	if(Rank[i]!=Rank[j]) return Rank[i]<Rank[j];
	int ri=i+K<=N?Rank[i+K]:-1,rj=j+K<=N?Rank[j+K]:-1;
	return ri<rj;
}

vi Suffix_Array(string s){
	N=s.size();
	vi sa(N+1);
	Rank=Tmp=vi(N+1);
	for(int i=0;i<=N;i++){
		sa[i]=i;
		Rank[i]=i<N?s[i]:-1;
	}
	for(K=1;K<=N;K*=2){
		sort(sa.begin(),sa.end(),Comp);
		Tmp[sa[0]]=0;
		for(int i=1;i<=N;i++) Tmp[sa[i]]=Tmp[sa[i-1]]+(Comp(sa[i-1],sa[i])?1:0);
		Rank=Tmp;
	}
	return sa;
}


vi LCP(string s,vi sa){
	int S=s.size(),h=0;
	vi rank(S+1),lcp(S);
	for(int i=0;i<=S;i++) rank[sa[i]]=i;
	for(int i=0;i<S;i++){
		if(h>0) h--;
		for(int j=sa[rank[i]-1];j+h<S&&i+h<S;h++) if(s[j+h]!=s[i+h]) break;
		lcp[rank[i]-1]=h;
	}
	return lcp;
}

string s;

int main(){
	cin>>s;
	vi sa=Suffix_Array(s);
	vi lcp=LCP(s,sa);
	sort(lcp.rbegin(),lcp.rend());
	cout<<(int)s.size()-lcp[0]<<endl;
}

Measured memory_bytes: 2816
package main

import (
	"fmt"
	"sort"
)

func chmax(a *int, b int) {
	if *a < b {
		*a = b
	}
}

type edge struct {
	to, col int
	idx     int
}
type byIdx []edge

func (p byIdx) Len() int      { return len(p) }
func (p byIdx) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
func (p byIdx) Less(i, j int) bool {
	return p[i].idx < p[j].idx
}

func main() {
	var n int
	fmt.Scan(&n)

	g := make([][]edge, n)
	for i := 0; i < n-1; i++ {
		var a, b int
		fmt.Scan(&a, &b)
		a--
		b--
		g[a] = append(g[a], edge{to: b, col: -1, idx: i})
		g[b] = append(g[b], edge{to: a, col: -1, idx: i})
	}

	bfs := func(s int) {
		q := []int{s}
		var now int
		isVisited := make([]bool, len(g))
		colorOfParentToNow := make([]int, n)
		colorOfParentToNow[0] = -1
		for len(q) != 0 {
			now, q = q[0], q[1:]
			isVisited[now] = true
			ct := 0
			for i := range g[now] {
				if isVisited[g[now][i].to] {
					continue
				}
				if ct == colorOfParentToNow[now] {
					ct++
				}
				g[now][i].col = ct
				ct++
				colorOfParentToNow[g[now][i].to] = g[now][i].col
				q = append(q, g[now][i].to)
			}
		}
	}
	bfs(0)

	maxDegree := -1
	for i := range g {
		chmax(&maxDegree, len(g[i]))
	}
	k := maxDegree
	fmt.Println(k)

	a := make([]edge, 0, n)
	for i := range g {
		for j := range g[i] {
			from := i
			to := g[i][j].to
			if from < to {
				a = append(a, g[i][j])
			}
		}
	}
	sort.Sort(byIdx(a))
	for _, edge := range a {
		fmt.Println(edge.col + 1)
	}
}


Measured memory_bytes: 18176
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

s = ns()

aa = 0 #連続するAカウント
i = 0
ans = 0

while i < len(s):
    if s[i] == 'A':
        aa += 1
    elif s[i] == 'B':
        if i+1 != len(s) and s[i+1] == 'C':
            ans += aa
            i += 1
        else:
            aa = 0
    elif s[i] == 'C':
        aa = 0
    i += 1

print(ans)

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

int main(){
    int N, K, h, i;

    cin >> N >> K;
    vector<int> high(N);
    for(i = 0; i < N; i++){
        cin >> high[i];
    }
    sort(high.begin(), high.end());
    if(high[0] >= K)cout << N << endl;
    else {
        reverse(high.begin(), high.end());
        i = 0;
        while(high[i] >= K)i++;
        cout << i << endl;
    }
}

Measured memory_bytes: 640
def f(x):
    if x==2:
        return 1
    if x<2 or x%2==0:
        return 0
    i=3
    while i<=x**(1/2):
        if x%i==0:
            return 0
        i+=2
    return 1
while True:
    n=int(input())
    if n==0:
        break
    else:
        p=0
        for i in range(2,n//2+1):
            m=n-i
            if f(m)==1 and f(i)==1:
                p+=1
        print(p)


Measured memory_bytes: 5640
#include <stdio.h>
#include <string.h>
int min(int x,int y){
    if(x<y) return x;
    else return y;
}
int main(void){
    char s[100001];
    int n=0,m=0,i;
    scanf("%s",s);
    for(i=0;i<strlen(s);i++){
        if(i%2==0 && s[i]=='0') n++;
        if(i%2==1 && s[i]=='1') n++;
    }
    for(i=0;i<strlen(s);i++){
        if(i%2==0 && s[i]=='1') m++;
        if(i%2==1 && s[i]=='0') m++;
    }
    printf("%d",min(n,m));
}

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

namespace Practice
{
    class Program
    {
        static void Main(string[] args)
        {
            SolveA();
            //SolveB();
            //SolveC();
            //SolveD();
        }
        private const long MOD = 1000000007;
        private static long[] Lucas = new long[100];
        static void SolveA()
        {
            int n = ReadAndParseInt();
            Lucas[0] = 2;
            Lucas[1] = 1;
            for(int i=2;i<=n;++i)
            {
                Lucas[i] = Lucas[i - 1] + Lucas[i - 2];
            }
            Console.WriteLine(Lucas[n]);
        }
        #region よく使う便利関数
        private static bool isPrime(long x)
        {
            if( x == 2) { return true; }
            if( x < 2 || x % 2 == 0) { return false; }
            long i = 3;
            while( i * i <= x)
            {
                if( x % i == 0) { return false; }
                i = i + 2;
            }
            return true;
        }
        private static long lcm(long x, long y)
        {
            return x / gcd(x, y) * y;
        }
        private static long gcd(long x, long y)
        {
            return y > 0 ? gcd(y, x % y) : x;
        }

        private static int ReadAndParseInt()
        {
            return int.Parse(Console.ReadLine());
        }
        private static int[] ReadAndParseIntArr()
        {
            return Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
        }
        private static long ReadAndParseLong()
        {
            return long.Parse(Console.ReadLine());
        }
        private static long[] ReadAndParseLongArr()
        {
            return Array.ConvertAll(Console.ReadLine().Split(' '), long.Parse);
        }
        #endregion
    }
}

Measured memory_bytes: 13140
#include<iostream>
#include<vector>
#include<functional>
#include<algorithm>
#include<cmath>
#include<string>
#include<iomanip>
using namespace std;

int a,b,k;
int gcd(int a,int b)
{
	if (a%b==0)
	{
		return(b);
    }
	else
	{
		return(gcd(b,a%b));
    }
}



int main(){
	cin>>a>>b>>k;
	int c=gcd(a,b);
	int cnt=0;
	for(int i=c;i>=1;i--)
	{
		if(!(c%i))
			cnt++;
		if(cnt==k){
			cout<<i<<endl;
		return 0;}
	}
}

Measured memory_bytes: 256
// https://atcoder.jp/contests/abc153/tasks/abc153_d

#include <bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl;
using namespace std;
int main() {

    
    #define int long long
    int H;
    cin >> H;

    int curnum = 1;
    int ans = 0;
    while(H != 1) {
        H /= 2;
        ans += curnum;
        curnum *= 2;

        // watch(H)
        // watch(curnum)
    }

    cout << ans+curnum << endl;
    
}

Measured memory_bytes: 256
/*Read the problem carefully before starting to work on it*/
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;
//#include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;

//ll ncr(ll n,ll r){ll ans=1;r=min(r,n-r);for (int i=1;i<=r;i++){ans*=(n-r+i);ans/=i;}return ans;}

#define pb push_back
#define eb emplace_back
#define mp(x,y) make_pair(x,y)
#define mod 1000000007

double PI=3.1415926535897932384626;

//template<typename T> T power(T x,T y,ll m=mod){T ans=1;while(y>0){if(y&1LL) ans=(ans*x)%m;y>>=1LL;x=(x*x)%m;}return ans%m;}

//typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ost;

#define fi first
#define se second

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n,m;
	cin>>n>>m;
	vector<ll>arr(n),arr1(n);
	for(ll i=0;i<n;i++)
	{
		cin>>arr[i];
	}
	sort(arr.begin(),arr.end());
	for(ll i=0;i<n;i++)
	{
	    arr1[i]=arr[i];
	}
	for(ll i=1;i<n;i++)
	{
		arr1[i]+=arr1[i-1];
	}
	ll lo=0,hi=1e12;
	ll ans=0;
	ll ccount=0;
	while(lo<hi)
	{
		ll mid=lo+(hi-lo+1)/2;
		ans=0;
		ccount=0;
		for(ll i=0;i<n;i++)
		{
			auto it=lower_bound(arr.begin(),arr.end(),mid-arr[i]);
			ccount+= (arr.end()-it);
		}
		if(ccount>=m)
		{
			lo=mid;
		}
		else
		{
			hi=mid-1;
		}
	}
		ccount=0;
		for(ll i=0;i<n;i++)
		{
			auto it=lower_bound(arr.begin(),arr.end(),hi-arr[i]);
			ccount+= (arr.end()-it);
			ll pos=it-arr.begin();
			if(pos==0)
			{
				ans+=arr1[n-1];
			}
			else
			{
				ans+=(arr1[n-1]-arr1[pos-1]);
			}
			ans+=(arr.end()-it)*arr[i];
		}
	cout<< ans-((ccount-m)*lo);
    return 0;
}


//252908XL

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

using pii = pair<int, int>; using vpii = vector<pii>;
using vi = vector<int>; using vvi = vector<vi>;
using ll = long long;
using pll = pair<ll, ll>; using vpll = vector<pll>;
using vll = vector<long long>; using vvll = vector<vll>;
template <class T> using min_queue = priority_queue<T, vector<T>, greater<T>>;
template <class T> istream &operator>>(istream &, vector<T> &);
template <class T> ostream &operator<<(ostream &, const vector<T> &);
template <class T, class U> istream &operator>>(istream &, pair<T, U> &);
template <class T, class U> ostream &operator<<(ostream &, const pair<T, U> &);
template <class T> struct Inf { static constexpr T inf() { return std::numeric_limits<T>::has_infinity ? std::numeric_limits<T>::infinity() : std::numeric_limits<T>::max(); } };
template <> struct Inf<int> { static constexpr int inf() { return 0x3f3f3f3f; } };
template <> struct Inf<long long> { static constexpr long long inf() { return 0x3f3f3f3f3f3f3f3fLL; } };
constexpr int INF = Inf<int>::inf(); constexpr ll BINF = Inf<ll>::inf();
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// }}}
// Preprocessing & "Global" variables {{{
struct Solver {
	Solver() {}
	int solve();
};
// }}}

int Solver::solve() {
	int n; cin >> n;
	vi a(n); cin >> a;
	const int M = 100000;
	vi cnt(M + 1);
	ll csum = 0;
	for (int x : a) cnt[x]++, csum += x;
	int q; cin >> q;
	while (q--) {
		int b, c; cin >> b >> c;
		int yo = cnt[b];
		cnt[b] = 0;
		csum -= 1LL * b * yo;
		cnt[c] += yo;
		csum += 1LL * c * yo;
		cout << csum << '\n';
	}
	return 0;
}

// Template Main {{{
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	Solver solver;
	#ifdef JUDGE_MULTI_CASE
		int t; cin >> t; for (int i = 1; i <= t; i++)
	#endif
	solver.solve();
	// cout << "Case #" << i << ": ", solve();
	return 0;
}

template <class T> istream &operator>>(istream &is, vector<T> &v) {
	for (auto it=v.begin();it!=v.end();++it) is >> *it;
	return is;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
	for (auto it=v.begin();it!=v.end();) os << *it, os << " \n"[++it==v.end()];
	return os;
}

template <class T, class U> istream &operator>>(istream &is, pair<T, U> &p) {
	return is >> p.first >> p.second;
}

template <class T, class U> ostream &operator<<(ostream &os, const pair<T, U> &p) {
	return os << p.first << ' ' << p.second;
}
// }}}

// vim: fdm=marker


Measured memory_bytes: 3932
#include<stdio.h>

#define PAI 3.141592653589;

int main(){
  double r;
  double s,cir;
  scanf("%lf",&r);
  
  s = r*r*PAI;
  cir = 2*r*PAI;
  printf("%lf %lf",s,cir);

  return 0;
}


Measured memory_bytes: 2108
#include <bits/stdc++.h>
#define ll long long
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
// rep(i, 1, 5) --> {1,2,3,4}
// rep(i, 5, 1) --> {4,3,2,1}
// rep(it, end(v), begin(v)) --> *it

using namespace std;

int nbr;
bool visited[100005];
vector<int> adj[100005]; /// wledou
// vector<vector<int>> adj; // Outside main
vector<int> dp(100005, 0);

void dfs(int s)
{
    visited[s] = true;
    // dp[s]++;
    for (int i = 0; i < adj[s].size(); i++)
    {
        if (visited[adj[s][i]] == false)
        {
            dfs(adj[s][i]);
        }
        // cout << s+1 << " " << adj[s][i]+1 << endl;
        dp[s] = max(dp[adj[s][i]]+1, dp[s]);
        // cout << dp[i] << endl;
    }
}

int main()
{
    cin >> nbr;
    int m;
    cin >> m;
    // adj.resize(n); // Inside main
    rep(i, 0, m)
    {
        int a, b;
        cin >> a >> b;
        a--; b--; // To have graph indexed from 0
        adj[a].push_back(b);
    }
    memset(visited,false,sizeof visited);
    // cout << "Hello\n";
    for (int i = 0; i < nbr; i++)
        if (visited[i] == false)
            dfs(i);
    // cout << "h";
    cout << *max_element(dp.begin(), dp.end());
    return 0;
}

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

int recursive(int pattern,int node,int v,vector<vector<pair<int,int>>> &g,vector<vector<int>> &dp);

int main()
{
	int v,e;
	cin >> v >> e;
	vector<vector<pair<int,int>>> g(v);

	for (int i=0;i<e;++i)
	{
		int s,t,d;
		cin >> s >> t >> d;
		g[s].push_back(make_pair(t,d));
		//g[t].push_back(make_pair(s,d));
	}

	int max_pattern=1<<v;
	vector<vector<int>> dp(max_pattern,vector<int>(v));
	const int infinity=32768*32767;
	for (int i=0;i<v;++i)
	{
		dp[0][i]=infinity;
	}

	for (int i=1;i<max_pattern;++i)
	{
		for (int j=0;j<v;++j)
		{
			dp[i][j]=-1;
		}
	}

	dp[1<<0][0]=0;
	for (int i=1;i<v;++i)
	{
		recursive(max_pattern-1,i,v,g,dp);
	}

	int min_d=infinity;
	for (int i=0;i<g[0].size();++i)
	{
		int dd=dp[max_pattern-1][g[0][i].first];
		if ( (dd>=0) && (dd!=infinity) )
		{
			min_d=min(min_d,dd+g[0][i].second);
		}
	}

	if (min_d!=infinity)
	{
		cout << min_d << endl;
	}
	else
	{
		cout << -1 << endl;
	}
}

int recursive(int pattern,int node,int v,vector<vector<pair<int,int>>> &g,vector<vector<int>> &dp)
{
	const int infinity=32768*32767;
	int min_d=infinity;

	pattern^=(1<<node); // clear bit
	for (int i=0;i<g[node].size();++i)
	{
		int d;
		int nn=g[node][i].first;
		if ((pattern&(1<<nn))!=0)
		{
			if (dp[pattern][nn]<0)
			{
				recursive(pattern,nn,v,g,dp);
			}
			min_d=min(min_d,dp[pattern][nn]+g[node][i].second);
		}
	}
	dp[pattern^(1<<node)][node]=min_d;
	//fprintf(stderr,"recursive: %d %d = %d\n",pattern^(1<<node),node,min_d);
	return 0;
}


			







Measured memory_bytes: 6320
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
	c = 0
	s = input()
	for t in s:
		if t == 'o':
			c += 1
	
	c += 15 - len(s)
	
	if c >= 8:
		print('YES')
	else:
		print('NO')


if __name__ == '__main__':
	import sys
	sys.exit(main())


Measured memory_bytes: 3064
n,k=map(int,input().split())
*x,=map(int,input().split())

ans=10**10

for i in range(n-k+1):
    left=x[i]
    right=x[i+k-1]

    if left*right>=0:
        ans=min(ans,max(abs(left),abs(right)))
    else:
        ans=min(ans,right-left+min(abs(right),abs(left)))

print(ans)

Measured memory_bytes: 84660
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <cstring>
#include <utility>
#include <numeric>

using namespace std;

int main(){

    string s;
    cin >> s;
    int N = (int)s.size();

    int ans = 10000;
    for(int i = 0; i < 26; i++){
        char temp = 'a' + i;
        if(s.find(temp) == string::npos){
            continue;
        }

        int cnt = 0;
        string tempS = s;
        string nextS = s;
        while(true){
            bool update = false;
            for(int j = 0; j < (int)nextS.size(); j++){
                if(nextS[j] != temp){
                    update = true;
                    if(j != (int)nextS.size() && tempS[j + 1] == temp){
                        nextS[j] = temp;
                    }
                }
            }

            if(!update){
                break;
            }
            tempS = nextS;
            nextS = tempS.substr(0, (int)tempS.size() - 1);
            cnt++;
        }

        ans = min(ans, cnt);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main() {
  int n, q, i, j, command, x, y, sum;

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

  int nums[n];
  memset(nums, 0, sizeof(nums));

  for (i = 0; i < q; i++) {
    scanf("%d %d %d", &command, &x, &y);
    if (command) {
      sum = 0;
      for (j = x - 1; j < y; j++)
	sum += nums[j];
      
      printf("%d\n", sum);
    } else {
      nums[x - 1] += y;
    }
  }
}



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

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


    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
typedef long long  ll;

#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)

ll strlength(const char *s) {
	ll l = 0;
	while (*s++)l++;
	return l;
}

int main()
{
	char A[101], B[101]; cin >> A >> B;
	ll strA = strlength(A);
	ll strB = strlength(B);

	if (strA > strB) {
		cout << "GREATER" << endl;
	}
	else if (strA < strB) {
		cout << "LESS" << endl;
	}
	else {
		ll i = 0;
		while (A[i] == B[i]) {
			if (A[i] == '\0') {
				cout << "EQUAL" << endl;
				return 0;
			}
			i++;
		}

		cout << ((A[i] > B[i]) ? "GREATER" : "LESS") << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int main()
{
    int R, C, N; cin >> R >> C >> N;
    auto toindex = [=](int x, int y) {
        if (y == 0) return x;
        if (x == R) return R+y;
        if (y == C) return R+C+R-x;
        if (x == 0) return R+C+R+C-y;
        return -1;
    };
    vector<pair<int, int>> P;
    for (int i = 0; i < N; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        int idx1 = toindex(x1, y1);
        int idx2 = toindex(x2, y2);
        if (idx1 == -1 || idx2 == -1) continue;
        P.emplace_back(idx1, i);
        P.emplace_back(idx2, i);
    }
    sort(begin(P), end(P));
    stack<int> S;
    for (auto& p : P) {
        int elem; tie(ignore, elem) = p;
        if (!S.empty() && S.top() == elem) S.pop();
        else S.push(elem);
    }
    auto YESNO = vector<string>{"NO", "YES"};
    cout << YESNO[S.empty()] << '\n';
    return 0;
}


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

using namespace std;
using ll = long long;

int main() {
    ll N;
    cin >> N;
    ll ans = 1e15;

    for(ll i = 1; i*i <= N; i++) {
        //cout << i << endl;
        if(N%i == 0) {
            //cout << "#" << endl;
            ans = min(ans, i + N/i - 2);
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3644
S=list(input())
max=0
count=0
for i in range(len(S)):
  if S[i] == "A" or S[i] == "T" or S[i] == "C" or S[i] == "G":
    count+=1
    if max<count:
      max=count
  else:
    count=0
print(max)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>

#define rep_ui(k,n)      for(ui  i = (k); i < (n); ++i)
#define rep_si(k,n)      for(int i = (k); i < (n); ++i)
#define rep_ul(k,n)      for(ul  i = (k); i < (n); ++i)
#define rep_sl(k,n)      for(ll  i = (k); i < (n); ++i)
#define rep_ui_down(k,n) for(ui  i = (k); i > (n); --i)
#define rep_si_down(k,n) for(int i = (k); i > (n); --i)
#define rep_ul_down(k,n) for(ul  i = (k); i > (n); --i)
#define rep_sl_down(k,n) for(ll  i = (k); i > (n); --i)

#define rep_uj(k,n)      for(ui  j = (k); j < (n); ++j)
#define rep_sj(k,n)      for(int j = (k); j < (n); ++j)
#define rep_uj_down(k,n) for(ui  j = (k); j > (n); --j)
#define rep_sj_down(k,n) for(int j = (k); j > (n); --j)

#define rep(k,n)         rep_ui(k,n)

typedef uintmax_t    ull;
typedef intmax_t     ll;
typedef uint64_t     ul;
typedef uint32_t     ui;
typedef uint8_t      uc;

template<class T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vc)
{
  boost::for_each(vc, [&os, &vc](T value) {
    os << value;
    if (value != vc.back())
      os << ' ';
    });
  return os;
}

template<class T1, class T2>
inline
std::ostream&
operator<<(std::ostream& os, const std::pair<T1, T2>& p)
{
  return os << p.first << ' ' << p.second;
}

void solve(void)
{
  //using std::string;
  //string S{}; std::cin >> S;
  
  ui N{}; std::cin >> N;
  ll L{}; std::cin >> L;

  typedef std::pair<ui, ll> Pair;
  std::vector<ll> A(N);
  ll sum{};
  rep(0, N)
  {
    A[i] = L + i;
    sum += A[i];
  }

  ull delta{UINT64_MAX};
  ui res{};
  rep(0, N)
  {
    ull dis = std::abs(A[i]);
    if (dis < delta)
    {
      res = i;
      delta = dis;
    }
  }

  auto ans = sum - A[res];

  std::cout << ans << '\n';

  return;
}

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

  solve();

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, double> Pid;
typedef pair<double, int> Pdi;
typedef pair<ll, int> Pl;
typedef pair<int, pair<int, int>> PP;
const double PI = 3.1415926535897932;   // acos(-1)
const double EPS = 1e-15;
const ll mod = 1e+9 + 7;
const int INF = 1001001001;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define chadd(x, y) x = (x + y) % mod

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

    int n;
    cin >> n;
    vector<int> x(n);
    for(int i = 0; i < n; ++i)  cin >> x[i];
    int mine = *min_element(x.begin(), x.end());
    int maxe = *max_element(x.begin(), x.end());
    
    int res = INF;
    for(int i = mine; i <= maxe; ++i){
        int sum = 0;
        for(int j = 0; j < n; ++j){
            sum += (x[j] - i) * (x[j] - i);
        }
        chmin(res, sum);
    }
    cout << res << endl;
}

Measured memory_bytes: 256
/*
 _____ _             _              _           _ 
|_   _| |__   ___   / \   _ __  ___| |__  _   _| |
  | | | '_ \ / _ \ / _ \ | '_ \/ __| '_ \| | | | |
  | | | | | |  __// ___ \| | | \__ \ | | | |_| | |
  |_| |_| |_|\___/_/   \_\_| |_|___/_| |_|\__,_|_|                                                

*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
#define ll          long long
#define pb          push_back
#define ppb         pop_back
#define	endl		'\n'
#define mii         map<ll,ll>
#define msi         map<string,ll>
#define mis         map<ll, string>
#define rep(i,a,b)    for(ll i=a;i<b;i++)
#define repr(i,a,b) for(ll i=b-1;i>=a;i--)
#define trav(a, x) 	for(auto& a : x)
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define vii         vector<pair<ll, ll>>
#define vs          vector<string>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll)x.size()
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define max(a,b)	(a>b?a:b)
#define min(a,b)	(a<b?a:b)

/*	For Debugging	*/
#define DEBUG 		cerr<<"\n>>>I'm Here<<<\n"<<endl;
#define display(x) trav(a,x) cout<<a<<" ";cout<<endl;
#define what_is(x)  cerr << #x << " is " << x << endl;

std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define TIME        cerr << "\nTime elapsed: " << setprecision(5) <<1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
#define DECIMAL(n)  cout << fixed ; cout << setprecision(n);
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace __gnu_pbds;
using namespace std;
#define PI 3.141592653589793
#define N  100005

void solve()
{
	ll n;
	cin>>n;
	vi v(n*n);
	rep(i,0,n*n) {
		cin>>v[i];
		v[i]--;
		// a[v[i]]=i;
	}
	vi ans(n*n);
	rep(i,0,n) {
		rep(j,0,n) {
			ans[i*n+j]=min(min(i,j),n-1-max(i,j));
		}
	}
	// rep(i,0,n) {
	// 	rep(j,0,n) {
	// 		cout<<ans[i*n+j]<<" ";
	// 	}
	// 	cout<<endl;
	// }
	// cout<<"-----"<<endl;
	queue<ll>q;
	vector<bool> vis(n*n,1);
	ll sum=0;
	rep(i,0,n*n) {
		sum+=ans[v[i]];
		vis[v[i]]=0;
		q.push(v[i]);
		ll node;
		while(!q.empty()) {
			node=q.front();
			q.pop();
			if(node%n!=0 && ans[node-1]>ans[node]+vis[node]) {
				ans[node-1]=ans[node]+vis[node];
				q.push(node-1);
			}
			if(node%n!=n-1 && ans[node+1]>ans[node]+vis[node]) {
				ans[node+1]=ans[node]+vis[node];
				q.push(node+1);
			}
			if(node/n!=0 && ans[node-n]>ans[node]+vis[node]) {
				ans[node-n]=ans[node]+vis[node];
				q.push(node-n);
			}
			if(node/n!=n-1 && ans[node+n]>ans[node]+vis[node]) {
				ans[node+n]=ans[node]+vis[node];
				q.push(node+n);
			}
		}
		// rep(i,0,n) {
		// 	rep(j,0,n) {
		// 		cout<<ans[i*n+j]<<" ";
		// 	}
		// 	cout<<endl;
		// }
		// cout<<"-----"<<endl;
	}
	cout<<sum<<endl;
	return;
}
int main()
{
	FAST
	int TESTS=1;
//	cin>>TESTS;
	while(TESTS--)
	{
		solve();
	}
	TIME
	return 0;
}

Measured memory_bytes: 7120
#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 pb push_back
using ll = long long;
using P = pair<int, int>;
using Graph = vector<vector<int>>;

int main(){
    int m1, d1, m2, d2; cin >> m1 >> d1 >> m2 >> d2;
    if(d1 > d2) cout << 1 << endl;
    else cout << 0 << endl;
}

Measured memory_bytes: 256
float c[8];j;f(i){return c[i+1]*(c[(i+2)%6]-c[6])+c[(i+3)%6]*(c[6]-c[i])+c[7]*(c[i]-c[(i+2)%6]);}main(){for(;~scanf("%f",c+j++);j%8||puts(f(j=0)*f(2)>0&f(2)*f(4)>0?"YES":"NO"));}

Measured memory_bytes: 0
H, W = map(int, input().split())

As = []
for _ in range(H):
  As.append(input())
paths = [[0 for _ in range(W)] for _ in range(H)]

paths[0][0] = 1

mod = 1e+9 + 7

for width in range(W):
  for height in range(H):
    if As[height][width] == "#":
      # 壁のマスであればスキップする
      continue
    if height < H-1:
      if As[height + 1][width] == ".":
        # 次のマスが通行可能であれば、これまでの経路を加える
        paths[height + 1][width] = int((paths[height + 1][width] + paths[height][width]) % mod)
    if width < W-1:
      if As[height][width + 1] == ".":
        # 次のマスが通行可能であれば、これまでの経路を加える
        paths[height][width + 1] = int((paths[height][width + 1] + paths[height][width]) % mod)

print(paths[H-1][W-1])


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

int main(){
    int n;
    cin >> n;
    int a[100][2];
    for(int i=0; i<n; i++){
        cin >> a[i][0] >> a[i][1];
    }
    for(int i=0; i<n-2; i++){
        if(a[i][0]==a[i][1] && a[i+1][0]==a[i+1][1] && a[i+2][0]==a[i+2][1]){
            cout  << "Yes";
            return 0;
        }
    }
    cout << "No";
}

Measured memory_bytes: 3556
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long int
#define ordered_set tree < ll ,  null_type ,  less<ll> ,  rb_tree_tag ,  tree_order_statistics_node_update >
//added two more functions to set
//(1)*(set.find_by_order(k))[kth element in the sorted set] 
//(2)set.order_of_key(k)[count of elements strictly less than k]
typedef vector< int > vi;
typedef vector< ll > lvi;
typedef vector< vi > vvi;
typedef vector< lvi > lvvi;
typedef pair< int,int > ii;
typedef pair< ll,ll > lii;
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(auto i = (c).begin(); i != (c).end(); i++)//remember i is an iterator
#define present(c,x) ((c).find(x) != (c).end())//for sets,maps,multimaps
#define cpresent(c,x) (find(all(c),x) != (c).end())//for vectors
#define tc(t) int (t); cin>>(t);while((t)--)
#define ff first
#define ss second
#define mp make_pair
#define ld long double
#define ull unsigned long long int
#define mod 1000000007
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);	
	ll n;
	cin>>n;
	ll a[300000]={0},b[300000];
	ll max1=0;
	for(int i=0;i<n;i++)
	{
		ll x;
		cin>>x;
		a[x]++;
		b[i]=x;
		max1=max(max1,x);
	}
	ll sum=0;
	for(int i=1;i<=max1;i++)
	{
		sum+=((a[i]*(a[i]-1))/2);
	}
	for(int i=0;i<n;i++)
	{
		ll x=b[i];
		x=a[x];
		ll tmp=sum-((x*(x-1))/2);
		x--;
		tmp+=((x*(x-1))/2);
		cout<<tmp<<endl;
	}
	return 0;
}

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

#define int long long
#define ll long long
#define pb push_back
#define mp make_pair
#define f(i,a,n) for(int i=a ; i<(int)n ; i++)
#define rf(i,n,a) for(int i=n ; i>=a ; i--)
#define F first
#define S second
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()
#define fill(a,v) memset(a,v,sizeof(a))
#define d1(a) cout << a << "\n"
#define d2(a,b) cout << a << " " << b << "\n"
#define d3(a,b,c) cout << a << " " << b << " " << c << "\n"
#define d4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << "\n"
#define fast ios:: sync_with_stdio(false),cin.tie(nullptr);

typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef vector<pii> vpi;

const int inf = 1e9;
const int inf64 = 1e18;
const int MOD = inf + 7;

int32_t main(){
	fast;
	int a,b,m;
	cin >> a >> b >> m;
	
	int arr[a] , arr1[b];
	
	
	f(i,0,a)    cin >> arr[i];
	f(i,0,b)    cin >> arr1[i];
	
	int ans = inf64;
	
	f(i,0,m){
		int x,y,c;
		cin >> x >> y >> c;
		x--,y--;
		ans = min(ans , arr[x] + arr1[y] - c);
		ans = max(ans , 0LL);
	}
	
	sort(arr,arr+a);
	sort(arr1,arr1+b);
	ans = min(ans , arr[0] + arr1[0]);
	cout << ans;
}


Measured memory_bytes: 1792
import java.io.*;
import java.util.*;

public class Main {

    static class Pair {
        int x;
        int y;
        int z;
        Pair(int a, int b, int c) {
            x = a;
            y = b;
            z = c;
        }
    }

    public static void main(String[] args) throws Exception {
        Reader sc = new Reader();
        PrintWriter pw = new PrintWriter(System.out);
        
        try {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int x1 = sc.nextInt()-1;
            int y1 = sc.nextInt()-1;
            int x2 = sc.nextInt()-1;
            int y2 = sc.nextInt()-1;
            char[][] c = new char[n][m];
            for(int i=0 ; i<n ; i++) {
                c[i] = sc.next().toCharArray();
            }

            int[][] min = new int[n][m];
            for(int i=0 ; i<n ; i++) {
                for(int j=0 ; j<m ; j++) min[i][j] = -1;
            }

            PriorityQueue<Pair> pq = new PriorityQueue<>(16, (o1, o2) -> o1.z-o2.z);
            pq.add(new Pair(x1, y1, 0));
            while(!pq.isEmpty()) {
                Pair p = pq.poll();

                if(min[p.x][p.y] != -1) continue;
                else min[p.x][p.y] = p.z;

                for(int x=-2 ; x<=2 ; x++) {
                    for(int y=-2 ; y<=2 ; y++) {
                        if(!(x==0 && y==0)) {
                            int dx = p.x+x;
                            int dy = p.y+y;
                            if(bound(dx, dy, n, m) && min[dx][dy] == -1) {
                                if((Math.abs(x) == 1 && y == 0) || (Math.abs(y) == 1 && x == 0)) {
                                    if(c[dx][dy] != '#') pq.add(new Pair(dx, dy, p.z));
                                }
                                else {
                                    if(c[dx][dy] != '#') pq.add(new Pair(dx, dy, p.z+1));
                                }
                            }
                        }
                    }
                }
            }

            pw.println(min[x2][y2]);
        }
        finally {
            pw.flush();
            pw.close();
        }
    }

    static boolean bound(int x, int y, int n, int m) {
        return x>=0 && x<n && y>=0 && y<m;
    }
    
    static class Reader {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        String next() {
            while(!st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch(IOException io) {
                    io.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
}


Measured memory_bytes: 64312
#include <bits/stdc++.h>
using namespace std;
const long long INF=1LL<<61;

const int MAX_N=101;

int N,a,b;
long long col=INF,lev=INF,cnt1,cnt2;
vector<pair<int,int>> es;
vector<vector<int>> G(MAX_N);
vector<long long> dep(MAX_N);
vector<long long> bra(MAX_N);

void dfs(int v,int p){
	long long cnt=0;
	for (int u:G[v]){
		if (u==p) continue;
		dep[u]=dep[v]+1; ++cnt;
		dfs(u,v);
	}
	bra[(int)dep[v]]=max(bra[(int)dep[v]],cnt);
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> N;
	for (int i=0;i<N-1;++i){
		cin >> a >> b;
		es.emplace_back(--a,--b);
		G[a].emplace_back(b);
		G[b].emplace_back(a);
	}
	for (int v=0;v<N;++v){
		fill(dep.begin(),dep.end(),1);
		fill(bra.begin(),bra.end(),1);
		dfs(v,-1);
		cnt1=1,cnt2=1;
		for (int j=0;j<N;++j) cnt1=max(cnt1,dep[j]);
		for (int j=0;j<MAX_N;++j) cnt2*=bra[j];
		if (cnt1<col) col=cnt1,lev=cnt2;
		else if (cnt1==col) lev=min(lev,cnt2);
	}
	for (int i=0;i<N-1;++i){
		fill(dep.begin(),dep.end(),1);
		fill(bra.begin(),bra.end(),1);
		int u=es[i].first,v=es[i].second;
		dfs(u,v); dfs(v,u);
		cnt1=1,cnt2=2;
		for (int j=0;j<N;++j) cnt1=max(cnt1,dep[j]);
		for (int j=0;j<MAX_N;++j) cnt2*=bra[j];
		if (cnt1<col) col=cnt1,lev=cnt2;
		else if (cnt1==col) lev=min(lev,cnt2);
	}
	cout << col << ' ' << lev << '\n';
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstdlib>

using namespace std;
using ll = long long;

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<ll> a(n);
	for(int i = 0; i < n; ++i){ cin >> a[i]; }
	const ll total = accumulate(a.begin(), a.end(), 0ll);
	ll acc = 0, answer = 1000000000000000000ll;
	for(int i = 0; i + 1 < n; ++i){
		acc += a[i];
		const ll x = acc, y = total - acc;
		answer = min(answer, llabs(x - y));
	}
	cout << answer << endl;
	return 0;
}



Measured memory_bytes: 1792
//ヘッダー
#include<bits/stdc++.h>
using namespace std;
 
//型定義
typedef long long ll;
 
//定数
const int INF=1e+9;
const int MOD=1e+9+7;
 
//REPマクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REP2(i,a,b) for(ll i=a;i<(ll)(b);i++)
#define REPD2(i,a,b) for(ll i=a;i>(ll)(b);i--)
 
//vectorの扱い
#define ALL(x) (x).begin(),(x).end() //sortなどの引数省略
#define SIZE(x) ((ll)(x).size()) //size
#define MAX(x) *max_element(ALL(x)) //最大値
#define MIN(x) *min_element(ALL(x)) //最小値
 
//グローバル変数
 
vector<long long> fact, fact_inv, inv;
//ライブラリ挿入
//二項係数前処理計算量O(SIZE)
void init_nCk(int SIZE) {
    fact.resize(SIZE + 5);
    fact_inv.resize(SIZE + 5);
    inv.resize(SIZE + 5);
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < SIZE + 5; i++) {
        fact[i] = fact[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD;
    }
}
    
//nCk　計算量(1)
long long nCk(int n, int k) {
    assert(!(n < k));
    assert(!(n < 0 || k < 0));
    return fact[n] * (fact_inv[k] * fact_inv[n - k] % MOD) % MOD;
}
 
int main(){
    int N,K;
    cin>>N>>K;
    vector<ll> A(N);
    REP(i,N)cin>>A[i];
    sort(A.begin(),A.end());
    ll ans=0;
    ll tmp;
 
    init_nCk(N);
    if(K==1){
        cout<<0<<endl;
        return 0;
    }

    vector<ll> g(N,0),h(N,0);

    REP(i,N){
        if(i>=K-1) g[i]=(A[i]*nCk(i,K-1))%MOD;
        if(i<=N-K) h[i]=(A[i]*nCk(N-i-1,K-1))%MOD;
    }

    REP(i,N){
        ans+=(g[i]-h[i]);
        while(ans<0){
            ans+=MOD;
        }
        ans%=MOD;
    }
    cout<<ans<<endl;
    
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int mod=1e9+7;
int arr[10][10];
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        string s=to_string(i);
        arr[s.front()-'0'][s.back()-'0']++;
    }
    int ans=0;
    for(int i=0;i<10;i++)
        for(int j=0;j<10;j++)
            ans+=arr[i][j]*arr[j][i];
    cout<<ans<<endl;
}


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

using namespace std;
int a,b;
int main()
{
	cin>>a>>b;
	if(a>b)swap(a,b);
	if(a>0&&b>0||a<0&&b<0&&(b-a+1)%2==0)cout<<"Positive\n";
	else if(a<=0&&b>=0)cout<<"Zero\n";
	else cout<<"Negative\n";
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define rrep2(ri,x,n) for(int ri = (int)(n-1); ri >= (int)(x); ri--)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a.at(i);
  vector<int> lgcd(n), rgcd(n);
  lgcd.at(0) = a.at(0);
  rep2(i, 1, n){
    lgcd.at(i) = __gcd(a.at(i), lgcd.at(i-1));
  }
  rgcd.at(n-1) = a.back();
  rrep(i, n-1){
    rgcd.at(i) = __gcd(a.at(i), rgcd.at(i+1));
  }
  int ans = 0;
  rep(i, n){
    int add;
    if(i == 0){
      add = rgcd.at(i+1);
    }else if(i == n-1){
      add = lgcd.at(i-1);
    }else{
      add = __gcd(lgcd.at(i-1), rgcd.at(i+1));
    }
    ans = max(ans, add);
  }
  cout << ans << endl;
  return 0;
}

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

int N, C;
vector<T> tsc;
int imos[100100];
set<int> S[35];

signed main() {
    cin >> N >> C;
    rep(i, N) {
        int s, t, c; cin >> s >> t >> c;
        tsc.pb(make_tuple(t, s, c));
    }
    sort(tsc.begin(), tsc.end());
    rep(i, N) {
        int t = get<0>(tsc[i]), s = get<1>(tsc[i]), c = get<2>(tsc[i]);
        if (S[c].find(s)==S[c].end()) {
            imos[s-1]++;
            imos[t]--;
        }
        else {
            imos[s]++;
            imos[t]--;
        }
        S[c].insert(t);
    }
    
    int ans = imos[0];
    
    for (int i=1; i<100100; i++) {
        imos[i] += imos[i-1];
        ans = max(ans, imos[i]);
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 8688
#include <bits/stdc++.h>
using namespace std; const int MAX = 7000000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(){
COMinit();
  int n,k;
  cin>>n>>k;
  int x=2*n-k;
  if(x%3!=0){
   cout<<0<<endl;
   return 0;
  }
  x/=3;
  int y=n-2*x;
  long long  xy=x+y;
int64_t ans=1;
long long u=min(x,y);

cout<<COM(xy,u)<<endl;
}



Measured memory_bytes: 164480
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.InputMismatchException;


public class Main {
	
	private static int[][] cache;
	private static int[] r;
	private static int[] c;
	

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

		int n = sc.nextInt();
		r = new int[n];
		c = new int[n];

		for (int i = 0; i < n; i++) {
			r[i] = sc.nextInt();
			c[i] = sc.nextInt();
		}

		// ボトムアップ型２
		cache = new int[n][n];
		for (int i = 0; i < n; i++) {
			Arrays.fill(cache[i], Integer.MAX_VALUE);
			cache[i][i] = 0;
		}

		for (int j = 1; j < n; j++) {
			for (int i = j - 1; i >= 0; i--) {
				for (int k = 0; k < j - i; k++) {
					cache[i][j] = Math.min(cache[i][j], cache[i][i + k] + r[i] * r[i+k+1] * c[j] + cache[i + k + 1][j]);
				}
			}
		}
		int ret = cache[0][n -1];
		
		System.out.println(ret);
		
		sc.close();
	}

	@SuppressWarnings("unused")
	private static class Scanner {
		InputStreamReader isr;
		BufferedReader br;
		StreamTokenizer st;

		private Scanner() {
		}

		Scanner (InputStream in) {
			isr = new InputStreamReader(in);
			br = new BufferedReader(isr);
			st = new StreamTokenizer(br);
		}

		String next() throws RuntimeException  {
			try {
				if (st.nextToken() != StreamTokenizer.TT_WORD) {
				}
			} catch (IOException e) {
				throw new IllegalStateException();
			}

			return st.sval;
		}

		int nextInt() throws RuntimeException {
			try {
				if (st.nextToken() != StreamTokenizer.TT_NUMBER) {
					throw new InputMismatchException();
				}
			} catch (IOException e) {
				throw new IllegalStateException();
			}

			return (int)st.nval;
		}

		void close() {
		}
	}
}

Measured memory_bytes: 19988
#include <bits/stdc++.h>
#define YES "YES"
#define NO "NO"
#define YESNO OUT(three(solve(),YES,NO))
#define ECHO OUT(solve())
#define three(A,B,C) ((A)?(B):(C))
#define FOR(i,a,b)  for(LL i=(a);i< (LL)(b);i++)
#define EFOR(i,a,b) for(LL i=(a);i<=(LL)(b);i++)
#define RFOR(i,a,b) for(LL i=(a);i>=(LL)(b);i--)
#define REP(i,b) FOR(i,zero,b)
#define EREP(i,b) EFOR(i,zero,b)
#define RREP(i,b) RFOR(i,zero,b)
#define ALL(c) c.begin(),c.end()
#define MP make_pair
#define FI first
#define SE second
#define SI(x) (LL(x.size()))
#define PB push_back
#define DEBUG(a) OUT(a)
#define DEBUG2(a,b) OUT2(a,b)
#define cat cout << __LINE__ << endl
#define OUT(a) cout << (a) << endl
#define OUT2(a,b) cout << (a) <<" "<<(b) << endl
#define int LL
#define zero 0LL
using namespace std;
template<typename T> inline void maximize(T &a,T b){a=max(a,b);}
template<typename T> inline void minimize(T &a,T b){a=min(a,b);}
template<typename T> inline bool middle(T a,T b,T c){return b<=a && a<=c;}
typedef long long LL;
typedef double ld;
typedef LL ut;
typedef vector<ut> VI;
typedef vector<VI> VII;
typedef pair<ut,ut> pr;
typedef pair<ut,pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef priority_queue<pr,Vpr,greater<pr> > PQ;
inline void outputVI(VI x){REP(i,SI(x)){cout << three(i," ","") << x[i];}OUT("");}
const int SIZE1=1e6+1000;
const int SIZE2=2020;
const int SIZE3=410;
const int SIZE=SIZE1;
const LL p=7+1e9;
const LL INF=1LL<<60;
const long double EPS=1e-7;
string S;
ut N,M,K,X,Y;
// ut A,B,C,D,E,F,G,H,I,J,L,O,P,Q,R,T,U;
VI edges[SIZE];
LL vals[SIZE],nums[SIZE],maps[SIZE2][SIZE2],answer=zero;
 
////////////////////////////////////////////////////////////////////////////////////////////
 
////////////////////////////////////////////////////////////////////////////////////////////
VI strs[30];
LL BIT[SIZE];
LL used[SIZE];
void add(int x,int t){
	x++;
	while(x<=SIZE){
		BIT[x]+=t;
		x+=x&-x;
	}
}
LL sum(int x){
	x++;
	int ans=0;
	while(x>0){
		ans+=BIT[x];
		x-=x&-x;
	}
	return ans;
}
LL sum(int a,int b){
	return sum(b)-sum(a-1);
}
LL solve(){
	string s;
	cin >> s;
	int ans=0;
	REP(i,SI(s)){
		strs[s[i]-'a'].PB(i);
		add(i,1);
	}
	int ables=0;
	REP(i,30){
		ables+=((SI(strs[i])%2)==1);
	}
	int solo=-1;
	if(ables>=2) return -1;
	REP(i,SI(s)){
		int op=strs[s[i]-'a'].back();
		if(used[op] or used[i]) continue;
		if(op==i){
			solo=i;
			continue;
		}
		used[op]=used[i]=true;
		strs[s[i]-'a'].pop_back();
		ans+=sum(op+1,SI(s)-1);
		add(op,-1);
	}
	if(solo!=-1){
		ans+=sum(solo+1,SI(s)-1);
	}
	return ans;
}
signed main(){
	OUT(solve());
	return 0;
}

Measured memory_bytes: 37496
#include<stdio.h>
#include<string.h>
#define LEN 100005

typedef struct pp{
    char name[100];
    int t;
} P;

P Q[LEN];
int head, tail, n;

void enqueue(P x){
    Q[tail] = x;
    tail = (tail+1)%LEN;
}

P dequeue(){
    P x=Q[head];
    head = (head+1)%LEN;
    return x;
}

int minimum(int a, int b){
    if(a<b) return a;
    else return b;
}

int main(){
    int elaps=0, c, i, q;
    P u;
    
    scanf("%d%d",&n,&q);
    for(i=1; i<=n; i++){
        scanf("%s", Q[i].name);
        scanf("%d", &Q[i].t);
    }
    head=1;
    tail=n+1;
    
    while(head!=tail){
        u=dequeue();
        c=minimum(q, u.t);
        u.t -= c;
        elaps += c;
        if(u.t>0) enqueue(u);
        else{
            printf("%s %d\n",u.name,elaps);
        }
    }
    
    return 0;
}


Measured memory_bytes: 11904
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e5;
const int mod=1e9+7;
int n,cnt,ans=1;
int a[maxn+8],deg[maxn+8],vis[maxn+8],cir[maxn+8],l1[maxn+8],l2[maxn+8],sum[maxn+8];
int f[maxn+8];
bool tree[maxn+8];

int read()
{
    int x=0,f=1;char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
    for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
    return x*f;
}

void solve(int x)
{
    int siz_line=0;
    while(!cir[x]) siz_line++,x=a[x];
    l1[x]=siz_line;
    tree[cir[x]]=1;
    siz_line=1,x=a[x];
    while(deg[x]!=2) siz_line++,x=a[x];
    l2[x]=siz_line;
}

int main()
{
    n=read();
    for (int i=1;i<=n;i++) a[i]=read(),deg[a[i]]++;
    for (int i=1;i<=n;i++)
	{
	    if (vis[i]) continue;
	    int x=i;
	    while(!vis[x]) vis[x]=i,x=a[x];
	    if (vis[x]!=i) continue;
	    ++cnt;
	    while(!cir[x]) cir[x]=cnt,x=a[x];
	}
    memset(vis,0,sizeof(vis));
    for (int i=1;i<=n;i++) if (deg[i]>(1+(cir[i]>0))) {puts("0");return 0;}
    for (int i=1;i<=n;i++) if (!deg[i]) solve(i);
    for (int i=1;i<=n;i++)
	if (l1[i]) ans=1ll*ans*((l2[i]>=l1[i])+(l2[i]>l1[i]))%mod;
    for (int i=1;i<=n;i++)
	{
	    if (!cir[i]) continue;
	    if (tree[cir[i]]) continue;
	    if (vis[i]) continue;
	    int x=i,siz=0;while(!vis[x]) siz++,vis[x]=1,x=a[x];
	    sum[siz]++;
	}
    for (int i=1;i<=n;i++)
	{
	    if (!sum[i]) continue;
	    //printf("%d %d\n",i,sum[i]);
	    f[0]=1;
	    for (int j=1;j<=sum[i];j++)
		{
		    f[j]=f[j-1];
		    if (i>1&&(i&1)) f[j]=(f[j]+f[j-1])%mod;
		    if (j>1) f[j]=(f[j]+1ll*f[j-2]*(j-1)%mod*i%mod)%mod;
		}
	    ans=1ll*ans*f[sum[i]]%mod;
	}
    printf("%d\n",ans);
    return 0;
}


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

typedef long long ll;
ll mod = 1000000007;
const double PI = 3.141592653589793238460;

ll power(ll x, ll y)
{
    ll res = 1;
    x = x%mod;
    while (y)
    {
        if (y&1) res = ((res%mod)*(x%mod))%mod;

        y>>=1;
        x = ((x%mod)*(x%mod))%mod;
    }
    return res;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    int arr[n+1];
    for(int i=1; i<=n; i++){
        cin >> arr[i];
    }

    int dp[n+1];

    dp[1]=0;
    dp[2]=abs(arr[2]-arr[1]);
    
    for(int i=3; i<=n; i++){
        dp[i] = min(dp[i-1]+abs(arr[i]-arr[i-1]), dp[i-2]+abs(arr[i]-arr[i-2]));    
    }

    cout<<dp[n]<<'\n';

    return 0;
}


Measured memory_bytes: 4412