akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;

int main(void){
    int n, q, t;
    string name;
    
    cin >> n >> q;
    queue<pair<string, int> > Q;
    
    for (int i = 0; i < n; i++) {
        cin >> name >> t;
        Q.push(make_pair(name, t));
    }
    
    pair<string, int> u;
    int elaps = 0, a;
    
    while (!Q.empty()) {
        u = Q.front(); Q.pop();
        a = min(u.second, q);
        u.second -= a;
        elaps += a;
        if (u.second > 0) {
            Q.push(u);
        }
        else {
            cout << u.first << " " << elaps << endl;
        }
    }
    return 0;
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
}



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

int n, k;
int res;

int main(){
  cin >> n >> k;
  res = k * (pow(k-1, n-1));
  
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 384
package main

import "fmt"

var N int
var A []int

func main() {
  fmt.Scanf("%d", &N)
  A = make([]int, N)
  for i:=0; i<N; i++ {
    fmt.Scanf("%d", &A[i])
  } 
  res := 0 
  for i:=1; i<N; i++ {
    if A[i] < A[i-1] {
    	res += A[i-1] - A[i]
      	A[i] = A[i-1]
    }
  }
  fmt.Println(res)
}


Measured memory_bytes: 6488
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define ll long long int
#define ull unsigned long long int
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
#define mod 1000000007
double p[5000],q[5000];
long double dp[3001][3001];
int main()
{
    fast;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>p[i];
        q[i]=1-p[i];
    }    
    dp[0][0]=1;
    for(int i=0;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==0)dp[i][j]=q[j]*dp[i][j-1];
            else
            dp[i][j]=dp[i][j-1]*q[j]+dp[i-1][j-1]*p[j];
        }
    }
    double ans=0;
    for(int i=n/2+1;i<=n;i++)ans+=dp[i][n];
    // for(int i=0;i<=n;i++){for(int j=0;j<=n;j++)cout<<dp[i][j]<<" ";cout<<"\n";}
    cout<<setprecision(12)<<ans<<"\n";
return 0;
}

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


int nextInt() { int x; scanf("%d", &x); return x;}

const int MAX_N = 212345;
ll A[MAX_N];
ll B[MAX_N];

// sum [l,r)
ll get(int l, int r) {
  return B[r] - B[l];
}

pair<ll,ll> f(const int from, const int to, const int mode) {
  ll tot = get(from, to);
  int lo = from+1;
  int hi = to-1;
  while (hi - lo > 1) {
    int mid = (hi + lo) / 2;
    ll val = get(from, mid);
    if (tot/2 < val) hi = mid; else lo = mid;
  }

  if (mode == 0)
    return {get(from, lo), get(lo, to)};
  else
    return {get(from, hi), get(hi, to)};
}

int main2() {
  int N = nextInt();
  REP(i, N) A[i] = nextInt();
  B[0] = 0;
  REP(i, N) B[i+1] = B[i] + A[i];
  ll ans = 1LL << 61;
  for (int i = 2; i <= N-2; i++) {
    REP(s, 2) REP(t, 2) {
      pair<ll,ll> x = f(0, i, s);
      pair<ll,ll> y = f(i, N, t);
      ll mi = min(min(x.first, x.second), min(y.first, y.second));
      ll ma = max(max(x.first, x.second), max(y.first, y.second));
      ll here = ma - mi;
      chmin(ans, here);
    }
  }
  cout << ans << endl;
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}

Measured memory_bytes: 3328
A=int(input())
B=int(input())
C=int(input())
X=int(input())
ans=0
for i in range(A+1):
    for j in range(B+1):
        for k in range(C+1):
            if 500*i+100*j+50*k==X:
                ans+=1
print(ans)

Measured memory_bytes: 3060
char E[200];
int p;
//A=M[+-]M[+-]M
//M=T[*/]T[*/]T
//T=(A)|%d
PM(){
	int r;
	r=PT();
	for(;;){
		if(E[p]=='*'){
			p++;
			r*=PT();
		}else if(E[p]=='/'){
			p++;
			r/=PT();
		}else
			return r;
	}
}
PA(){
	int r;
	r=PM();
	for(;;){
		if(E[p]=='+'){
			p++;
			r+=PM();
		}else if(E[p]=='-'){
			p++;
			r-=PM();
		}else
			return r;
	}
}
PT(){
	int r,l;
	if(E[p]=='('){
		p++;
		r=PA();
		p++;
	}else{
		sscanf(E+p,"%d%n",&r,&l);
		p+=l;
	}
	return r;
}
main(){
	scanf("%*d\n");
	for(;~scanf("%[^=]=\n",E);){
		p=0;
		printf("%d\n",PA());
	}
}

Measured memory_bytes: 0
s =list(str(input()))
s_replace = [1 if i == "B" else 0 for i in s]
 
count = 0
ans = 0
 
for i in range(len(s_replace)):
  if s_replace[i] == 1: #もし黒だったらカウントしてください
    count += 1
    continue
  else: #もし白だったら黒の数を足してください
    ans = ans + count
    continue
    
print(ans)

Measured memory_bytes: 6436
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

#include <limits.h>

using namespace std;

typedef long long ll;

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

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

const int INF = INT_MAX / 2;

vector<pair<int, int>> walls;

// ref. https://www.youtube.com/watch?v=D6dr2CrEgns
int main(void) {
    int H, W;
    cin >> H >> W;

    walls.resize(H);
    for (int i = 0; i < H; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        walls[i] = make_pair(a, b);
    }

    map<int, int> pos_to_start;
    multiset<int> dist;
    for (int i = 0; i < W; i++) {
        pos_to_start[i] = i;
        dist.insert(0);
    }

    for (int h = 0; h < H; h++) {
        const int l = walls[h].first;
        const int r = walls[h].second;

        auto it = pos_to_start.lower_bound(l);
        int most_right_start = -1;
        while (it != pos_to_start.end() && it->first <= r) {
            if (r < W) {
                chmax(most_right_start, it->second);
            }
            dist.erase(dist.find(it->first - it->second));
            it = pos_to_start.erase(it);
        }
        if (most_right_start != -1) {
            pos_to_start[r] = most_right_start;
            dist.insert(r - most_right_start);
        }

        if ((int) dist.size() > 0) {
            cout << *(dist.begin()) + (h + 1) << endl;
        } else {
            cout << -1 << endl;
        }

        // printf("h: %d\n", h);
        // for (auto p : pos_to_start) {
        //     cout << p.first << " " << p.second << endl;
        // }
    }

    return 0;
}


