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

typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vii;
#define rrep(i, m, n) for(int (i)=(m); (i)<(n);  (i)++)
#define erep(i, m, n) for(int (i)=(m); (i)<=(n); (i)++)
#define  rep(i, n)    for(int (i)=0; (i)<(n);  (i)++)
#define rrev(i, m, n) for(int (i)=(n)-1; (i)>=(m); (i)--)
#define erev(i, m, n) for(int (i)=(n); (i)>=(m); (i)--)
#define  rev(i, n)    for(int (i)=(n)-1; (i)>=0; (i)--)
#define vrep(i, c)    for(__typeof((c).begin())i=(c).begin(); i!=(c).end(); i++)
#define  ALL(v)       (v).begin(), (v).end()
#define pb            push_back
#define mp            make_pair
template<class T, class S> inline bool minup(T& m, const S x){ return m>(T)x ? (m=(T)x, true) : false; }
template<class T, class S> inline bool maxup(T& m, const S x){ return m<(T)x ? (m=(T)x, true) : false; }

const int    INF = 1000000000;
const ll     MOD = 1000000007LL;
const double EPS = 1E-10;

typedef long long int llu;
const llu MODD[3] = {1000000009, 2000000011, 3000000019};
const llu base[3] = {901502696, 617916109, 103244261};
const llu basi[3] = {938106584, 434659818, 480258097};
llu B = 100000007LLU;
llu BI = 158730160LLU;
int n, m;
string s;
string q[333333];
llu b[3][333333];

template<typename T> T modMulti(T x, T y, T mod = MOD)
{
  T res = 0;
  x %= mod;
  while(y > (T)0){
    if(y & (T)1) res = (res + x) % mod;
    x = (x << 1) % mod;
    y >>= 1;
  }
  return res;
}

int main(int argc, char *argv[])
{
  cin >> n >> m;
  cin >> s;
  rep(i, m) cin >> q[i];
  rep(i, 3) b[i][0] = 1LL;
  rep(i, 3) rep(j, m) b[i][j + 1] = b[i][j] * base[i] % MODD[i];

  llu H[3] = {s[0], s[0], s[0]};
  int l = 0;
  int r = 0;
  vector<vector<llu> > can;
  rep(i, m){
    rep(j, 3){
      if(q[i] == "L++") H[j] += - (b[j][r - l] * s[l]) % MODD[j];
      if(q[i] == "L--") H[j] += b[j][r - l + 1] * s[l - 1];
      if(q[i] == "R++") H[j] = modMulti(H[j], base[j], MODD[j]) + s[r + 1];
      if(q[i] == "R--") H[j] = modMulti(H[j] - s[r] + MODD[j], basi[j], MODD[j]);
      if(H[j] < 0) H[j] += MODD[j];
      H[j] %= MODD[j];
    }
    if(q[i] == "L++") l += 1;
    if(q[i] == "L--") l -= 1;
    if(q[i] == "R++") r += 1;
    if(q[i] == "R--") r -= 1;
    vector<llu> tmp;
    rep(j, 3) tmp.pb(H[j]);
    can.pb(tmp);
  }

  sort(ALL(can));
  can.erase(unique(ALL(can)), can.end());

  cout << can.size() << endl;
  
  return 0;
}

Measured memory_bytes: 47468
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define dbg(x) cerr << #x << " = " << x << endl
#define _ << ' ' <<
using namespace std;
using ll = long long;
using vi = vector<int>;

