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

#define DRACARYS ios_base::sync_with_stdio(false);cin.tie(NULL);cin.exceptions(cin.failbit);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a)  memset(a, -1, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
#define PI 3.14159265
const long long int MAXN = 1e5+10;
const long long int MINN = 1e5+10;
const long long int inf = 21000;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi; 
typedef stack<int> st;
ll n,w,wt[MAXN],val[MAXN],dp[105][MAXN];
int main(){
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    DRACARYS
    cin>>n>>w;
    repA(i,1,n) cin>>wt[i]>>val[i]; 
    repA(i,1,n){
        repA(j,1,w){
            if(wt[i]<=j) dp[i][j]=max(dp[i][j],max(dp[i-1][j-wt[i]]+val[i],dp[i-1][j]));
            else dp[i][j]=dp[i-1][j];
        }
    }
    cout<<dp[n][w]<<endl;
    return 0;
}

Measured memory_bytes: 79488
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    int a;
    int amax = -1;
    int amin = 1001;
    for(int i=0; i<n; i++){
        cin >> a;
        amax = max(a, amax);
        amin = min(a, amin);
    }
    cout << amax - amin << endl;
    return 0;
}

Measured memory_bytes: 256
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <unordered_map>
#include <complex>
#include <iomanip>
#include <cmath>
#include <tuple>
using namespace std;

long long const MOD = 1000000007LL;

int main() {
    int n;
    cin >> n;

    long res = 0;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        if (a % 2 == 0) {
            while (a % 2 == 0) {
                ++res;
                a /= 2;
            }
        }
    }

    cout << res << endl;
}


Measured memory_bytes: 256
from sys import stdin
input = stdin.readline

class Node:    
    def __init__(self, number):
        self.number  = number
        self.parent, self.sibling, self.degree, self.depth, self.height = -1,-1,0,0,0
        self.nodetype = 'internal node'
        self.child = []
    
    def output(self):
        print('node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %s, %s'%(self.number,self.parent,self.sibling,self.degree,self.depth,self.height,self.nodetype))

def check(node, depth):
    node.depth = depth
    if node.child != []:
        depth += 1
        for num in node.child:
            node.height = max(check(nodelist[num],depth) + 1, node.height)
    return node.height

n = int(input())
nodelist = [Node(i) for i in range(n)]
for _ in range(n):
    idx, left, right = map(int, input().split())
    if left == -1 and right == -1:
        nodelist[idx].nodetype = 'leaf'
    elif left != -1 and right != -1:
        nodelist[idx].child = [left,right]
        nodelist[idx].degree = 2
        nodelist[left].sibling, nodelist[right].sibling = right, left
        nodelist[left].parent, nodelist[right].parent = idx, idx
    elif left == -1 or right == -1:
        exist = max(left,right)
        nodelist[idx].child = [exist]
        nodelist[idx].degree = 1
        nodelist[exist].parent = idx

for node in nodelist:
    if node.parent == -1:
        node.nodetype = 'root'
        node.height = check(node, 0)
        break

for node in nodelist:
    node.output()


Measured memory_bytes: 5620
n = int(input())
num = [ int(v) for v in input().split() ]
counter = [3] + [ 0 for i in range(n) ]
ans = 1
mod = 10**9+7
for i in num:
    ans *= counter[i]
    ans %= mod
    counter[i] -= 1
    counter[i+1] += 1

print(ans)

Measured memory_bytes: 57028
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, y;
    cin >> n >> y;
    FOR(i, 0, n)FOR(j, 0, n) {
        int k = n - i - j;
        if(k < 0 or n < k) continue;
        if(i * 10000 + j * 5000 + k * 1000 == y) {
            cout << i << " " << j << " " << k << endl;
            return 0;
        }
    }
    cout << "-1 -1 -1" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <math.h>
#include <string>
#include <string.h>
#include <stack>
#include <algorithm>
#include <stdio.h>
#include <functional>
using namespace std;

int main()
{
	int a, b;
	cin >> a >> b;
	cout.setf(ios::fixed);
	cout.precision(5);
	cout << a / b << " " << a % b << " " << (double)a / b << endl;
	return 0;
}

Measured memory_bytes: 1248
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

N  = read()
p = [x-1 for x in reads()]
ans = 0

for i in range(N):
  if p[i] == i:
    if p[i] < N-1:
      p[i], p[i+1] = p[i+1], p[i]
    ans += 1

print(ans)

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

int main() {
	map<char, char> mp;
  	mp['C'] = 'G';
  	mp['G'] = 'C';
  	mp['A'] = 'T';
  	mp['T'] = 'A';
  	
  	char c; cin >> c;
  	cout << mp[c];
  	return 0;
}

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

int main()
{
    string A;
	char R;

	cin >> A;	
	for(int i=0; i<A.length()/2; i++){
		R = A[i];
		A[i] = A[A.length()-i-1];
		A[A.length()-i-1] = R;
	}
	cout << A << "\n";
	
    return 0;
}

Measured memory_bytes: 1160
// AOJ 1312: Where's Wally
// 2018.3.18 bal4u

#include <stdio.h>
#include <string.h>

typedef unsigned long long ull;

#define HB 3181
 
char tr[128];
char img[1005][1005], pat[105][105], rot[105][105];
ull  imghash[1005][1005], pathash[8];
char buf[200];

