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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define SP << " " 
#define LLi long long int

using namespace std;

void PV(vector<int> pvv) {
	rep(i, pvv.size()) cout << pvv[i] SP;
	cout << endl;
}

void PVL(vector<LLi> pvv) {
	rep(i, pvv.size()) cout << pvv[i] SP;
	cout << endl;
}

bool VV(vector<int> vv1, vector<int> vv2) {
	if(vv1.size()!=vv2.size()) return false;
	rep(i, vv1.size()) if(vv1[i]!=vv2[i]) return false;

	return true;
}

bool VVL(vector<LLi> vv1, vector<LLi> vv2) {
	if(vv1.size()!=vv2.size()) return false;
	rep(i, vv1.size()) if(vv1[i]!=vv2[i]) return false;

	return true;
}

//vecotr<LLi>の総和
LLi SML(vector<LLi> smv) {
	LLi tmp=0;
	rep(i, smv.size()) tmp+=smv[i];

	return tmp;
}

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
	vector<int> siz; // siz[i]:iの属する木に含まれる点の数

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
		siz.resize(par.size(), 1); //最初は全てサイズ1
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

	int tsize(int x){ // siz[x]の木の根を見に行き、サイズを返す
		if (par[x] == x) return siz[x];
		par[x] = root(par[x]);
		return tsize(par[x]);
	}

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
		siz[rx]+=siz[ry]; //根で管理
		siz[ry]=siz[rx]; //根で管理
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main(){

	int n, m, a, b, ma=0;
	cin>> n >> m;

	UnionFind uf(n);
	rep(i, m){
		cin>> a >> b;
		uf.unite(a-1, b-1);
	}

	rep(i, n) ma=max(ma, uf.tsize(i));

	cout<< ma <<endl;

	return 0;
}