Measured memory_bytes: 23576
n = int(input())
s = tuple(map(int,input().split()))

# a = A
# b = A-B
ans = 0
for b in range(1,(n-1)//2):
    point = 0
    count = 0
    for a in range((n-1-b), b, -b):
        if( a%b == 0)&( 2*a <= n-1):
            break
        count += 1
        point += s[b*count] + s[a]
        ans = max(point, ans)

print(ans)

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

string s;

int main() {
    cin>>s;
    for (int i=0; i<s.size()-1; i++) {
        if (s[i]==s[i+1]) {
            cout<<"Bad"<<endl;
            return 0;
        }
    }
    cout<<"Good"<<endl;
    return 0;
}


Measured memory_bytes: 256
import math
 
def div(m):
  d = {}
  temp = int(math.sqrt(m))+1
  for i in range(2, temp):
    while m%i== 0:
      m //= i
      if i in d:
        d[i] += 1
      else:
        d[i] = 1
  if d == {}:
    d[m] = 1
  else:
    if m in d:
      d[m] += 1
    elif m != 1:
      d[m] =1
  return d

n, m = map(int, input().split())
if m == 1:
  print(1)
  exit()
#print(div(m))
from math import factorial
d = div(m)
#print(d)
ans = 1
for i in d.values():
  ans *= int(factorial(i+n-1)) // int(factorial(n-1)) // int(factorial(i))
  ans %= 10**9+7
print(ans)

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

int main(){
    bool isHamming[1000001] = {};
    isHamming[1] = true;
    for(int i = 1; i <= 1000000; i++){
        if(isHamming[i]){
            if(i*2 <= 1000000)  isHamming[i*2] = true;
            if(i*3 <= 1000000)  isHamming[i*3] = true;
            if(i*5 <= 1000000)  isHamming[i*5] = true;
        }
    }

    int m, n;
    while(1){
        cin >> m >> n;
        if(m == 0)  break;

        int cnt = 0;
        for(int i = m; i <= n; i++) if(isHamming[i])    cnt++;
        cout << cnt << endl;
    }
    return 0;
}


Measured memory_bytes: 4072
#include <stdio.h>
#include <string.h>
int main(void){
  char S[11], T[12];
  scanf("%s", S);
  scanf("%s", T);
  for(int i=0; i<strlen(S); i++){
    if(T[i]!=S[i]){
      printf("No\n");
      return 0;
    }
  }
  printf("Yes\n");
  return 0;
}

Measured memory_bytes: 1648
#include <bits/stdc++.h>
#define loop(n) for (int ngtkana_is_genius = 0; ngtkana_is_genius < int(n); ngtkana_is_genius++)
#define rep(i, begin, end) for(int i = int(begin); i < int(end); i++)
auto cmx = [](auto& a, auto b){if (a < b) {a = b; return true;} return false;};

void err() {
  std::cout << -1 << std::endl;
  exit(0);
}

std::vector<int> dp;
std::vector<int> ckd;
std::vector<std::vector<int>> graph;

auto cal(int crr) {
  if (ckd.at(crr) == 2) return dp.at(crr);
  ckd.at(crr) = 1;
  for (auto nxt : graph.at(crr)) {
    if (ckd.at(nxt) == 1) err();
    cmx(dp.at(crr), cal(nxt) + 1);
  }
  ckd.at(crr) = 2;
  return dp.at(crr);
}

auto encode(int i, int j) {
  if (i < j) std::swap(i, j);
  return i * (i - 1) / 2 + j + 1;
}

int main() {
  int n; std::cin >> n;
  auto N = n * (n - 1) / 2;
  graph.resize(N + 1);
  rep(i, 0, n) {
    auto prev = 0;
    loop(n - 1) {
      int x; std::cin >> x; x--;
      auto crr = encode(i, x);
      graph.at(prev).emplace_back(crr);
      prev = crr;
    }
  }
  dp.resize(N + 1, 0);
  ckd.resize(N + 1, 0);
  auto ret = cal(0);
  std::cout << ret << std::endl;
  return 0;
}


Measured memory_bytes: 31616
using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());

            var d = new Dictionary<string, int>();
            for (var i = 0; i < N; i++)
            {
                var S = Console.ReadLine();
                if (!d.ContainsKey(S)) d[S] = 0;
                d[S]++;
            }

            var m = d.Values.Max();
            var l = new List<string>();
            foreach (var kv in d)
            {
                if (kv.Value != m) continue;
                l.Add(kv.Key);
            }

            l.Sort(StringComparer.Ordinal);
            Console.WriteLine(string.Join("\n", l));
        }
    }
}

Measured memory_bytes: 49528
s=input()


sp=s.replace("?","P")
sd=s.replace("?","D")

d= sd.count('D')+sd.count('DP')
p= sp.count('D')+sp.count('DP')
          
                  
if d < p:
                  
    print(sp)
else:
    print(sd)              
                  
   

Measured memory_bytes: 9468
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define BLANK '#'
int main()
{
  int n,m;
  int i,j,blank,maximum,d1,d2;
  bool f;
  char c;
  vector<char> seat;
  while(cin>>n>>m,n|m){
    seat.resize(n);
    for(i=0;i<n;i++)seat[i]=BLANK;
    while(m-->0){
      cin>>c;
      switch(c){
	// A
	case 'A':
	  for(i=0;i<n;i++)
	    if(seat[i]==BLANK){seat[i]=c;break;}
	  break;
	// B
	case 'B':
	  for(i=n;i-->0;){
	    if(seat[i]==BLANK){
	      f=true;
	      if(i+1<n&&seat[i+1]=='A')f=false;
	      if(i>0&&seat[i-1]=='A')f=false;
	      blank=i;
	      if(f){seat[blank]=c;break;}
	    }
	  }
	  if(seat[blank]==BLANK)seat[blank]=c;
	  break;
	// C
	case 'C':
	  f=true;
	  for(i=0;i<n;i++)if(seat[i]!=BLANK)f=false;
	  if(f){seat[n/2]=c;break;}
	  for(i=0;i<n;i++){
	    if(seat[i]!=BLANK){
	      if(i+1<n&&seat[i+1]==BLANK){seat[i+1]=c;break;}
	      if(i>0&&seat[i-1]==BLANK){seat[i-1]=c;break;}
	    }
	  }
	  break;
	// D
	case 'D':
	  maximum=-1;
	  blank=0;
	  for(i=0;i<n;i++){
	    if(seat[i]==BLANK){
	      f=false;
	      for(d1=0,j=i;j-->0;d1++)if(seat[j]!=BLANK){f=true;break;}
	      if(!f)d1=n;
	      f=false;
	      for(d2=0,j=i;++j<n;d2++)if(seat[j]!=BLANK){f=true;break;}
	      if(!f)d2=n;
	      if(maximum<min(d1,d2)){maximum=min(d1,d2);blank=i;}
	    }
	  }
	  seat[blank]=c;
	  break;
      }
    }
    for(i=0;i<n;i++)cout<<seat[i];
    cout<<endl;
  }
}