bool f(string& s, string& t)
{
    map<char, char> m;
    int n = s.size();
    for (int i = 0; i < n; ++i)
    {
        if (m[t[i]])
        {
            if (m[t[i]] != s[i])
                return false;
        }
        else
            m[t[i]] = s[i];
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s, t;
    cin >> s >> t;
    if (!f(s, t) || !f(t, s))
        return cout << "No", 0;
    cout << "Yes";
}


Measured memory_bytes: 916
#include <iostream>
#include <cassert>

template<int Modulus>
struct modint {
	using value_type = int;

	static constexpr int mod = Modulus;
	static_assert(mod > 1, "Modulus must be greater than 1");

private :
	value_type x;

	template<class T>
	static constexpr value_type normalize (T value) noexcept {
		if (value < 0) {
			value = (-value) % mod;
			return (value ? value : mod - value);
		}
		return (value % mod);
	}

public :
	explicit constexpr modint () noexcept : x(0) { }

	template<class T>
	constexpr modint (T value) noexcept : x(normalize(value)) { }

	constexpr modint operator+ () const noexcept {
		return modint(*this);
	}

	constexpr modint operator- () noexcept {
		if (x != 0) x = mod - x;
		return modint(*this);
	}

	constexpr modint &operator+= (const modint &p) noexcept {
		if ((x += p.x) >= mod) x -= mod;
		return (*this);
	}

	constexpr modint &operator-= (const modint &p) noexcept {
		if ((x += mod - p.x) >= mod) x -= mod;
		return (*this);
	}

	constexpr modint &operator*= (const modint &p) noexcept {
		x = (int)(1LL * x * p.x % mod);
		return (*this);
	}

	constexpr modint &operator/= (const modint &p) noexcept {
		return ((*this) *= p.inverse());
	}

	constexpr modint operator+ (const modint &p) const noexcept {
		return (modint(*this) += p);
	}

	constexpr modint operator- (const modint &p) const noexcept {
		return (modint(*this) -= p);
	}

	constexpr modint operator* (const modint &p) const noexcept {
		return (modint(*this) *= p);
	}

	constexpr modint operator/ (const modint &p) const noexcept {
		return (modint(*this) /= p);
	}

	constexpr modint pow (long long exp) const noexcept {
		modint value(1), buff(x);
		while (exp) {
			if (exp & 1) value *= buff;
			buff *= buff;
			exp >>= 1;
		}
		return value;
	}

	constexpr modint inverse () const noexcept {
		return pow(Modulus - 2);
	}

	friend std::ostream &operator<< (std::ostream &os, const modint &p) {
		return (os << p.x);
	}

	friend std::istream &operator>> (std::istream &is, modint &p) {
		long long v;
		is >> v;
		p = modint(v);
		return (is);
	}

};


#include <iostream>
#include <vector>

constexpr int MOD = 1'000'000'007;

int main() {
	std::size_t n;
	std::cin >> n;
	std::vector<int> xs(n);
	for (std::size_t i = 0; i < n; i++) {
		std::cin >> xs[i];
	}
	
	int i = 0;
	modint<MOD> ans = 1;
	for (int x : xs) {
		if (x <= (i << 1)) ans *= (i + 1);
		else i++;
	}
	while (i) ans *= i--;
	
	std::cout << ans << '\n';
	
	return 0;
}

Measured memory_bytes: 3768
#include <bits/stdc++.h>
#define ll long long 
using namespace std;
const int maxn=2000000;
ll f[maxn][4];
int a[maxn][4];
int main()
{
	int n;
	cin>>n;
	for (int i=1;i<=n;i++) 
		for (int j=1;j<=3;j++)
			scanf("%d",&a[i][j]);
	for (int i=1;i<=3;i++) f[1][i]=a[1][i];
	for (int i=2;i<=n;i++)
		for (int j=1;j<=3;j++)
			for (int k=1;k<=3;k++)
				if (j!=k) f[i][j]=max(f[i][j],f[i-1][k]+a[i][j]);
	ll ans=0;
	for (int i=1;i<=3;i++) ans=max(ans,f[n][i]);
	cout<<ans; 
	return 0;
}

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

int main()
{
  //配列の個数入力
  int N;
  cin >> N;
  //配列の宣言
  int a[210];
  int i;
  //配列の初期化
  for (int i = 0; i < N; ++i) cin >> a[i];
  
  //回す変数の宣言
  int n=0;
  int m=0;
  
  while(m < 1){
      m = 0;
      for (i = 0; i < N; ++i) {
          if (a[i]%2==0){
            a[i] = a[i]/2;
          }else{
            ++m;
          }
      }
      ++n;
  }
  n = n-1;
  cout << n <<endl;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static final long mod = (long)1e9+7;
    public static final int inf = Integer.MAX_VALUE/10;

    static void solve(InputReader in, PrintWriter out){
        int h = in.ni();
        int n = in.ni();
        int sum = 0;
        for(int i = 0; i < n; i++) {
            sum += in.ni();
        }
        out.println(sum>=h?"Yes":"No");
    }

    public static void main(String[] args) throws Exception{
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        solve(in, out);
        out.close();
    }
    public static class InputReader{
        private BufferedReader br;
        private StringTokenizer st;
        public InputReader(InputStream is){
            br = new BufferedReader(new InputStreamReader(is));
            st = null;
        }
        public String ns(){
            if(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (Exception e){
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }
        public long nl(){
            return Long.parseLong(ns());
        }
        public int ni(){
            return Integer.parseInt(ns());
        }
        public Double nd(){
            return Double.parseDouble(ns());
        }
        public int[] ni(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }
        public long[] nl(int n){
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nl();
            }
            return a;
        }
        public double[] nd(int n){
            double[] a = new double[n];
            for (int i = 0; i < n; i++) {
                a[i] = nd();
            }
            return a;
        }
    }
}

Measured memory_bytes: 32220
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int MAX_N = 100005;
const ll MOD = 1e9+7;
ll T[MAX_N],A[MAX_N];

int main()
{
	int N;
	cin >> N;
	rep(i,N)
	{
		cin >> T[i];
	}
	rep(i,N)
	{
		cin >> A[i];
	}

	ll ans = 1;
	if (A[0] < T[0])
	{
		cout << 0 << endl;
		return 0;
	}
	for(int i = 1; i < N-1; ++i)
	{
		bool flag1 = false, flag2 = false;
		if (T[i-1] < T[i])
		{
			flag1 = true;
		}
		if (A[i] > A[i+1])
		{
			flag2 = true;
		}

		if (flag1 && flag2)
		{
			if (T[i] != A[i])
			{
				cout << 0 << endl;
				return 0;
			}
		}
		else if (flag1 && !flag2)
		{
			if (A[i] < T[i])
			{
				cout << 0 << endl;
				return 0;
			}
		}
		else if (!flag1 && flag2)
		{
			if (T[i] < A[i])
			{
				cout << 0 << endl;
				return 0;
			}
		}
		else
		{
			ans = ans * min(T[i],A[i]) % MOD;
		}
	}
	if (T[N-1] < A[N-1])
	{
		cout << 0 << endl;
		return 0;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 5196
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;

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

signed main(){
	int n,a[100010],ans[100010],all = 0,sum = 0;
	cin >> n;
	for(int i = 0;i < n;i++){
		cin >> a[i];
		all += a[i];
	}
	for(int i = 0;i < n - 2;i += 2) sum += a[i];
	for(int i = n - 1;i >= 0;i -= 2){
		ans[i] = all - sum * 2;
		if(i) sum = sum - a[i - 2] + a[i - 1];
	}
	for(int i = 1;i < n;i += 2) ans[i] = a[i - 1] * 2 - ans[i - 1];
	for(int i = 0;i < n;i++) cout << (i ? " " : "") << ans[i];
	cout << endl;
}

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

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        int a, b;
        cin >> a >> b;
        int ans = a * (a - 1) / 2;
        ans += b * (b - 1) / 2;
        cout << ans << "\n";
    }
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mp makepair
#define deb(x) cout<<x<<"\n";
#define deB(x,y) cout<<x<<" "<<y<<"\n";
#define Deb(x,y,z) cout<<x<<" "<<y<<" "<<z<<"\n" 
#define YES cout<<"YES\n";
#define Yes cout<<"Yes\n";
#define NO cout<<"NO\n";
#define No cout<<"No\n";
#define all(v) (v).begin(),(v).end()
int main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  //freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);
  ll t;
  cin>>t;
  string q;
  set<string> s;
  while(t--)
  {
  	cin>>q;
  	s.insert(q);
  }
  deb(s.size());
}

Measured memory_bytes: 19244
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<list>
#include<stack>
#include<queue>
#include<climits> //INT_MIN/MAX


using namespace std;

#define FOR(i,s,e) for(int (i)=(s);(i)<(e);(i)++)
#define FORR(i,s,e) for(int (i)=(s);(i)>(e);(i)--)
#define MOD 1000000007
#define llong long long
#define debug(x) cout<<#x<<": "<<x<<endl

llong n;


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

    int p[30] = { 0 };
    string s;
    cin >> s;

    FOR(i, 0, s.size()) {
        p[s[i] - 'a']++;
    }
    FOR(i, 0, 30) {
        if (0 != (p[i] % 2)) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
        return 0;
}

Measured memory_bytes: 256
import java.util.*;

class Main{
	public static void main(String[] args){
		Solve s = new Solve();
		s.solve();
	}	
}

class Solve{
	Solve(){}
	
	Scanner in = new Scanner(System.in);

	void solve(){
		int n = in.nextInt();
		int[] p = new int[n];
		int[][] d = new int[n][3];

		for(int i = 0; i < n; i++){
			for(int  j = 0; j < 3; j++){
				d[i][j] = in.nextInt();
			}
		}

		for(int j = 0; j < 3; j++) {
			Map<Integer,Integer> m = new HashMap<>();
			for(int i = 0; i < n; i++){
				if(m.get(d[i][j]) == null) m.put(d[i][j], 1);
				else m.put(d[i][j],m.get(d[i][j]) + 1);
			}
			for(int i = 0; i < n; i++){
				if(m.get(d[i][j]) == 1) p[i] += d[i][j];
			}
		}

		for(int i = 0; i < n; i++){
			System.out.println(p[i]);
		}
	}

	
	
}

Measured memory_bytes: 28836
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <functional>
#include <numeric>
#include <iostream>
#include <string>
#include <time.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (n); ++i)

char s[212345];
string S;
vector<vector<pair<int, int>>> AD;

int main() {

	scanf("%s", s);
	int N = strlen(s);
	rep(i, N) {
		if (s[i] == 'B' && s[i + 1] == 'C') {
			S.push_back('D');
			++i;
		}
		else {
			S.push_back(s[i]);
		}
	}

	int Ac = 0, Dc = 0;
	vector<pair<int, int>> sub;
	for (auto ss : S) {
		if (Dc) {
			if (ss == 'A') {
				sub.push_back({ Ac, Dc });
				Ac = 1;
				Dc = 0;
			}
			else if (ss == 'D') ++Dc;
			else {
				sub.push_back({ Ac, Dc });
				AD.push_back(sub);
				sub.clear();
				Ac = 0;
				Dc = 0;
			}
		}
		else if (Ac) {
			if (ss == 'A') ++Ac;
			else if (ss == 'D') ++Dc;
			else {
				Ac = 0;
				if(sub.size()) AD.push_back(sub);
				sub.clear();
			}
		}
		else {
			if (ss == 'A') ++Ac;
		}
	}
	if (Ac && Dc) sub.push_back({ Ac, Dc });
	if (sub.size()) AD.push_back(sub);

	ll ans = 0;
	for (auto ad : AD) {
		int size = ad.size();
		for (int i = 0; i < size; ++i) {
			for (int j = 0; j < size - i; ++j) {
				ans += (ll)ad[j].first * ad[j + i].second;
			}
		}
	}

	printf("%lld\n", ans);

	return 0;
}


Measured memory_bytes: 1284
n,m=map(int,input().split())

x=[[] for i in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    if b not in x[a-1]:
        x[a-1].append(b)
        if a not in x[b-1]:
            x[b-1].append(a)

ans=0

while True:
    idx,flg=0,0
    for i in x:
        if len(i)==1:
            flg=1
            x[i[0]-1].remove(idx+1)
            x[idx]=[]
            ans+=1
        idx+=1
    if flg==0:
        break
print(ans)


Measured memory_bytes: 3064
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

C = np.array([a // 400 for a in A])
C[C >= 8] = 8

ans = 0
for i in range(8):
    ans += np.any(C == i)
print(max(ans, 1), ans + (C == 8).sum())


Measured memory_bytes: 13668
s = input()
ans = 0
tmp = 0
flg = 0
for i in range(len(s)):
  if s[i] == 'A' and flg == 0:
    ans += 1
    flg = 1
  elif flg == 1 and s[i] == 'Z':
    flg = 2
    ans += 1
  elif flg == 1:
    ans += 1
  elif flg == 2 and s[i] == 'Z':
    ans += tmp+1
    tmp = 0
  elif flg == 2:
    tmp += 1
print(ans)

Measured memory_bytes: 3516
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    ll n; cin >> n;
    queue<ll> q, z;
    for(int i = 1; i < 10; i++){
        q.push(i);
        z.push(i);
    }
    for(int i = 0; i <= 8; i++){
        queue<ll> p;
        ll tam = z.size();
        for(int j = 0; j < tam; j++){
            ll hlp = z.front();
            z.pop();
            for(int k = 0; k < 10; k++){
                if(abs((hlp % 10) - k) <= 1){
                    ll y = (hlp * 10) + k;
                    p.push(y);
                }
            }
        }
        while(!p.empty()){
            z.push(p.front());
            q.push(p.front());
            p.pop();
        }
    }
    vector<ll> w;
    while(!q.empty()){
        w.push_back(q.front());
        q.pop();
    }
    sort(w.begin(), w.end());
    cout << w[n - 1] << "\n";
    return 0;
}


Measured memory_bytes: 5108
#pragma region template 2.4
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using pq_asc = priority_queue<T, vector<T>, greater<T>>;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP1(i, n) for (ll i = 1; i <= (n); ++i)
#define FOR(i, a) for (auto &i : a)
#define CH(f, x, y) x = f(x, y)
#define IN(T, x) \
    T x;         \
    cin >> x;
#define AIN(T, a, n) \
    vector<T> a(n);  \
    FOR(i, a)        \
    cin >> i;
#define A2IN(T1, a, T2, b, n) \
    vector<T1> a(n);          \
    vector<T2> b(n);          \
    REP(i, n)                 \
    cin >> a[i] >> b[i];
#define OUT(x) cout << (x) << endl;
#define FOUT(x) cout << fixed << setprecision(15) << (x) << endl;
#define ALL(a) (a).begin(), (a).end()
#define SORT(a) sort(ALL(a))
#define RSORT(a) \
    SORT(a);     \
    reverse(ALL(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define DUMPA(a)          \
    cout << #a << " = {"; \
    JOUT(ALL(a), ", ", cout) << "}" << endl;

template <typename T>
ostream &JOUT(T s, T e, string sep = " ", ostream &os = cout)
{
    if (s != e)
    {
        os << *s;
        ++s;
    }
    while (s != e)
    {
        os << sep << *s;
        ++s;
    }
    return os;
}

ostream &YES(bool cond, string yes = "Yes", string no = "No", ostream &os = cout)
{
    if (cond)
    {
        os << yes << endl;
    }
    else
    {
        os << no << endl;
    }
    return os;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p)
{
    os << '(' << p.first << ", " << p.second << ')';
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << '[';
    JOUT(ALL(v), ", ", os) << ']';
    return os;
}

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#pragma endregion template

int main()
{
    IN(ll, n);
    IN(ll, m);
    AIN(ll, a, n);
    FOR(x, a)
    {
        --x;
    }
    vi delta(2 * m), cnt(2 * m);
    ll ans = 0;
    REP(i, n - 1)
    {
        ll d = (a[i + 1] - a[i] + m) % m;
        ans += d;
        if (d >= 2)
        {
            // ++delta[a[i] + 2];
            ++cnt[a[i] + 2];
            delta[a[i] + d + 1] += -(d - 1);
            --cnt[a[i] + d + 1];
        }
    }
    // DUMP(ans);
    // DUMP(delta);
    // DUMP(cnt);
    // 1 2 3  4 -4 0 0  0
    // 0 0 1  2  3 4 5 -5
    // 0 1 2 -2  0 0 0  0

    // 1 2 3  2  1 1 1  0
    // 1 3 6  6  3 4 5  0
    ll c = 0;
    vi s(2 * m);
    REP1(i, 2 * m - 1)
    {
        c += cnt[i];
        s[i] = s[i - 1] + c + delta[i];
    }
    // DUMP(c);
    // DUMP(s);
    ll opt = 0;
    REP(i, m)
    {
        CH(max, opt, s[i] + s[i + m]);
    }
    ans -= opt;
    OUT(ans);
}

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

using ll = long long;

#define pb push_back
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a.size())
#define clr(a, b) memset(a, b, sizeof(a))
#define REP(i, a, b) for(int i=(int)(a); i<(int)(b); ++i)
#define REPD(i, a, b) for(int i=(int)(a)-1; i>=(int)(b); --i)
#define FOR(it,c) for ( __typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++ )

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e5 + 5;
vector<int> adj[N];
int n, m, used[N], pa[N];

void dfs(int node) {
	if(used[node])
		return;
	used[node] = 1;
	// pa[node] = p;
	for(int x: adj[node]) {
		dfs(x);
	}
}

void bfs() {
	clr(used, 0);
	queue<int> q;
	q.push(0);
	while(!q.empty()) {
		int f = q.front();
		q.pop();
		for(int x: adj[f]) {
			if(!used[x]) {
				used[x] = 1;
				q.push(x);
				pa[x] = f;
			}
		}
	}
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    REP(i, 0, m) {
    	int x, y;
    	cin >> x >> y;
    	--x, --y;
    	adj[x].pb(y);
    	adj[y].pb(x);
    }
    dfs(0);
    REP(i, 0, n) {
    	pa[i] = 1e9;
    	if(!used[i]) {
    		cout << "No\n";
    		return 0;
    	}
    }
    bfs();
    cout << "Yes\n";
    REP(i, 1, n) {
    	cout << pa[i]+1 << "\n";
    }
    return 0;
}


Measured memory_bytes: 12832
#include <stdio.h>
int main(void){
    int n, s;
    scanf("%d", &n);
    int ns[n];
    for (int i=0; i<n; i++) {
        scanf("%d", &ns[i]);
    }
    
    scanf("%d", &s);
    int ss[s];
    for (int i=0; i<s; i++) {
        scanf("%d", &ss[i]);
    }
    
    int c = 0;
    
    for (int i=0; i<s; i++) {
        for (int j=0; j<n; j++) {
            if (ss[i] == ns[j]) {
                c++;
                break;
            }
        }
    }
    
    printf("%d\n", c);
}



Measured memory_bytes: 2116
#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
using namespace std;
long long ap(long long X, long long D, long long N){
	return (X * 2 + D * (N - 1)) * N / 2;
}
int main(){
	long long N, X, D;
	cin >> N >> X >> D;
	if (D == 0){
		if (X == 0){
			cout << 1 << endl;
		} else {
			cout << N + 1 << endl;
		}
	} else {
		if (D < 0){
			X += (N - 1) * D;
			D = -D;
		}
		long long sum = ap(X, D, N);
		map<int, vector<pair<long long, long long>>> mp;
		for (int i = 0; i <= N; i++){
			long long sum1 = ap(X, D, i);
			long long diff1 = sum1 - (sum - sum1);
			long long sum2 = ap(X, D, N - i);
			long long diff2 = (sum - sum2) - sum2;
			long long r = (diff1 % (D * 2) + D * 2) % (D * 2);
			mp[r].push_back(make_pair(diff2, diff1));
		}
		long long ans = 0;
		for (auto P : mp){
			int r = P.first;
			vector<pair<long long, long long>> R = P.second;
			sort(R.begin(), R.end());
			int cnt = R.size();
			for (int i = 0; i < cnt; i++){
				R[i].first = (R[i].first - r) / (D * 2);
				R[i].second = (R[i].second - r) / (D * 2);
			}
			vector<pair<long long, long long>> R2;
			for (int i = 0; i < cnt; i++){
				long long left = R[i].second;
				long long right = R[i].first;
				while (!R2.empty()){
					if (left <= R2.back().first){
						left = min(left, R2.back().second);
						R2.pop_back();
					} else {
						break;
					}
				}
				R2.push_back(make_pair(right, left));
			}
			int cnt2 = R2.size();
			for (int i = 0; i < cnt2; i++){
				ans += R2[i].first - R2[i].second + 1;
			}
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 25412
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long ul;
// for文短縮類
#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 FOR(i, a, b) for (ll i = a; i <= (ll)(b); i++)
#define FORD(i, a, b) for (ll i = a; i >= (ll)(b); i--)
// iteratorのbeginとendをまとめて渡す
#define ALL(x) (x).begin(), (x).end()
//略
#define PB push_back  // vectorヘの挿入
#define MP make_pair  // pairのコンストラクタ
#define F first       // pairの一つ目の要素
#define S second      // pairの二つ目の要素
//出力
#define COUT(x) cout << (x) << endl
#define SCOUT(x) cout << (x) << " "
#define ENDL cout << endl
/************ Combination wtih MOD ************
const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
// preprocess for some tables
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;
  }
}
// combination
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;
}
*******************************************************/
struct UnionFInd {
  vector<ll> par;
  UnionFInd(ll N) : par(N) {
    for (ll i = 0; i < N; i++) {
      par[i] = i;
    }
  }
  ll root(ll x) {
    if (par[x] == x) return x;
    return par[x] = root(par[x]);
  }
  void unite(ll x, ll y) {
    ll rx = root(x);
    ll ry = root(y);
    if (rx == ry) return;
    par[rx] = par[ry];
  }
  bool same(ll x, ll y) {
    ll rx = root(x);
    ll ry = root(y);
    return rx == ry;
  }
};
int main(int argc, char *argv[]) {
  // input高速化。cinとcoutの結合解除。scanfとprintfは使えない。
  cin.tie(0);
  ios_base::sync_with_stdio(0);

  ll n,m;
  cin >> n >> m;

  vector<ll> a(m);
  vector<ll> b(m);
  REP(i, m){
      ll ai, bi;
      cin >> ai >> bi;
      ai--;
      bi--;
      a[i] = ai;
      b[i] = bi;
  }

  ll ans = 0;
  REP(ex, m){
      UnionFInd uf(n);

      REP(i, m){
          if(i == ex){
              continue;
          }
          uf.unite(a[i], b[i]);
      }

      if(!uf.same(a[ex], b[ex])){
          uf.unite(a[ex], b[ex]);
          if(uf.same(a[ex], b[ex]))
              ans += 1;
      }
  }
  cout << ans << endl;
}

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

const int CountStop=245959;

int main() {
  while (1) {
    int n; cin>>n;
    if (n==0) break;
    vector<int> x(CountStop+1, 0);
    rep(i, n) {
      string S,G; cin>>S>>G;
      int start=0;
      start+=(int)(S[0]-'0')*100000;
      start+=(int)(S[1]-'0')*10000;
      start+=(int)(S[3]-'0')*1000;
      start+=(int)(S[4]-'0')*100;
      start+=(int)(S[6]-'0')*10;
      start+=(int)(S[7]-'0')*1;
      x[start]++;
      int goal=0;
      goal+=(int)(G[0]-'0')*100000;
      goal+=(int)(G[1]-'0')*10000;
      goal+=(int)(G[3]-'0')*1000;
      goal+=(int)(G[4]-'0')*100;
      goal+=(int)(G[6]-'0')*10;
      goal+=(int)(G[7]-'0')*1;
      x[goal]--;
    }
    rep(i, CountStop) x[i+1]+=x[i];
    int res=0;
    rep(i, CountStop+1) res=max(res, x[i]);
    cout<<res<<endl;
  }
}



Measured memory_bytes: 4104
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author cherrypi59
 */

#pragma GCC optimize ("O2")
#pragma GCC optimize ("tree-vectorize")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define FFOR(i, a, b) FOR(i, a, b+1)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) FOR(i, 1, n+1)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define LEN(x) (int)(x).size()
#define DUMP(x) cerr<<__LINE__<<' '<<#x<<"="<<(x)<<endl;
#define pb push_back
#define eb emplace_back
#define mp make_pair

using namespace std;
using lint = long long;
using pii =  pair<int, int>;
using pll =  pair<lint, lint>;
template <typename T> using vc = vector<T>;
template <typename T> using vvc = vector<vector<T>>;
template <typename T> inline bool chmax(T &a, T b){if(a<b){a = b; return true;} return false;}
template <typename T> inline bool chmin(T &a, T b){if(a>b){a = b; return true;} return false;}

constexpr lint ten(int n) {return n==0 ? 1 : ten(n-1)*10;}

class CTsundoku {
public:
    void solve(std::istream& in, std::ostream& out){
        ios_base::sync_with_stdio(false);
        in.tie(nullptr), out.tie(nullptr);
        int N, M, K;
        in>>N>>M>>K;
        vc<lint> A(N+1, 0), B(M+1, 0);
        REP(i, N) in>>A[i+1], A[i+1] += A[i];
        REP(i, M) in>>B[i+1], B[i+1] += B[i];
        int ans = 0;
        REP(i, N+1){
            if(A[i]>K) break;
            int id = upper_bound(ALL(B), K-A[i])-B.begin()-1;
            chmax(ans, i+id);
        }
        out<<ans<<'\n';
    }
};


int main() {
	CTsundoku solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 6368
n,x = map(int,input().split())

a = list(map(int,input().split()))

a.sort()


now=x
cnt=0
for i in range(n):
    now -=a[i]
    cnt +=1
    if now<0:
        cnt -=1
        print(cnt)
        exit()

if now==0:
    print(cnt)
else:
    print(cnt-1)


Measured memory_bytes: 38384
import sys;      from decimal import Decimal
import math;     from itertools import combinations, product
import bisect;   from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def lcm(a: int, b: int) -> int: return (a * b) // math.gcd(a, b)

import numpy as np
from numba import njit, i8

@njit(i8(i8))
def dp(N):
    dp = np.full(100005, INF, dtype=np.int64)
    dp[0] = 0
    
    for n in range(1, N + 1):
        pow6 = 1
        while pow6 <= n:
            dp[n] = min(dp[n], dp[n - pow6] + 1)
            pow6 *= 6
        pow9 = 1
        while pow9 <= n:
            dp[n] = min(dp[n], dp[n - pow9] + 1)
            pow9 *= 9
    
    return dp[n]

def Main():
    n = read_int()
    print(dp(n))    

if __name__ ==  '__main__':
    Main()

Measured memory_bytes: 108784
import bisect
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort()
c.sort()
ans=0
for i in b:
  ans+=bisect.bisect_left(a,i)*(n-bisect.bisect_right(c,i))
print(ans)

Measured memory_bytes: 105380
#include<stdio.h>
int main(void)
{
char ch;
int counter[26],num;
for(num=0;num<26;num++){counter[num]=0;}
while ( scanf("%c", &ch) != EOF ){
	if(ch<91 && ch>64)num=ch-'A';
	else num = ch - 'a'; 
	if(num<26)counter[num]++;  
}
for(num=0;num<26;num++){
	ch=num+'a';
	printf("%c : %d\n",ch,counter[num]);
}
return 0;
}

Measured memory_bytes: 540
#include <bits/stdc++.h>
using namespace std;
int main(){
  int q;
  cin >> q;
  long long a = 0;
  long long b = 0;
  for (int i = 0; i < q; i++){
    int p;
    char c;
    int n;
    cin >> p >> c >> n;
    if (c == '('){
      a += n;
    }
    if (c == ')'){
      b += n;
    }
    if (a == b){
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
  }
}


Measured memory_bytes: 3096
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cmath>
#include <iomanip>
#include <string>

typedef long long ll;
using namespace std;
const int mod = 1000000007;

ll gcd(ll a, ll b) {
    while (b) {
        int tmp = a;
        a = b;
        b = tmp % b;
    }
    return a;
}

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

    ll c = gcd(a, b);

    ll ans = a * b;
    cout << ans / c << '\n';

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repe(i, n) for (int i = 0; i <= (int)(n); i++)
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define ANS cout << ans << endl
#define all(a) a.begin(),a.end()
#define SORT(a) sort(all(a))
#define REVERSE(a) reverse(all(a))
#define int ll
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORe(i, m, n) for(int i = m;i <= n;i++)
#define VIin(a) for(int i=0; i<a.size(); i++) cin >> a[i]
#define OUT(a) cout << a << endl
#define IN(a) cin >> a
#define INT(a) int a; cin >> a
typedef vector<int> VI;
typedef vector<VI> VVI;
const int MOD=1e9+7;
const long long INF = 1LL << 60;
/*最大公約数*/int gcd(int x, int y) { return y ? gcd(y,x%y) : x;}
/*最小公倍数*/int lcm(int a, int b) { int g = gcd(a, b); return a / g * b; }
/*素数判定*/int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*約数列挙*/vector<int> getDivisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------------------------------------
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    INT(a); INT(b); INT(c);
    INT(x);
    int ans = 0;
    repe(i,a) repe(j,b) repe(k,c) if(i* 500 + j * 100 + k * 50 == x) ans++;
    ANS;

    return 0;
}

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

typedef long long ll;
using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M; cin >> N >> M;
    const int INF = 1e8;
    int def[10] = {-INF, 2, 5, 5, 4, 5, 6, 3, 7, 6};
    int dp[N+1];
    fill(dp, dp + N + 1, -INF);
    vector<pair<int, int>> hand;
    int A[M];
    for (int i = 0; i < M; i++) {
        cin >> A[i];
    }
    dp[0] = 0;
    for (int i = 0; i <= N; i++) {
        if (dp[i] < 0) continue;
        for (int k = 0; k < M; k++) {
            if (def[A[k]] + i > N) continue;
            dp[def[A[k]] + i] = max(dp[i] + 1, dp[def[A[k]] + i]);
        }
    }
    sort(A, A + M, greater<>());
    vector<int> ans;
    int initial = N;
    while (ans.size() < dp[initial]) {
        for (int i = 0; i < M; i++) {
            if (dp[N - def[A[i]]] == dp[N] - 1 && N - def[A[i]] >= 0) {
                N -= def[A[i]];
                ans.push_back(A[i]);
                break;
            }
        }
    }
    sort(ans.begin(), ans.end(), greater<>());
    for (auto &an : ans) cout << an;
    return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<numeric>
#include<utility>

using namespace std;

typedef long long int ll;
const int INF = 1<<30;
const long long LINF = 1LL<<60;

int main(){
  string s, t;
  cin >> s >> t;
  int ans = 0;
  for(int i = 0; i < 3; i++){
    if(s[i] == t[i]){
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
//
//  main.cpp
//  breadth_first_search
//
//  Created by ???????????? on 2017/10/22.
//  Copyright ?? 2017 ????????????. All rights reserved.
//

#include <iostream>
#include <stdio.h>
#include <queue>

#define n_max 100
#define INFTY 1000
#define WHITE 0
#define GRAY 1
#define BLACK 2

using namespace std;

int M[n_max][n_max], color[n_max], d[n_max], n;

queue<int> Q;

void encode_graph(){
    int i, j, id, num, node;
    
    //initialize with 0
    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            M[i][j] = 0;
        }
    }
    
    for (i = 0; i < n; i++){
        scanf("%d", &id);
        scanf("%d", &num);
        for(j = 0; j < num; j++){
            scanf("%d", &node);
            M[id-1][node-1] = 1;
        }
    }
}

void bfs(){
    for(int i = 0; i < n ; i++){
        color[i] = WHITE;
        d[i] = INFTY;
    }
    //starting point
    int s = 0;
    color[s] = GRAY;
    d[s] = 0;
    Q.push(s);
    
    while(!Q.empty()){
        int u = Q.front(); Q.pop();
        for(int v = 0; v < n; v++){
            if((M[u][v]) && (color[v] == WHITE)){
                color[v] = GRAY;
                d[v] = d[u] + 1;
                Q.push(v);
            }
        }
        color[u] = BLACK;
    }
    
    
    
}

int main(int argc, const char * argv[]) {
    scanf("%d", &n);
    
    encode_graph();
    bfs();
    
    for(int i = 0; i < n; i++){
        cout<<i+1<<" "<<((d[i] == INFTY) ? (-1): (d[i]))<<endl;
    }
    
//    std::cout << "Hello, World!\n";
    return 0;
}

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

int main(){
int N,L;
  cin >> N >> L;
  vector<string> vec(N);
  for(int i=0 ; i<N ; i++){
     cin >> vec.at(i);
  }
sort(vec.begin(), vec.end());
  string ans = "";
  for(int j=0; j <N ; j++){
  ans += vec.at(j);
  }
  cout << ans << endl;
return 0;
}

Measured memory_bytes: 256
object Main extends App {

  import scala.io.StdIn._

  val Array(n, m) = readLine.trim.split(' ').map(_.toInt)
  val prices = readLine.trim.split(' ').map(_.toInt)

  println(buyLowest(prices, m, n) match {
    case Some(l) ⇒ l.mkString
    case None ⇒ "NA"
  })

  def buyLowest(prices: Array[Int], money: Int, card: Int, current: Int = 0): Option[List[Int]] = {
    if (card == 0) Some(Nil)
    else if (current == 10) None
    else {
      (0 to math.min(card, money / prices(current))).reverse.flatMap{buy ⇒
        buyLowest(prices, money - buy * prices(current), card - buy, current + 1).map{l ⇒ List.tabulate(buy){_ ⇒ current} ++ l}
      }.headOption
    }
  }

  implicit class Extend[T](value: T){
    def also(func: T ⇒ Unit): T = {func(value); value}
    def let[A](func: T ⇒ A): A = func(value)
  }
}


Measured memory_bytes: 44420
#include <bits/stdc++.h>
#include <algorithm>  
#include <unordered_set>
#include <cmath>

#define ll long long

using namespace std;

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	ll k;

	cin >> k;

	ll curr = 0;

	for (int i = 1; i <= 1000000; i++) {

		curr = curr * 10 + 7;
		curr = curr % k;

		if (curr == 0) {
			cout << i << endl;
			return 0;
		}
	}

	cout << -1 << endl;
	return 0;
}


Measured memory_bytes: 3656
#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 3e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n, m;

vector<pll> rem[MAXN];

ll tree[MAXN], t[4*MAXN], lazy[4*MAXN];
ll dp[MAXN];

ll get(int ind){
    ll res = 0;
    for(; ind > 0; ind -= (ind & -ind)){
        res += tree[ind];
    }
    return res;
}
void push(int v){
    t[2*v] += lazy[v];
    t[2*v + 1] += lazy[v];
    lazy[2*v] += lazy[v];
    lazy[2*v + 1] += lazy[v];
    lazy[v] = 0;
}

void build(int v, int l, int r){
    if(l == r){
        t[v] = -INF;
    }else{
        int m = (l + r)  / 2;
        build(2*v, l, m);
        build(2*v + 1, m + 1, r);
        t[v] = -INF;
    }
}

void upd1(int v, int tl, int tr, int pos, ll val){
    if(tl == tr){
        t[v] = val;
    }else{
        push(v);
        int m = (tl + tr) / 2;
        if(pos <= m)
            upd1(2*v, tl, m, pos, val);
        else upd1(2*v + 1, m + 1, tr, pos, val);
        t[v] = max(t[2*v], t[2*v + 1]);
    }
}

void upd2(int v, int tl, int tr, int l, int r, ll val){
    if(l > r) return;
    if(tl == l && tr == r){
        t[v] += val;
        lazy[v] += val;
    }else{
        push(v);
        int m = (tl + tr) / 2;
        upd2(2*v, tl, m, l, min(m, r), val);
        upd2(2*v + 1, m + 1, r, max(m + 1, l), r, val);
        t[v] = max(t[2*v], t[2*v + 1]);
    }
}

ll qu(int v, int tl, int tr, int l, int r){
    if(l > r)
        return -INF;
    if(tl == l && tr == r){
        return t[v];
    }else{
        push(v);
        int tm = (tl + tr) / 2;
        ll ans1 = qu(2*v, tl, tm, l, min(r, tm)), ans2 = qu(2*v + 1, tm + 1, tr, max(l, tm + 1), r);
        return max(ans1, ans2);
    }
}

void upd(int ind, ll val){
    for(; ind <= n; ind += (ind & -ind))
        tree[ind] += val;
}

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

    #ifdef Local
        freopen("../IO/int.txt","r",stdin);
        freopen("../IO/out.txt","w",stdout);
    #endif

    cin>>n>>m;

    for(int i = 0; i < m; i++){
        ll l, r, a;
        cin>>l>>r>>a;
        rem[r].push_back({l, a});
        upd(l, a);
    }
    ll ans = 0;
    build(1, 1, n);
    for(int i = 1; i <= n; i++){
        dp[i] = -INF;
    }
    for(int i = 1; i <= n; i++){
        ll a = get(i);
        ll b = max(0LL, qu(1, 1, n, 1, i - 1));
        dp[i] = max(dp[i], a + b);
        ans = max(ans, dp[i]);
        for(auto j: rem[i]){
            upd(j.ff, -j.ss);
            upd2(1, 1, n, j.ff, n, j.ss);
        }
        upd1(1, 1, n, i, dp[i] - get(i));
    }
    cout<<ans<<endl;

    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Measured memory_bytes: 30336
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <fstream>
using namespace std;

int solve(int*, int, int);
int main(){
  int n, points;
  while(cin>>n>>points, n!=0 && points!=0){
    int darts[n+1]; //投げない場合を考えるため、1つだけ多く取っておく
    darts[0]=0; //投げない場合
    for(int i=1; i<=n; i++) cin >> darts[i];


    //ダーツを2回投げた時の場合を考える
    //ループを抜けた後に cnt=(n+1)*(n+1)
    int cnt=0;
    int set[(n+1)*(n+1)];
    for(int i=0; i<=n; i++){
      for(int j=0; j<=n; j++){
        set[cnt++]=darts[i]+darts[j];
      }
    }

    //upper_boundを使うためソート
    sort(set, set+(n+1)*(n+1));

    int ans=0;
    for(int i=0; i<(n+1)*(n+1); i++){
      int aim = points-set[i];//目標
      if(aim<0) continue;
      int last = *(upper_bound(set, set+(n+1)*(n+1), aim)-1);
      if(set[i]+aim <= points) ans=max(ans, set[i]+last);
    }


    printf("%d\n", solve(darts, n+1, points));
  }

  return 0;
}

/*
int solve(int* darts, int size, int point){
  int temp[size*size];
  int k=0;
  //2本投げ終わった後の合計点数を探索
  for(int i=0; i<size; i++){
    for(int j=0; j<size; j++){
      temp[k++]= darts[i]+darts[j];
    }
  }

  sort(temp, temp+size*size);

  int ans=0;
  for(int i=0; i<size*size; i++){
    int aim = point-temp[i];
    if(aim<0) continue;
    int last = *(upper_bound(temp, temp+size*size, aim)-1);
    if(temp[i]+last<=point) ans=max(ans, temp[i]+last);
  }

  return ans;
}
*/


int solve(int* darts, int size, int points){
  //ダーツを2回投げた時の場合を考える
  //ループを抜けた後に cnt=(n+1)*(n+1)
  int cnt=0;
  int set[size*size];
  for(int i=0; i<size; i++){
    for(int j=0; j<size; j++){
      set[cnt++]=darts[i]+darts[j];
    }
  }

  //upper_boundを使うためソート
  sort(set, set+size*size);

  int ans=0;
  for(int i=0; i<size*size; i++){
    int aim = points-set[i];//目標
    if(aim<0) continue;
    int last = *(upper_bound(set, set+size*size, aim)-1);
    if(set[i]+aim <= points) ans = max(ans, set[i]+last);
  }
  return ans;
}



Measured memory_bytes: 11020
from statistics import mean, median,variance,stdev
import numpy as np
import sys
import math
import fractions
import itertools
import copy
from operator import itemgetter
#以下てんぷら
def j(q):
    if q==1: print("Yes")
    else:print("No")
    exit(0)


def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")

def ip():
    return int(input())
#n = ip()                                     #入力整数1つ
x,y= (int(i) for i in input().split())       #入力整数横2つ以上
#a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
a=[input() for i in range(x)]    #入力セット(整数改行あり)(2/2)

#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
#こっから本文
a.sort()
print(''.join(a))

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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;

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

const ll INF = 1e15;
const int MOD = 1e9+7;
const ll LINF = 1e18;


signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n; cin>>n;
  vll a(n);
  rep(i,n){
    cin>>a[i];
  }
  ll ans=0;
  ll now=1;
  rep(i,n){
    if(now==a[i]){
      ans++;
      now++;
    }
  }
  if(ans!=0) cout<<n-ans<<endl;
  else cout<<-1<<endl;
}

Measured memory_bytes: 1792
N = gets.chomp.to_i
T = gets.chomp
S = Array.new(N)
for i in 0...N do
    S[i] = T[i].to_i
end
a = Array.new(3)
answer = 0
for i in 0...1000 do
    a[0] = i/100
    a[1] = (i/10)%10
    a[2] = i%10
    j = 0
    k = 0
    while j < N && k < 3
        if a[k] == S[j]
            k += 1
            if k == 3
              answer += 1  
            end
        end
        j += 1
    end
end
puts answer

Measured memory_bytes: 2044
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

constexpr static int MOD = 1e9 + 7;
constexpr static int MAXN = 1e6;

int n;
int x[MAXN];

int solve() {
    // look at the range at which the kth pick can "go"
    int cur = 1;
    int used = 0;
    int64_t total = 1;
    for (int i = 0; i < n; i++) {
        if (x[i] < cur) {
            total = total * (i + 1 - used) % MOD;
            used++;
        }
        else {
            cur += 2;
        }
    }
    while (used < n) {
        total = total * (n - used) % MOD;
        used++;
    }
    return (int) total;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &x[i]);
    printf("%d\n", solve());
}


Measured memory_bytes: 512
#include<iostream>

using namespace::std;
#define int long long int

main(){
    int n,a,b;
    cin>>n>>a>>b;
    int minn=min(min(a,b)+abs(b-a)/2,min(n-a,n-b)+1+abs(b-a)/2);
    if(!((a^b)&1))
        minn=min(minn,abs(a-b)/2);
    cout<<minn<<'\n';
}

Measured memory_bytes: 256
import bisect
n = int(input())
l_li = list(map(int,input().split()))
l_li.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        ind = bisect.bisect_left(l_li,l_li[i]+l_li[j])
        ans += ind-1 - j
print(ans)


Measured memory_bytes: 42972
#include "bits/stdc++.h"
using namespace std;

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

    int n;
    cin >> n;
    int res = n;
    for(int i = 0; i <= n; i++){
        int cc = 0;
        int t = i;
        while(t > 0){
            cc += t % 6;
            t /= 6;
        }
        t = n - i;
        while(t > 0){
            cc += t % 9;
            t /= 9;
        }
        if(res > cc) res = cc;
    }
    cout << res << endl;
}

Measured memory_bytes: 256