akhauriyash/Code-Regression huggingface dataset:
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
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;}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const ll mod=1e9+7;
const int inf=1<<30;

ll a[200010];
ll s[200010];

int main(){
  ll n,p; cin >> n >> p;
  string t; cin >> t;
  reverse(all(t));
  if(p==2){
    ll ans=n*(n+1)/2;
    rep(i,n){
      if((t[i]-'0')%2==1) ans-=n-i;
    }
    cout << ans << endl;
    return 0;
  }
  if(p==5){
    ll ans=n*(n+1)/2;
    rep(i,n){
      if(t[i]!='0'&&t[i]!='5') ans-=n-i;
    }
    cout << ans << endl;
    return 0;
  }
  ll x10=1;
  rep(i,n){
    a[i]=(t[i]-'0')*x10%p;
    x10*=10; x10%=p;
  }
  rep(i,n){
    s[i+1]=(s[i]+a[i])%p;
  }
  map<ll,ll> mp;
  rep(i,n+1){
    mp[s[i]]++;
  }
  ll ans=0;
  for(auto c:mp){
    ans+=c.second*(c.second-1)/2;
  }
  cout << ans << endl;
}


Measured memory_bytes: 4100
s = sorted(input())
t = sorted(input(), reverse = True)
if len(s) >= len(t):
  lenth = len(t)
else:
  lenth = len(s)
count = 0
while (s[count] == t[count]) and (lenth - 1 > count):
  count += 1
if s[count] == t[count]:
  if len(s) < len(t):
    print("Yes")
  else:
    print("No")
else:
  if s[count] < t[count]:
    print("Yes")
  else:
    print("No")


Measured memory_bytes: 3064
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	A = inputInt()
	T = input()

	ST = T.split()

	ans = ""
	for i in range(A):
		ans += ST[0][i]
		ans += ST[1][i]

	print(ans)



if __name__ == "__main__":
	main()


Measured memory_bytes: 38256
a = int(input())
b = int(input())
c = int(input())
x = int(input())
cnt = 0
for ai in range(a+1):
    for bi in range(b+1):
        for ci in range(c+1):
            if 500*ai + 100*bi + 50 *ci ==x:
                cnt += 1
print(cnt)

Measured memory_bytes: 3060
import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		int n = stdIn.nextInt();
		int q = stdIn.nextInt();

		Queue<String> queP = new LinkedList<String>();
		Queue<Integer> queT = new LinkedList<Integer>();

		int timeCount = 0;

		for (int i=0; i<n; i++) {
			queP.add(stdIn.next());
			queT.add(stdIn.nextInt());
		}

		while (queP.size() != 0) {
			if (queT.peek() - q >0) {
				queP.add(queP.poll());
				queT.add(queT.poll()-q);
				timeCount += q;
			}else {
				timeCount += queT.poll();
				System.out.println(queP.poll()+" "+timeCount);
			}
		}
	}
}

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

inline long long read(){
    long long s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9'){
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9'){
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * w;
}

int main(){
    int x1 = read(), x2 = read(), x3 = read(), x4 = read(), x5 = read();
    if (x1 == 0) puts("1");
    else if(x2 == 0) puts("2");
    else if(x3 == 0) puts("3");
    else if(x4 == 0) puts("4");
    else puts("5");
    return 0;
}

Measured memory_bytes: 3628
def main():
    n, m = map(int, input().split())
    ABs = [list(map(int, input().split())) for _ in range(m)]
    anss = [0]*n
    for AB in ABs:
        anss[AB[0]-1] += 1
        anss[AB[1]-1] += 1
    for ans in anss:
        print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 2940
//BadWaper gg
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<deque>
#include<bitset>
#include<map>
#include<set>
#define inf 1e9
#define eps 1e-6
#define mp make_pair
#define N 2010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
	char ch=getchar();
	ll s=0,w=1;
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
	return s*w;
}
char s[N];
int n;
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%s",s+1);
	n=strlen(s+1);
	int vis[4]={0,0,0,0};
	for(register int i=1;i<=n;i++)
	{
		if(s[i]=='N')vis[0]=1;
		if(s[i]=='S')vis[1]=1;
		if(s[i]=='W')vis[2]=1;
		if(s[i]=='E')vis[3]=1;
	}
	(((vis[0]&&vis[1])||((!vis[0])&&(!vis[1])))&&((vis[2]&&vis[3])||((!vis[2])&&(!vis[3]))))?puts("Yes"):puts("No");
	return 0;
}


Measured memory_bytes: 3764
/*
    Author: isaf27 (Ivan Safonov)
*/

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

//defines
typedef long long ll;
typedef double ld;
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define fast_read cin.sync_with_stdio(0)
#define nul point(0, 0)
#define str_to_int(stroka) atoi(stroka.c_str())
#define str_to_ll(stroka) atoll(stroka.c_str())
#define str_to_double(stroka) atof(stroka.c_str())
#define what_is(x) cerr << #x << " is " << x << endl
#define solve_system int number; cin >> number; for (int i = 0; i < number; i++) solve()
#define solve_system_scanf int number; scanf("%d", &number); forn(i, 0, number) solve()