Measured memory_bytes: 0
import sys
input = sys.stdin.readline
from collections import defaultdict
import bisect

s = input().rstrip()
t = input().rstrip()
d = defaultdict(list)

for i,c in enumerate(s):
    d[c].append(i)
ans = 0
ind = -1
for c in t:
    #print("c=",c,"d[c]=",d[c])
    if not d[c]:
        ans = -1
        break
    ins = bisect.bisect_left(d[c],ind+1)
    if ins < len(d[c]):
        ind =d[c][ins]
     #   print("ins=",ins,end = "")
    else:
      #  print("追加",end = "")
        ans += len(s)
        ind = d[c][0]
    #print("ind=", ind)
    #print()
else:
    ans += ind+1

print(ans)

Measured memory_bytes: 45808
import           Control.Applicative
import           Control.Monad
import qualified Data.ByteString.Char8 as B

import           Data.IntMap.Lazy      (IntMap, (!))
import qualified Data.IntMap.Lazy      as M
import           Data.List
import           Data.Sequence         (Seq (..), ViewL (..), ViewR (..), (<|),
                                        (><), (|>))
import qualified Data.Sequence         as S

read' :: B.ByteString -> Int
read' bs | Just (n, _) <- B.readInt bs = n

getCycle :: (Int, Int)
         -> Seq Int    -- read only
         -> IntMap Int -- read only
         -> Seq Bool   -- update
         -> ([Int], Seq Bool)
getCycle (n, w) sa mb sc = go (n, w) [] sc
  where
    go (i, k) ws bs
        | bs `S.index` i = (ws, bs) -- already checked
        | otherwise      = go (i', k') (k:ws) bs'
      where
        bs' = S.update i True bs
        i' = mb ! k
        k' = sa `S.index` i'

getCycles :: [(Int, Int)]
          -> Seq Int    -- read only
          -> IntMap Int -- read only
          -> Seq Bool   -- update
          -> [[Int]]
getCycles [] _ _ _ = []
getCycles (w:ws) sa mb sc
    | null cs   = getCycles ws sa mb sc'
    | otherwise = cs : getCycles ws sa mb sc'
  where
    (cs, sc') = getCycle w sa mb sc

calcCost :: Int   -- minimum weight
         -> [Int] -- cycle
         -> Int
calcCost w cs = min (sumc + (n - 2) * mc) (sumc + mc + (n + 1) * w)
  where
    n = length cs
    mc = minimum cs
    sumc = sum cs

main :: IO ()
main = do
    n <- read' <$> B.getLine
    ws <- fmap read' . B.words <$> B.getLine

    let wseq = S.fromList ws
    let imap = M.fromList $ zip (sort ws) [0..]
    let bseq = S.replicate n False

    let minw = minimum ws
    let cycles = getCycles (zip [0..] ws) wseq imap bseq

    print $ sum $ fmap (calcCost minw) cycles



Measured memory_bytes: 4508
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

int main(){
  int N;
  cin >> N;
  int p[N];
  int ind[N+1];
  for(int i = 0; i < N; i++){
    cin >> p[i];
    ind[p[i]] = i;
  }

  ll ans = 0;
  multiset<int> st;
  st.insert(-1);
  st.insert(-1);
  st.insert(N);
  st.insert(N);

  for(int i = N; i >= 1; i--){
    int mp = ind[i];
    auto it = st.lower_bound(mp);
    int c = *it;
    int d = *(++it);
    int b = *(--(--it));
    int a = *(--it);

    ll cnt = (b - a) * (c - mp) + (mp - b) * (d - c);
    ans += cnt * i;

    //cout << cnt  << endl;
    //cout << a << " " << b << " " << mp << " " << c << " " << d << endl;

    st.insert(mp);
  }

  cout << ans << endl;
}


Measured memory_bytes: 5760
import java.io.BufferedReader;
import java.io.*;
import java.util.*;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Collections;
import java.util.Arrays;

public class Main {
	public static void main(final String[] args){
    
    Scanner sc = new Scanner(System.in);
    
    int n = sc.nextInt();
    long t = sc.nextLong();
    int count = 0;

    List<Long> list = new ArrayList<>();

    for(int i = 0; i < n ; i++){
        list.add(sc.nextLong());
    }

    for(int i = 0 ; i < n - 1 ; i++){
        if(list.get(i + 1) - list.get(i) > t){
            count += t;
        }else{
            count += list.get(i + 1) - list.get(i);
        }
    }

    count += t;

    System.out.println(count);




    





    
    


    
	}
}

Measured memory_bytes: 65132
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<complex>
#define INF 2147483647
#define llINF 9223372036854775807
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long

using namespace std;
int main(){
  int a,b,c,d;
  string str,strr;
  cin>>a>>b>>c;
  bool flag=false;
  for(int i=a;i<a+c&&i<=b;i++){
    cout<<i<<endl;
    if(i==b){flag=true;break;}
    // cout<<"!"<<endl;
	}
  int ij=max(b-c+1,a+c);
  if(flag==false){
  for(int i=ij;i<=b;i++)
    cout<<i<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
n, k = map(int,input().split())
s = input() + '1'
L = []

i = 0
d = []
while i <= n:
    if s[i] == '0':
        d.append(i)

    else:
        if d != []:
            L.append(d)
            d = []
    i += 1

ans = 0
nl = len(L)

if nl <= k:
    print(n)
else:
    for i in range(nl - k + 1):

        if i == 0:
            sta = 0
        else:
            sta = L[i - 1][-1] + 1

        if i == nl - k:
            end = n - 1
        else:
            end = L[i + k][0] - 1

        ans = max(ans, end - sta + 1)

    print(ans)


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

int n;
vector< vector<int> > f;

class data {
	public:
		bool map[64];
		int last;
	
		data() {
			for(int i = 0; i < 64; i++) {
				map[i] = false;
			}
			last = 0;
		}

		bool judge() {
			for(int i = 0; i < n; i++) {
				if(map[i] == false)
					return false;
			}

			return true;
		}
};

void init() {
	f.clear();
}

bool input() {
	int tmp;
	cin >> n;
	if(!n)
		return false;

	f.resize(n);
	for(int i = 0; i < n; i++) {
		cin >> tmp;
		for(int j = 0; j < tmp; j++) {
			int tmp2;
			cin >> tmp2;
			f[i].push_back(tmp2);
		}
	}

	return true;
}

int solve() {
	vector<data> vd;
	vd.resize(n);

	for(int i = 0; i < n; i++)
		vd[i].map[i] = true;

	for(int date = 1; date < 31; date++) {
		vector<int> tmp;
		for(int i = 0; i < f.size(); i++) {
			for(int j = 0; j < f[i].size(); j++) {
				if(date == f[i][j])
					tmp.push_back(i);
			}
		}

		if(tmp.size() > 1) {
			for(int i = 0; i < tmp.size(); i++) {
				for(int j = 0; j < tmp.size(); j++)
					vd[tmp[i]].map[tmp[j]] = true;
				for(int j = 0; j < n; j++) {
					for(int k = 0; k < tmp.size(); k++) {
						vd[tmp[i]].map[j] = vd[tmp[i]].map[j] | vd[tmp[k]].map[j];
					}
				}
			if(vd[tmp[i]].judge())
				return date;
			}
		}
	}

	return -1;
}

int main(void) {
	while(init(), input()) {
		cout << solve() << endl;
	}
	return 0;
}

Measured memory_bytes: 1236
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int k = sc.nextInt();
		int x = sc.nextInt();
		print(k * 500 >= x ? "Yes" : "No");
		sc.close();
	}

	public static void print(Object obj) {
		System.out.println(obj);
	}
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define N 500006
using namespace std;
int T,n,p,a[N];long long ans;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=3*n;i++)scanf("%d",&a[i]);
	sort(a+1,a+3*n+1);
	for(int i=3*n-1;i>=1;i-=2){
		p++;ans+=1LL*a[i];if(p==n)break; 
	}
	printf("%lld\n",ans);
}

