akhauriyash/Code-Regression huggingface dataset:
# ARC 076 D
# クラスカル法による最小全域木問題

# 辺をコストの小さい順に見ていき、閉路ができない(Union-Findで判定)場合は追加する

from heapq import heappush, heappop


class UnionFind(object):

    def __init__(self, N):
        self.tree = [i for i in range(N)]
        self.rank = [0] * (N + 1)

    def find(self, x):
        if self.tree[x] == x:
            return x
        else:
            self.tree[x] = self.find(self.tree[x])  # 経路圧縮
            return self.tree[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        # ランクを考慮しない場合はどちらが親になっても良い
        if self.rank[x] < self.rank[y]:
            self.tree[x] = y
        else:
            self.tree[y] = x

        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    def has_same_parent(self, x, y):
        return self.find(x) == self.find(y)


class Edge(object):

    def __init__(self, src, dst, cost):
        self.src = src
        self.dst = dst
        self.cost = cost


def mst_kruskal():
    """
    kruskalのアルゴリズムによって最小全域木を構成する。

    :return: 最小全域木、つまりMSTに含まれる辺のリスト
    """
    pass


N = int(input())
V = list()
for i in range(N):
    x, y = map(int, input().split())
    V.append((i, x, y))

# グラフがx, yの格子のみなので、全ての頂点をそれぞれx座標についてy座標についてソートした列で隣接する2点の張る辺だけを考えれば良い
edges = list()
V.sort(key=lambda v: v[1])
for i in range(1, N):
    (src_i, src_x, src_y), (dst_i, dst_x, dst_y) = V[i - 1], V[i]
    heappush(edges, (abs(dst_x - src_x), src_i, dst_i))
V.sort(key=lambda v: v[2])
for i in range(1, N):
    (src_i, src_x, src_y), (dst_i, dst_x, dst_y) = V[i - 1], V[i]
    heappush(edges, (abs(dst_y - src_y), src_i, dst_i))

total_cost = 0
uf = UnionFind(N)
while len(edges) != 0:
    cost, src, dst = heappop(edges)
    if uf.find(src) != uf.find(dst):
        uf.unite(src, dst)
        total_cost += cost

print(total_cost)


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

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

int main(){
  cin.tie(nullptr);ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  int a,b,t;cin>>a>>b>>t;
  int cnt=a,ans=0;
  while(cnt<t+0.5){
    cnt+=a;
    ans+=b;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
def ddprint(x):
  if DBG:
    print(x)

n,k = inm()
if k>(n-1)*(n-2)//2:
    print(-1)
    exit()
print((n-1)*(n-2)//2 - k + n-1)
cnt = 0
print("{} {}".format(n-1,n))
for i in range(1,n-1):
    print("{} {}".format(i,n))
    for j in range(i+1,n):
        cnt += 1
        if cnt <= k:
            continue
        print("{} {}".format(i,j))


Measured memory_bytes: 3584
s = input()
if len(s)%2 == 0:
    first = s[:len(s)//2]
    last2 = s[len(s)//2:]
    last = last2[::-1]
    count = 0
    for i in range(len(first)):
        if first[i] != last[i]:
            count += 1
    print(count)
else:
    first = s[:(len(s)-1)//2]
    last2 = s[(len(s)-1)//2:]
    last = last2[::-1]
    count = 0
    for i in range(len(first)):
        if first[i] != last[i]:
            count += 1
    print(count)

Measured memory_bytes: 3064
#include<cassert>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<map>

using namespace std;
#define sz(x)(int)(x.size())
#define fi(a, b) for(int i=a;i<b;++i)
#define fj(a, b) for(int j=a;j<b;++k)
#define fk(a, b) for(int k=a;k<b;++j)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
////////////




void solve(){
	int n, a, b;
	string s;
	cin >> n >> a >> b;
	cin >> s;
	int j = 0, o = 0, c=0;
	
	fi(0, n){
		if(s[i] == 'c' ) {cout << "No" << endl; continue;}
		if(s[i] == 'a') {
			if(j + o < a + b) {cout << "Yes" << endl; ++j;}
			else cout << "No" << endl;
		}else{
			if(j + o < a + b && o < b) {cout << "Yes" << endl; ++o;}
			else cout << "No" << endl;
		}
	}
}

int main(){
#ifdef _DEBUG
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
#endif

	solve();

	return 0;
}

Measured memory_bytes: 896
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <math.h>
#include <vector>
#include <map>
#include <queue>
#include <utility>
#include <algorithm>
#include <string>
using namespace std;

int main() {
  int N;
  cin >> N;
  int sum = 0;
  int m   = 0;
  for (int i = 0; i < N; i++) {
	  int L;
	  cin >> L;
	  sum += L;
	  m    = max(m, L);
	}
  if (2 * m < sum) {
	  cout << "Yes" << endl;
	} else {
	  cout << "No" << endl;
	}
  return 0;
}


Measured memory_bytes: 256
n = gets.to_i
aryV = gets.split.map(&:to_i)
aryC = gets.split.map(&:to_i)

ans = 0
n.times do |i|
  if aryV[i] > aryC[i]
    ans += aryV[i] - aryC[i]
  end
end

puts ans


Measured memory_bytes: 1788
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.InputMismatchException;

public class Main {
	static InputStream is;
	static String INPUT = "";

	public static void main(String[] args) throws Exception
	{
		long S = System.currentTimeMillis();
		is = System.in;
		
		int n = ni();
		int M = 1000001;
		int W = (M>>>6)+1;
		long[] f1 = new long[W];
		long[] f2 = new long[W];
		long[] ex = new long[W];
		for(int i = 0;i < n;i++){
			int v = ni();
			if(f1[v>>>6]<<~v>=0){
				f1[v>>>6] |= 1L<<v;
				if(ex[v>>>6]<<~v>=0){
					for(int j = v*2;j < M;j+=v){
						ex[j>>>6] |= 1L<<j;
					}
				}
			}else{
				f2[v>>>6] |= 1L<<v;
			}
		}
		int ans = 0;
		for(int i = 0;i < W;i++){
			ans += Long.bitCount((f1[i]^f2[i])&~ex[i]);
		}
		System.out.println(ans);
		
		long G = System.currentTimeMillis();
		tr(G-S+"ms");
	}
	
	private static byte[] inbuf = new byte[1024];
	static int lenbuf = 0, ptrbuf = 0;
	
	private static int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
//	private static boolean isSpaceChar(int c) { return !(c >= 32 && c <= 126); }
	private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private static double nd() { return Double.parseDouble(ns()); }
	private static char nc() { return (char)skip(); }
	
	private static String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private static char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private static char[][] nm(int n, int m)
	{
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}
	
	private static int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	
	private static int ni()
	{
		int num = 0, b;
//		boolean minus = false;
//		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
//		if(b == '-'){
//			minus = true;
//			b = readByte();
//		}
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9')));
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return num;
//				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}


Measured memory_bytes: 37116
#include "bits/stdc++.h"
#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
typedef long long ll;
typedef unsigned long long ull;
const ull INF = 1e18;
using namespace std;

int main(){
    int x,n,tmp,ans=200;
    cin>>x>>n;
    bool lst[102];
    rep(i,0,102)
        lst[i]=true;
    rep(i,0,n){
        cin>>tmp;
        lst[tmp]=false;
    }
    rep(i,0,102){
        if(lst[i]){
            if(abs(ans-x)>abs(i-x)){
               ans=i; 
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3632
#include<string>
#include<iostream>

#define	rep(i,n)	for(int i=0;i<n;i++)

using namespace std;

char ope;

string parse(string tr1,string tr2){
	int len1=tr1.length(),len2=tr2.length();

	string lhs1,rhs1;
	int pcnt=0;
	rep(i,len1){
		if(tr1[i]=='(')	pcnt++;
		if(tr1[i]==')')	pcnt--;
		if(tr1[i]==',' && pcnt==1){
			lhs1=tr1.substr(1,i-1);
			rhs1=tr1.substr(i+1,len1-i-2);
			break;
		}
	}

	string lhs2,rhs2;
	pcnt=0;
	rep(i,len2){
		if(tr2[i]=='(')	pcnt++;
		if(tr2[i]==')')	pcnt--;
		if(tr2[i]==',' && pcnt==1){
			lhs2=tr2.substr(1,i-1);
			rhs2=tr2.substr(i+1,len2-i-2);
			break;
		}
	}

	string lhs,rhs;
	if(ope=='i'){	// intersection
		if(lhs1!="" && lhs2!="")	lhs=parse(lhs1,lhs2);
		if(rhs1!="" && rhs2!="")	rhs=parse(rhs1,rhs2);
	}
	else{			// union
		if(lhs1!="" || lhs2!="")	lhs=parse(lhs1,lhs2);
		if(rhs1!="" || rhs2!="")	rhs=parse(rhs1,rhs2);
	}

	return '('+lhs+','+rhs+')';
}

int main(){
	for(string tr1,tr2;cin>>ope>>tr1>>tr2;)	cout<<parse(tr1,tr2)<<endl;
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define pi 3.141592653589793
#define debug(x) cout << #x << " = " << x << '\n';
using namespace std;



int main() {
    cout << fixed << setprecision(10);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    int n;
    string s;
    cin >> n >> s;
    int ans = 0;
    for (int i = 0; i < n - 2; i++) {
        if (s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C') ++ans;
    }
    cout << ans;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(...) cerr << "[(" << __LINE__ << ") " << (#__VA_ARGS__) << "]: " << __VA_ARGS__ << endl;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    int m, n;
    cin >> n >> m;

    int a[n];
    ll sm = 0;
    for (int i=0; i<n; i++) {
        cin >> a[i];
        sm += a[i];
    }
    int li = ceil(sm/(4.0*m)); 
    int cnt = 0;
    for (auto e: a) {
        if (e >= li) cnt++;
    }
    cout << (cnt < m ? "No" : "Yes") << "\n";
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/**
 * @author Pavel Mavrin
 */
public class Main {

    private void solve() throws IOException {
        int n = nextInt();
        int x = 0;
        int y = 0;
        int t = 0;
        for (int i = 0; i < n; i++) {
            int tt = nextInt();
            int xx = nextInt();
            int yy = nextInt();
            int d = Math.abs(x - xx) + Math.abs(y - yy);
            if (tt < t + d || (xx + yy) % 2 != tt % 2) {
                out.println("No");
                return;
            }
            x = xx;
            y = yy;
            t = tt;
        }
        out.println("Yes");
    }

    // ------------------

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    PrintWriter out = new PrintWriter(System.out);

    String next() throws IOException {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(br.readLine());
        }
        return st.nextToken();
    }

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

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

    private void run() throws IOException {
        solve();
        out.close();
    }

}


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

struct strc{
    int val1;
    int key;

    strc(int v1,int k){
        val1=v1;
        key=k;
    }
};

bool cmp(const strc &a,const strc &b){
    return a.key<b.key;
}


int main(){
    int flag=1;
    int n = 0;
    int a,b,t=0;;
    cin >> n;
    vector<strc> tasks;
    for (int i = 0; i < n; i++){
        cin >>a>>b;
        strc task(a,b);
        tasks.push_back(task);
    }

    sort(tasks.begin(),tasks.end(),cmp);
    
    for (int i = 0; i < n; i++){
        t += tasks[i].val1;
        if(t > tasks[i].key)flag=0;
    }

    //cout <<fixed<<setprecision(16)<< << endl;
    //cout << ans << endl;

    if(flag==1)cout << "Yes" <<endl;
    else cout << "No" <<endl;
    
    return 0;
}


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

#define reps(v, f, l) for (int v = (f), v##_ = (l); v < v##_; ++v)
#define rep(v, n) reps(v, 0, n)
#define lep(v, n) reps(v, 1, n + 1)
#define rreps(v, f, l) for (int v = (l), v##_ = (f); v >= v##_; --v)
#define rrep(v, n) rreps(v, 0, n - 1)
#define rlep(v, n) rreps(v, 1, n)
#define show_a(a, size) rep(a##_it, size) std::cout << a[a##_it] << " \n"[a##_it == a##_it_ - 1];
#define show_v(v) show_a(v, v.size())
#define debug(x) std::cerr << #x << " = " << (x) << "\n";

using namespace std;

typedef long long int lint;

static inline int in(){ int x; scanf("%d", &x); return x; }
static inline lint inl(){ lint x; scanf("%lld", &x); return x; }

int main()
{
  int n, m;
  while (n = in()){
    m = in();
    string ioi;
    cin >> ioi;
    vector<int> count(m, 0);
    count[0] = 1;
    rep(i, m){
      if (i == 0) continue;
      if (ioi[i] != ioi[i - 1]){
        count[i] = count[i - 1] + 1;
      }
      else {
        count[i] = 1;
      }
    }
    int ans = 0;
    rep(i, m){
      if (ioi[i] == 'I' && count[i] >= 2 * n + 1) ans++;
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 6020
import java.util.Scanner;

public class Main{
		
	public static void main(String args[]){
		  
	    Scanner sc = new Scanner(System.in);
	    
	    String s = sc.next();
	    
	    String out = "";
	    
	    for (int i = 0; i < s.length(); i++) {
			if(s.charAt(i) == ',')	out += " ";
			else	out += s.charAt(i);
		}
	    
	    System.out.println(out);
	}
}

Measured memory_bytes: 22612
s = int(input())
an = [s]
for i in range(1, 1000000):
    if an[i-1]%2==0:
        ins = an[i-1]//2
    else:
        ins = 3*an[i-1]+1

    if ins not in an:
        an.append(ins)
    else:
        print(i+1)
        exit()


Measured memory_bytes: 8968
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
const int N=200010;
ll s[N],ans=1ll<<60;
int a[N],n;
void upd(int a,int b,int c){
    ll tp[5];
    tp[1]=s[a];
    tp[2]=s[b]-s[a];
    tp[3]=s[c]-s[b];
    tp[4]=s[n]-s[c];
    sort(tp+1,tp+5);
    ans=min(ans,tp[4]-tp[1]);
}
int getp(int l,int r){
    int lb=l,rb=r-1,mid;
    while(rb-lb>1){
        mid=lb+rb>>1;
        if((s[mid]-s[l-1])*2<=s[r]-s[l-1]) lb=mid;
        else rb=mid;
    }
    return lb;
}
int main(){
    int i,x,y;
    scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%d",&a[i]),s[i]=s[i-1]+a[i];
    for(i=2;i<=n-2;i++){
        x=getp(1,i);
        y=getp(i+1,n);
        upd(x,i,y);
        upd(x,i,y+1);
        upd(x+1,i,y);
        upd(x+1,i,y+1);
    }
    printf("%lld\n",ans);
    return 0;
}


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

int main(){
    string S,T;
    cin>>S>>T;
    int count=0;
    rep(i, S.length()){
        if(S[i]!=T[i])count++;
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 3916
n = int(input())
A = list(map(int, input().split()))
A.sort()

while(len(A) > 1):
    v = A[0]
    for i in range(1, len(A)):
        A[i] = A[i] % v
    for _ in range(A.count(0)):
        A.remove(0)
    A.sort()
print(A[0])


Measured memory_bytes: 14224
from functools import lru_cache
import sys
sys.setrecursionlimit(10**7)

n,m,*l=map(int,open(0).read().split())
graph=[[]*n for _ in range(n)]
unvis=[True]*n

@lru_cache(maxsize=None)
def dfs(x):
	for y in graph[x]:
		if unvis[y]:
			unvis[y]=False
			dfs(y)
			
for i,j in zip(l[::3],l[1::3]):
	graph[i-1].append(j-1)
	graph[j-1].append(i-1)

ans=0
for x in range(n):
	if unvis[x]:
		unvis[x]=False
		dfs(x)
		ans+=1
print(ans)


Measured memory_bytes: 291544
import math
n = int(input())
s = []
s = input().split()
s = list(map(int,s))
q = int(input())
t = []
t = input().split()
t = list(map(int,t))
cnt = 0

def binalySearch(s,key):
    first = 0
    last = n
    while first < last:
        dist = math.floor((last + first)/2)
        if s[dist] == key:
            return 1
        elif key < s[dist]:
            last = dist
        else:
            first = dist + 1
    return 0

for i in range(q):
    cnt = cnt + binalySearch(s,t[i])


print(cnt)
    



Measured memory_bytes: 16768
/*
AuThOr Gwj
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define KEEP while(1)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define debug_pair(A) cerr<<A.FIR<<" "<<A.SEC<<endl;
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
typedef pair<mp,mp> superpair;
LL n,s,a[3003];
LL f[3003][3003];
const int MOD=998244353;
int main(){
	fastio;
	cin>>n>>s;
	rb(i,1,n)
		cin>>a[i];
	f[0][0]=1;
	rb(i,1,n){
		rb(j,0,s){
			f[i][j]=f[i-1][j]*2;
			f[i][j]%=MOD;
			if(j>=a[i]){
				f[i][j]+=f[i-1][j-a[i]];
				f[i][j]%=MOD;
			}
		}
	}
	cout<<f[n][s]<<endl;
	return 0;
}


Measured memory_bytes: 74056
#include<stdio.h>
#include<stdlib.h>
int l[200005], r[200005];
long long int d[200005];
int asc1(const void* a, const void* b)
{
	if (l[*(int*)a] > l[*(int*)b])return 1;
	if (l[*(int*)a] < l[*(int*)b])return -1;
	if (r[*(int*)a] > r[*(int*)b])return 1;
	if (r[*(int*)a] < r[*(int*)b])return -1;
	if (d[*(int*)a] > d[*(int*)b])return 1;
	if (d[*(int*)a] < d[*(int*)b])return -1;
	return 0;
}
int asc2(const void* a, const void* b)
{
	if (r[*(int*)a] > r[*(int*)b])return 1;
	if (r[*(int*)a] < r[*(int*)b])return -1;
	if (l[*(int*)a] > l[*(int*)b])return 1;
	if (l[*(int*)a] < l[*(int*)b])return -1;
	if (d[*(int*)a] > d[*(int*)b])return 1;
	if (d[*(int*)a] < d[*(int*)b])return -1;
	return 0;
}
int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	int i;
	for (i = 0; i < m; i++)
		scanf("%d %d %lld", &l[i], &r[i], &d[i]);
	int p[200005], q[200005];
	for (i = 0; i < m; i++)
		p[i] = q[i] = i;
	qsort(p, m, sizeof(int), asc1);
	qsort(q, m, sizeof(int), asc2);
	long long int x[100005];
	int check[200005];
	for (i = 0; i < m; i++)
		check[i] = 0;
	int kakutei[100005];
	for (i = 0; i < n; i++)
		kakutei[i + 1] = 0;
	int visited[100005];
	for (i = 0; i < n; i++)
		visited[i + 1] = 0;
	int min, max, mid;
	int count = 0;
	int w[200005];
	int ll = 0;
	int people;
	while (count < m)
	{
		i = 0;
		while (check[i] > 0)
			i++;
		x[l[i]] = 0;
		x[r[i]] = d[i];
		kakutei[r[i]] = 1;
		kakutei[l[i]] = 1;
		w[ll] = r[i];
		w[ll + 1] = l[i];
		ll = 2;
		check[i] = 1;
		count++;
		while (ll > 0)
		{
			ll--;
			people = w[ll];
			if (visited[people] > 0)
				continue;
			visited[people] = 1;
			min = 0;
			max = m;
			while (max - min > 1)
			{
				mid = (max + min) / 2;
				if (l[p[mid]] < people)
					min = mid;
				else
					max = mid;
			}
			if (l[p[min]] != people)
				min++;
			if (min < m)
			{
				while (l[p[min]] == people)
				{
					if (check[p[min]] > 0)
					{
						min++;
						if (min == m)
							break;
						continue;
					}
					check[p[min]] = 1;
					count++;
					if (kakutei[r[p[min]]] > 0)
					{
						if (x[l[p[min]]] + d[p[min]] != x[r[p[min]]])
						{
							printf("No\n");
							return 0;
						}
					}
					else
					{
						kakutei[r[p[min]]] = 1;
						x[r[p[min]]] = x[l[p[min]]] + d[p[min]];
						w[ll] = r[p[min]];
						ll++;
					}
					min++;
					if (min == m)
						break;
				}
			}
			min = 0;
			max = m;
			while (max - min > 1)
			{
				mid = (max + min) / 2;
				if (r[q[mid]] < people)
					min = mid;
				else
					max = mid;
			}
			if (r[q[min]] != people)
				min++;
			if (min < m)
			{
				while (r[q[min]] == people)
				{
					if (check[q[min]] > 0)
					{
						min++;
						if (min == m)
							break;
						continue;
					}
					check[q[min]] = 1;
					count++;
					if (kakutei[l[q[min]]] > 0)
					{
						if (x[l[q[min]]] + d[q[min]] != x[r[q[min]]])
						{
							printf("No\n");
							return 0;
						}
					}
					else
					{
						kakutei[l[q[min]]] = 1;
						x[l[q[min]]] = x[r[q[min]]] - d[q[min]];
						w[ll] = l[q[min]];
						ll++;
					}
					min++;
					if (min == m)
						break;
				}
			}
		}
	}
	printf("Yes\n");
	return 0;
}

Measured memory_bytes: 8428
#include <iostream>
#include <iomanip>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <tuple>
#include <vector>
#include <map>
#include <unordered_map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#define MP(a, b) make_pair(a, b)
#define POWER9 1000000000
#define MOD POWER9+7
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483647
#define INT_MAX 2147483647
#define LL_MIN (LL)-9223372036854775807
#define LL_MAX (LL)9223372036854775807
#define PI 3.14159265359

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << setprecision(9);
	
	int N;
	cin >> N;
	vector<int> A,B,C;
	for(int i=0; i<N; i++){
		int tmp;
		cin >> tmp;
		A.push_back(tmp);
	}
	for(int i=0; i<N; i++){
		int tmp;
		cin >> tmp;
		B.push_back(tmp);
	}
	for(int i=0; i<N; i++){
		int tmp;
		cin >> tmp;
		C.push_back(tmp);
	}
	sort(A.begin(), A.end());
	sort(B.begin(), B.end());
	sort(C.begin(), C.end());

	LL ans = 0;
	vector<int> B2;
	for(int i=0; i<N; i++){
		auto itr = upper_bound(C.begin(), C.end(), B[i]);
		B2.push_back(N-(itr-C.begin()));
		//cout << B2[i] << endl;
	}
	vector<LL> Bwa;
	for(int i=0; i<N; i++) Bwa.push_back(0);
	Bwa[N-1] = B2[N-1];
	for(int i=N-2; i>=0; i--){
		Bwa[i] = Bwa[i+1] + B2[i];
	}
	//for(int i=0; i<N; i++) cout << Bwa[i] << endl;
	for(int i=0; i<N; i++){
		auto itr = upper_bound(B.begin(), B.end(), A[i]);
		if(itr == B.end()) continue;
		int j = itr-B.begin();
		ans += Bwa[j];
	}
	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 2936
/*
g++ -std=c++11 -Wall -O2 -o main.exe main.cpp
./main.exe
*/

#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <climits>
//intの最大値: INT_MAX
//longの最大値: LONG_MAX
//long longの最大値: LLONG_MAX
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <map>
#include <functional>
#include <algorithm>
#include <complex>
#include <numeric>
#include <queue>
#include <stack>
#include <tuple>
//最大公約数: gcd()
//最小公倍数: lcm()

#define ll long long int

using namespace std;

template <typename T>
void sortasc(vector<T> &v){ //vectorを昇順にソート
    sort(v.begin(), v.end(), std::less<T>());
    return;
}

template <typename T>
void sortdesc(vector<T> &v){ //vectorを降順にソート
    sort(v.begin(), v.end(), std::greater<T>());
    return;
}

//------------------------------------------------------------------------------

const double PI=3.14159265358979323846;

int main(){
	double a, b, h, m, hrad, mrad;
	cin >> a >> b >> h >> m;
	hrad = h * (PI / 6.0) + m * (PI / 360.0);
	mrad = m * (PI / 30.0);

	double x = abs(a * sin(hrad) - b * sin(mrad));
	double y = abs(a * cos(hrad) - b * cos(mrad));

	cout << std::setprecision(15) << sqrt(x*x + y*y) << endl;
}


Measured memory_bytes: 4128
# include<bits/stdc++.h>
using namespace std;
#define tmprep(i,n) for(int i=2;i<=(int)n;i++)
#define rep(i,n) for(int i=1;i<=(int)n;i++)
typedef long long ll;
unordered_map<ll,char> mp;

int main(){
  ll N;
  cin >> N;
  ll a[N+10];
  rep(i,N) cin >> a[i];
  
  ll S=0;
  rep(i,N) S ^= a[i];
  
  rep(i,N){
    ll ans = S^a[i];
    cout << ans << ' ';
  }
  
  return 0;
}

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

int main()
{
    int n;
    cin >> n;
    vector<int> p(n);
    rep(i,n) cin >> p[i];
    int ans = 0;
    for(int i=1; i<p.size()-1; i++){
        if((p[i-1]-p[i])*(p[i+1]-p[i])<0) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <math.h>

using namespace std;

int main() {
	int n, t, a, minNum;
	double h[1000], min;
	cin >> n >> t >> a;
	for (int i = 0; i < n; i++) {
		cin >> h[i];
		h[i] = a - (t - h[i] * 0.006);
		if (h[i] < 0) {
			h[i] *= -1;
		}
	}
	min = h[0];
	minNum = 0;
	for (int i = 1; i < n; i++) {
		if (min > h[i]) {
			min = h[i];
			minNum = i;
		}
	}
	cout << minNum + 1 << endl;

	return 0;
}

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

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <fstream>
#include <functional>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

#define ll long long int
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define REP(i, n) for(int i=0;i<n;++i)
#define FOREACH(x, a) for(auto& (x) : (a))
#define ALL(a) (a).begin(),(a).end()
#define COUT(x) out << (x) << endl;
#define M0(x) memset(x,0,sizeof(x))
#define MINF(x) memset(x,0x3f,sizeof(x))
#define MMINUS(a) memset(a,0xff,sizeof(a))

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

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

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

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

using namespace std;

class BOrdinaryNumber {
public:
    int N;
    int p[100]{0};
    int ans = 0;

    void solve(std::istream& in, std::ostream& out) {
        in >> N;
        REP(i, N) in >> p[i];
        for (int i = 1; i < N-1; i++) {
            if (p[i-1] < p[i] && p[i] < p[i+1]) ans++;
            if (p[i-1] > p[i] && p[i] > p[i+1]) ans++;
        }
        COUT(ans);
    }
};


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


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include <iomanip>
#define rep(i,n) for(int i=0;i<(n);++i)
using ll = long long;
#define _GLIBCXX_DEBUG

using namespace std;



int main() {
    int n, k;
    cin >> n >> k;
    int total = 0;
    vector<int>v(n);
    int number = 0;
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        v[i]++;
    }
    int mx = 0;
    int s = 0;
    queue<int> q;
    for (int i = 0; i < n; i++) {
        s += v[i];
        q.push(v[i]);
        if (q.size()>=k) {
            mx = max(mx, s);
            s -= q.front();
            q.pop();
        }
    }
    double ans = double(mx)/2;
    printf("%.10f\n", ans);
}



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

using namespace std;

int n;

void f(string s) {
  int len = (int)s.size();
  if (len < n) {
    char mx = 'a';
    for (int i = 0; i < len; i++) {
      mx = max(mx, s[i]);
    }
    for (char c = 'a'; c <= mx + 1; c++) {
      f(s + c);
    }
  } else {
    cout << s << '\n';
  }
  return;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  f("a");
  return 0;
}

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

#define ll long long

ll k,n,a[200002],ans;

int main()
{
//    freopen("a.in","r",stdin);
    cin>>k>>n>>a[0];
    for(ll i=1;i<n;i++)
    {
        cin>>a[i];
        ans=max(ans,a[i]-a[i-1]);
    }
    ans=max(ans,k-a[n-1]+a[0]);
    cout<<k-ans;

}




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

namespace abc052
{
    public class Program
    {
        public static void Main(string[] args)
        {
            int n = Convert.ToInt32(Console.ReadLine());
            string s = Console.ReadLine();
            int x = 0;
            int max = 0;

            for (int i = 0; i < s.Length; i++)
            {
                if (s[i] == 'I')
                {
                    x++;
                }
                else if(s[i]=='D')
                {
                    x--;
                }

                if (max < x)
                {
                    max = x;
                }
            }

            Console.WriteLine(max.ToString());

        }
    }
}


Measured memory_bytes: 2776
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define pi acos(-1.0)
const ll INF = 1LL<<61;
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
ll jou(ll N, ll P){if(P==0) return 1;
  if(P%2==0){ll t = jou(N, P/2);return t*t % mod;
  }return (N * jou(N, P-1)) % mod;}  //jou(n,mod-2)で逆元
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'大文字'+=32;    で小文字に
//  cout << fixed << setprecision (20);   小数点以下2０桁まで
//実行時間制約2秒では２×10^8回くらいまで計算できる




int main() {
  int n;
  cin>>n;
  
  ll ans=0;

  vector<ll> p(n);
  vector<ll> q(n);  
  rep(i,n){
    cin>>p[i]>>q[i];
  }

  for(int i=n-1;i>=0;i--){
    ll x = q[i]-1-(p[i]+ans+q[i]-1)%q[i];
    ans+=x;
  }

  cout << ans << endl;

}



Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,a,b;
int main(){
	cin>>n;
	while (n--){
		char ch=getchar();
		while (ch!='B'&&ch!='R') ch=getchar();
		if (ch=='B') a++;else b++;
	}
	if (b>a) puts("Yes");else puts("No");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define mset(x,y) memset(x,y,sizeof(x))
#define rep(i,n) for(int i=0;i<int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
#ifdef LOCAL
#define dmp(...) _dmp(#__VA_ARGS__, __VA_ARGS__)
#else
#define dmp(...) (__VA_ARGS__)
#endif
template<class T> using vt=vector<T>;
template<class T> using vvt=vt<vt<T>>;
template<class TA,class TB> void chmax(TA&a,TB b){if(a<b)a=b;}
template<class TA,class TB> void chmin(TA&a,TB b){if(b<a)a=b;}
template<class TA,class TB>
ostream& operator<<(ostream& os,const pair<TA,TB>& p){
	return os<<"{"<<p.fi<<","<<p.se<<"}";
}
template<class T> ostream& operator<<(ostream& os,const vt<T>& v){
	os<<"{";for(auto& e:v)os<<e<<",";return os<<"}";
}
template<class TH> void _dmp(const char *sdbg, TH h){cout<<sdbg<<"="<<h<<endl;}
template<class TH, class... TA> void _dmp(const char *sdbg, TH h, TA...a){
while(*sdbg!=',')cout<<*sdbg++;cout<<"="<<h<<","; _dmp(sdbg+1, a...);
}
template<class T> void make_unique(vt<T>& v) {
	sort(all(v));v.erase(unique(all(v)),v.end());
}
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
int ri(){int x;cin>>x;return x;}
ll rll(){ll x;cin>>x;return x;}
vi rvi(int n){vi v;rep(i,n)v.pb(ri());return v;}
ll n;
vt<ll> fact(ll n) {
	vt<ll> v;
	for(ll i=2;i*i<=n;i++) {
		if(n%i==0) {
			v.pb(i);
			if(n/i!=i)v.pb(n/i);
		}
	}
	if(n>1)v.pb(n);
	sort(all(v));
	return v;
}
void MAIN() {
	cin>>n;
	vt<ll> v1=fact(n);
	vt<ll> v2=fact(n-1);
	ll cnt=0;
	for(auto& it:v1) {
		ll t=n;
		while(t%it==0)t/=it;
		if(t%it==1)cnt++;
	}
	cout<<sz(v2)+cnt;
}
int main() {
	ios::sync_with_stdio(false);cin.tie(0);
	int T=1;
	//cin>>T;
	for(int tt=1;tt<=T;tt++) {
		MAIN();
	}
	return 0;
}

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

using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for (ll i = (ll)(n) - 1; i >= 0; i--)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1LL << 62)

#define PI (acos(-1))
#define print(x) cout << x << endl
 
ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll countDigit(ll n) { return floor(log10(n) + 1); } 
typedef pair <ll,ll> P;
static const ll dy[4] = {0,1,0,-1}, dx[4] = {1,0,-1,0};

template <typename T> 
ostream& operator<<(ostream& os, const vector<T>& v) 
{ 
    for (int i = 0; i < (int)v.size(); ++i) { 
        os << v[i]; 
        if (i != (int)v.size() - 1) 
            os << " "; 
    } 
    return os; 
} 

int main()
{
    string S,T;
    cin >> S >> T;
    ll A, B;
    cin >> A >> B;
    string U;
    cin >> U;
    if (S == U) {
        print(A-1 << " " << B);
    } else {
        print(A << " " << B-1);
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>

using namespace std;
using ll = long long int;
#define rep(i,n) for(int i = 0; i < n; i++)
#define FOR(i, a, b)  for(int i = (a); i < (b) ; i++)

#define pb push_back
#define SORT(v,n) sort(v, v+n)
#define ALL(x) (x).begin(),(x).end()
#define debug(x) cerr << #x << ": " << x << '\n'
#define elif else if
#define itn ll
#define int ll
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
///                →,↑,←,↓,↗,↖,↙,↘
int dx[8] = { 1, 0, -1, 0, 1, -1, -1, 1 };
int dy[8] = { 0, 1, 0, -1, 1, 1, -1, -1 };

int h[1010];

int M[110][110];

signed main() {
	ios::sync_with_stdio(false);
	int i, n;
	cin >> n;
	rep(i, n) {
		int u, k;
		cin >> u >> k;
		int j;
		rep(j, k) {
			int v;
			cin >> v;
			M[u][v] = 1;
		}
	}

	rep(i, n) {
		int j;
		rep(j,n){
			if (j) cout << ' ';
			cout << M[i + 1][j + 1];
		}
		cout << endl;
	}
	return 0;
}


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

using namespace std;

#define forn(i, n) for (ll i = 0; i < (ll) (n); ++i)
#define sz(a) static_cast<int>((a).size())
#define pb emplace_back
#define mp make_pair
#define endl '\n'
#define f first
#define s second

#ifdef SEREZHKA
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(...)
#endif

template<typename T>
void _dbg(const char* _s, T _h) { cerr << _s << " = " << _h << "\n"; }

template<typename T, typename... Ts>
void _dbg(const char*_s, T _h, Ts... _t) {
    int _b = 0;
    
    while (((_b += *_s == '(') -= *_s == ')') != 0 || *_s != ',')
        cerr << *_s++;
    
    cerr << " = " << _h << ",";
    _dbg(_s + 1, _t...);
}

using ll = long long;

const ll INF = static_cast<ll>(1e9) + 7ll;
const ll LINF = INF * INF;
const int MAXN = static_cast<int>(3e3) + 17;

int n;
long double p[MAXN];
long double dp[MAXN][MAXN];

bool read() {
    if (!(cin >> n))
        return false;

    forn (i, n)
        cin >> p[i + 1];

    return true;
}

void solve() {
    dp[0][0] = 1;

    for (int i = 1; i <= n; ++i) {
        dp[i][0] = (1 - p[i]) * dp[i - 1][0];

        for (int j = 1; j <= i; ++j)
            dp[i][j] = p[i] * dp[i - 1][j - 1] + (1 - p[i]) * dp[i - 1][j];
    }

    long double res = 0;

    for (int i = n / 2 + 1; i <= n; ++i)
        res += dp[n][i];

    cout << setprecision(10) << fixed << res << endl;
}

int main() {
    cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    
#ifdef SEREZHKA
    freopen("file.in", "r", stdin);
#endif
    
    while (read())
        solve();
    
    return 0;
}



Measured memory_bytes: 139904
#include<bits/stdc++.h>
using namespace std;
#define M 1000000007
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define gcd __gcd
#define in(a) scanf("%d",&a)
#define in2(a,b) scanf("%d%d",&a,&b)
#define in3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define read(v,i,n) for(i=0;i<n;i++)in(v[i])
#define twod(mat,i,j,n,m) rep(i,n){rep(j,m)in(mat[i][j]);}
#define sc(ch) scanf("%c",&ch)
#define sstr(str) scanf("%s",str)
#define pr(n) printf("%d ",n)
#define out(n) printf("%d\n",n)
#define inl(a) cin >> a
#define prl(a) cout << a << " "
#define outl(a) cout << a << endl
#define yes printf("YES\n")
#define no printf("NO\n")
#define lin printf("\n")
#define dbg(v,i,n) for(i=0;i<n;i++)pr(v[i]); lin
#define ck printf("continue\n")
#define all(vec) vec.begin(),vec.end()
#define asc(vec) sort(vec.begin(),vec.end())
#define lower(v,k) lower_bound(v.begin(),v.end(),k)-v.begin()
#define upper(v,k) upper_bound(v.begin(),v.end(),k)-v.begin()
#define tf(mytuple) get<0>(mytuple)
#define ts(mytuple) get<1>(mytuple)
#define tt(mytuple) get<2>(mytuple)
#define tddd tuple<double,double,double>
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int> >
#define vvi vector<vector<int> >
#define viii vector<pair<pair<int,int>,int > >
#define vvii vector<vector<pair<int,int> > >
#define lp(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) for(i=0;i<n;i++)
#define N 10005
typedef long long int ll;
ll dp[2][N];
int a,b;
bool cmp(pair<ii,int> A,pair<ii,int> B)
{
        return min(A.F.S,B.F.S-A.F.F)>min(B.F.S,A.F.S-B.F.F);
}
int main()
{
    int i,j,n,w,c,v;
    int C=0;
    in(n);
    viii ad(n);
    rep(i,n)
    {
        in3(w,c,v);
        C=max(C,c);
        ad[i]={{w,c},v};
    }
    sort(all(ad),cmp);
    int a=0,b=1;
    ll x,ans=0;
    rep(i,n)
    {
        w=ad[i].F.F,c=ad[i].F.S,v=ad[i].S;
        x=0;
        rep(j,c+1)
            x=max(x,dp[a][j]);
        ans=max(ans,x+v);
        rep(j,C+1)
            if(j>=w && j<=c+w)dp[b][j]=max(dp[b][j],v+dp[a][j-w]);
        rep(j,C+1)
            dp[a][j]=dp[b][j];
    }
    outl(ans);
}








Measured memory_bytes: 384
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n,m = myinput()
abc = mylistinput(m)

for i in range(m):
    a = abc[i][0] - 1
    b = abc[i][1] - 1
    c = -1 * abc[i][2]
    abc[i][0] = a
    abc[i][1] = b
    abc[i][2] = c
# print(abc)

# def BellmanFord(edges,num_v,source):
#     #グラフの初期化
#     inf = float("inf")
#     dist = [ inf for i in range(num_v) ]
#     dist[source] = 0
#     #辺の緩和
#     for i in range(num_v):
#         for edge in edges:
#             if edge[0]!=inf and dist[edge[1]]>(dist[edge[0]]+edge[2]):
#                 dist[edge[1]] = dist[edge[0]] + edge[2]
#                 if i==(num_v-1):
#                     return False,[]
#     return True,dist

# sからiへの最短距離を求める（Bellman-Ford法）
# s:始点，n:頂点数，w:辺の数，es[i]:[辺の始点,辺の終点,辺のコスト]
def BellmanFord(s,n,w,es):
    # 初期化
    d = [float("inf")]*n
    d[s] = 0
    # 更新
    for i in range(n):
        # update = False
        for p,q,r in es:
            # [p,q,r] = [from, to, cost]
            if d[p]!=float("inf") and d[q]>(d[p]+r):
                d[q] = d[p] + r
                # update = True
                if i==(n-1) and q==(n-1):
                    return False,[]
        # if update:
        #     pass
        # else:
        #     break
    return True,d

# def find_negative_loop(s,n,w,es):
#     #負の経路の検出
#     #n:頂点数, w:辺の数, es[i]:[辺の始点,辺の終点,辺のコスト]
#     d = [float("inf")] * n
#     d[s] = 0
#     #この始点はどこでもよい <----よくない
#     for i in range(n):
#         for j in range(w):
#             e = es[j]
#             if d[e[1]] > d[e[0]] + e[2]:
#                 d[e[1]] = d[e[0]] + e[2]
#                 if i==(n-1):
#                     return True
#     return False

flag,distance = BellmanFord(0,n,m,abc)
if flag:
    print(-1*distance[n-1])
else:
    print("inf")

Measured memory_bytes: 45784
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int n=0;

void maxHeapify(int node[],int i){
  int l =2*i;
  int r = 2*i+1;
  int largest;
  int temp;

  if(l <= n && node[l] > node[i]){
    largest =l;
  }
  else{
    largest = i;
  }
  if(r <= n && node[r] > node[largest]){
    largest = r; 
  }
  if(largest != i){
    temp = node[i];
    node[i] = node[largest];
    node[largest] = temp;
    maxHeapify(node,largest);
  }
}

void buildMaxHeap(int node[]){
  int i;
  for(i=n/2;i>0;i--){
    maxHeapify(node,i);
  }
}

void heapIncreaseKey(int node[],int i,int k){
  int temp;
  if(k < node[i]){
    fprintf(stderr,"error\n");
  }
  node[i] = k;
  while(i >1 && node[i/2] < node[i]){
    temp = node[i];
    node[i] = node[i/2];
    node[i/2] = temp;
    i = i/2;
  }
}


void heapInsert(int node[],int k){
  n = n+1;
  node[n] = -10000000;
  heapIncreaseKey(node,n,k);
}

int heapExtractMax(int node[]){
  int max;
  if(n < 1){
    fprintf(stderr,"error\n");
  }
  max = node[1];
  node[1] = node[n];
  n = n-1;
  maxHeapify(node,1);
  return max;
}

int main(){
  int i,k,node[2000000];
  char s[20];

  while(1){
    scanf("%s",s);
    if(strcmp(s,"insert") == 0){
      scanf("%d",&k);
      heapInsert(node,k);
    }
    else if(strcmp(s,"extract") == 0){
      printf("%d\n",heapExtractMax(node));
    }
    else if(strcmp(s,"end")== 0){
      break;
    }
  }
  return 0;
}

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

using ll = long long;
using namespace std;

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

  for (int i = 0; i < min((ll)S.size(), K); ++i) {
    if (S[i]-'0' >= 2) {
      cout << S[i] << endl;
      return 0;
    }
  }

  cout << 1 << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 
  
#define ll long long
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
	enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
	ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
	*this << "[";
	for (auto it = d.b; it != d.e; ++it)
		*this << ", " + 2 * (it == d.b) << *it;
	ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

const int MOD = (int)1e9 + 7;
const int MX = (int)1e5 + 10;

void add_self(int &x, int y, int md = MOD){x += y; if(x >= md) x -= md;}
void sub_self(int &x, int y, int md = MOD){x -= y; if(x < 0) x += md;}
void mul_self(int &x, int y, int md = MOD){x = x * 1LL * y % md;}
inline int mul(int x, int y, int md = MOD){return x * 1LL * y % md;}
inline int add(int x, int y, int md = MOD){x += y; if(x >= md) x -= md; return x;}
inline int sub(int x, int y, int md = MOD){x -= y; if(x < 0) x += md; return x;}

void pre(){
}	


void solve(){
	string s;
	cin >> s;
	int rem = 0;
	for(auto &c : s){
		rem += (c - '0');
		rem %= 9;
	}
	cout << (rem == 0 ? "Yes" : "No") << "\n";
	return;
}

int main(){

	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(0);

	// freopen("input.in", "r", stdin);
	// freopen("output.out", "w", stdout);

	int t;
	t = 1;
	// cin >> t;
	// pre();
	for(int i = 1; i <= t; ++i){
		// cout << "Case #" << i << ": ";
		solve();
		// cout << '\n';
		// cout << endl;
	}

	return 0;
}


Measured memory_bytes: 3740
#include<stdio.h>
#define N 100

main(){

  int i,j,n,a[N],min,u=0,x;

  scanf("%d",&n);

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



  for(i=0;i<n;i++){
    min=i;
    for(j=i;j<n;j++){
      if(a[j]<a[min]){ 
	min=j;
      }    
    }
    if(i!=min){
    x=a[i];
    a[i]=a[min];
    a[min]=x;
    u++;
    }
  }


  for(i=0;i<n-1;i++){

      printf("%d ",a[i]);
 }
 printf("%d\n",a[n-1]);

 printf("%d\n",u);
 return 0;
}  

Measured memory_bytes: 600
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INF INT_MAX // 2147483647
#define INFLL LLONG_MAX // 9223372036854775807
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define per(i, n) for(ll i=((ll)(n))-1; i>=0; i--)
#define perf(i, n) for(ll i=((ll)(n)); i>0; i--)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
#define Init() std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout<<fixed<<setprecision(15);
template<class T>bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }
using namespace std;

ll repOp(ll dist, ll k){
    return ceil(1.0*dist/(k-1));
}

int main(){
    Init();
    ll n, k, pos, ans = INFLL; cin >> n >> k;
    vi a(n);

    // 入力処理
    rep(i, n){
        cin >> a[i];
        if(a[i] == 1) pos = i;
    }

    // nとkが等しいなら1回で終わる
    if(n == k) ans = 1;
    // nとkが等しくないなら、左右毎に何回操作が必要か計算する。
    else{
        // 始点のとり方をk通り試す
        for(ll i=0; i<k; i++){
            // i個kの枠を左にずらす考え方
            if(pos-i < 0 || pos+(k-1)-i > n-1) continue;
            
            ll tmp = 1 + repOp(abs(0-(pos-i)), k) + repOp(abs(n-1-(pos+(k-1)-i)), k);
            chmin(ans, tmp);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
using namespace std;

int main() {
    long long N;
    long long a[100000];
    long long ans = 0;

    cin >> N;

    for (long long i = 0; i < N; i++) {
        cin >> a[i];
    }

    for (long long i = 0; i < N; i++) {
        long long j;
        j = a[i]-1;
        if (i < j && a[j]-1 == i) {
            ans++;
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 1024
l,r=map(int,input().split())
ans=2018
for i in range(l,min(r,l+2019)):
    for j in range(i+1,min(r+1,i+2019)):
        a = (i*j) % 2019
        ans = min(ans,a)
        #print(i,j,ans)
print(ans)



Measured memory_bytes: 2940