//permanent constants
const ld pi = 3.141592653589793238462643383279;
const ld log23 = 1.58496250072115618145373894394781;
const ld eps = 1e-10;
const ll INF = 1e18 + 239;
const ll prost = 239;
const int two = 2;
const int th = 3;
const ll MOD = 1e9 + 7;
const ll MOD2 = MOD * MOD;
const int BIG = 1e9 + 239;
const int alf = 26;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
const int dig = 10;
const string str_alf = "abcdefghijklmnopqrstuvwxyz";
const string str_alf_big = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int digarr[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
const int bt = 31;

//easy functions
template< typename T >
inline T gcd(T a, T b) { return a ? gcd(b % a, a) : b; }
template< typename T >
inline T lcm(T a, T b) { return (a / gcd(a, b)) * b; }
inline bool is_down(char x) { return ('a' <= x && x <= 'z'); }
inline bool is_upper(char x) { return ('A' <= x && x <= 'Z'); }
inline bool is_digit(char x) { return ('0' <= x && x <= '9'); }
ll power(ll a, int k)
{
    ll ans = 1;
    while (k)
    {
        if (k & 1) ans = (ans * a) % MOD;
        ans = (ans * ans) % MOD;
        k >>= 1;
    }
    return ans;
}

//random
mt19937 rnd(239);

//constants
const int M = 3 * 1e5 + 239;
const int N = 2 * 1e3 + 239;
const int L = 20;
const int T = (1 << 19);
const int B = trunc(sqrt(M)) + 1;
const int X = 10;

// Code starts here

int n, a[M];
ll sum[M];
int pref[M];

int main()
{   //*
    #ifdef ONPC
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif /**/
    fast_read;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    pref[0] = 0;
    sum[0] = 0;
    for (int i = 0; i < n; i++)
    {
        sum[i + 1] = sum[i] + (ll)a[i];
        pref[i + 1] = pref[i] ^ a[i];
    }
    ll ans = 0;
    for (int i = 0; i < n; i++)
    {
        int l = i;
        int r = n;
        while (r - l > 1)
        {
            int h = (l + r) >> 1;
            if ((sum[h + 1] - sum[i]) != (pref[h + 1] ^ pref[i]))
                r = h;
            else
                l = h;
        }
        ans += (r - i);
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 4224
/*
*          Name : chaitanya
*
*     Institute : ANITS,Visakhapatnam
*
*/
#include<cstdio>
#include<iostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<complex>
#include<cstring>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<numeric>
#include<limits>
#include<climits>
#include<cfloat>
#include<functional>
#include<iterator>
#include <random>
#define infy  1000000000
#define all(x) begin(x),end(x)
#define ll long long int
#define ff first
#define ss second
#define pb push_back
const ll m = 1000000007;
#pragma GCC optimization ("O3")
const int N = 1000010;
using namespace std;
vector<string> vec_splitter(string s) {
  s += ',';
  vector<string> res;
  while(!s.empty()) {
    res.push_back(s.substr(0, s.find(',')));
    s = s.substr(s.find(',') + 1);
  }
  return res;
}
void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
  if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
  stringstream ss; ss << H;
  cerr << args[idx] << " = " << ss.str();
  debug_out(args, idx + 1, LINE_NUM, T...);
}
#ifndef ONLINE_JUDGE
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

ll f[2000010];

ll lcm(ll a,ll b)
{
  return (a*b)/__gcd(a,b);
}
ll binpow(ll a, ll b) {
     ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
 
ll find_ncr(ll n, ll r)
{
    ll m1=max(r,n-r);
    ll i,j,s,d=1,k;
    s=1;
 
    for(i=m1+1;i<=n;i++)
    {
        s=((s%m)*(i%m))%m;
    }
 
    m1=min(r,n-r);
 
    for(i=1;i<=m1;i++)
    {
        k=binpow(i,m-2);
        d=((d%m)*(k%m))%m;
    }
 
    k=(s%m*(d%m))%m;
 
    return k;
}

int main()
{
  // int x = -1, y = 10000;
  // double z = 0.2;
  // string s2 = "beginner1010";
  // long long b = 1LL << 60;
    
  // // debug(x, y, z, s, b);
    
  // double aux = 1010.0;
  // string code = "code";
    
  // debug(code + "forces",-aux / 10 * 2.3);
  // freopen("input.txt","r",stdin);
  // freopen("output.txt","w",stdout);
  //ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  int x = (a+d-1)/d;
  int y = (b+c-1)/b;
  if(x >= y)
    cout << "Yes";
  else
    cout << "No";
  return 0;
}


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

using namespace std;

int main()
{
  int n, m, i, win, miss, wcard, cost, takeN;
  vector<int> missPoint;

  cin >> n >> m;

  wcard = 0;

  for (i = 0; i < m; i++)
  {
    cin >> win >> miss;
    if (win >= n)
    {
      wcard++;
    }
    else
    {
      missPoint.push_back(miss - n);
    }
  }

  sort(missPoint.begin(), missPoint.end());

  cost = 0;
  takeN = (m - 1) - wcard;
  for (i = 0; i < takeN; i++)
  {
    cost += missPoint[i];
  }

  cout << cost << endl;

  return 0;
}


Measured memory_bytes: 3160
#include<bits/stdc++.h>
#define ll long long int
#define FOR(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n)
using namespace std;

int main()
{
	int n[3];
	cin >> n[0] >> n[1] >> n[2];
	sort(n,n+3);
	cout << n[0] << " " << n[1] << " " << n[2] << "\n";
}

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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<int,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

int main(){
	string s;
	cin >> s;
	for(int i = 0 ; i+1 < s.size() ; i ++){
		if(s[i] == 'A' && s[i+1] == 'C'){
			puts("Yes");
			return 0;
		}
	}
	puts("No");
}



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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

const int MAXN = 2e5 + 5;

int mex[MAXN], gr[MAXN];

char s[MAXN];

int to[MAXN][2], d[MAXN];

void dfs(int s){
}

void solve(){
	int n, root = 1, top = 2;
	ll l;
	scanf("%d%lld", &n, &l);
	REP(i, 0, n){
		scanf("%s", &s[0]);
		int cur = root;
		for(int j = 0; s[j]; j++){
			int ind = s[j] - '0';
			if (to[cur][ind]){
				cur = to[cur][ind];
			} else {
				to[cur][ind] = top;
				d[top] = d[cur] + 1;
				cur = top;
				top++;
			}
		}
	}
	ll gr = 0ll;
	REP(i, 1, top){
		if (to[i][0] && !to[i][1] || !to[i][0] && to[i][1]){
			ll v = d[i];
			v = l - v;
			//cout << v << endl;
			if (v <= 0){
				continue;
			}
			ll tmp = 1;
			for(; v % 2 == 0; v /= 2){
				tmp *= 2ll;
			}
			gr ^= tmp;
		}
	}
	if (gr){
		printf("Alice\n");
	} else {
		printf("Bob\n");
	}
	
	/*REP(i, 1, 100){
		mex[0] = i;
		int x = 0;
		for(int j = i - 1; j > 0; j--){
			x ^= gr[j];
			mex[x] = i;
		}
		for(int j = 0; ; j++){
			if (mex[j] != i){
				gr[i] = j;
				break;
			}
		}
		printf("%d %d\n", i, gr[i]);
	}*/
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 3456
#include<iostream>

using namespace std;

int main(){
  int a;
  cin>> a;
  
  if(10 > a)cout << a << endl;
  else if(100 > a) cout << 9 << endl;
  else if(1000 > a) cout << a-90 << endl;
  else if(10000 > a) cout << 909 << endl;
  else if(100000 > a)cout << a-9090 << endl;
  else if(a == 100000)cout << 90909 << endl;
  return 0;
}

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

bool v[100010];

long long joulist[100010];

long long jou(int N){
    if(N==0) return joulist[0]=1;
    else if(joulist[N]!=0) return joulist[N];
    else return joulist[N]=(jou(N-1)*3)%1000000007;
}

long long search(int N){
    bool x=v[N-1];
    if(N==1){
        if (x) return 3;
        else return 1;
    }
    
    else{
        if(x) return (jou(N-1)+2*search(N-1))%1000000007;
        else return search(N-1);
    }
}

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

    int N=S.size();

    for(int i=0;i<N;i++) {
        if(S.at(N-1-i)=='0') v[i]=false;
        else v[i]=true;
    }

    
    cout<<search(N)<<endl;
}

Measured memory_bytes: 2944
package main

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

var rs = bufio.NewReaderSize(os.Stdin, 1000000)

func readLine() string {
	buf := make([]byte, 0, 1000000)
	for {
		l, p, e := rs.ReadLine()
		if e != nil {
			panic(e)
		}
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}

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

func main() {
	var n, t, ti, ti_plus1 int
	fmt.Scan(&n, &t)

	s := readLine()
	ti_list := strings.Split(s, " ")

	total := t

	for i := 0; i < n; i++ {
		ti_plus1, _ = strconv.Atoi(ti_list[i])
		total += min(ti_plus1-ti, t)
		ti = ti_plus1
	}
	fmt.Println(total)
}


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

using namespace std;

#define SZ(x) (int)(x.size())

using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

int f(int a) {
  return (a * a + 4) / 8;
}

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

  int n, k; cin >> n >> k;
  vi l(n);
  for(int i=0;i<n;++i) {
    cin >> l[i];
  }
  sort(l.rbegin(), l.rend());
  int ans = 0;
  for(int i=0;i<k;++i) {
    ans += l[i];
  }
  cout << ans << endl;
}


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

using namespace std;

int main()
{
    long long int k , a , b;
    cin>>k>>a>>b;
    for(int i = a ; i <= b ; i++)
    {
        if(i%k==0)
        {
            cout<<"OK"<<endl;
            return 0;
        }
    }
    cout<<"NG"<<endl;
}

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

int64_t ncr (int64_t n, int64_t r) {
    double res = 1;
    for (int64_t i = 1; i <= r; ++i) 
        (res *= (n - i + 1)) /= (1.0 * i);
    return int64_t(res);
}

signed main () {
    int n, p;
    cin >> n >> p;
    int odd = 0, even = 0;
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        if (a & 1)
            ++odd;
        else
            ++even;
    }
    int64_t twos = (int64_t(1) << int64_t(even)), res;
    if (p) {
        res = 0;
        for (int i = 1; i <= odd; i += 2) 
            res += ncr(odd, i);
    }
    else {
        res = 1;
        for (int i = 2; i <= odd; i += 2) 
            res += ncr(odd, i);
    }
    cout << twos * res << '\n';
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const ll inf = (ll)1e9;
const ll mod = (ll)1e9 + 7;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

#define print(s) cout << s;
#define println(s) cout << s << endl;
#define printd(s, f) cout << fixed << setprecision(f) << s << endl;


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

	ll res = 0;
	for (int i = 0; i <= n; i++)
	{
		ll add = 0;
		for (int j = i; j > 0; j /= 10)
		{
			add += j % 10;
		}
		if (a <= add && add <= b)
		{
			res += i;
		}
	}

	println(res);
}

Measured memory_bytes: 256
n, c = map(int, input().split())

x = [0 for _ in range(n + 2)]
v = [0 for _ in range(n + 1)]
for i in range(n):
    x[i + 1], v[i + 1] = map(int, input().split())

x[n + 1] = c

left = [0 for _ in range(n + 1)]
right = [0 for _ in range(n + 1)]
left_rev = [0 for _ in range(n + 1)]
right_rev = [0 for _ in range(n + 1)]

left_temp = 0
right_temp = 0
for i in range(1, n + 1):
    left[i] = left[i - 1] + v[i] - (x[i] - x[i - 1])
    if left_temp < left[i] - x[i]:
        left_rev[i] = left[i] - x[i]
        left_temp = left_rev[i]
    else:
        left_rev[i] = left_temp
    right[i] = right[i - 1] + v[n - i + 1] - (x[n - i + 2] - x[n - i + 1])
    if right_temp < right[i] - (c - x[n - i + 1]):
        right_rev[i] = right[i] - (c - x[n - i + 1])
        right_temp = right_rev[i]
    else:
        right_rev[i] = right_temp

result = 0
for i in range(1, n + 1):
    result = max( (left[i] + right_rev[n - i]) , (right[i] + left_rev[n - i]) , result )

print(result)

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

using namespace std;
int main(){
    int A;
    int B;
    int kuchi;
    int tap;
    cin >> A >> B;
    
    kuchi = 1;
    while(kuchi<B){
        kuchi+=A;
        kuchi--;    
        tap++;
    }
    
    cout << tap << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <stdio.h>

using namespace std;

int main(){
	
	double x1,y1,x2,y2;
	cin >> x1 >> y1 >> x2 >> y2;
	
	printf("%.8lf\n", sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));
		
	return 0;
}

Measured memory_bytes: 1236
#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
int main() {
  ios::sync_with_stdio(false);
  int N;
  ll D, A, X, H;
  cin >> N >> D >> A;
  map<ll,ll> m;
  for (int i=0; i<N; i++) {
    cin >> X >> H;
    m[X] = H;
  }
  ll ret = 0;
  priority_queue<P, vector<P>, greater<P> > q;
  ll S = 0;
  for (map<ll,ll>::iterator it = m.begin(); it != m.end(); ++it) {
    while (!q.empty()) {
      P p = q.top();
      if (p.first > it->first) break;
      S -= p.second;
      q.pop();
    }
    ll v = it->second - S * A;
    if (v <= 0) continue;
    ll num = (v + A - 1) / A;
    ret += num;
    ll R = it->first + 2 * D + 1;
    q.push(make_pair(R, num));
    S += num;
  }
  cout << ret << endl;
}

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

using lli = int64_t;

using vi = vector<lli>;

int pred(vi& v, lli n, lli mx, lli b, lli c)
{
    lli t = b * mx;

    lli cnt = 0;

    for(lli i = 0; i < n; i++) if(v[i] > t)
    {
        lli diff = v[i] - t;
        cnt += diff / c + !!(diff % c);
    }

    return cnt <= mx;
}

int main()
{
    ios_base::sync_with_stdio(0);

    lli n, a, b; cin >> n >> a >> b;
    lli c = a - b;

    vi v(n);

    for(lli i = 0; i < n; i++) cin >> v[i];

    lli l = 0, h = INT_MAX;

    while(l < h)
    {
        lli m = (l + h) / 2;

        if(pred(v, n, m, b, c)) h = m;
        else l = m + 1;
    }

    cout << l << endl;
    return 0;
}

Measured memory_bytes: 1024
//package oct30;

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static Scanner io = new Scanner(System.in);

    public static void main(String[] args) {

        int N = io.nextInt();
        io.nextLine();
//        System.out.println("N: " + N);

        ArrayList<Integer> stones = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            stones.add(io.nextInt());
        }
        ArrayList<Integer> min = new ArrayList<>();
        min.add(0);
        min.add(Math.abs(stones.get(0) - stones.get(1)));

        for (int i = 2; i < N; i++) {
            int one = Math.abs(stones.get(i) - stones.get(i-1))+min.get(i-1);
            int two = Math.abs(stones.get(i) - stones.get(i-2))+min.get(i-2);
            min.add(Math.min(one, two));
//            System.out.print("array so far: ");
//            for (int j : min) System.out.print(j + " ");
//            System.out.println();
        }
        System.out.println(min.get(N-1));

    }
}