Measured memory_bytes: 1408
class UnionFind:
    def __init__(self,n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rank = [0]*(n+1)

    def find(self,x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] > self.rank[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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

    def size(self,x):
        return -self.root[self.find(x)]

    def member(self,x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.root) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_member(self):
        return {r:self.member(r) for r in self.roots()}

    def __str__(self):
        return "\n".join("{}: {}".format(r,self.member(r)) for r in self.roots())

def main():
    N,M,K = map(int,input().split())
    adj = [[] for _ in range(N)]
    ans = [None]*N
    uf = UnionFind(N)
    for i in range(M+K):
        a,b = map(int,input().split())
        if i < M:
            uf.unite(a-1,b-1)
            adj[a-1].append(b-1)
            adj[b-1].append(a-1)
        elif uf.same(a-1,b-1):
            adj[a-1].append(b-1)
            adj[b-1].append(a-1)
    for i in range(N):
        ans[i] = uf.size(i) - len(adj[i]) - 1
    print(*ans,sep=" ")


if __name__ == '__main__':
    main()

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

int main(){

    string s;
    cin >> s;

    int cnt = 0;
    int smax = 0;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == 'A'|| s[i] == 'G'|| s[i] == 'C'|| s[i] == 'T'){
            cnt++;
            smax = max(cnt, smax);
        }else{
            cnt = 0;
        }
    }
    cout << smax << endl;
    return 0;
}

Measured memory_bytes: 256
val = input()
if int(val) <= 999:
  str_val = str(val)
  val_one = str_val[-1]
  if val_one in {'2','4','5','9','7'}:
    print('hon')
  elif val_one in {'0','1','6','8'}:
    print('pon')
  elif val_one == '3':
    print('bon')


Measured memory_bytes: 9172
void solve();

int main() {
	solve();
	return 0;
}

//////////////////////////////////////////////////
//////////////////////////////////////////////////
#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
#include <algorithm>
#include <deque>

using namespace std;

vector<string> strvect;
void solve() {
	string SS, T;
	cin >> SS >> T;
	for (int n = 0; n <= (int)SS.size() - (int)T.size(); n++) {
		//SSのn文字目からTに置き換える
		bool flag = true;
		for (int t = 0; t < T.size(); t++) {
			if (SS[n + t] == '?')continue;
			if (SS[n + t] != T[t]) {
				flag = false;
				break;
			}
		}
		if (!flag)continue;
		string sstemp = SS;
		for (int ntemp = 0; ntemp < n; ntemp++) {
			if (sstemp[ntemp] == '?')sstemp[ntemp] = 'a';
		}
		for (int t = 0; t < T.size(); t++) {
			sstemp[n + t] = T[t];
		}
		for (int ntemp = n + T.size(); ntemp < SS.size(); ntemp++) {
			if (sstemp[ntemp] == '?')sstemp[ntemp] = 'a';
		}
		strvect.push_back(sstemp);
	}
	if (strvect.size() == 0) {
		cout << "UNRESTORABLE" << endl;
		return;
	}
	sort(strvect.begin(), strvect.end(), [](string a, string b) {
		for (int i = 0; i < min(a.size(), b.size()); i++) {
			if (a[i] != b[i])return a[i] < b[i];
		}
		return a.size() < b.size();
	});
	cout << strvect[0] << endl;
	return;
}

Measured memory_bytes: 256
import sys
def input():
    return sys.stdin.readline()[:-1]
N,A,B=map(int,input().split())
X=tuple(map(int,input().split()))
k=B//A
a=0
for i in range(N-1):
    if X[i+1]-X[i]>k:
        a+=B
    else:
        a+=(X[i+1]-X[i])*A
print(a)

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

vector<int> g[200001];
bool visited[200001];
ll n, r, c, p;

void dfs(int u) {
    if (visited[u]) return;
    visited[u] = true;
    if (u <= 100000)
        ++r;
    else
        ++c;
    for (int v : g[u]) {
        ++p;
        dfs(v);
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y + 100000);
        g[y + 100000].push_back(x);
    }
    ll ans = 0;
    for (int u = 1; u <= 200000; ++u) {
        r = c = p = 0;
        dfs(u);
        ans += r * c - p / 2;
    }
    cout << ans << endl;
}