Measured memory_bytes: 11044
(let* ((n (read))
       (a (make-array `(,(+ n 1)) :initial-element 0))
       (m 0)
       (dp)
       (c)
       (r 0))
  ;; read
  (loop :for i :from 1 :to n
        :do (setf (aref a i) (read)))
  ;;
  (setf a (sort a #'<))
  (setf m (* 2 (aref a (1- (length a)))))
  (setf dp (make-array `(,(1+ m)) :initial-element t))
  (setf c (make-array `(,(1+ m)) :initial-element nil))
  ;;
  (loop :for i :from 1 :to n
        :do (let ((x (aref a i)))
              (when (and (null (aref c x)) (aref dp x))
                (setf (aref c x) t)
                (loop :for y :from (* x 2) :upto m :by x
                      :do (setf (aref dp y) nil)))))
  ;;
  (loop :for i :from 1 :to n
        :if (and (or (= i n) (/= (aref a i) (aref a (1+ i))))
                 (or (= i 1) (/= (aref a (1- i)) (aref a i)))
                 (aref dp (aref a i)))
        :do (incf r))
  (format t "~A~%" r))


Measured memory_bytes: 108316
# include <stdio.h>

int main (void){
  int N, X, i, x = 0, k = 0;
  scanf("%d %d",&N,&X);
  int L[N];
  for(i = 0; i < N+1; i++)
    scanf("%d",&L[i]);
  for(i = 0; i< N+1;i++){
    
    if( x <= X)
      k++;
    
    x = x + L[i];
    
  }
  printf("%d",k);
  
  return 0;
}
    
    
  


Measured memory_bytes: 128
/* Manish Pant - insider_pants */

#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#include "debug.h"
#endif

#define F first
#define S second
#define endl "\n"
#define pb push_back
typedef long long ll;
typedef long double ldob;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int main()
{
    fast();
    int n, k; cin >> n >> k;
    vector<int> v;
    for(int i = 0; i < n; i++)
    {
        int a; cin >> a;
        v.pb(a);
    }
    sort(v.begin(), v.end());

    ll ans = 0;
    for(int i = 0; i < k; i++)
    {
        ans += v[i];
    }
    cout << ans << endl;
}

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

using namespace std;

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

#define MAX 100000
#define NIL -1
#define MOD 1000000007

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

#define debug(x) cout<<#x<<": "<<x<<endl
#define debig_vec(v) cout<<#v<<":";rep(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

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

#define print2D(h, w, arr) rep(i, h) { rep(j, w) cout << arr[i][j] << " "; cout << endl; }
template<class T> inline void print(const T& x){cout << setprecision(12) << x << endl;}
template<class T, class... A> inline void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const long long INF = 1LL<<60;

int main() {
    int n; cin >> n;
    n %= 1000;
    int ans = 1000 - n;
    print(ans%1000);
    return 0;
}


Measured memory_bytes: 3620
import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, core.bitop;

enum inf3 = 1_001_001_001;
enum inf6 = 1_001_001_001_001_001_001L;
enum mod = 1_000_000_007;

void main() {
    int n, x;
    scan(n, x);
    auto L = readln.split.to!(int[]);
    int p;
    int ans = 1;
    foreach (i ; 0 .. n) {
        p += L[i];
        if (p <= x) ans++;
    }
    writeln(ans);
}























int[][] readGraph(int n, int m, bool isUndirected = true, bool is1indexed = true) {
    auto adj = new int[][](n, 0);

    foreach (i; 0 .. m) {
        int u, v;
        scan(u, v);
        if (is1indexed) {
            u--, v--;
        }
        adj[u] ~= v;
        if (isUndirected) {
            adj[v] ~= u;
        }
    }

    return adj;
}

alias Edge = Tuple!(int, "to", int, "cost");

Edge[][] readWeightedGraph(int n, int m, bool isUndirected = true, bool is1indexed = true) {
    auto adj = new Edge[][](n, 0);

    foreach (i; 0 .. m) {
        int u, v, c;
        scan(u, v, c);
        if (is1indexed) {
            u--, v--;
        }
        adj[u] ~= Edge(v, c);
        if (isUndirected) {
            adj[v] ~= Edge(u, c);
        }
    }

    return adj;
}

void yes(bool b) {
    writeln(b ? "Yes" : "No");
}

void YES(bool b) {
    writeln(b ? "YES" : "NO");
}

T[] readArr(T)() {
    return readln.split.to!(T[]);
}

T[] readArrByLines(T)(int n) {
    return iota(n).map!(i => readln.chomp.to!T).array;
}

void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}

void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

bool chmin(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x > arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}

bool chmax(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x < arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}


Measured memory_bytes: 256
#include <set>
#include <array>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <vector>
#include <tuple>
#include <string>
#include <math.h>
#include <time.h>
#include <bitset>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <limits>
#include <climits>
#include <numeric>

#define lnd '\n'
// #define reverse(i, n) for(ll i = n-1; i >= 0; --i)
#define from(i, n) for (ll i = 0; i < n; ++i)
#define REPN(i, n) for (ll i = 1; i <= n; ++i)
#define ALL(s) (s).begin(), (s).end()
#define rALL(s) (s).rbegin(), (s).rend()
#define sz(s) (int)(s).size()
#define mk make_pair
#define pb push_back
#define sqr(s) ((s) * (s))

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int ui;

template <class T>
T GCD (T a, T b) {
  if(a == 0) return b;
  return GCD(b%a, a);
}

template <class T>
T modpow(T x, T p){
    T res = 1;
    while(p > 0){
        if(p&1) res *= x;
        x *= x;
        p /= 2;
    }
    return res;
}

template <class T>
void print(T a[], ll n){
    for (ll i = 0; i < n; i++) std::cout << a[i] << ' ';
    cout << endl;
}

template<class T>
void printc(T c){
    for(auto const& v: c) std::cout << v << ' ';
    cout << endl;
}

struct HASH{
  size_t operator()(const pair<long,long>&x)const{
    return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
  }
};

bool pair_sort(const pair<int, int> &p1, const pair<int,int> &p2){
    if(p1.first != p2.first) return p1.first < p2.first;
    else return p1.second < p2.second;
}

const int INF = std::numeric_limits<int>::max();
const ll M_INF = std::numeric_limits<ll>::min();

void solution();
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solution();
    return 0;
}

void solution(){
    ll A, B, m;
    cin >> A >> B >> m;
    vector<ll> a(A+1), b(B+1);
    ll am = 1e9;
    ll bm = 1e9;
    from(i, A) {
        cin >> a[i+1];
        am = min(am, a[i+1]);
    }
    from(i, B) {
        cin >> b[i+1];
        bm = min(bm, b[i+1]);
    }

    ll dcost = 1e9;
    from(i, m) {
        ll x1, y1, c1;
        cin >> x1 >> y1 >> c1;
        ll cur = a[x1] + b[y1]-c1;
        if(cur < dcost){
            dcost = cur;
        }
    }

    cout << min(am+bm, dcost) << endl;;
}   

Measured memory_bytes: 1792
n,m = map(int,input().split())
s_lst = [list(map(int,input().split())) for i in range(m)]
for i in range(m):
    del s_lst[i][0]
p_lst = list(map(int,input().split()))
answer = 0

for i in range(2**n): #各電球がonかoffかビット全探索
    on_lst =[0]*n
    flag = True
    for j in range(n):
        if (i>>j) & 1:
            on_lst[j] = 1
    for l in range(m): ##　一つ一つの電球について確認
        number = 0
        s = s_lst[l]
        for sw in s:
            if on_lst[sw-1]==1:
                number += 1
        if number%2 != p_lst[l]:
            flag = False
            break
    if flag:
        answer += 1

print(answer)

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

typedef long long ll;
typedef pair<int, int> P;
#define MOD 1000000007
#define INF (1 << 30)
#define REP(i, m, n) for(int i = (int)m; i < (int)n; ++i)
#define rep(i, n) REP(i, 0, n)


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

    int total;
    while(cin >> total) {
        if(total == 0) break;
        int sum = 0;
        rep(i, 9) {
            int v; cin >> v;
            sum += v;
        }
        cout << total - sum << '\n';
    }
    return 0;
}


Measured memory_bytes: 3132
#include <bits/stdc++.h>
 
using namespace std;
 
#define rep(i, n) for(int i=0; i<(n); i++)
#define FOR(i, m, n) for(int i=(m);i<(n);i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort((x).begin(),(x).end())
#define RSORT(x) sort((x).rbegin(),(x).rend())
#define REVE(x) reverse((x).begin(),(x).end())
#define mp make_pair
#define pb push_back
#define chmax(x,y) x = max(x,y)

 
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<vector<int> > VVI;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<bool> VB;
typedef vector<LL> VL;
typedef vector<vector<long long>> VVLL;
typedef vector<set<int>> VSI;
const int MOD = 1e9+7;
const int INF = 1e9;
const LL LINF = 1e18;
int gcd(int a, int b)
{
   if (a%b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a%b));
   }
}

int lcm(int a, int b)
{
   return a * b / gcd(a, b);
}

int main() {
    string s;
    cin >> s;
    LL ans = 0;

    rep(i,s.length()) {
        ans += (s[i] - '0');
    }

    if(ans % 9 == 0) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

}


Measured memory_bytes: 3748
using System;
using System.IO;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Numerics;
using System.Threading.Tasks;
using System.Text.RegularExpressions;
using static System.Math;
using Debug = System.Diagnostics.Debug;
using LayoutKind = System.Runtime.InteropServices.LayoutKind;
using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;
using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;


static class P
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        var a = Console.ReadLine().Split().Select((x, y) => int.Parse(x) - y).ToArray();
        long mid = a.OrderBy(x => x).Skip(n / 2).First();
        Console.WriteLine(a.Sum(x => Abs(x - mid)));
    }
}


Measured memory_bytes: 32320
#include <stdio.h>
#include <vector>
#include <iostream>
#include <queue>
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<vs> vvs;

typedef vector<pair<int, int>> vpi;
typedef vector<tuple<int, int, int>> vti;


int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m, i;
    cin >> n >> m;
    vpi t_vec(n);
    for (i=0;i<n;i++){
        int t1, t2;
        cin >> t1 >> t2;
        t_vec[i] = make_pair(t1, t2);
    }
    
    sort(t_vec.begin(), t_vec.end());
    priority_queue<int> pq;
    

    ll idx=0;
    ll res=0;
    for (i=1;i<m+1;i++){
        while (idx < t_vec.size() && t_vec[idx].first <= i){
            pq.push(t_vec[idx].second);
//            cout << idx << " " << t_vec[idx].second << " " << t_vec[idx].first << endl;
            idx++;
        }
        if (pq.size() > 0){
            res += pq.top();
            pq.pop();
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 1660
S = input()

if S[0] != 'A' or S[-1].isupper():
    print('WA')
    exit()

c = 0
for i in S:
    if i.isupper():
        c += 1

S = S[2:-1]

if c == 2:
    if 'C' in S:
        print('AC')
        exit()

print('WA')


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

cul_sum = [0 for _ in range(N+1)]
for i in range(N):
    cul_sum[i+1] = A[i] + cul_sum[i]

def diff_left(center, left):
    return abs(cul_sum[center+1] - 2 * cul_sum[left+1])

def diff_right(center, right):
    return abs(cul_sum[N]-2*cul_sum[right+1]+cul_sum[center+1])

L = [-1 for _ in range(N-1)]
R = [-1 for _ in range(N-1)]
# 真ん中の切り方が i と i+1 の間
l = 0
r = 2
ans = float('inf')
for i in range(1, N-2):
    while l < i and diff_left(i, l) > diff_left(i, l+1):
        l += 1
    if r <= i:
        r = i+1
    while r < N and diff_right(i, r) > diff_right(i, r+1):
        r += 1
    part_sum = [
        cul_sum[l+1],
        cul_sum[i+1] - cul_sum[l+1],
        cul_sum[r+1] - cul_sum[i+1],
        cul_sum[N] - cul_sum[r+1],
    ]
    ans = min(ans, max(part_sum)-min(part_sum))

print(ans)


Measured memory_bytes: 25676
#include<iostream>
#include<algorithm>
#include<queue>
#define inf 200000000
#define Max 10000
#define W 0
#define G 1
#define B 2
using namespace std;
vector<pair<int,int>> g[Max];
int n,d[Max];
void dikstr(int s){
	int color[Max];
int i,j;
	pair<int,int> u;
	priority_queue<pair<int,int>> PQ;
	for(i=0;i<n;i++){
	color[i]=W;
		d[i]=inf;
	}
	d[s]=0;
	PQ.push(make_pair(s,0));
	color[s]=G;
	while(!PQ.empty()){
		u=PQ.top();PQ.pop();
		int uf=u.first,us=u.second;
		color[us]=B;
		if(d[us]<uf*(-1))
		continue;
		
		for( j=0;j<g[us].size();j++){
			int v=g[us][j].first;
			if(color[v]!=B){
				if(d[us]+(g[us][j].second)<d[v]){
					d[v]=d[us]+(g[us][j].second);
					color[v]=G;
					PQ.push(make_pair(d[v]*(-1),v));
				}
			}
		}
	}
	
	
}

main(){
	int u,k,v,c;
	scanf("%d",&n);
	int i,j;
	for(i=0;i<n;i++){
		scanf("%d%d",&u,&k);
		for(j=0;j<k;j++){
			scanf("%d%d",&v,&c);
			g[u].push_back(make_pair(v,c));
		}
	}
	dikstr(0);
	for(i=0;i<n;i++){
		printf("%d %d\n",i,d[i]);
	}
	return 0;
}



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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	string s;
	cin >> n >> s;
	for(int i = 0; i < (int) s.length(); i++) {
		int let = s[i] - 'A';
		let += n;
		let %= 26;
		s[i] = 'A' + let;
	}
	
	cout << s << endl;
}


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

#define INF 1e9
#define llINF 1e18
#define MOD 1e9+7
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ALL(a) (a).begin(),(a).end()
#define Yes(hoge) cout<<((hoge)?"Yes":"No")<<endl;
#define YES(hoge) cout<<((hoge)?"YES":"NO")<<endl;
using namespace std;
int main(){
  string s1,s2;
  cin>>s1>>s2;
  if(s1==s2){cout<<"Yes"<<endl;return 0;}
  if(s1.size()!=s2.size()){cout<<"No"<<endl;return 0;}
  int ss1[30]={};
  int ss2[30]={};
  int henkan[s1.size()+10]={};
  int henkan2[s2.size()+10]={};
  int cnt1=1,cnt2=1;
  for(int i=0;i<s1.size();i++){
    if(ss1[s1[i]-'a']==0){
      ss1[s1[i]-'a']=cnt1;
      cnt1++;
      henkan[i]=cnt1;
    }else{
      henkan[i]=ss1[s1[i]-'a'];
    }
    if(ss2[s2[i]-'a']==0){
      ss2[s2[i]-'a']=cnt2;
      cnt2++;
      henkan2[i]=cnt2;
    }else{
      henkan2[i]=ss2[s2[i]-'a'];
    }
  }
  bool flag=true;
  for(int i=0;i<s1.size();i++)
    if(henkan[i]!=henkan2[i])
      flag=false;
  Yes(flag);
  return 0;
}


Measured memory_bytes: 2312
N, M = map(int, input().split())
R = list()
for i in range(N):
  R.append(0)
for i in range(M):
  c1, c2 = map(int, input().split())
  R[c1-1] += 1
  R[c2-1] += 1
for i in range(N):
  print(R[i])

Measured memory_bytes: 3060
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iomanip>



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

using namespace std;
int a,b,c,d;
int k1,k2;
string s;

int main(){
  cin >> a >> b >> c >> d;
  cout << min(a,b) + min(c,d) << endl;
  
  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <complex>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B,C,L,R;
string S,T;
const ll MOD = (1e+9) + 7;
const ll INF = 1LL << 60;
const long double EPS = 1e-9;
typedef pair<ll,ll> P;

typedef vector<P> vp;
typedef vector<vp> matP;

int main() {
    cin>>N>>M;
    cout<<max(0LL, N - M)<<endl;
}

Measured memory_bytes: 256
n = int(input())

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

multi_four = []
multi_two  = []

for i in l:
    if i % 4 == 0:
        multi_four.append(i)
    
    elif i % 2 == 0 and i % 4 != 0:
        multi_two.append(i)

if len(multi_two) == 0:
    if n - (len(multi_two) + len(multi_four)) <= len(multi_four) + 1:
        print('Yes')
    
    else:
        print('No')

else:
    if n - (len(multi_two) + len(multi_four)) <= len(multi_four):
        print('Yes')
    
    else:
        print('No')

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

// dp[i][j] := i桁目まで見たときに，あまりjの場合の数
ll dp[101010][13];

ll mod = 1e9 + 7;

int main() {
    string s;
    cin >> s;
    reverse(s.begin(), s.end());

    dp[0][0] = 1;
    ll b = 1;
    rep(i, s.size()) {
        for (int k=0; k<10; ++k) {
            if (s[i] != '?' and s[i]-'0' != k) continue;
            ll now = (b * k) % 13;
            for (int j=0; j<13; ++j) {
                dp[i+1][(j + now) % 13] += dp[i][j];
                dp[i+1][(j + now) % 13] %= mod;
            }
        }
        b *= 10;
        b %= 13;
    }

    cout << dp[(int)s.size()][5] << endl;
    return 0;
}


Measured memory_bytes: 10752
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, D = MAP()

te = 1 + D*2

print(ceil(N/te)) 

Measured memory_bytes: 61804
package main

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

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

// Arithmetic
func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

// Sort
type RuneSlice []rune

func (a RuneSlice) Len() int           { return len(a) }
func (a RuneSlice) Less(i, j int) bool { return a[i] < a[j] }
func (a RuneSlice) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

func primeFactors(n int) map[int]int {
	pfs := make(map[int]int)
	for n%2 == 0 {
		pfs[2]++
		n = n / 2
	}
	for i := 3; i*i <= n; i = i + 2 {
		for n%i == 0 {
			pfs[i]++
			n = n / i
		}
	}
	if n > 2 {
		pfs[n]++
	}

	return pfs
}

func modComb(big, small, mod int) int {
	if big < 0 || small < 0 || big < small {
		return 0
	}
	tmp := modFact(big, mod) * modInv(modFact(small, mod), mod) % mod
	return tmp * modInv(modFact(big-small, mod), mod) % mod
}

func modFact(a, mod int) int {
	res := 1
	for i := a; i > 0; i-- {
		res *= i
		res %= mod
	}
	return res
}

func modInv(a, mod int) int {
	b := mod
	u := 1
	v := 0
	for b > 0 {
		t := a / b
		a -= t * b
		a, b = b, a
		u -= t * v
		u, v = v, u
	}
	u %= mod
	if u < 0 {
		u += mod
	}
	return u
}

func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	mod := int(1e+9) + 7
	N := sc.nextInt()
	set := make(map[int]int)
	for i := N; i > 1; i-- {
		pf := primeFactors(i)
		for k, c := range pf {
			set[k] += c
		}
	}
	ans := 1
	for _, c := range set {
		ans *= c + 1
		ans %= mod
	}

	fmt.Fprintln(wtr, ans)
	wtr.Flush()
}


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

int main(){
  int N; cin >> N;
  int a[N]; int sum=0;
  vector<int> v;
  
  for(int i; i<N; i++){
    cin >> a[i];
    sum = sum + a[i];
    if(a[i]%10!=0){v.push_back(a[i]);}
  }
  
  if(v.size()>0){
    sort(v.begin(), v.end());
    if(sum%10!=0){cout << sum;}
  	else{cout << sum - v[0];}
  }
  else{
    cout << 0;
  }
  
  return 0;
}

Measured memory_bytes: 256
fun main(args : Array<String>) {
  val n = readLine()!!.toInt() / 2 - 1
  readLine()!!.split(" ").map { it.toInt() }.apply {
    sorted().let { sort -> forEach { if (sort[n] < it) println(sort[n]) else println(sort[n + 1]) } }
  }
}

Measured memory_bytes: 98668
#include <iostream>

int main()
{
    int a,b;
    std::cin >> a >> b;
    int sum = 0;
    for(int i = 0; i < 2; i++){
        if(a > b){
            sum += a;
            a--;
        }
        else if(b > a){
            sum += b;
            b--;
        }
        else if(a == b){
            sum += a;
            a--;
        }
    }
    std::cout << sum;
    return 0;
}


Measured memory_bytes: 888
#include<iostream>
#include<iomanip>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<string>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;

using ll = long long;

void read();
template<typename First, typename... Rest> void read(First& first, Rest&... rest);
void write();
template<typename First, typename... Rest> void write(First first, Rest... rest);
template<typename T> void write_vec(vector<T>& v, char divider);

int main(){
    int K;
    read(K);
    ll ans = 0;
    for(int a = 1; a <= K; a++){
        for(int b = 1; b <= K; b++){
            for(int c = 1; c <= K; c++){
                int t = __gcd(a, b);
                ans += __gcd(t, c);
            }
        }
    }
    write(ans);
    return 0;
}

//配列以外の入力を受け取る
void read(){

}
template<typename First, typename... Rest>
void read(First& first, Rest&... rest){
    cin >> first;
    read(rest...);
}
//
//配列以外を出力する
void write(){

}
template<typename First, typename... Rest>
void write(First first, Rest... rest){
    cout << first << " ";
    write(rest...);
}
//
//配列を区切って出力する
template<typename T>
void write_vec(vector<T>& v, char divider){
    for(size_t i = 0; i < v.size(); i++){
        cout << v[i] << divider;
    }
}
//

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

int main(){
  int n,k;
  cin >> n >> k;
  vector<int> d(k);
  for(int i=0;i<k;i++) cin >> d.at(i);
  sort(d.begin(),d.end());
  
  for(int i=n;i<=100000;i++){
    int m=i;
    int ans=1;
    while(m>0){
      if(binary_search(d.begin(),d.end(),m%10)){
        ans=0;
        break;
      }
      else{
        m/=10;
      }
    }
    if(ans){
      cout << i << endl;
      i=100000;
    }
  }
}

Measured memory_bytes: 256
import java.util.*;

public class Main{
  public static void main(String[]args){
    Scanner sc = new Scanner(System.in);
    int A = Integer.parseInt(sc.next());
    int B = Integer.parseInt(sc.next());
    
    int c = A - (B*2);
    int ans = c <= 0 ? 0 : c;
    System.out.println(ans);
  }
}

Measured memory_bytes: 21972
N  = int(input())
A = list(map(int, input().split()))
kabu, money, tmp = 0, 1000, 0

for i in range(N - 1):
    if not kabu and A[i] < A[i + 1]:
        tmp = A[i]
        money, kabu = money % tmp, money // tmp
    elif kabu and A[i] > A[i + 1]:
        money += kabu * A[i]
        kabu = 0

if kabu:
    money += max(tmp, A[-1]) * kabu

print(money)


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

typedef long long ll;

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

    //freopen("input.txt", "r", stdin);

    int n;
    cin >> n;

    int cnt = 0;
    while(n)
    {
        int rem = n % 10;
        if(rem == 7)
            cnt++;

        n /= 10;
    }
    if(cnt)
        cout << "Yes\n";
    else
        cout << "No\n";

    return 0;
}


Measured memory_bytes: 3636
#![allow(unused_imports)]
#![allow(unused_macros)]
use std::cmp::{max, min};
use std::collections::*;
use std::io::{stdin, Read};

#[allow(unused_macros)]
macro_rules! parse {
    ($it: ident ) => {};
    ($it: ident, ) => {};
    ($it: ident, $var:ident : $t:tt $($r:tt)*) => {
        let $var = parse_val!($it, $t);
        parse!($it $($r)*);
    };
    ($it: ident, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = parse_val!($it, $t);
        parse!($it $($r)*);
    };
    ($it: ident, $var:ident $($r:tt)*) => {
        let $var = parse_val!($it, usize);
        parse!($it $($r)*);
    };
}

#[allow(unused_macros)]
macro_rules! parse_val {
    ($it: ident, [$t:tt; $len:expr]) => {
        (0..$len).map(|_| parse_val!($it, $t)).collect::<Vec<_>>();
    };
    ($it: ident, ($($t: tt),*)) => {
        ($(parse_val!($it, $t)),*)
    };
    ($it: ident, u1) => {
        $it.next().unwrap().parse::<usize>().unwrap() -1
    };
    ($it: ident, $t: ty) => {
        $it.next().unwrap().parse::<$t>().unwrap()
    };
}

#[cfg(debug_assertions)]
macro_rules! debug {
    ($( $args:expr ),*) => { eprintln!( $( $args ),* ); }
}

#[cfg(not(debug_assertions))]
macro_rules! debug {
    ($( $args:expr ),*) => {
        ()
    };
}

fn solve(s: &str) {
    let mut it = s.split_whitespace();
    parse!(it, r: usize, c: usize, k: usize);
    let mut board = vec![vec![0; c]; r];
    let ns = 4;
    for _ in 0..k {
        parse!(it, r: u1, c: u1, v: usize);
        board[r][c] = v;
    }
    let mut dp = vec![vec![vec![0; ns]; c]; r];
    if board[0][0] > 0 {
        dp[0][0][1] = board[0][0];
    }
    for i in 0..r {
        for j in 0..c {
            for k in 0..ns {
                for &(ni, nj) in &[(i + 1, j), (i, j + 1)] {
                    if ni >= r || nj >= c {
                        continue;
                    }
                    if ni == i {
                        dp[ni][nj][k] = max(dp[ni][nj][k], dp[i][j][k]);
                    } else {
                        dp[ni][nj][0] = max(dp[ni][nj][0], dp[i][j][k]);
                    }
                    let v = board[ni][nj];
                    if v > 0 {
                        if ni == i {
                            if k < ns - 1 {
                                dp[ni][nj][k + 1] = max(dp[ni][nj][k + 1], dp[i][j][k] + v);
                            }
                        } else {
                            dp[ni][nj][1] = max(dp[ni][nj][1], dp[i][j][k] + v);
                        }
                    }
                }
            }
        }
    }
    println!("{}", dp[r - 1][c - 1].iter().max().unwrap());
}

fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    solve(&s);
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_input() {
        let s = "
        ";
        solve(s);
    }
}


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

A = list()
B = list()
C = [[0]*l for i in range(n)]

for i in range(n):
    A.append(list(map(int, input().split())))

for i in range(m):
    B.append(list(map(int, input().split())))

for i in range(n):
    for j in range(l):
        for k in range(m):
            C[i][j] += A[i][k]*B[k][j]

# for i in range(n):
#     for j in range(l):
#         print("%d"%C[i][j],end=" ")
#     print("")

for line in C:
    print(*line)



Measured memory_bytes: 7060
N, W = map(int, input().split())
wv = [[0 for i in range(2)] for j in range(N)]

for i in range(N):
    w, v = map(int, input().split())
    wv[i] = [w, v]

dp = [[10**10 for i in range(10**5+100)] for j in range(150)]
dp[0][0] = 0

for i in range(N):
    for j in range(10**5+100):
        if j - wv[i][1] >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j-wv[i][1]]+wv[i][0])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

ans = 0
for i in range(10**5+100):
    if dp[N][i] <= W: 
        ans = i
print(ans)

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

const int MAX_N = 1 << 17;
const int INF = 1 << 30;

template <class T>
struct MaxSegTree2 {
	int n;
	T segMax[2 * MAX_N - 1], segAdd[2 * MAX_N - 1];
	void init(int n_) {
		n = 1;
		while(n < n_) n *= 2;
		for(int i = 0; i < 2 * n - 1; i++) segMax[i] = 0;
	}

	void add(int a, int b, T x) { add(a, b, x, 0, 0, n); }

	void add(int a, int b, T x, int k, int l, int r) {
		if(r <= a || b <= l) return;
		if(a <= l && r <= b) {
			segAdd[k] += x;
			return;
		}
		add(a, b, x, k * 2 + 1, l, (l + r) / 2);
		add(a, b, x, k * 2 + 2, (l + r) / 2, r);
		segMax[k] = max(segMax[k * 2 + 1] + segAdd[k * 2 + 1], segMax[k * 2 + 2] + segMax[k * 2 + 2]);
	}

	T query(int a, int b) { return query(a, b, 0, 0, n); }

	T query(int a, int b, int k, int l, int r) {
		if(r <= a || b <= l) return -INF;
		if(a <= l && r <= b) return segMax[k] + segAdd[k];
		int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
		int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
		return max(vl, vr) + segAdd[k];
	}
};

MaxSegTree2<int> st;

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

	int n, q;
	cin >> n >> q;

	st.init(n);
	while(q--) {
		int a;
		cin >> a;
		if(a == 0) {
			int s, t, x;
			cin >> s >> t >> x;
			st.add(s - 1, t, x);
		}
		else {
			int i;
			cin >> i;
			cout << st.query(i - 1, i) << endl;
		}
	}
}

Measured memory_bytes: 4872
#include <bits/stdc++.h>
#define rep(i, n) REP(i, 0, n)
#define REP(i, l, r) for (int i = l; i < r; ++i)
#define int long long
#ifdef DEBUG
#define dout cout
#else
std::stringstream dout;
#endif
using namespace std;
typedef pair<int, int> P;
// other libs

signed main(int argc, char* argv[]) {
	string s;
	bool b = false, bback = false;
	cin >> s;
	int ans = 1;
	rep(i, s.size() - 1) {
		if (s[i] == s[i + 1] && b == false && bback == false) {
			bback = b;
			b = true;
		}
		else {
			bback = b;
			b = false;
			ans++;
		}
	}
	cout << ans << endl;
}

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

/*============================ DEBUGGING =============================*/

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

/*============================= DEFINES ==============================*/

#define eps 1e-9
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define B begin()
#define E end()
#define F first
#define S second
#define tostr(x) to_string(x)
#define SZ(x) ((int)x.size())
#define ins insert
#define rep(i,x,y) for(int i=x;i<y;i++)
#define per(i,x,y) for(int i=x;i>y;i--)
#define repi(i,x,y) for(int i=x;i<=y;i++)
#define peri(i,x,y) for(int i=x;i>=y;i--)
#define inf (ll)LLONG_MAX
#define ds1(i,x) for(auto i=x.begin();i!=x.end();i++)
#define ds2(i,x) for(auto i:x)
#define fib(n) ceil(pow((1+sqrt(5),n)-pow((1-sqrt(5),n)/(float)(pow(2,n)*sqrt(5)
#define FIO {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
#define dig(n) (int)(log10(n)+1)
#define ss(x,k) substr(x,k)  // x is the start pos and k is the length of substr.
#define set(x,k) memset(x,k,sizeof x)

/*============================== TYPEDEFS ============================*/

typedef long long ll;
typedef long l;
typedef string str;
typedef vector<int> vi;
typedef vector<ll> vlli;
typedef vector<bool> vb;
typedef queue<int> qi;
typedef vector<pair<int,int> > vpii;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;

/*============================ START FROM HERE =======================*/

int main(){
	FIO
	
	int n,k;cin>>n>>k;
	int a[n],c=0;
	rep(i,0,n){
		cin>>a[i];if(a[i]>=k)c++;
	}
	cout<<c;
	return 0;
}


Measured memory_bytes: 640
#include<iostream>
#include<fstream>
#include<sstream>
#include<cstdio>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<utility>
#include<cctype>
using namespace std;
 
#define ull unsigned long long
#define stt(it,order) sort(it.begin(),it.end(),order)
#define st(it) sort(it.begin(),it.end())
#define ll long long
#define rep(i,j) for(int i=0;i<j;++i)
#define loop(i,a,j) for(int i=a;i<j;++i)
#define mpi(it,table,T,E) for(map<T,E>::iterator it = table.begin();it!=table.end();++it)
#define PI 3.141592654
/*
ifstream fin("input.txt");
ofstream fout("output.txt");
#define cin fin
#define cout fout
*/
 
 
int main(){
    int t = 0;
        rep(i,4){
          int j;
          scanf("%d",&j);
          t += j;
        }
        printf("%d\n",t/60);
        printf("%d\n",t%60);
    return 0;
}

Measured memory_bytes: 3196
A, B = [int(i) for i in input().split()];

A -= 1;
B -= 1;

ans = [['#' for i in range(100)] for j in range(50)] + [['.' for i in range(100)] for j in range(50)];

for i in range(1, 50, 2) :
    for j in range(1, 100, 2) :
        if (A) :
            ans[i][j] = '.';
            A -= 1;

for i in range(51, 100, 2) :
    for j in range(1, 100, 2) :
        if (B) :
            ans[i][j] = '#';
            B -= 1;

print(100, 100);
for i in ans :
    for j in i :
        print(j, end = '');
    print();


Measured memory_bytes: 4596
package main

import (
	"fmt"
	"sort"
)

type K struct {
	v, dif int
}

func main() {
	var X, N int
	fmt.Scan(&X, &N)
	if N == 0 {
		fmt.Println(X)
		return
	}
	P := make(map[int]bool)
	for i := 0; i < N; i++ {
		var V int
		fmt.Scan(&V)
		P[V] = true
	}
	KS := []K{}
	for i := -1000; i <= 1000; i++ { //なんかi=1じゃないらしい（なんで？？？？？
		if !P[i] {
			KS = append(KS, K{v: i, dif: abs(X - i)})
		}
	}
	sort.Slice(KS, func(i, j int) bool {
		if KS[i].dif < KS[j].dif {
			return true
		} else if KS[i].dif > KS[j].dif {
			return false
		} else {
			return KS[i].v < KS[j].v
		}
	})
	if len(KS) > 0 {
		if P[KS[0].v] {
			panic("あわわわわわ")
		} else {
			fmt.Println(KS[0].v)
		}
	} else {
		fmt.Println(0) // なんかXじゃないらしい（なんで？？？？？？？
	}
}

func abs(x int) int {
	if x < 0 {
		x *= -1
	}
	return x
}


Measured memory_bytes: 1980
D,G = list(map(int,input().split()))

p = []
c = []
for i in range(D):
    a,b = list(map(int,input().split()))
    p.append(a)
    c.append(b)
ans = 10**9
for i in range(2**D):
    score = 0
    count = 0
    #print(list(bin(i+2**D)[3:]))
    #print(list(bin((2**(D+1)-1) ^ i)[3:][::-1]))
    for j,s in enumerate(list(bin(i+2**D)[3:])):
        if s=="1":
            score+=c[j] + p[j]*100*(j+1)
            count+=p[j]
    rev = list(bin((2**(D+1)-1) ^ i)[3:][::-1])
    #print(rev)
    #print(rev[0])
    for j in range(D):
        #print(score,rev[j])
        if G <= score:
            break
        if rev[j]=="1":
            if (G-score)//((D-j)*100)<p[D-j-1]-1:
                if (G-score)%((D-j)*100)==0:
                    count+=(G-score)//((D-j)*100)
                    score+=((G-score)//((D-j)*100))*((D-j)*100)
                else:
                    count+=(G-score)//((D-j)*100)+1
                    score+=((G-score)//((D-j)*100)+1)*((D-j)*100)
                
                break
            else:
                score+=(p[D-j-1]-1)*(D-j)*100
                count += p[D-j-1]-1

    if G<=score:
        ans = min(count,ans)

print(ans)

Measured memory_bytes: 42096
#!/usr/bin/env python3
import sys
INF = float("inf")


class UnionFind(object):
    """重み付きUnionFind木
    """

    def __init__(self, N, unity=0):
        self.tree = list(range(N))
        self.rank = [0] * N
        self.diff_weight = [unity]*N

    def root(self, i):
        if self.tree[i] == i:
            return i
        else:
            r = self.root(self.tree[i])
            self.diff_weight[i] += self.diff_weight[self.tree[i]]
            self.tree[i] = r
            return r

    def weight(self, i):
        self.root(i)
        return self.diff_weight[i]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y, w):
        w += self.weight(x)
        w -= self.weight(y)
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.rank[x] < self.rank[y]:
            x, y = y, x
            w = -w
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.tree[y] = x
        self.diff_weight[y] = w
        return True

    def diff(self, x, y):
        return self.weight(x) - self.weight(y)


def solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    uf = UnionFind(N)
    for x, y, z in zip(X, Y, Z):
        uf.unite(x-1, y-1, z)

    print(len(set([uf.root(i) for i in range(N)])))

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    X = [int()] * (M)  # type: "List[int]"
    Y = [int()] * (M)  # type: "List[int]"
    Z = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        X[i] = int(next(tokens))
        Y[i] = int(next(tokens))
        Z[i] = int(next(tokens))
    solve(N, M, X, Y, Z)


if __name__ == '__main__':
    main()


Measured memory_bytes: 27392
#include<bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional> 
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define MOD 1000000007
#define MOD9 1000000009
#define pi 3.1415926535
#define ms(s, n) memset(s, n, sizeof(s))
#define prec(n) fixed<<setprecision(n)
#define eps 0.000001
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define bolt ios::sync_with_stdio(0)
#define light cin.tie(0);cout.tie(0)
#define umll unordered_map<ll,ll>
#define mll map<ll,ll>
#define forr(i,p,n) for(ll i=p;i<(ll)n;i++)
#define test int t;cin>>t;while(t--)
#define MAXN 1000003
typedef long long ll;
using namespace std;
ll mult(ll a,ll b, ll p=MOD){return ((a%p)*(b%p))%p;}
ll add(ll a, ll b, ll p=MOD){return (a%p + b%p)%p;}
ll fpow(ll n, ll k, ll p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n%p; n = n * n%p;} return r;}
ll inv(ll a, ll p = MOD) {return fpow(a, p - 2, p);}
ll inv_euclid(ll a, ll m = MOD){ll m0 = m;ll y = 0, x = 1;if (m == 1)return 0;while (a > 1){ll q = a / m;ll t = m;m = a % m, a = t;t = y;y = x - q * y;x = t;}if (x < 0)x += m0;return x;}
using namespace __gnu_pbds;  
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>ordered_set; 
string a[1000];
ll n,m;
ll dp[1000][1000];
void solve() {
	cin>>n>>m;
	forr(i,0,n)  cin>>a[i];
	dp[0][0]=1;
	forr(i,1,m) {
		if(a[0][i-1]=='.') dp[0][i] = dp[0][i-1]%MOD;
	}
	forr(i,1,n) {
		if(a[i-1][0]=='.') dp[i][0] = dp[i-1][0]%MOD;
	}
	forr(i,1,n) {
		forr(j,1,m) {
			if(a[i-1][j]=='.') dp[i][j]=add(dp[i][j],dp[i-1][j]);
			if(a[i][j-1]=='.') dp[i][j]=add(dp[i][j],dp[i][j-1]);
		}
	}
	cout<<dp[n-1][m-1]%MOD<<"\n";
}
int main(){
	bolt;
	light;
		solve();
 	return 0;
 }

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

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define Debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long LL;
typedef long double LD;
typedef unsigned int uint;
typedef pair <int, int> pii;
typedef unsigned long long uLL;

template <typename T> inline void Read(T &x) {
  char c = getchar();
  bool f = false;
  for (x = 0; !isdigit(c); c = getchar()) {
    if (c == '-') {
      f = true;
    }
  }
  for (; isdigit(c); c = getchar()) {
    x = x * 10 + c - '0';
  }
  if (f) {
    x = -x;
  }
}

template <typename T> inline bool CheckMax(T &a, const T &b) {
  return a < b ? a = b, true : false;
}

template <typename T> inline bool CheckMin(T &a, const T &b) {
  return a > b ? a = b, true : false;
}

const int N = 305;

int n, m, mod, c[N][N], f[N][N], g[N][N];

int main() {
#ifdef wxh010910
  freopen("d.in", "r", stdin);
#endif
  Read(n), Read(m), Read(mod);
  for (int i = 0; i <= n; ++i) {
    c[i][0] = 1;
    for (int j = 1; j <= i; ++j) {
      c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    }
  }
  for (int i = 1; i <= m; ++i) {
    f[1][i] = g[1][i] = (m - i + 1) % mod;
  }
  for (int i = 2; i <= n; ++i) {
    for (int j = m - 1; j; --j) {
      f[i][j] = (g[i - 1][j + 1] + f[i][j + 1]) % mod;
    }
    for (int j = 1; j <= m; ++j) {
      g[i][j] = f[i][j];
      for (int k = 1; k < i; ++k) {
        g[i][j] = (1LL * f[k][j] * g[i - k][j] % mod * c[i - 1][k - 1] + g[i][j]) % mod;
      }
    }
  }
  printf("%d\n", g[n][1]);
#ifdef wxh010910
  Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
  return 0;
}


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

int main(){
    long long N, K;
    long long time=0;
    cin >> N;
    pair<long long, long long> v[N];
    bool flag=true;

    for(int i = 0; i < N; i++) {
	cin >> v[i].second >> v[i].first;
    }

    sort(v, v+N);
    
    for(int i=0; i<N; i++){
	time += v[i].second;
	if(time > v[i].first){
	    flag = false;
	    break;
	    
	}
    }

    if(flag)
	puts("Yes");
    else
	puts("No");
}



Measured memory_bytes: 3328
#include<set>
#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
#define pb push_back
#define lowbit(x) x&(-x)
#define PII  pair<int, int> 
#define all(x) x.begin(), x.end()
#define FAST ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int mod = (int)1e9 + 7;
const int maxn = (int)1e5 + 5;
using namespace std;

#define int ll

int32_t main()
{
	int n, k; cin >> n >> k;
	int t = n / k;
	ll ans = 0;
	if(k & 1){
		ans = t * t * t;
	} 
	else{
		int t2 = t;
		if(n % k >= k / 2) t2++;
		ans = t * t * t + t2 * t2 * t2;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
candi_num, can_exist_num = list(map(int, input().split()))
A = list(map(int, input().split()))

ans = 0

# first candi
ofs = max(0, A[0] + A[1] - can_exist_num)
if ofs > A[1]:
  A[0] -= ofs - A[1]
  ans += ofs - A[1]

for i in range(1, candi_num):
  two_sum = A[i - 1] + A[i]
  ofs = max(0, two_sum - can_exist_num)
  A[i] -= ofs
  ans += ofs

print(ans)

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

const int N = 1e5 + 9;

int subSum[ N ], out[ N ];

int main(){
    string s;
    int n, q;

    cin >> n >> q;
    cin >> s;

    for( int i = 1; i < s.size(); i++ ){
        if( s[ i ] == 'C' && s[ i - 1 ] == 'A' )
            subSum[ i ] = subSum[ i - 1 ] + 1;
        else
            subSum[ i ] = subSum[ i - 1 ];
    }

    int len = 0, t = q;
    while( t-- ){
        int l, r;
        cin >> l >> r;

//        cout << max( subSum[ r - 1 ] - subSum[ l - 1 ], 0) << endl;
        out[ len++ ] = subSum[ r - 1 ] - subSum[ l - 1 ];
    }

    for( int i = 0; i < q; i++ )
        cout << out[ i ] << endl;
    return 0;
}

Measured memory_bytes: 1792