Measured memory_bytes: 60564
n=int(input())
a=list(map(int,input().split()))

count=0
for i in range(0,10*7):
  keep=0
  for j in range(0,n):
    if a[j]%2==0:
      a[j]=a[j]//2
    else:
      keep=1
  if keep==0:
    count+=1
  else:
    break
print(count)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> iint;
typedef pair<ll,ll> llll;
#define ALL(x) (x).begin(),(x).end()
const ll zero = 0;
const ll INF = 3000000000000000000; //10^18
const int inINF = 1000000000; //10^9
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int main(){
    ll N, K;
    cin >> N >> K;
    vector<ll> P(N);
    vector<ll> C(N);
    for (ll i = 0; i < N; i++) {
        cin >> P[i];
        P[i]--;
    }
    for (ll i = 0; i < N; i++) {
        cin >> C[i];
    }

    ll ans = - INF;
    ll D, l, q, r;
    ll m1, m2;
    vector<ll> s(N);
    ll now, pre;
    for (ll i = 0; i < N; i++) {
        fill(ALL(s), 0);
        pre = i;
        now = P[i];
        s[0] = C[P[i]];
        l = 1;
        while(now != i) {
            pre = now;
            now = P[pre];
            s[l] = s[l-1] + C[now];
            l++;
        }
        D = s[l-1];
        q = K / l;
        r = K % l;
        m1 = -INF;
        m2 = -INF;
        for (ll i = 0; i < r; i++) {
            m1 = max(m1, s[i]);
            m2 = max(m2, s[i]);
        }
        for (ll i = r; i < N; i++) {
            m2 = max(m2, s[i]);
        }

        if( K < l ){
            ans = max(ans, m1);
        }
        else{
            if( D <= 0 ){
                ans = max(ans, m2);
            }
            else{
                ans = max(ans, max(D*q + m1, D*(q-1) + m2));
            }
        }
        


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


}

Measured memory_bytes: 3844
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)