Measured memory_bytes: 10240
d = int(input())
c_li = list(map(int, input().split()))
s_li = [list(map(int, input().split())) for _ in range(d)]
t_li = [int(input()) for _ in range(d)]

last_d = [-1] * 26
ans = 0

for i in range(d):
    op = t_li[i] - 1
    ans += s_li[i][op]
    last_d[op] = i
    for j in range(26):
        ans -= c_li[j] * (i-last_d[j])
    
    print(ans)

Measured memory_bytes: 9388
#include<bits/stdc++.h>
#define all(v) v.begin(),v.end()
#define rep(a,n,b) for(unsigned ll i=a;i<n;i+=b)
#define rrep(a,n,b) for(int i=n;i>=a;i-=b)
#define iter(obj) for(auto x : obj) 
#define pb(i) push_back(i)
#define ff first
#define ss second
#define pchr(flag) cout<<(flag ? "YES" : "NO")
#define ll long long int
#define input freopen("input.txt","r",stdin)
#define op freopen("output.txt","w",stdout);
#define fastio std::ios::sync_with_stdio(false)
using namespace std;
const int N = 2e5+7;
const int MOD  = 1000000007;
const float PI = 3.1415926535;
//33333333333;
int prime[N];
int arr[N];
void SieveOfEratosthenes(int n) 
{ 
     for (int p=2; p*p<=n; p++) {
        if (prime[p] == 0)  {
            for (int i=p*p; i<=n; i += p) 
                prime[i] = 1; 
        } 
    } 
} 
int main() 
{ 
	// input;
	fastio;
	int a,b;
	cin>>a>>b;
	unsigned ll x = 10e18;
	unsigned ll ans = max(a,b);
	unsigned	ll res = min(a,b);
	rep(ans,x,ans){
		if(i%res==0 and i%ans ==0) {
			cout<<i;
			return 0;
		}
	} 
}
 


Measured memory_bytes: 256
fn station_and_bus() -> Result<&'static str, &'static str> {
    let mut input = String::new();
    std::io::stdin().read_line(&mut input)
        .map_err(|_| "input error")?;

    input = input.trim_right().to_string();
    let c1 = input.pop().unwrap();
    let c2 = input.pop().unwrap();
    let c3 = input.pop().unwrap();

    if c1 == c2 && c2 == c3 {
        Ok("No")
    }
    else {
        Ok("Yes")
    }
}

fn main() {
    println!("{}", station_and_bus().unwrap());
}

Measured memory_bytes: 4352
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string.h>
#define s(n)                        scanf("%d",&n)
#define sc(n)                       scanf("%c",&n)
#define sl(n)                       scanf("%I64d",&n)
#define sf(n)                       scanf("%lf",&n)
#define ss(n)                       scanf("%s",n)
#define INF                         (int)1e9
#define EPS                         1e-9
#define bitcount                    __builtin_popcount
#define gcd                         __gcd
#define forall(i,a,b)               for(int i=a;i<b;i++)
#define foreach(v, c)               for( typeof( (c).begin()) v = (c).begin();  v != (c).end(); ++v)
#define all(a)                      a.begin(), a.end()
#define in(a,b)                     ( (b).find(a) != (b).end())
#define pb                          push_back
#define fill(a,v)                    memset(a, v, sizeof a)
#define sz(a)                       ((int)(a.size()))
#define mp                          make_pair
#define MOD                         1000000007
typedef long long ll;
/*For you see , each day i love you
 more.Today more than yesterday
  less than tomorrow.*/
using namespace std;

int main()
{
	int n;s(n);
	vector<int> vec;
	for(int i = 0;i<n;i++)
	{
		int x;s(x);
		vec.push_back(x);
	}
	vector<int> ans(n+1 , 0);
	for(int i = n-2;i>=0;i--)
	{
		if(i == n-2) ans[i] = abs(vec[i] - vec[i+1]);
		else
		{
			ans[i] = min(ans[i+1] + abs(vec[i] - vec[i+1]) , ans[i+2] + abs(vec[i] - vec[i+2]));
			}	
	}
	
	cout<<ans[0]<<endl;
	return 0;
}


Measured memory_bytes: 1144
#include <iostream>

using namespace std;

int main() {
  
  int N;	string st;
  cin >> N >> st;
  
  int max = 0;
  int atai = 0;
  
  for(int i = 0; i < N; i++){
    if ( st.at(i) == 'I')	atai++;
    else	atai--;
    
    if(atai > max)	max = atai;
  }
  
  cout << max << endl;
   
}

Measured memory_bytes: 256
#include<stdio.h>
 
int main(){
   
  int i,j,k,v,A[100],N;
   
  scanf("%d",&N);
   
  for(i = 0; i < N; i++){
    scanf("%d",&A[i]);
  }
   
  for(i = 1; i < N+1; i++){
    for(k = 0; k < N; k++){
      printf("%d",A[k]);
      if(k == N-1) break;
      printf(" ");
    }
     
    printf("\n");
     
    v = A[i];
    j = i - 1;
    while(j >= 0 && A[j] > v){
       
      A[j+1] = A[j];
      j--;
      A[j+1] = v;
    }
  }
  return 0;
}

Measured memory_bytes: 1756
#include <iostream>

const int MAXN=1e5+5;
long long int a[MAXN],b[MAXN];
int main() {
	
	int n;
	scanf("%d",&n);
    
    for(int i=0;i<n+1;i++){
    	scanf("%d",&a[i]);
	}
    long long int sum=0;
    for(int i=0;i<n;i++){
    	scanf("%d",&b[i]);
    	if(b[i]<=a[i]){
    		sum+=b[i];
		}else if(b[i]<=(a[i]+a[i+1])){
			sum+=b[i];
			a[i+1]-=b[i]-a[i];
		}else{
			sum+=a[i]+a[i+1];
			a[i+1]=0;
		}
	}
	printf("%lld",sum);
	return 0;
    
}





/*
2 3 5
3 3
3 2
3 2

4 3 8
8

1 1 100
1 1 1
1 2
1 3
*/





 

Measured memory_bytes: 1792
#include <bits/stdc++.h>
 