int main()
{
	int  w, h, p, r, c, i, j, ans;
	ull  hbr, hbc, s;
	char *q, ch;

	for (i = 'A'; i <= 'Z'; i++) tr[i] = i-'A';
	for (i = 'a'; i <= 'z'; i++) tr[i] = i-'a'+26;
	for (i = '0'; i <= '9'; i++) tr[i] = i-'0'+52;
	tr['+'] = 62, tr['/'] = 63;

	while (fgets(q=buf, 20, stdin) && *q != '0') {
		sscanf(q, "%d%d%d", &w, &h, &p);
		hbr = 1; for (i = 0; i < p; i++) hbr *= HB;
		hbc = 1; for (i = 0; i < p; i++) hbc *= hbr;

		memset(img, 0, sizeof(img));
		for (r = 0; r < h; r++) {
			fgets(q=buf, 200, stdin);
			for (c = 0; *q >= ' '; c+=6) {
				ch = tr[*q++];
				for (j = 5; j >= 0; j--) if (ch & (1<<(5-j))) img[r][c+j] = 1;
			}
		}

		memset(pat, 0, sizeof(pat));
		for (r = 0; r < p; r++) {
			fgets(q=buf, 200, stdin);
			for (c = 0; *q >= ' '; c+=6) {
				ch = tr[*q++];
				for (j = 5; j >= 0; j--) if (ch & (1<<(5-j))) pat[r][c+j] = 1;
			}
		}

		for (i = 0; i < 8; i++) {
			memcpy(rot, pat, sizeof(pat));
			for (r = 0; r < p; r++) for (c = 0; c < p; c++) pat[p-c-1][r] = rot[r][c];
			if (i == 4) {
				memcpy(rot, pat, sizeof(pat));
				for (r = 0; r < p; r++) for (c = 0; c < p; c++)	pat[r][p-c-1] = rot[r][c];
			}
			pathash[i] = 0;
			for (r = 0; r < p; r++) for (c = 0; c < p; c++)	pathash[i] = pathash[i]*HB + pat[r][c];
		}

		for (r = 0; r < h; r++) {
			s = 0; for (c = 0; c < w; c++) {
				s = s*HB + img[r][c];
				if (c >= p) s -= hbr * img[r][c-p];
				imghash[r][c] = s;
			}
		}

		ans = 0;
		for (c = p-1; c < w; c++) {
			s = 0;
			for (r = 0; r < h; r++) {
				s = s*hbr + imghash[r][c];
				if (r >= p)	s -= hbc * imghash[r-p][c];
				if (r >= p-1) {
					for (i = 0; i < 8; i++) if (pathash[i] == s) { ans++; break; }
				}
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}


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

int main() {
  int n;
  cin >> n;
  vector<int> ls(n), rs(n);
  rep(i, n) cin >> ls[i] >> rs[i];
  sort(ls.begin(), ls.end());
  sort(rs.begin(), rs.end());
  int ans = 0;
  if (n % 2 == 1) {
    int l = ls[n / 2];
    int r = rs[n / 2];
    ans = r - l + 1;
  } else {
    int l2 = ls[n / 2 - 1] + ls[n / 2];
    int r2 = rs[n / 2 - 1] + rs[n / 2];
    ans = r2 - l2 + 1;
  }
  cout << ans << endl;
  return 0;
}


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

int main(){
	long long a, maximum;
	int n;
	while (cin >> n, n){
		maximum = -1000000;
		long long S[5010] = {};
		for (int i = 1; i <= n; i++){
			cin >> a;
			S[i] = S[i - 1] + a;
		}

		for (int i = 0; i <= n; i++)
			for (int j = i + 1; j <= n; j++){
				maximum = max(maximum, S[j] - S[i]);
			}
		cout << maximum << endl;
	}
}

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

int N;

int main(){
  int d;
  cin >> N >> d;
  int res = 0;
  for(int i=0;i<N;i++){
    int a; cin >> a; if( a > d ) res += a-d;
  }
  if( !res ) cout << "kusoge" << endl;
  else cout << res << endl;
}

Measured memory_bytes: 3092
#include<iostream>
#include<string>
  
using namespace std;
  
int main()
{
    int n;
    string t_cade,h_cade;
    int t_point=0,h_point=0;
    cin >>n;
  
    for(int i=0;i<n;i++){
        cin>>t_cade>>h_cade;
  
        if(t_cade==h_cade){
            t_point++;
            h_point++;
        }else{
            int index=0;
            while (t_cade[index] == h_cade[index]){
                index++;
            }
  
            if(t_cade[index] > h_cade[index]){
                t_point+= 3;
            }else{
                h_point += 3;
            }
        }
    }
    cout<<t_point<<" "<< h_point<<endl;
  
    return 0;
}

Measured memory_bytes: 3184
// 'That's all it is. A leap of faith'

#include <bits/stdc++.h>

#define append push_back

using namespace std;
using ll = long long;

const int N = 1e5 + 3;
const int M = 1e6 + 7;
const long long MOD = 1e9 + 7;
const long long INF = 1e18 + 9;
const int SM = 1e3 + 5;
const int logN = 22, BL = 400;
const double EPS = 1e-9, PI = acos(-1);
const int dx[] = {1, 0, 0, -1, -1, 1, -1, 1};
const int dy[] = {0, 1, -1, 0, -1, 1, 1, -1};

template<typename Type>
long long sz(Type x) {
    return ll(x.size());
}

void debug() {
	cerr << "\n";
}
template<typename Type1, typename... Type2>
void debug(Type1 a, Type2... b) {
    cerr << a << " ";
    debug(b...);
}

int main() {
//    freopen(".in", "r", stdin);
//    freopen(".out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    long long n; cin >> n;

    vector<vector<long long>> d(n, vector<long long>(2));

    bool flag = false;

    for(long long i = 0; i < n; i++) {
        cin >> d[i][0] >> d[i][1];
        if(i > 1) {
            if(d[i - 2][0] == d[i - 2][1] && d[i - 1][0] == d[i - 1][1] && d[i][0] == d[i][1]) {
                flag = true;
            }
        }
    }

    cout << (flag ? "Yes" : "No");

    return 0;
}


Measured memory_bytes: 3624
#include <cstdio>
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef unsigned long long ull;
int main()
{
    int a, b;
    cin >> a >> b;
    if (a == b) {
        cout << 0 << endl;
        return 0;
    }
    if ((a+b)%2 == 0) {
        cout << (a+b)/2 << endl;
    } else {
        cout << "IMPOSSIBLE" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, s, e) for(int i = s; i < e; i++)
#define rrep(i, s, e) for(int i = s; i > (s)-(e); i--)
#define pr(s) std::cout << s << std::endl
#define prb(s) std::cout << s
using namespace std;



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


  int n;
  cin >> n;

  pr(n*800 - (n/15)*200);


  return 0;
}


Measured memory_bytes: 256
l = 1
loop{
  capacity = readline.chomp.to_i
  break if capacity == 0

  treasure_num = readline.chomp.to_i
  weights = []
  values = []
  treasure_num.times{
    v, w = readline.chomp.split(/,/).map{|c| c.to_i}
    values << v
    weights << w
  }

  dp = Array.new(treasure_num){ Array.new(capacity+1){ 0 } }

  (0..treasure_num-1).each{|t|
    (0..capacity).each{|c|
      if c < weights[t]
        dp[t][c] = dp[t-1][c]
      else
        dp[t][c] = [dp[t-1][c], dp[t-1][c-weights[t]]+values[t]].max
      end
    }
  }

  max_value = 0
  max_weight = 0
  dp[treasure_num-1].each_with_index{|v, i|
    if v > max_value
      max_value = v
      max_weight = i
    end
  }
  puts "Case #{l}:\n#{max_value}\n#{max_weight}"
  l += 1
}

Measured memory_bytes: 16976
#include <iostream>
#include <numeric>
#include <vector>
#include <algorithm>
#include <string>
#include "math.h"

using namespace std;
int main(int argc, char const *argv[]) {
  int N, A, B;
  cin >> N >> A >> B;
  string S;
  cin >> S;
  int count_A = 0;
  int count_B = 0;
  for (auto s : S) {
    if (s == 'a') {
      if (count_A + count_B < A + B) {
        cout << "Yes" << endl;
        count_A++;
      } else {
        cout << "No" << endl;
      }
    }
    else if (s == 'b') {
      if ((count_A + count_B < A + B) && (count_B < B)) {
        cout << "Yes" << endl;
        count_B++;
      } else {
        cout << "No" << endl;
      }
    }
    else {
      cout << "No" << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 832
#include <iostream>
using namespace std;
int SoF(int x){ //Sum of figures(格桁の和の略)
    int a=0;
    int b=x;
    for(int i=0; i<1000 ; i++){ //10^1000まで計算可能
        int c;
        c=b%10;
        a += c;
        b /= 10;
        if(b==0)
            break;
    }
    return a;
}
int main() {
    int N,A,B;
    int ans=0;
    cin >>N >> A >> B;
    for (int i=1;i<=N;i++){
        if (A<=SoF(i)&&SoF(i)<=B){
            ans += i;
        }
    }
    cout << ans << endl;
}


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

//repetition
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;


//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline ll toLL(string s) {ll v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    s += "X";
    VI num;
    rep(i,s.size()-1){
      if(s[i] == 'A') num.push_back(1);
      else if(s[i] == 'B' && s[i+1] == 'C'){
        num.push_back(2);
        i++;
      }else{
        num.push_back(3);
      }
    }
    int cnt1 = 0;
    int cnt2 = 0;
    ll ans = 0;
    for(ll i=num.size()-1 ; i>= 0; i--){
      if(num[i] == 3){
        cnt1 = 0;
        cnt2 = 0;
      }else if(num[i] == 2){
        cnt2 ++;
      }else{
        ans += cnt2;
      }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1680
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <sstream>
#include <cmath>
#include <math.h>
#include <string>
using namespace std;
          

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    for ( int i = 0 ; i < s.length() ; i++ ) {
        if ( s[i] == ',' ) cout << ' ';
        else cout <<  s[i];
    }
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, AS):
    num_division = 0
    maxAS = max(AS)
    eratree = [0] * (maxAS + 10)
    for p in range(2, maxAS + 1):
        if eratree[p]:
            continue
        # p is prime
        eratree[p] = p
        x = p * p
        while x <= maxAS:
            if not eratree[x]:
                eratree[x] = p
            x += p

    from collections import defaultdict
    count = defaultdict(int)
    for a in AS:
        factors = []
        while a > 1:
            d = eratree[a]
            factors.append(d)
            a //= d
            num_division += 1
        # debug(": ", factors)
        for f in set(factors):
            count[f] += 1

    # debug(": num_division", num_division)
    if any(x == N for x in count.values()):
        return "not coprime"
    if any(x >= 2 for x in count.values()):
        return "setwise coprime"
    return "pairwise coprime"


def main():
    # parse input
    N = int(input())
    AS = list(map(int, input().split()))
    print(solve(N, AS))


# tests
T1 = """
3
3 4 5
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
pairwise coprime
"""

T2 = """
3
6 10 15
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
setwise coprime
"""

T3 = """
3
6 10 16
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
not coprime
"""

T4 = """
3
100000 100001 100003
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
pairwise coprime
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()


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

using namespace std;
using ll =long long;
typedef pair<int,int> P;
#define SORT(a) sort((a).begin(),(a).end())
#define REV(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

void coY() {cout <<"Yes"<<endl;}
void coN(){cout <<"No"<<endl;}
 
//Write From this Line

//const ll mod = 1e9+7;
//const ll mod = 998244353;
int main()
{
	int x, a;
	cin >> x >> a;
	cout << (x < a ? 0 : 10) << endl;
}


Measured memory_bytes: 3476
n,q=map(int,input().split())
s=input()
ans,c=[0]*q,[0]*n
k=0
for i in range(1,n):
    if s[i-1]=="A" and s[i]=="C":
        k+=1
    c[i]=k

for i in range(q):
    l,r=map(int,input().split())
    ans[i]=c[r-1]-c[l-1]
for i in ans:
    print(i)


Measured memory_bytes: 10220
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
char st[21000];
int ans=0;
int main()
{
	scanf("%s",st);
	for(int i=0;i<strlen(st);i++)
	{
		if(st[i]=='1') ans++;
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<iomanip>
#include<deque>
#include<tuple>
#include<queue>
#include<map>
#include<cstdint>
#include<unordered_map>
#include<boost/multiprecision/cpp_int.hpp>


#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define vi vector<int>
#define all(x) (x).begin(),(x).end()
#define Endl endl
#define F first
#define S second

namespace mp = boost::multiprecision;

using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;


int main() {
	int N, Q;
	cin >> N >> Q;
	string s;
	cin >> s;
	vector<char>a(Q),b(Q);
	rep(i, Q) {
		cin >> a[i] >> b[i];
	}
	int l = 0; int r = N + 1;
	while (r-l>1) {
		int mid = (l + r) / 2;
		char tmp = s[mid-1];
		int pos = mid;
		rep(i, Q) {
			if (tmp == a[i]) {
				if (b[i] == 'R') {
					pos++;
				}
				else {
					pos--;
				}
				if (pos == N + 1 || pos == 0) {
					break;
				}
				tmp = s[pos-1];
			}
		}
		if (pos == 0) {
			l = mid;
		}
		else {
			r = mid;
		}
		//cout << r << " " << l << endl;
		//cout << tmp << endl;
	}
	int rside = r;
	l = 0; r = N + 1;
	while (r - l>1) {
		int mid = (l + r) / 2;
		char tmp = s[mid-1];
		int pos = mid;
		rep(i, Q) {
			if (tmp == a[i]) {
				if (b[i] == 'R') {
					pos++;
				}
				else {
					pos--;
				}
				if (pos == N+1 || pos==0){
					break;
				}
				tmp = s[pos-1];
			}
		}
		if (pos == N+1) {
			r = mid;
		}
		else {
			l = mid;
		}
	}
	int lside = r;
	cout << lside - rside << endl;
}


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

using namespace std;
const int N=2e4+5;
typedef long long ll;
const int mod=1e9+7;
bool f[11];
pair<int,int> a[11];
int n,g,ans=1e9;
void qu(int x,int sum,int t)
{
    if(sum>=g) {ans=min(ans,t);return;}
    for(int i=n;i>=1;i--)
    {
        if(!f[i]&&(a[i].first-1)*i*100+sum>=g)
        {
            int gi=1;
            while(gi*100*i+sum<g) gi++;
            ans=min(t+gi,ans);
            break;
        }
    }
    for(int i=x+1;i<=n;i++)
    {
        if(!f[i])
        {
            f[i]=true;
            qu(i,sum+a[i].first*i*100+a[i].second,t+a[i].first);
            f[i]=false;
        }
    }
}
int main()
{
    cin >>n >> g;
    for(int i=1;i<=n;i++) cin >> a[i].first >> a[i].second;
    qu(0,0,0);
    cout << ans <<endl;
    return 0;
}


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

using namespace std;

int main() {
	int n, tr, ans = 0;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> tr;
		while (tr % 2 == 0) {
			++ans;
			tr /= 2;
		}
	}
	cout << ans << '\n';
}


Measured memory_bytes: 256
#include<algorithm>
#include<cmath>
#include<cstdint>
#include<cstdio>
#include<functional>
#include<iostream>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
using namespace std;

#define loop(i,a,b) for(int i=(a); i<(b); ++i)
#define rep(i,n) for(int i=0; i<n; ++i)
#define all(v) begin(v), end(v)
#define dump(a) cerr << #a << " = " << (a) << "(L:" << __LINE__ << ")" << endl

const double PI = acos(-1.0);

int main() {
  std::ios::sync_with_stdio(false);

  string s;
  while(cin >> s){
    string org = s;
    int ans = 100;
    for(char c = 'a'; c <= 'z'; ++c) {
      s = org;

      rep(p, 100) {
        int k = count(all(s), c);
        if (k == 0) {
          break;
        }
        if (k == s.size()) {
          ans = min(ans, p);
          break;
        }

        string t = s.substr(0, s.size() - 1);
        rep(i, s.size() - 1) {
          if (s[i] == c || s[i+1] == c) {
            t[i] = c;
          }
        }
        s = t;
      }
    }
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 888
while 1:
    top = 1
    south = 2
    east = 3
    n = input()
    if n == 0:
        break
    Sum = 1
    for i in range(n):
        line = raw_input().strip()
        if line == "North":
            top, south, east = south, 7 - top, east
            Sum += top
        elif line == "East":
            top, south, east = 7- east, south, top
            Sum += top
        elif line == "West":
            top, south, east = east, south, 7 - top
            Sum += top
        elif line == "South":
            top, south, east = 7 - south, top, east
            Sum += top
        elif line == "Right":
            top, south, east = top, east, 7 - south
            Sum += top
        elif line == "Left":
            top, south, east = top, 7 - east, south
            Sum += top
    print Sum

Measured memory_bytes: 4392
#include<string.h>
#include<vector>
#include<queue>
#include<cstdio>
#include<math.h>
#include<algorithm>



using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
const int INF=1001001001;
int map[10][10000];//0????????????



int main(){
	while(1){
		int d,n,m;//????????¨?????????????????°?????¨???????????°
		int N[100002];
		scanf("%d",&d);
		if(d==0)break;
		scanf("%d %d",&n,&m);

		N[0]=0;
		rep(i,n-1){scanf("%d",&N[i+1]);}
		sort(N,N+n);
		N[n]=d;//??¬?????????????°??????????
		long long int ans=0;
		rep(i,m){
			int t;
			scanf("%d",&t);
			int a=lower_bound(N,N+n+1,t)-N;
			if(a==0)ans+=N[a]-t;
			else{
				if(t-N[a-1]<=N[a]-t)ans+=t-N[a-1];
				else ans+=N[a]-t;
			}
		}
		printf("%lld\n",ans);
	}
}

Measured memory_bytes: 1436
#include <bits/stdc++.h>
using namespace std;
#define WHOLE(v) (v).begin(), (v).end()
#define REV_WHOLE(v) (v).rbegin(), (v).rend()
using i64 = int64_t;
int main() {
    string s;
    cin >> s;
    int N = s.length();
    vector<int> v(1);
    for(auto x : s) v.push_back(x == '1');
    bool ans_judge = true;
    ans_judge &= v[1] == 1 && v[N] == 0;
    for(int i = 1; i < N; i++) {
        ans_judge &= v[i] == v[N - i];
    }
    if(!ans_judge) {
        cout << -1 << endl;
        return 0;
    }
    vector<pair<int, int>> ans;
    int pivot = 0;
    for(int i = 1; i < N; i++) {
        ans.push_back(make_pair(pivot, i));
        if(i <= N / 2 && v[i]) pivot = i;
    }
    for(auto x : ans) {
        int u, v;
        tie(u, v) = x;
        u++, v++;
        cout << u << " " << v << endl;
    }
    return 0;
}

Measured memory_bytes: 2868
#include<stdio.h>
int main()
{
   long long int N,K,s[100000],i,x=0;
   scanf("%lld%lld",&N,&K);

   for(i=0;i<N;i++)
   {

      scanf("%lld",&s[i]);

      if(s[i]>=K)
      {
         x=x+1;
       }
    }
    printf("%lld",x);
    return 0;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
#define fv               first
#define sv               second
#define ll               long long
#define pll              pair<ll,ll>
#define pii              pair<int,int>
#define READ(x)          freopen(x,"r",stdin)
#define WRITE(x)         freopen(x,"w",stdout)
#define isWorking()      cout<<"Wroking"<<endl
#define all(x)           (x).begin(),(x).end()
#define allr(x)          (x).rbegin(),(x).rend()
#define fill(x,y)        memset(x, y, sizeof(x))
#define PRINT(ok)        cout<<(ok? "YES":"NO")<<endl
#define DoublePrint(x,a) cout<<fixed<<setprecision(x)<<a<<endl
#define Fast_Input       ios_base :: sync_with_stdio(0),cin.tie(0);

const ll mod = 1e9+7, INF = 1e8, mx = 1e5+5, mn = 100;
int testCase=1,cas=0;

int main() {
    Fast_Input

    while(testCase--){
        int n; cin >> n;
        int k =1000;
        while(k<n) k+=1000;

        cout << k-n << endl;
    }
    return 0;
}


Measured memory_bytes: 3608
#include <bits/stdc++.h>
#define rep(i,a) for(int i=0;i<int(a);++i)
#define REP(i,a,b) for(int i=int(a);i<int(b);++i)
using ll = long long;
using itn = int;
using namespace std;
using Graph = vector<vector<int>>;
int GCD(int a, int b){
    return b ? GCD(b, a%b) : a;
}
int main() {
	int N,M;
	cin>>N>>M;
	cout<< M*1900*pow(2,M)+(N-M)*100*pow(2,M) <<endl;
	return 0;
}

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

vector<int> g[5000000];
int h[5000000];
map<pair<int, int>, ll> mp;
map<ll, pair<int, int>> mp2;

int main() {
    ll N;
    cin >> N;

    ll cur = 1;
    rep(i, N) {
        pair<int, int> prev;
        {
            int A;
            cin >> A;
            A--;

            pair<int, int> p;
            int a = i, b = A;
            if (a > b) swap(a, b);
            p = { a, b };
            if (mp[p] == 0) {
                mp[p] = cur;
                mp2[cur++] = p;
            }
            prev = p;
        }

        rep(j, N-2) {
            int A;
            cin >> A;
            A--;
            pair<int, int> p;
            int a = i, b = A;
            if (a > b) swap(a, b);
            p = { a, b };

            if (mp[p] == 0) {
                mp[p] = cur;
                mp2[cur++] = p;
            }

            g[mp[prev]].push_back(mp[p]);
            prev = p;
            h[mp[p]]++;
        }
    }

    ll v = N * (N-1) / 2;

    // for (int i=1; i<=v; ++i) {
    //     pair<int, int>
    //     for (int j : g[i]) {
    //
    //     }
    // }

    queue<int> st;
    for (int i=1; i<=v; ++i) if (h[i] == 0) st.push(i);

    vector<int> ans;
    while (st.size()) {
        int i = st.front(); st.pop();
        ans.push_back(i);
        for (auto& j : g[i]) {
            h[j]--;
            if (h[j] == 0) st.push(j);
        }
    }

    // rep(i, ans.size()) {
    //     cout << ans[i] << endl;
    // }


    if (ans.size() != v) {
        cout << -1 << endl;
        return 0;
    }

    {
        int cur = 0;
        bitset<3030> days;
        for (int day=1; day<=v; ++day) {
            for (;cur<ans.size(); ++cur) {
                pair<int, int> p = mp2[ans[cur]];
                if (!days[p.first] and !days[p.second]) {
                    days[p.first] = days[p.second] = 1;
                }
                else {
                    break;
                }
            }

            days.reset();
            if (cur == ans.size()) {
                cout << day << endl;
                break;
            }
        }
    }

}


Measured memory_bytes: 200696
#include<bits/stdc++.h>
using namespace std;
	
// Let dp[i][j][player] denote the winner for a player k considering upto i stones, and

int dp[100000][2];


// The given function returns the code of the player that wins
int Solve(int chance, int rem, int n, int stn[]){

	int otherPlayer = (chance == 0)?1:0;
	//cout << otherPlayer << " s " << rem << "\n";
	// If there is no stone to unturn for the current player, the other player loses
	if(rem < 0){return otherPlayer;}

	if(dp[rem][chance] != -1){return dp[rem][chance];}

	for(int i=0 ; i<n ; i++){

		if(rem-stn[i] < 0){continue;}

		// For the current chance, try each stone
		int winner = Solve(otherPlayer, rem-stn[i], n, stn);

		// If winner is current player, return winner
		if(winner == chance){return dp[rem][chance] = chance;}
	}
	return dp[rem][chance] = otherPlayer;
}

int main(){
	int n,k;
	cin >> n >> k;
	int stn[n];
	for(int i=0 ; i<n ; i++){
		cin >> stn[i];
	}

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

	int winner = Solve(0, k, n, stn);

	if(winner == 0){
		cout << "First\n";
	}
	else{
		cout << "Second\n";
	}
	return 0;
}

Measured memory_bytes: 10368
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	char c;
	rep(i,3)rep(j,3){
		cin >> c;
		if(i == j) cout << c;
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int a[100050];
    for(int i=0;i<100050;i++)
    {
        if(i<=9)
        {
            a[i]=i;
        }
        else if(i<=99)
        {
            a[i]=a[i-1];
        }
        else if(i<=999)
        {
            a[i]=a[i-1]+1;
        }
        else if(i<=9999)
        {
            a[i]=a[i-1];
        }
        else if(i<=99999)
            a[i]=a[i-1]+1;
        else
            a[i]=a[i-1];
    }
    int n;
    cin>>n;
    cout<<a[n]<<endl;
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 10001;

vector<int> par(N);
vector<int> ran(N);

int find(int a){
    if(par[a] == a)
        return a;
    else{
        par[a] = find(par[a]);
        return par[a];
    }
}

void merge(int a, int b){
    if(ran[find(a)] < ran[find(b)]){
        par[find(a)] = find(b);
    }
    else if(ran[find(b)] < ran[find(a)]){
        par[find(b)] = find(a);
    }
    else{
        par[find(b)] = find(a);
        ran[find(a)] += 1;
    }
}


int main(){
    
    int n, q;
    cin >> n >> q;
    
    for(int i = 0; i < n; i++){
        par[i] = i;
        ran[i] = 0;
    }
    
    for(int i = 0; i < q; i++){
        int c, x, y;
        cin >> c >> x >> y;
        if(c == 0){
            merge(x, y);
        }
        else{
            if(find(x) == find(y))
                cout << 1 <<endl;
            else
                cout << 0 <<endl;
        }
    }
    
}

Measured memory_bytes: 3188
s = gets.chomp
t = gets.chomp

n = s.length

ss = Hash.new()

s = s + s
s.chars.each_with_index do |c, idx|
    ss[c] = Array.new unless ss[c]
    ss[c].push(idx)
end

ss.each do |k, v|
    ss[k].sort!
end

ans = 0
cur = n-1

t.chars.each do |c|
    unless ss[c]
        ans = -1
        break
    end

    r = ss[c].bsearch_index{|x| x > cur}
    nex = r ? ss[c][r] : ss[c].last

    nex %= n
    step = (nex - cur + n) % n
    step = n if step == 0

    ans += step
    cur = nex
end

puts ans


Measured memory_bytes: 22136
#include<bits/stdc++.h>
using namespace std;
int a[100002];
inline bool cmp(int x,int y){return x>y;}
int main(){
	int n,ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++) if(i+1>a[i+1]){
		for(int j=i+1;a[j]==i;j++) ans^=1;
		ans|=(a[i]-i)&1,printf(ans?"First":"Second");
		return 0;
	}
}

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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define repr(i,a,b) for(int i=(int)(a-1);i>=b;i--)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout << #x" = " << x << endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define INF INT_MAX/3

int a[100010];

int main(){
  cin.sync_with_stdio(false);
  int n;
  cin >> n;
  rep(i, n) cin >> a[i];
  sort(a, a + n);
  int num = 0, cnt = 0, ans = 0;
  a[n + 1] = 1e9 + 1;
  rep(i, n + 1) {
    if (num != a[i]) {
      if (num <= cnt) ans += (cnt - num);
      else ans += cnt;
      num = a[i];
      cnt = 1;
    } else {
      cnt++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 640
import sys
from collections import Counter

N = int(input())
A = list(map(int, sys.stdin.readline().rsplit()))
mod = 10 ** 9 + 7

C = Counter(A)
if N % 2 == 0:
    if not all([i == 2 for i in C.values()]):
        print(0)
    else:
        print(pow(2, N // 2, mod))
else:
    for i, v in C.items():
        if v > 2:
            print(0)
            exit()
        elif i != 0 and v == 1:
            print(0)
            exit()
        elif i == 0 and v > 1:
            print(0)
            exit()
    if 0 in C:
        print(pow(2, N // 2, mod))
    else:
        print(0)


Measured memory_bytes: 20600
#include<stdio.h>

#define INF 100000000

int h, w;
char s[50][50];
int dp[50][50];

int min(int a, int b)
{
    if(a > b) return b;
    else return a;
}

int main()
{
    int i, j, k;
    char buf[64];
    int white_num = 0;
    int ans;
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, -1, 0, 1};
    int x, y;
    int cnt = 0;

    fgets(buf, sizeof(buf), stdin);
    sscanf(buf, "%d %d", &h, &w);

    for(i = 0; i < h; i++){
        fgets(buf, sizeof(buf), stdin);
        for(j = 0; j < w; j++) s[i][j] = buf[j];
    }

    for(i = 0; i < h; i++) for(j = 0; j < w; j++)
        if(s[i][j] == '.') white_num++;

    for(i = 0; i < h; i++) for(j = 0; j < w; j++)
        dp[i][j] = INF;
    dp[0][0] = 0;
    while(dp[h-1][w-1] == INF){
        for(i = 0; i < h; i++) for(j = 0; j < w; j++){
            if(s[i][j] == '#') continue; 
            for(k = 0; k < 4; k++){
                x = j + dx[k]; y = i + dy[k];
                if(0 <= x && x < w && 0 <= y && y < h && s[y][x] == '.'){
                    dp[i][j] = min(dp[i][j], dp[y][x]+1);
                }
            }
            cnt++;
        }
        if(cnt > INF) break;
    }

    if(dp[h-1][w-1] == INF) ans = -1;
    else ans = white_num - (dp[h-1][w-1]+1);
    printf("%d\n", ans);

    return 0;
}

Measured memory_bytes: 128
from enum import Enum
import sys
import math

# 0:中央 1:南 2:東 3:西 4:北 5:裏側


class Dice():

    def __init__(self):
        self.number = [i for i in range(6)]
        self.work = [i for i in range(6)]
        self.order = 'NNNNWNNNWNNNENNNENNNWNNN'

    def setNumber(self, n0, n1, n2, n3, n4, n5):
        self.number[0] = n0
        self.number[1] = n1
        self.number[2] = n2
        self.number[3] = n3
        self.number[4] = n4
        self.number[5] = n5

    def roll(self, loc):
        for i in range(6):
            self.work[i] = self.number[i]

        if loc == 'E':
            self.setNumber(self.work[3], self.work[1], self.work[0],
                           self.work[5], self.work[4], self.work[2])
        elif loc == 'N':
            self.setNumber(self.work[1], self.work[5], self.work[2],
                           self.work[3], self.work[0], self.work[4])
        elif loc == 'S':
            self.setNumber(self.work[4], self.work[0], self.work[2],
                           self.work[3], self.work[5], self.work[1])
        elif loc == 'W':
            self.setNumber(self.work[2], self.work[1], self.work[5],
                           self.work[0], self.work[4], self.work[3])

    def query(self, another_dice):

        self.save_data = [i for i in range(6)]
        # 元の値の保存
        for i in range(len(self.number)):
            self.save_data[i] = self.number[i]

        is_same_face = False
        for i in range(len(self.order)):
            self.roll(self.order[i])
            if [f == s for f, s in zip(self.number, another_dice)].count(False) == 0:
                is_same_face = True
                break

        # 元の値の復元
        for i in range(len(self.number)):
            self.number[i] = self.save_data[i]
        return is_same_face


query_num = int(input())
dices = []
for _ in range(query_num):
    dice = Dice()
    table = list(map(int, input().split()))
    dice.setNumber(table[0], table[1], table[2],
                   table[3], table[4], table[5])
    dices.append(dice)

for i in range(query_num):
    for q in range(query_num):
        if i == q:
            continue
        first_dice = dices[i]
        second_dice = dices[q]
        if first_dice.query(second_dice.number) == True:
            print("No")
            sys.exit()
print("Yes")



Measured memory_bytes: 6396
N = int(input())
alphabet_list = [chr(i) for i in range(97, 97 + 26)]

def num2alpha(num):
    if num <= 26:
        return chr(64 + num)
    elif num % 26 == 0:
        return num2alpha(num // 26 - 1) + chr(90)
    else:
        return num2alpha(num // 26) + chr(64 + num % 26)

print(num2alpha(N).lower())

Measured memory_bytes: 61820
n,d=map(int,input().split())
a=[list(map(int,input().split()))for i in range(n)]
t=0
for i in range(n-1):
    for j in range(i+1,n):
        s=0
        for h in range(d):
            s+=(a[i][h]-a[j][h])**2
        else:
            if s==int(s**0.5)**2:
                t+=1
print(t)

Measured memory_bytes: 38384
#include <iostream>

using namespace std;

int main() {

char c[6] = {'A','B','C','D','E','F'};
int num[6] = {1,2,3,4,5,6};

char x,y;
int xnum,ynum;

cin >> x >> y;

for(int i = 0;i < 6;i++){
    if(x == c[i]) xnum = num[i];
}
for(int i = 0;i < 6;i++){
    if(y == c[i]) ynum = num[i];
}

if(x < y) cout << '<' << endl;
else if(x > y) cout << '>' << endl;
else cout << '=' << endl;

return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <string>
#include <map>
#include <stack>
#include <queue>
//#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
#define urept(soeji, start, n) for (int soeji = start; soeji < n; soeji++)
#define drept(soeji, start, n) for (int soeji = start; soeji > n; soeji--)

//input
int main(void)
{
    int N;
    cin >> N;
    //int p[N];
    //int q[N];
    vector<int> cp, p, q;
    for (int i = 0; i < N; i++)
    {
        int tmp;
        cin >> tmp;
        p.push_back(tmp);
    }
    for (int i = 0; i < N; i++)
    {
        int tmp;
        cin >> tmp;
        q.push_back(tmp);
    }
    for (int i = 0; i < N; i++)
    {
        cp.push_back(p[i]);
    }
    sort(cp.begin(), cp.end());
    int cnt1 = 0;
    do
    {
        cnt1++;
        if (cp == p)
        {
            break;
        }
    } while (next_permutation(cp.begin(), cp.end()));
    sort(cp.begin(), cp.end());
    int cnt2 = 0;
    do
    {
        cnt2++;
        if (cp == q)
        {
            break;
        }
    } while (next_permutation(cp.begin(), cp.end()));
    cout << abs(cnt1 - cnt2) << endl;
    return 0;
}


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

int main(){
    int n;
    cin >> n;

    const int N = 10;

    char ch[N];

    vector<string> s(n,"");

    for(int i = 0; i < n; ++i){//cout << "a";
        for(int j = 0; j < N; ++j){
            cin >> ch[j];
        }

        sort(ch,ch + N);

        for(int j = 0; j < N; ++j){
            s[i] += ch[j];
        }
    }
    LL ans = 0;
    sort(s.begin(),s.end());
    LL l = 0;
    LL r = l + 1;
    cerr << endl;
    //for(int i = 0; i < n; ++i){
        //cerr << s[i] << endl;
    //}
    while(r < n && l < n){//cout << "b";
        if(s[l] == s[r]){
            r++;
        }else{//cerr << r - l << endl;
            ans += (r - l)*(r - l - 1)/2;
            l = r;
            r++;
        }
    }
    //cerr << r - l << endl << endl;
    ans += (r - l)*(r - l - (LL)1)/(LL)2;

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 7296
#[allow(unused_imports)]
use std::cmp::{min,max};
#[allow(unused_imports)]
use std::collections::BTreeMap;
#[allow(unused_imports)]
use std::ops::*;
#[allow(unused_imports)]
use std::collections::BinaryHeap;

fn ccw(x: (i64,i64), y: (i64,i64), z: (i64,i64)) -> i64 {
    ((y.0-x.0)*(z.1-x.1) - ((y.1-x.1)*(z.0-x.0))).signum()
}

fn norm(x: (i64,i64)) -> f64 {
    ((x.0*x.0 + x.1*x.1) as f64).sqrt()
}

fn dot(x: (i64,i64), y: (i64,i64)) -> i64 {
    x.0*y.0 + x.1*y.1
}

fn arg(x: (i64,i64), y: (i64,i64)) -> f64 {
    (dot(x,y) as f64 / norm(x) / norm(y)).acos()
}

fn convex(ps: &Vec<(i64,i64)>) -> Vec<(i64,i64)> {
    let qs = {
        let mut qs = ps.clone();
        qs.sort();
        qs
    };
    let n = qs.len();
    let mut u = vec![];
    let mut l = vec![];
    u.push(qs[0]);
    u.push(qs[1]);
    l.push(qs[n-1]);
    l.push(qs[n-2]);
    for i in 2..n {
        while u.len() >= 2 && ccw(u[u.len()-2], u[u.len()-1], qs[i]) > 0 {
            u.pop();
        }
        u.push(qs[i]);
    }
    for i in (0..n-2).rev() {
        while l.len() >= 2 && ccw(l[l.len()-2], l[l.len()-1], qs[i]) > 0 {
            l.pop();
        }
        l.push(qs[i]);
    }
    for i in 1..u.len()-1 {
        l.push(u[i]);
    }
    let mut map = BTreeMap::new();
    use std::f64;
    for j in 0..l.len() {
        let i = (j + l.len() - 1) % l.len();
        let k = (j + 1) % l.len();
        let a = (f64::consts::PI - arg((l[i].0-l[j].0, l[i].1-l[j].1), (l[k].0-l[j].0,l[k].1-l[j].1))) / f64::consts::PI / 2.0;
        map.insert(l[j], a);
    }
    l
}

fn main() {
    let n = read_i64() as usize;
    let ps = {
        let mut ps = vec![];
        for _ in 0..n {
            let xs = read_vec_i64();
            ps.push((xs[0], xs[1]));
        }
        ps
    };
    let l = convex(&ps);
    let mut map = BTreeMap::new();
    use std::f64;
    for j in 0..l.len() {
        let i = (j + l.len() - 1) % l.len();
        let k = (j + 1) % l.len();
        let a = (f64::consts::PI - arg((l[i].0-l[j].0, l[i].1-l[j].1), (l[k].0-l[j].0,l[k].1-l[j].1))) / f64::consts::PI / 2.0;
        map.insert(l[j], a);
    }
    for i in 0..n {
        match map.get(&ps[i]) {
            Some(res) => {
                println!("{}", res);
            }
            None => {
                println!("0");
            }
        }
    }
}

#[allow(dead_code)]
fn read_line() -> String {
    let mut ret = String::new();
    std::io::stdin().read_line(&mut ret).ok();
    ret.pop();
    return ret;
}

#[allow(dead_code)]
fn read_i64() -> i64 {
    let ss = read_line();
    return ss.parse::<i64>().unwrap();
}

#[allow(dead_code)]
fn read_vec_i64() -> Vec<i64> {
    let mut res = vec![];
    let ss = read_line();
    for ts in ss.split_whitespace() {
        let x = ts.parse::<i64>().unwrap();
        res.push(x);
    }
    return res;
}

use std::fmt::Display;
#[allow(dead_code)]
fn write_vec<T: Display>(xs: &Vec<T>) {
    if xs.len() == 0 {
        println!("");
        return;
    }
    print!("{}", xs[0]);
    for i in 1..xs.len() {
        print!(" {}", xs[i]);
    }
    println!("");
}


Measured memory_bytes: 4476
#include <iostream>
#include <cmath>

int main()
{
  int a, b, c, d;
  std::cin >> a >> b >> c >> d;

  bool can_direct = std::abs(c - a) <= d;
  bool can_indirect = (std::abs(b - a) <= d &&
                       std::abs(c - b) <= d);

  int can = can_direct || can_indirect;
  std::cout << (can ? "Yes" : "No") << std::endl;

  return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <fstream>
#include <iomanip>

#include <vector>
#include <set>
#include <bitset>
#include <map>
#include <deque>
#include <string>

#include <algorithm>
#include <numeric>
#include <random>

#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>

using namespace std;

#define forn(i, n) for (ll i = 0; i < (ll) (n); ++i)
#define sz(a) static_cast<int>((a).size())
#define endl '\n'

using ll = long long;

const ll INF = static_cast<ll>(1e9) + 7;
const int MAXN = static_cast<int>(1e2) + 17;

int n;

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

    return true;
}

void solve() {
    if (n < 1200) {
        cout << "ABC\n";
    } else if (n < 2800) {
        cout << "ARC\n";
    } else {
        cout << "AGC\n";
    }
}

int main() {
    cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::mt19937 rand('S' + 'E' + 'R' + 'E' + 'Z' + 'H' + 'K' + 'A');

    while (read())
        solve();

    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <cstdio>
#include <string.h>
#define rep(i,n) for (int i = 0; i < (int)n; i++)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<pi, pi> pp;
typedef pair<ll, ll> pl;
double PI = 3.1415926535897932;
const double EPS = 1e-9;
const ll MOD = 1000000007;
const int inf = 1 << 30;
const ll linf = 1LL << 60;

int k;
int ans[500][500];

int main() {
    cin >> k;
    if (k == 1) {
        cout << 1 << endl << 1 << endl;
        return 0;
    }
    int n = (k%4==0?k:k+4-k%4)/2;
    cout << n << endl;
    rep(i,n) {
        rep(j,n) {
            if (i%2 == 0) ans[i][j] = (n+j-i)%n;
            else ans[i][j] = (n+j-i)%n + n;
            if (ans[i][j] >= k) ans[i][j] %= n;
            cout << ans[i][j]+1;
            if (j == n-1) cout << endl;
            else cout << " ";
        }
    }
}

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

char f(char sw1, char sw2, char tr) {
	if ((sw2 == 'S' && tr == 'o') || (sw2 == 'W' && tr == 'x'))return sw1;
	return sw1 == 'S' ? 'W' : 'S';
}

int main() {
	int n; string s; cin >> n >> s;
	string d[] = { "SS","SW","WS","WW" };
	for (int i = 0; i < 4; i++) {
		string ans = d[i];
		for (int j = 0; j < n - 2; j++) {
			ans += f(ans[j], ans[j + 1], s[j + 1]);
		}
		if (f(ans[n - 2], ans[n - 1], s[n - 1]) != ans[0])continue;
		if (f(ans[n - 1], ans[0], s[0]) != ans[1])continue;
		cout << ans << endl;
		return 0;
	}
	cout << -1 << endl;

	return 0;
}

Measured memory_bytes: 776
n,m = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(n)]
ab = sorted(ab)
cost = 0
for i in range(len(ab)):
  if m > 0:
    cost += ab[i][0] * min(ab[i][1], m)
    m -= min(ab[i][1],m)
  else:
    break
print(cost)

Measured memory_bytes: 17756