def main():
    N, M = map(int, input().split())
    S = []

    d = [[float("inf")] * N for _ in range(N)]
    L = []
    for i in range(M):
        a, b, c = map(int, input().split())
        d[a - 1][b - 1] = c
        d[b - 1][a - 1] = c
        if a < b:
            L.append((a - 1, b - 1))
        else:
            L.append((b - 1, a - 1))
    for i in range(N):
        d[i][i] = 0
    L = set(L)

    def warshall_floyd(d):
        # d[i][j]: iからjへの最短距離
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    if d[i][j] > d[i][k] + d[k][j]:
                        d[i][j] = d[i][k] + d[k][j]
                        if i < j:
                            if (i, j) in L:
                                S.append((i, j))
                        else:
                            if (j, i) in L:
                                S.append((j, i))
        return d

    warshall_floyd(d)
    print(len(set(S)))


if __name__ == "__main__":
    main()


Measured memory_bytes: 3820
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define fo(i,n) for(ll i=0;i<n;i++)
#define fok(i,k,n) for(ll i=k;i<n;i++)
#define ci(x) cin>>x
#define ci2(x,y) cin>>x>>y
#define co(x) cout<<x<<"\n"
#define co2(x,y) cout<<x<<" "<<y<<"\n"
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define PI 3.1415926535897932384626
#define deb1(x) cout<<#x<<" "<<x<<endl
#define deb2(x,y) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<"\n"
#define deb3(x,y,z) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<" "<<#z<<" "<<z<<"\n"
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;
typedef vector<int>		vi;
typedef vector<ll>		vl;
typedef vector<pii>		vpii;
typedef vector<pll>		vpll;
typedef vector<vi>		vvi;
typedef vector<vl>		vvl;
const int mod = 1000000007;	
int gcd(int a, int b){ if(a==0) return b; return gcd(b%a, a);}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int h ,w,k;
	cin>>h>>w>>k;
	int arr[h][w];
	fo(i,h){
		fo(j,w){
			char tmp;
			ci(tmp);
			if(tmp=='.') arr[i][j]=0;
			else arr[i][j]=1;
		}
	}
	int cnt=0;
	fo(y,(1<<h)){
		fo(x,(1<<w)){
			int black=0;
			fo(i,h){
				if(((y>>i)&1)==0) continue;
				fo(j,w){
					if(((x>>j)&1)==0) continue;
					black+=arr[i][j];
				}
			}
			if(black==k) cnt++;
		}
	}
	co(cnt);
	return 0;
}


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