#define mp make_pair
#define eb emplace_back
#define ff first
#define ss second
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
const int MAXN = 100;
//#define int long long
const int INF = 1e9;
 
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
	int n;
  cin >> n;
  map<string, int> m;
  for (int i = 0; i < n; i++){
  	string s;
    cin >> s;
    if (!m.count(s)) m[s] = 0;
    m[s]++;
  }
  if (!m.count("AC")) m["AC"] = 0;
  if (!m.count("WA")) m["WA"] = 0;
  if (!m.count("TLE")) m["TLE"] = 0;
  if (!m.count("RE")) m["RE"] = 0;
  cout << "AC x " << m["AC"] << '\n';
  cout << "WA x " << m["WA"] << '\n';
  cout << "TLE x " << m["TLE"] << '\n';
  cout << "RE x " << m["RE"] << '\n';
 
    return 0;
}


Measured memory_bytes: 3668
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <map>
typedef long long LL;

int main() {
	int d, n;
	int temp = 1;
	std::cin >> d >> n;

	for (int i = 0; i < d; ++i) {
		temp *= 100;
	}
	if (d == 0) {
		temp = 1;
	}

	if (n == 100) {
		std::cout << (temp * n) + (1*temp) << std::endl;
		return 0;
	}
	std::cout << temp * n << std::endl;

}

Measured memory_bytes: 256
//	Problem Name: Frog 1
//
//  Created by Kushal Warke
//  Copyright © 2018 Kushal Warke. All rights reserved.
//

#include <iostream>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
#include <fstream>
#include <map>
#include <vector>
#include <set>
#include <sstream>
#include <stack>
#include <list>
#include <queue>

using namespace std;

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(x) ((x)<0?-(x):(x))

typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef vector< pair<int,int> > vpi;
typedef vector< pair<long long,long long> > vpll;

double EPS = 1e-9; 
int INF = 1000000005; 
long long INFF = 1000000000000000005LL;
const int N = 100001;
const int M = 4;
int n;
int data[N];
int cost[N];

int solve(int i) {
    if(cost[i]!=-1) {
        return cost[i];
    }
    if(i==n) {
        return cost[i] = 0;
    }
    if(i==n-1) {
        return cost[i] = abs(data[i+1] - data[i]);
    }
    return cost[i] = min(abs(data[i+1]-data[i])+solve(i+1),abs(data[i+2]-data[i])+solve(i+2));
} 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    FOR(i,1,n+1) {
        cin>>data[i];
        cost[i] = -1;
    }
    solve(1);
    cout<<cost[1]<<endl;
    return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
#define pb push_back
#define ppb pop_back
#define mer make_pair
#define fi first
#define se second
using namespace std;

int n,m;
vector<pair<int,int> > v[110000];
int a[110000];
bool vis[110000];
queue<int> q;

int main(){
	memset(a,-1,sizeof(a));
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int l,r,d;
		cin>>l>>r>>d;
		v[l].pb(mer(r,d));
		v[r].pb(mer(l,-d));
	}
	for(int i=1;i<=n;i++)
		if(!vis[i]){
			q.push(i);
			while(!q.empty()){
				int y=q.front();
				q.pop();
				for(int i=0;i<v[y].size();i++){
					int then=v[y][i].fi;
					if(vis[then]){
						if(a[then]!=a[y]+v[y][i].se){
							cout<<"No";
							return 0;
						}
					}
					else{
						vis[then]=true;
						a[then]=a[y]+v[y][i].se;
						q.push(then);
					}
				}
			}
		}
	cout<<"Yes";
	return 0;
}


Measured memory_bytes: 9728
//let's do it
 #include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define inf 1000000000000
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define S second
#define F first
#define boost1 ios::sync_with_stdio(false);
#define boost2 cin.tie(0);
#define mem(a,val) memset(a,val,sizeof a)
#define endl "\n"
#define maxn 100001

ll x[maxn],y[maxn];
inline ll add(ll x,ll y)
{
	return (x+y)%mod;
}
inline ll mul(ll x,ll y)
{
	return (x*y)%mod;
}
inline ll sub(ll x,ll y)
{
	return (x-y+mod)%mod;
}
int main()
{
	boost1;boost2;
	ll i,j,n,m,ans=0,sum=0,val=0;
	cin>>n>>m;
	for(i=1;i<=n;i++)
	cin>>x[i];
	for(i=1;i<=m;i++)
	cin>>y[i];
	for(i=1;i<=m;i++)
	{
		val=add(val,mul(y[i],(i-1)));
		val=sub(val,sum);
		sum=add(sum,y[i]);
	}
	sum=0;
	for(i=1;i<=n;i++)
	{
		ans=add(ans,mul(i-1,x[i]));
		ans=sub(ans,sum);
		sum=add(sum,x[i]);
	}
	cout<<mul(ans,val);
	return 0;
}


Measured memory_bytes: 1792
using System;
using System.Linq;

namespace b122C {
    class Program {
        static void Main(string[] args) {
            var input = Console.ReadLine();
            var sp = input.Split(' ');
            var n = int.Parse(sp[0]);
            var q = int.Parse(sp[1]);
            var s = Console.ReadLine();

            var x = 0;
            var t = new int[n];
            for (int i = 0; i < n - 1; i++) {
                t[i + 1] = t[i] + (s.Substring(i, 2) == "AC" ? 1 : 0);
            }

            for (int i = 0; i < q; i++) {
                var lr = Console.ReadLine().Split(' ').Select(int.Parse).ToList();
                var l = lr[0] - 1;
                var r = lr[1] - 1;


                Console.WriteLine(t[r] - t[l]);
            }
        }
    }
}

Measured memory_bytes: 16444
from collections import Counter

N = int(input())
S = input()

r = S.count('R')
g = S.count('G')
b = S.count('B')

sum = r*g*b

for i in range(N):
    for j in range(i+1, N):
        k = 2 * j - i
        if k > N - 1:
            break
        if not S[i] == S[j] and not S[j] == S[k] and not S[k] == S[i]:
            sum -= 1
print(sum)

Measured memory_bytes: 9472
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<queue>
#define _USE_MATH_DEFINES
#include<math.h>
#include<cmath>
#include<ctime>
#include<map>
#include<typeinfo>
#define R(i, n) for(int i = 0;i < n; i++)
#define R1(i, n) for(int i = 1; i <= n; i++)
#define S(a) scanf("%d", &a)
#define S2(a, b) scanf("%d%d", &a, &b)
#define S3(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define SL(a) scanf("%lld", &a)
#define SL2(a, b) scanf("%lld%lld", &a, &b)
#define SL3(a, b, c) scanf("%lld%lld%lld", &a, &b, &c)
#define SC(a) scanf("%c", &a)
#define P(a) printf("%d", a)
#define PL(a) printf("%lld", a)
#define PY printf("YES")
#define PN printf("NO")
#define Py printf("Yes")
#define Pn printf("No")
using namespace std;
using ll = long long;
using PR = pair<int, int>;
const ll MOD = 1e+9 + 7;
const int INF = 1e+9;
const double PI = acos(-1);

int main() {
	string s;
	ll k;
	cin >> s;
	SL(k);
	int onum = 0;
	int num;
	int i = 0;
	while (i < s.size()) {
		if (s[i] == '1') {
			onum++;
			i++;
		}
		else {
			num = s[i] - '0';
			break;
		}
	}
	if (k <= onum) P(1);
	else P(num);
}

Measured memory_bytes: 3796
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    n,k=map(int, input().split())
    r,s,p=map(int, input().split())
    t=input()
    def kachip(te):
        if te=='r':
            return p
        elif te=='s':
            return r
        else:
            return s
    def kachite(te):
        if te == 'r':
            return 'p'
        elif te == 's':
            return 'r'
        else:
            return 's'

    check=[0]*k # 出した手
    ans=0
    for i in range(n):
        point=kachip(t[i])
        te=kachite(t[i])
        if check[i%k]==te:
            check[i%k]=0
        else:
            ans+=point
            check[i%k]=te
    print(ans)
resolve()

Measured memory_bytes: 48496
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    long[] a = new long[N];
    long sum = 0;
    for (int i = 0; i < N; i++) {
      a[i] = sc.nextLong();
      sum += a[i];
    }
    long sum2 = 0;
    long min = Long.MAX_VALUE;
    for (int i = 0; i < N - 1; i++) {
      sum2 += a[i];
      long tmp = Math.abs(2 * sum2 - sum);
      if (tmp < min) {
        min = tmp;
      }
    }
    System.out.println(min);
  }
}

Measured memory_bytes: 85728
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long 
ll a,b,c,d;
ll ans=-1000000000000000000;
int main(){
    cin>>a>>b>>c>>d;
    ans=max(ans,a*c);
    ans=max(ans,a*d);
    ans=max(ans,b*c);
    ans=max(ans,b*d);
    cout<<ans;
    return 0;
}