using namespace std;
using ll = long long;
using ii = pair<int, int>;

const int MAX { 200010 };
const ll MOD { 1000000007 }, oo { 1LL << 62 };

string solve(int N, const string& s)
{
    string ans(s);

    for (size_t i = 0; i < s.size(); ++i)
        ans[i] = (((s[i] - 'A') + N) % 26) + 'A';

    return ans;
}

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

    int N;
    string s;

    cin >> N >> s;

    auto ans = solve(N, s);

    cout << ans << '\n';

    return 0;
}


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

int main() {
    do {
        int n, x;
        int temp = 0;
        cin >> n >> x;
        if (n == 0 && x == 0) break;
        for (int a = 1; a<=n; a++){
            for (int b = (a+1); b<=n; b++){
                for (int c = (b+1); c<=n; c++){
                    int sum = a + b + c;
                    if (sum == x) temp++;
                }
            }
        }
        cout << temp << endl;

    } while(1);

    return 0;
}

Measured memory_bytes: 3100
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List
import qualified Data.Map as M

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
    n <- getInt
    as <- getIntList
    let as' = solveAll as
    let aas = M.fromList as'
    let sumAll = sum $ map (comb2 . snd) as'
    mapM print $ [ sumAll - solveK aas k | k <- as]

solveAll as = map (\i -> (head i, length i)) . group $ sort as

solveK aas k = l - 1
    where (Just l) = M.lookup k aas

comb2 n | n <= 1 = 0
        | otherwise = (n * (n-1)) `div` 2

Measured memory_bytes: 65148
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

class Vec2 {
    private final int x;
    private final int y;

    Vec2(int x, int y){
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }
}

class Solver {

    private final String S;
    private final int Q;
    private final Vec2[] ranges;

    Solver(Scanner in){
        in.nextInt();
        Q = in.nextInt();
        S = in.next();
        ranges = new Vec2[Q];
        for (int i = 0; i < Q; i++) {
            ranges[i] = new Vec2(in.nextInt() - 1, in.nextInt() - 1);
        }
    }