Measured memory_bytes: 3600
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define forE(i,x) for(int i=head[x];i!=-1;i=ne[i])
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned u32;
typedef pair<int,int> pin;
#define mk(a,b) make_pair(a,b)
#define lowbit(x) ((x)&(-(x)))
#define sqr(a) ((a)*(a))
#define clr(a) (memset((a),0,sizeof(a)))
#define ls ((x)<<1)
#define rs (((x)<<1)|1)
#define mid (((l)+(r))>>1)
#define pb push_back
#define w1 first
#define w2 second
inline void read(int &x){
	x=0;int f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
inline void judge(){
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
}
/*******************************head*******************************/
const int maxn=1000005;
const int mod=998244353;
int fac[maxn],facinv[maxn];
inline int powmod(int a,int b){
	int res=1;for(;b;b>>=1){
		if(b&1)res=1ll*res*a%mod;a=1ll*a*a%mod;
	}return res;
}
inline int C(int n,int m){
	if(n<0||m<0||n<m)return 0;
	return 1ll*fac[n]*facinv[m]%mod*facinv[n-m]%mod;
}
inline void prprpr(){	
	fac[0]=1;
	rep(i,1,1000000)fac[i]=1ll*fac[i-1]*i%mod;
	facinv[1000000]=powmod(fac[1000000],mod-2);
	per(i,999999,0)facinv[i]=1ll*facinv[i+1]*(i+1)%mod;
}
int n,m;
int main(){
	read(n);read(m);prprpr();
	if(n<m)swap(n,m);//cout<<facinv[1000000]<<endl;
	int ans=n;//cout<<C(2,1)<<endl;
	int d=powmod(C(n+m,n),mod-2);
	rep(i,1,m){
		ans=(ans+1ll*C(2*i-1,i)*C(n+m-2*i,n-i)%mod*d%mod)%mod;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 8064
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

const int DEFAULT = 0;

const int NIL = -1;

typedef long long ll;

struct Node {
    ll sum;
    ll lazy;
    int lchild;
    int rchild;
    Node(int sum = 0, int lazy = 0, int lchild = NIL, int rchild = NIL)
            :sum(sum), lazy(lazy), lchild(lchild), rchild(rchild) {
    }
};


struct SegmentTree {
 
    vector<Node> heap;
    int rootId;
    int lrange;
    int rrange;

    SegmentTree(int rootId, int lrange, int rrange) 
        : rootId(rootId), lrange(lrange), rrange(rrange) {
        heap.assign(rootId + 1, Node());
    }
    
    void add(int ql, int qr, int inc) {
        add(rootId, lrange, rrange, ql, qr, inc);
    }
    
    ll query(int ql, int qr) {
        return query(rootId, lrange, rrange, ql, qr);
    }

    void add(int nodeId, int l, int r, int ql, int qr, int inc) {
        if (qr < l || ql > r) {
            return;
        } else if (ql <= l && r <= qr) {
            heap[nodeId].lazy += inc;
        } else {
            pushDown(nodeId, l, r);
            int m = l + (r - l) / 2;
            add(heap[nodeId].lchild, l, m, ql, qr, inc);
            add(heap[nodeId].rchild, m + 1, r, ql, qr, inc);
            pullUp(nodeId, l, r);
        }
    }

    void pushDown(int nodeId, int l, int r) {    
        ensureChildren(nodeId);
        
        Node& node = heap[nodeId];
        if (node.lazy > 0) {
            heap[node.lchild].lazy += node.lazy;
            heap[node.rchild].lazy += node.lazy;
            
            heap[nodeId].sum = evalSum(nodeId, l, r);
            heap[nodeId].lazy = 0;
        }
    }

    void pullUp(int nodeId, int l, int r) {
        int m = l + (r - l) / 2;
        heap[nodeId].sum = evalSum(heap[nodeId].lchild, l, m) + evalSum(heap[nodeId].rchild, m + 1, r);
    }

    ll evalSum(int nodeId, int l, int r) {
        return heap[nodeId].lazy * (r - l + 1) + heap[nodeId].sum;
    }

    ll query(int nodeId, int l, int r, int ql, int qr) {
        if (qr < l || ql > r) {
            return DEFAULT;
        }
        if (ql <= l && r <= qr) {
            return evalSum(nodeId, l, r);
        }
        else {
            pushDown(nodeId, l, r);
            int m = l + (r - l) / 2;
            return query(heap[nodeId].lchild, l, m, ql, qr) +
                    query(heap[nodeId].rchild, m + 1, r, ql, qr);
        }
    }
    
    void ensureChildren(int nodeId) {
        if (heap[nodeId].lchild == NIL) {
            heap.push_back(Node());
            heap[nodeId].lchild = heap.size() - 1;
        }
        if (heap[nodeId].rchild == NIL) {
            heap.push_back(Node());
            heap[nodeId].rchild = heap.size() - 1;
        } 
    }
};

int main() {
    int n, q;
    cin >> n >> q;
    SegmentTree st(1, 1, n);
    for (int i = 0; i < q; i++) {
        int cmd;
        cin >> cmd;
        if (cmd == 0) {
            int ql, qr, v;
            cin >> ql >> qr >> v;
            st.add(ql, qr, v);

        } else {
            int ql, qr;
            cin >> ql >> qr;
            cout << st.query(ql, qr) << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 9116
#include <bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<pair<int, string>> s(m);
    vector<string> ans(n, "0");
    rep(i, m){
        cin >> s[i].first >> s[i].second;
        s[i].first--;
    }
    sort(all(s));
    bool ok = true;
    REP(i, m-1){
        if(s[i].first == s[i-1].first && s[i].second != s[i-1].second)ok = false;
    }
    if(ok){
        bool ok2 = true;
        rep(i, m){
            if(s[i].first == 0 && s[i].second == "0")ok2 = false;
            ans[s[i].first] = s[i].second;
        }  
        if(n == 1){
            cout << ans[0] << endl;
            exit(0);
        }
        if(!ok2)cout << -1;
        else {
            if(ans[0] == "0")ans[0] = "1";
            rep(i, n)cout << ans[i];
        }
    }
    else cout << -1 << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
using namespace std;
int main() {
	int a, b, ans;
	cin >> a >> b;
	if (a == 1) ans = 1;
	else ans = a - b + 1;
	cout << ans << endl;
}


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

using namespace std;

#define REP(i, N) for (int i = 0; i < (int)N; i++)
#define LOOP(i, N) for (int i = 1; i <= (int)N; i++)
#define RREP(i, N) for (int i =(int)N-1; i >= 0; i--)
#define RLOOP(i, N) for (int i =(int)N; i > 0; i--)
#define FOR(i, a, b) for (int i = a; i < (int)b; i++)
#define ALL(x) (x).begin(), (x).end()
#define INF (1 << 30)
#define LLINF (1LL << 62)
#define DEBUG(...) debug(__LINE__, ":" __VA_ARGS__)

typedef long long ll;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;
int main(){
  ll n,m;
  cin>>n>>m;
  if(n==1&&m==1){
    cout<<1<<endl;
  }else if(n==1||m==1){
    if(n==1){
      cout<<m-2<<endl;
    }else{
      cout<<n-2<<endl;
    }
  }else if(n==2||m==2){
    cout<<0<<endl;
  }else{
    cout<<(n-2)*(m-2)<<endl;
  }
}


Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <cmath>
#include <deque>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define ll long long
#define rep2(i,a,b) for(int i=a;i<=b;++i)
#define rep(i,n) for(int i=0;i<n;i++)
#define rep3(i,a,b) for(int i=a;i>=b;i--)
#define REP(e,v) for(auto e:v)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
#define mt make_tuple
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define vecpll vector<pll>
#define vecbl vector<bool>
#define endl "\n"
#define ALL(c) (c).begin(),(c).end()
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}
string stin(){string s;cin>>s;return s;}

int main(){
    int n=in();
    cout<<999-(n-1)%1000<<endl;
}

Measured memory_bytes: 3644
#include<bits/stdc++.h>
#define $$ long long int
#define pb push_back
#define db pop_back
#define q2(n) (n%2)==0
#define vp vector<pair <$$,$$> >
#define vctr vector<$$>
#define in(a) scanf("%lld",&a)
#define out(a) printf("%lld ",a)
#define loop(i,m,p) for ($$ i = m; i < p; ++i)
#define loopn(i,m,p) for ($$ i = p-1; i >=m; --i)

using namespace std;

int main()
{
  $$ n,sum=0,sum2=0;
  cin>>n;
  $$ ar[n],arr[n];
  loop(i,0,n) in(ar[i]);
  //loop(i,0,n) arr[i]=ar[i];
  $$ flag=0;
  loop(i,0,n)
  {
    if (ar[i]<0)
    {
      flag++;
    }
  }
  if (q2(flag))
  {
    loop(i,0,n) sum+=(abs(ar[i]));
  }
  else
  {
    $$ mn=100000000000;
    loop(i,0,n)
    {
        if (abs(ar[i])<mn)
        {
          mn=abs(ar[i]);
        }
    }
    loop(i,0,n)
    {
        sum+=(abs(ar[i]));
    }
    sum-=mn;
    sum-=mn;
  }

  cout<<sum<<endl;



  return 0;

}


Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>

#define ll long long

using namespace std;

int main() {
    int n; cin >> n;
    vector<int> s(n);
    for(int i=0; i<n; i++) cin >> s[i];
    ll sum = std::accumulate(s.begin(), s.end(), 0);
    if(sum%10!=0) {
        cout << sum << endl;
    } else {
        sort(s.begin(), s.end());
        for(int i=0; i<n; i++) {
            if(s[i]%10!=0) {
                sum = sum-s[i];
                break;
            }
        }
        if(sum%10==0) {
            cout << 0 << endl;
        } else {
            cout << sum << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 256
n = int(input())
fl = [list(map(int, input().split())) for _ in range(n)]
pl = [list(map(int, input().split())) for _ in range(n)]

import itertools

xl = list(itertools.product(range(2), repeat=10))

res = -1*(10**10)

for i in range(1,1024):# 開店パターン
    temp =0
    for j in range(n):#　店の数
        op = 0
        
        for k in range(10):#掛け算して営業タイミング確認
            op += xl[i][k]*fl[j][k] 
        temp += pl[j][op]
    
    res = max(res,temp)
    
print(res)

Measured memory_bytes: 3188