    void solve() {
        char[] chars = S.toCharArray();
        boolean prev = chars[0] == 'A';
        int sum = 0;
        int[] cur = new int[chars.length];
        for (int i = 1; i < chars.length; i++) {
            if (prev && chars[i] == 'C') sum++;
            cur[i] = sum;
            prev = chars[i] == 'A';
        }
        cur[chars.length - 1] = sum;
        System.out.println(Arrays.stream(ranges).mapToInt(p -> cur[p.getY()] - cur[p.getX()]).mapToObj(String::valueOf).collect(Collectors.joining("\n")));
    }
}

class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);

        new Solver(in).solve();

        in.close();
    }
}

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

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<=(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define Eunique(v) v.erase(unique(all(v)),v.end())
#define Eback(s) s.erase(s.end()-1,s.end())
#define rev(v) reverse(all(v))
#define minvec(v) *min_element(all(v))
#define maxvec(v) *max_element(all(v))
#define sumvec(v) accumulate(all(v),0LL)
#define mapmin(v) v.rbegin()->first
#define mapmax(v) v.begin()->first
#define pb push_back
#define pf push_front
#define m_p make_pair
#define DOUBLE fixed << setprecision(15)
#define OK cerr<<"OK\n"
#define OK1 cerr<<"OK1\n"
#define OK2 cerr<<"OK2\n"
#define SIZE(s) (int)s.size()
#define INF ((1LL<<62)-(1LL<<31))
#define zero(x,n) setw(x) << setfill('0') << n
#define endl '\n'

typedef long long ll;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long long> vll;
typedef vector<vll> vvll;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<string> vs;

typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<pair<int,int>> vpii;
typedef vector<pair<ll,ll>> vpll;

const double pi = acos(-1.0);
const ll mod=1000000007;
const ll mod2=998244353;

template<class A, class B>
ostream& operator<<(ostream& ost, const pair<A, B>&p) {
	ost << "{" << p.first << ", " << p.second << "} ";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost, const vector<T>&v) {
	ost << "{";
	for (int i = 0; i<(int)v.size(); i++) {
		if (i)ost << " ";
		ost << v[i];
	}
	ost << "} \n";
	return ost;
}

template<class A, class B>
ostream& operator<<(ostream& ost, const map<A, B>&v) {
	ost << "{";
	for (auto p:v) {
		ost << "{" << p.first << ", " << p.second << "} ";
	}
	ost << "} ";
	return ost;
}

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;}

void YES(bool b) {cout << ((b)?"YES\n":"NO\n");}
void Yes(bool b) {cout << ((b)?"Yes\n":"No\n");}
void yes(bool b) {cout << ((b)?"yes\n":"no\n");}
void Yay(bool b) {cout << ((b)?"Yay!\n":":(\n");}

ll powmod(ll a,ll b){ll c=1; while(b>0){ if(b&1){ c=a*c%mod; } a=a*a%mod; b>>=1; } return c;}
ll gcd(ll x, ll y) {return __gcd(x,y);}
ll lcm(ll x, ll y) {return x/__gcd(x,y)*y;}

int main()
{
	ll n,ans=INF;
	string s;
	cin >> n >> s;
	vll l(n+1),r(n+1);
	rep(i,n){
		if(s[i]=='#') l[i+1]++;
		if(s[n-i-1]=='.') r[n-i-1]++;
		l[i+1]+=l[i];
		r[n-i-1]+=r[n-i];
	}
	rep(i,n) chmin(ans,l[i]+r[i+1]);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3716
#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <deque>
#include <cmath>
#include <stack>
#include <queue>
#include <string>
#include <iomanip>
#include <cstring>
#include <climits>
#include <cstdio>
 
#define nl '\n'
 
using namespace std;
 
long long s, x, t, y;

int main(){

    cin >> s;

    set<long long> se;

    x = s;

    se.insert(x);

    while(true){
        t = se.size();
        if(x%2 == 0){
            x = x/2;
            se.insert(x);
        } else {
            x = (3*x)+1;
            se.insert(x);
        }
        y++;

        if(t == se.size()){
            cout << y+1;
            return 0;
        }

    }


}
 
//g++ -std=c++14 comp.cpp -o b; ./b.exe
//g++ -std=c++14 comp.cpp && ./a.out
 
//Surely this will AC

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007
#define deb(x) cerr << "\n" \
                    << #x << "=" << x << "\n";
#define deb2(x, y) cerr << "\n"                   \
                        << #x << "=" << x << "\n" \
                        << #y << "=" << y << "\n";
#define w(x) \
  int x;     \
  cin >> x;  \
  while (x--)

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin>>n;
  string s;
  cin>>s;
  int red = 0;
  for(auto i:s)
    if(i == 'R')
      red ++;
  int ans = 0;
  for(int i=0;i<red;i++) {
    if(s[i] != 'R')
      ans++;
  }
  cout<<ans;
  return 0;
}

Measured memory_bytes: 3764
#include<stdio.h>
#define N 100000
#define Q 50000

int  binarySearch(int);
  int n,s[N];  
int main(){
  int i,q,l,cnt = 0;
  int t[Q];
  
  scanf("%d",&n);

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

  for(i=0;i<q;i++){
      scanf("%d",&t[i]);
  }
  for(i=0;i<q;i++){
  l = binarySearch(t[i]);
  if(l > 0) cnt++;
  }
  printf("%d\n",cnt);

  return 0;
}
int  binarySearch(int key){
  int left,right,mid;
  left = 0;
  right = n;
  while(left < right){
    mid = (left + right) / 2;
    if(s[mid] == key) return mid;
    else if(key < s[mid]) right = mid;
    else left = mid +1;
  }
    return 0;
  }
    
 

  

Measured memory_bytes: 1180
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)

int main() {
    ll n, k;
    cin >> n >> k;
    ll a = 1;
    rep(i, 0, n) {
        if(2 * a < a + k) a *= 2;
        else a += k;
    }
    cout << a << endl;
    return 0;
}

Measured memory_bytes: 3560
#include<cstdio>
#include <string>
main(){int e;while(scanf("%d",&e)&&e){int m=1<<30;for(int z=0,c=0;c<=e;c=++z*z*z)for(int y=0,b=0;c+b<=e;b=++y*y)m=std::min(m,e-c-b+y+z);printf("%d\n",m);}}

Measured memory_bytes: 756
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
#include <set>
#include <math.h>
#include <queue>
#define rep(i,n) for (int i = 0; i < (n); ++i)
typedef long long ll;
using namespace std;

int main() {
    int x, y;
    cin >> x >> y;
    bool flag = false;
    rep(i,x+1) {
        int ans;
        ans = i*2+(x-i)*4;
        if (ans==y) flag = true;
    }
    if (flag) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 3096
#include<iostream>
#include<cstdio>
#include<math.h>
#include <stdlib.h>
#define M 100000
using namespace std;
  
int main(){
    int n, m,l = 0;
    int pos = 0;
    int ans = 0;
    int x[100010];
    scanf("%d %d",&n,&m);
    x[0] = 0;
    for (int i = 1; i < n; i++){
        scanf("%d", &x[i]);
        x[i] += x[i - 1];
    }
    while (m--){
        scanf("%d", &l);
        if(l > 0){
            ans += x[pos + l] - x[pos];
        }
        else{
            ans -= x[pos + l] - x[pos];
        }
        pos += l;
        ans %= M;
    }
    printf("%d\n", ans);
}

Measured memory_bytes: 1580
#include <algorithm>
#include <bitset>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define MOD (1000000007l)
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)

using namespace std;

void solve() {
  ll n;
  cin >> n;
  ll _min = 100000000;
  ll _max = -100000000;
  ll _sum = 0;
  rep (i, n) {
    ll tmp;
    cin >> tmp;
    if (_min > tmp) _min = tmp;
    if (_max < tmp) _max = tmp;
    _sum += tmp;
  }
  cout << _min << " " << _max << " " << _sum << endl;
}

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(12);
  cout << fixed;
  solve();
  return 0;
}



Measured memory_bytes: 3216
#include <iostream>
#include <algorithm>
#include <limits>
#include <vector>
#include <map>
#include <cmath>
#include <limits>
#include <iomanip>
#define ll long long int
#define rep(i,n) for(int i = 0;i < n;i++)
#define rep1(i,n) for(int i = 1;i < n;i++)
#define co(x) cout << x << endl
#define cosp(x) cout << x << " "
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair

using namespace std;

int main(){

    ll n,k;
    cin >> n >> k;

    vector<ll> a(n);
    rep(i,n) cin >> a[i];

    vector<int> b(41,0);
    rep(i,41){
        rep(j,n){
            b[i] += a[j] >> i & 1ll;
        }
    }

    int k2[41];
    rep(i,40){
        k2[i] = k >> i & 1ll;
    }

    vector<vector<ll> > dp(41,vector<ll>(2,0));//[i][0]がkを越すかもしれない値,[i][1]はkより完全に下の数
    rep(i,41) dp[i][1] = -1;

    for(int i = 39;i >= 0;i--){
        int sa = n - b[i];
        ll k3 = (1ll << i);
        if(dp[i + 1][1] != -1) dp[i][1] = max(dp[i][1],dp[i+1][1] + k3 * max(b[i],sa));

        if(k2[i]){//k2[i] == 1なら0,1どっちでもok
            dp[i][1] = max(dp[i][1],dp[i+1][0] + k3 * b[i]);
            dp[i][0] = max(dp[i][0], dp[i+1][0] + k3 * sa);
        }
        else{
            dp[i][0] = max(dp[i][0], dp[i+1][0] + k3 * b[i]);
        }
    }

    /*rep(i,41){
        cout << b[i] << " ";
    }
    cout << endl;

    rep(i,41){
        cout << k2[i] << " ";
    }
    cout << endl;

    rep(i,2){
        rep(j,20){
            cout << dp[j][i] << " ";
        }
        cout << endl;
    }*/

    cout << max(dp[0][0],dp[0][1]) << endl;

    return 0;
}

Measured memory_bytes: 1024
def resolve():
    import sys
    input = sys.stdin.readline
    # 整数 1 つ
    n = int(input())
    # 整数複数個
    # a, b = map(int, input().split())
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    L = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    # A = [list(map(int, input().split())) for i in range(H)]

    L.sort()
    import bisect

    cnt = 0
    for i in range(n-2):
        for j in range(i+1, n-1):
            k = bisect.bisect_left(L, (L[i]+L[j]))
            if k > j:
                cnt += k - j -1

    print(cnt)


resolve()

Measured memory_bytes: 44072
n, d = map(int, input().split())
x = [[0]]*n
for i in range(n):
  x[i] = [int(i) for i in input().split()]
s = 0
for i in range(n-1):
  for j in range(i+1,n):
    a = (sum((x[j][k] - x[i][k])**2 for k in range(d)))**0.5 
    if a//1 == a:
      s += 1
print(s)
   
 

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

int gcd(long long a, long long b){
  long long M = max(a, b), m = min(a, b);
  while(m != 0){
  	long long r = M%m;
    M = m; m = r;
  }
  return M;
}

int digit_sum(long long n){
  long long ans;
  while(n != 0){
  	ans += n%10;
  	n /= 10;
  }
  return ans;
}

int main(){
  int n;
  cin >> n;
  vector<int> h(n+1);
  for(int i = 0; i < n; i++){
  	cin >> h.at(i);
  }
  h.at(n) = 1000000001;
  
  map<int, int> mp;
  int first = 0;
  int ans = 0;
  for(int i = 0; i < n; i++){
  	if(h.at(i+1) <= h.at(i)){
    	ans++;
    }
  
  	else{
    	mp[first] = ans;
    	first++;
      	ans = 0;
    }
  }
  int count = 0;
  for(auto p : mp){
  	count = max(count, p.second);
  }
  
  cout << count << endl;
}

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


int main()
{
int N,M,C;
cin>>N>>M>>C;
vector<int>B(M);
for(int i=0;i<M;i++)
{cin>>B[i];}
vector<vector<int>>A(N,vector<int>(M));
for(int i=0;i<N;i++)
{for(int j=0;j<M;j++)

{cin>>A[i][j];}

}

int answer=0;

for(int i=0;i<N;i++)
{
int number=C;
for(int j=0;j<M;j++)
{number+=A[i][j]*B[j];}
if(number>0){answer++;}

}

cout<<answer<<endl;



}


Measured memory_bytes: 256
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int l, r;
        long count = 0;
        for(int i=0; i<n; i++) {
            l = Integer.parseInt(sc.next());
            r = Integer.parseInt(sc.next());
            count += r-l+1;
        }
        System.out.println(count);
    }   
}

Measured memory_bytes: 21972
#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>

using namespace std;

typedef pair<long long , long long > P;

int main(){
    int a, b ,c;
    cin >> a >> b >> c;
    cout << max(0, c-(a-b))<<endl;
}

Measured memory_bytes: 256
require 'scanf'
while str = STDIN.gets
    n = str.to_i
    exit 0 if n==0
    hash = Hash.new
    idlist = Array.new
    for i in 0..n-1 do
        #id tanka num
        list = STDIN.gets.scanf("%d %d %d")
        money = list[1] * list[2]
        id = list[0]
        if not hash.has_key?id then
            hash[id] = 0
            idlist.push id
        end
        hash[id] = hash[id] + money
    end
    flag = true
    for i in idlist do
        if hash[i] >= 1000000 then
            print i,"\n" 
            flag = false
        end
    end
    print "NA\n" if flag
end

Measured memory_bytes: 6712
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1e9 + 7;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class T>
istream& operator >> (istream& is, vector<T>& v)
{
	for (auto &i : v) is >> i;
	return is;
}
template<class T>
ostream& operator<<(ostream& os, vector<T>& v)
{
	const string delimiter = "\n";
	REP(i, v.size())
	{
		os << v[i];
		if (i != v.size() - 1) os << delimiter;
	}
	return os;
}
/*--------------------template--------------------*/

int cal(vi v)
{
	if (v.size() == 0) return 0;
	int k = *min_element(ALL(v));
	REP(i, v.size()) v[i] -= k;
	int ans = k;
	vi t;
	REP(i, v.size())
	{
		if (v[i] == 0)
		{
			ans += cal(t);
			t.clear();
		}
		else
		{
			t.push_back(v[i]);
		}
	}
	ans += cal(t);
	return ans;
}

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	int n; cin >> n;
	vi v(n); cin >> v;
	cout << cal(v) << endl;
	return 0;
}

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

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(ARC095_C());
        }

        static int ARC095_C()
        {
            var inputs = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            var A = inputs[0];
            var B = inputs[1];
            var C = inputs[2];
            var X = inputs[3];
            var Y = inputs[4];

            var length = X > Y ? X : Y;
            var ans = int.MaxValue;
            for (var i = 100000; i >= 0; i -= 1)
            {
                var ab = i * 2;
                var a = Math.Max(0, X - i);
                var b = Math.Max(0, Y - i);
                var sum = (a * A) + (b * B) + (ab * C);
                ans = Math.Min(ans, sum);
            }
            return Math.Min(ans, (X * A) + (Y * B));
        }
    }
}

Measured memory_bytes: 13396
let split_on_char sep s =
  let open String in
  let r = ref [] in
  let j = ref (length s) in
  for i = length s - 1 downto 0 do
    if get s i = sep then begin
      r := sub s (i + 1) (!j - i - 1) :: !r;
      j := i
    end
  done;
  sub s 0 !j :: !r

let () =
  let n = read_int () in
  let tbl = Hashtbl.create ~random:true n in
  for _ = 0 to n - 1 do
    match split_on_char ' ' (read_line ()) with
    | ["find"; s] -> print_endline (if Hashtbl.mem tbl s then "yes" else "no")
    | [_; s] -> Hashtbl.add tbl s ()
    | _ -> assert false
  done

Measured memory_bytes: 43912
h,w = map(int, input().split())

strs = [input() for i in range(h)]

hFlag = []
wFlag = []

for i in range(h):
    if len(strs[i]) == len(strs[i].replace('#','')):
        wFlag.append(False)
    else:
        wFlag.append(True)

for i in range(w):
    flag = False
    for j in range(h):
        if strs[j][i] == '#':
            flag = True
            break

    if flag :
        hFlag.append(True)
    else:
        hFlag.append(False)

for i in range(h):
    if wFlag[i]:
        for j in range(w):
            if hFlag[j]:
                print(strs[i][j], end='')

        print()



Measured memory_bytes: 4468