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

typedef long long ll;
#define mod 1000000007

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

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

void solve() {
    int x;
    cin>>x;
    cout<<(int)!x;
}
int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    // pre();
    while (t--)
        solve();

    return 0;
}

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

int main()
{
int a, b;
cin >> a >> b;
int ans = a * b;
if(ans % 2 != 0){
    cout << "Yes" << endl;
}else if(ans % 2 == 0){
    cout << "No" <<  endl;
}


}


Measured memory_bytes: 256
import sys


def resolve(in_):
    N, K = map(int, next(in_).split())
    A = map(int, next(in_).split())
    number_plus1 = list(i + 1 for i in A)

    v = [0] * N
    v[0] = sum(number_plus1[:K])
    for i, (before, after) in enumerate(zip(number_plus1, number_plus1[K:]), 1):
        v[i] = v[i - 1] - before + after

    expected = max(v) / 2

    return expected


def main():
    answer = resolve(sys.stdin.buffer)
    print(f'{answer:.12f}')


if __name__ == '__main__':
    main()


Measured memory_bytes: 28716
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
const int MR=1e6+10;
typedef long long LL;

int A[11],a[51],b[51],c[51],d[51];
int n,m,q,ans=-1;

int check(){
	int sum=0;
	for(int i=0;i<q;i++){
		if(A[b[i]]-A[a[i]]==c[i]) sum+=d[i];
	}
	return sum;
}

void dfs(int p){
	if(p==n+1){
		ans=max(ans,check());
		return;
	}
	for(A[p]=A[p-1];A[p]<=m;A[p]++){
		dfs(p+1);
	}
}

int main() {
	cin>>n>>m>>q;
	for(int i=0;i<q;i++) cin>>a[i]>>b[i]>>c[i]>>d[i];
	A[0]=1;
	dfs(1);
	cout<<ans<<endl;
    return 0;
}

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define MAXN 100010
#define rep(i,n) for (int i = 0; i < (n); ++i)
const ll mod = 1e9+7;


int main() {
    int n;
    vector<int> a;
    vector<int> b;
    vector<int> c;

    cin >> n;
    int tmp;
    rep(i,n) {
        cin >> tmp;
        a.push_back(tmp);
    }
    int ans = 0;
    rep(i,n) {
        cin >> tmp;
        ans += tmp;
        b.push_back(tmp);
    }
    rep(i,n-1) {
        cin >> tmp;
        c.push_back(tmp);
    }

    rep(i, n-1) {
        if (a[i]+1 == a[i+1]) ans += c[a[i]-1];
    }
    cout << ans << endl;
}



Measured memory_bytes: 256
def main():
  h, w, d = map(int, input().split())
  a = [list(map(int, input().split())) for i in range(h)]
  pts = [(0, 0) for i in range(h * w)]
  for i in range(h):
    for j in range(w):
      a[i][j] -= 1
      pts[a[i][j]] = (i, j)
  c = [[0 for j in range(h * w // d + 10)] for i in range(d)]
  for s in range(d):
    i = s
    j = s + d
    while j < h * w:
      iy, ix = pts[i]
      jy, jx = pts[j]
      c[s][(j - j % d) // d] = c[s][(i - i % d) // d] + abs(iy - jy) + abs(ix - jx)
      i += d
      j += d
  q = int(input())
  for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    s = l % d
    print(c[s][(r - r % d) // d] - c[s][(l - l % d) // d])

if __name__ == "__main__":
  main()

Measured memory_bytes: 32688
#include<bits/stdc++.h>
#define rep(i,n) for(int (i) = 0;(i) < (n);(i)++)
#define SORT(c) sort((c).begin(),(c).end())
#define MOD 1000000007
using namespace std;
typedef long long ll;

vector<int> ans;
int n;
vector<vector<int>> a(2, vector<int>(105, 0));
void dfs(int h, int w, int sum){
  sum += a[h][w];
  if(w == n - 1 && h == 0) {
    sum += a[1][n - 1];
    ans.push_back(sum);
    return;
  }
  if(w == n - 1 && h == 1) {
    ans.push_back(sum);
    return;
  }
  if(h == 0){
    dfs(h, w + 1, sum);
    dfs(h + 1, w, sum);
  }
  else dfs(h, w + 1, sum);
}
int main(void){
  cin >> n;
  rep(i, n) cin >> a[0][i];
  rep(i, n) cin >> a[1][i];
  dfs(0,0,0);
  SORT(ans);
  cout << ans[ans.size() - 1] << endl;
  return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
 
    static int count = 0;
    static int input = 0;
 
    public static int sum(int x, int y) {
        return (x + y) * (y - x + 1) / 2;
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        while (true) {
            input=0;
            count=0;
            String num = br.readLine();
            if (num.equals("0")) {
                return;
            }
 
            input = Integer.parseInt(num);
 
            for (int i = 1; i < input; i++) {
                for (int j = i+1; j < input; j++) {
                    if (input == sum(i, j)) {
                        count++;
                        break;
                    }
                    if (input < sum(i, j)) {
                        break;
                    }
                }
            }
            System.out.println(count);
        }
    }
 
}


Measured memory_bytes: 24716
#include<bits/stdc++.h>
    using namespace std;
     
    int main(void){
      int N,sum = 0; cin>>N;
      vector<int> vec;
      vec.resize(N);
      for(int t=0;t<N;t++)cin>>vec[t];
      sort(vec.begin(),vec.end());
      for(int i = 0;i <= N-2;i++){
      	sum+=vec[i];
      }
      
      cout<<(vec[N-1]<sum?"Yes":"No");
    }

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

#define int long long
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n) for (int i = 1; i <= (n); i++)
#define all(x) begin(x), end(x)
#define uniq(x) (x).erase(unique(all(x)), end(x))
#define bit(n) (1LL << (n))
#define dump(x) cerr << #x " = " << (x) << endl
using vint = vector<int>;
using vvint = vector<vint>;
using pint = pair<int, int>;
using vpint = vector<pint>;
template<typename T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
constexpr long double PI = 3.1415926535897932384626433832795028L;
constexpr int DY[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int DX[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int gcd(int a, int b) {
    while (b) { swap(a %= b, b); }
    return a;
}
int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<typename T> void fin(T mes) {
    cout << mes << endl;
    exit(0);
}
template<typename T, typename U> bool chmax(T &a, const U &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> bool chmin(T &a, const U &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &rhs) {
    os << "(" << rhs.first << ", " << rhs.second << ")";
    return os;
}
template<typename T> ostream &operator<<(ostream &os, const vector<T> &rhs) {
    os << "{";
    for (auto itr = rhs.begin(); itr != rhs.end(); itr++) {
        os << *itr << (next(itr) != rhs.end() ? ", " : "");
    }
    os << "}";
    return os;
}
struct setup {
    static constexpr int PREC = 20;
    setup() {
        cout << fixed << setprecision(PREC);
        cerr << fixed << setprecision(PREC);
    };
} setup;

int N, K;
signed main() {
    cin >> N >> K;
    N = N % K;
    cout << min(N, K - N) << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int a, b, c, d, e, f;
int main() {
	cin >> a >> b >> c >> d >> e >> f;
	cout << a + b + c + d + e + f - min({ a, b, c, d }) - min(e, f) << endl;
	return 0;
}

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

const long long INF = 4000000000;

long long d[300][300];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> d[i][j];
        }
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i == j) continue;
            for (int k = 0; k < n; k++)
            {
                if (i == k || j == k) continue;

                if (d[i][j] + d[i][k] < d[j][k]) {
                    cout << -1 << endl;
                    return 0;
                }
            }
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i == j) continue;
            for (int k = 0; k < n; k++)
            {
                if (i == k || j == k) continue;

                if (d[i][j] + d[i][k] <= d[j][k]) {
                    d[j][k] = INF;
                }
            }
        }
    }

    long long ans = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (d[i][j] == INF) continue;

            ans += d[i][j];
            d[j][i] = 0;
        }
    }
    
    cout << ans << endl;
}

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

const int MOD = 1000000007;

//long long
using ll = long long;

//出力系
#define print(x) cout << x << endl
#define printf(x) cout << fixed << setprecision(9) << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
 
// begin() end()
#define all(x) (x).begin(),(x).end()

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

//最大公約数 
unsigned gcd(unsigned a, unsigned b) {
  if(a < b) return gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

//最小公倍数
int lcm(int number1,int number2){
	return number1 * number2 / gcd(number1,number2);	
}

int main(){

int N, K;
cin >> N >> K;
double ans = 0;

for(int i = 1; i <= N; i++){ 
   double ret = 1.0 / N;
   int now = i;
   while(now < K){
     now *= 2;
     ret /= 2;
   }

ans += ret;
}

 printf(ans);
}

Measured memory_bytes: 256
#include <algorithm>
#include <bits/stdc++.h>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <functional>
#include <iostream>
#include <map>
#include <math.h>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string>
#include <utility>
#include <vector>

#define REP(i, n) for(int i = 0; i != n; ++i)
#define REPR(i, n) for(int i = n - 1; i != -1; --i)
#define FOR(i, a, b) for(int i = a; i != b; ++i)
#define RBF(i, n) for(auto &i : n)
#define ABS(n) (n < 0 ? -n : n)
#define MIN(a, b) (a < b ? a : b)
#define MAX(a, b) (a > b ? a : b)
#define IN(n) (cin >> n)
#define OUT(n) (cout << n << "\n")
#define INF 1e9
#define ALL(v) (v).begin(), (v).end()

using namespace std;
using ll = long long;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int N, K, Q;
  cin >> N >> K >> Q;
  vector<int> X(N,K);
  vector<int> Y(N,-Q);
  int win;
  REP(i,Q){
    cin >> win;
    Y[win-1] =Y[win-1] +1;
  }
  REP(i,N){
    if(X[i] + Y[i] >0) OUT("Yes");
    else OUT("No");
  }
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
#define FR first
#define SE second
using namespace std;

const int S=(1<<20)+5;
char buf[S],*H,*T;
inline char Get()
{
    if(H==T) T=(H=buf)+fread(buf,1,S,stdin);
    if(H==T) return -1;return *H++;
}
inline int read()
{
    int x=0;char c=Get();
    while(!isdigit(c)) c=Get();
    while(isdigit(c)) x=x*10+c-'0',c=Get();
    return x;
}
char obuf[S],*oS=obuf,*oT=oS+S-1,c,qu[55];int qr;
inline void flush(){fwrite(obuf,1,oS-obuf,stdout);oS=obuf;}
inline void putc(char x){*oS++ =x;if(oS==oT) flush();}
inline void printd(int d,double x)
{
    long long t=(long long)floor(x),f=t;
    while(t) qu[++qr]=t%10,t/=10;
    while(qr) putc(qu[qr--]+'0');
    putc('.');x-=f;
    while(d--)
    {
        double y=x*10;x*=10;
        int c=(int)floor(y);
        putc(c+'0');x-=c;
    }
}

typedef long long LL;
typedef pair<LL,double> pld;
const int N=500010;
LL t[N],v[N];
pld q[N];
int l=1,r=0;

int main()
{
    int n=read(),L=read();
    for(int i=1;i<=n;i++)
        t[i]=read(),v[i]=read();
    int sum=0;double cur=0;
    for(int i=1;i<=n;i++)
    {
        while(v[i]+sum>L)
        {
            int pour=min(v[i]+sum-L,q[l].FR);
            sum-=pour;
            q[l].FR-=pour;
            cur-=q[l].SE*pour;
            if(!q[l].FR) l++;
        }
        q[++r]=pld(v[i],t[i]);
        sum+=v[i];cur+=1ll*t[i]*v[i];
        while(l<r&&q[r].SE<q[r-1].SE)
        {
            q[r-1].SE=(q[r-1].SE*q[r-1].FR+q[r].SE*q[r].FR)/(q[r-1].FR+q[r].FR);
            q[r-1].FR+=q[r].FR;r--;
        }
        printd(7,cur/L);putc('\n');
    }
    flush();
    return 0;
}

Measured memory_bytes: 26752
import numpy as np

N, D = map(int, input().split())

X = np.zeros((N,D))
for i in range(N):
    X[i,:] = np.array(list(map(int, input().split())))

count = 0
for i in X:
    for j in X:
        if (np.sqrt(sum((i-j)**2))%1 == 0) == True:
            count += 1
print((count-N)//2)

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

using namespace std;

//#define MD 100010

int main(){
   int n,a;
   cin>>n>>a;
    vector<int> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    
    long long int dp[60][60][2800]={0};
    
    dp[0][0][0]=1;
    
    for(int j=0;j<=n;j++){
        for(int k=0;k<=n;k++){
            for(int s=0;s<=n*a;s++){
                if(k>=1 && v[j]<=s){
                    dp[j+1][k][s]=dp[j][k][s]+dp[j][k-1][s-v[j]];
                }else{
                    dp[j+1][k][s]=dp[j][k][s];
                }
            }
        }
    }
    
    long long int ans=0;
    
    for(int k=1;k<=n;k++){
        ans+=dp[n][k][k*a];
    }
    cout<<ans<<endl;
    
   return 0;
}

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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define LCM(a, b) (a) / __gcd((a), (b)) * (b)
#define CEIL(a, b) (a)/(b)+(((a)%(b))?1:0)
#define ln '\n'

using namespace std;
using LL = long long;
using ldouble = long double;
using P = pair<int, int>;
using LP = pair<LL, LL>;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1e9 + 7;
static const int SIZE = 200005;

const int dx[] = {0, -1, 1, 0};
const int dy[] = {-1, 0, 0, 1};

vector<LL> Div(LL n) {
    vector<LL> ret;
    for(LL i = 1; i * i <= n; ++i) {
        if(n % i == 0) {
            ret.pb(i);
            if(i * i != n) ret.pb(n / i);
        }
    }
    sort(all(ret));
    return ret;
}

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

    int N, X;
    cin >> N >> X;
    int c = 1;
    int p = 0;
    for(int i = 0; i < N; ++i) {
        int l;
        cin >> l;
        p += l;
        if(p <= X) ++c;

    }
    cout << c << endl;
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i <= (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

int main()
{
	int N;
	cin >> N;
	int A[N],B[N];
	REP(i,N)cin >> A[i] >> B[i];
	long long sum = 0;
	for (int i = N-1; i >= 0; --i)
	{
		int d = 0;
		if((A[i]+sum)%B[i]!=0){
			d = B[i] - (A[i]+sum)%B[i];
		}
		sum += d;
	}
	cout << sum << endl;
    return 0;
}

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

public class Main {
    boolean[] bs;

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

    void run() {
        FastReader sc = new FastReader();
        char[] cs = sc.next().toCharArray();
        bs = new boolean[cs.length];
        for (int i = 0; i < cs.length; i++) {
            bs[i] = cs[i] == '1';
        }
        solve();
    }

    void solve() {
        int ans = bs.length;
        for (int i = 0; i < bs.length - 1; i++) {
            if (bs[i] ^ bs[i + 1]) {
                ans = Math.min(ans, Math.max(i + 1, bs.length - i - 1));
            }
        }
        System.out.println(ans);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

        long nextLong()
        {
            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
}


Measured memory_bytes: 23252
import java.util.*;
class Main{
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		int N =Integer.parseInt(in.next());
		int A =Integer.parseInt(in.next());
		int B =Integer.parseInt(in.next());
		int ans = 0;
		int temp = 1;
		for(int i = 1; i <= N; i++){
			temp = w(i);
			if((A <= temp) && (temp <= B)) ans += i;
		}
		System.out.println(ans);
	}
	static int w(int n){
		if(n == 10000)return 1;
		else return (int)(Math.floor(n/1000)+Math.floor((n%1000)/100)+Math.floor(((n%1000)%100)/10)+Math.floor((((n%1000)%100)%10)));
	}
}

Measured memory_bytes: 23124
#include<bits/stdc++.h>
using namespace std;
#define bada 1000000000000000000

int64_t gcd(int64_t a, int64_t b)
{
    if(b)
        return gcd(b,a%b);
    return a;
}
int64_t lcm(int64_t a,int64_t b)
{
    return (a*b)/gcd(a,b);
}
int main ()
{
    int64_t n;
    cin>>n;
    int64_t a[n];
    int64_t sumprev=0;
    unordered_map<int64_t,int64_t> m;
    for(int64_t i=0;i<n;i++)
    {
        m[cin>>a[i],a[i]]++;
        sumprev+=a[i];
    }
    int64_t q;
    cin>>q;
    while(q--)
    {
        int64_t b,c;
        cin>>b>>c;
        if(m.find(b)!=m.end())
        {
            sumprev+=(c-b)*m[b];
            m[c]+=m[b];
            m[b]=0;
        }
        cout<<sumprev<<endl;
    }
}



Measured memory_bytes: 7536
def main():
    N = str(input())
    #A_list = list(map(int, input().split()))

    if N[0] == "R" :
        if N[1] == "R" :
            if N[2] == "R" :
                print("3")
            else :
                print("2")
        else :
            print("1")
    else :
        if N[1] == "R" :
            if N[2] == "R" :
                print("2")
            else :
                print("1")
        else :
            if N[2] == "R" :
                print("1")
            else :
                print("0")

if __name__ == '__main__':
    main()


Measured memory_bytes: 9068
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef set<int> si;
typedef map<int,int> mii;
typedef map<string, int> msi;
typedef map<int,pair<int,int> > miii;
typedef complex<double> point;
typedef pair<int, ii> iii;
typedef vector<iii> viii;
#define X real()
#define Y imag()
#define FileIn(file) freopen(file".txt", "r", stdin)
#define FileOut(file) freopen(file".txt", "w", stdout)
#define Fill(ar, val) memset(ar, val, sizeof(ar))
#define PI 3.1415926535897932385
#define all(ar) ar.begin(), ar.end()
#define pb push_back
#define bit(n) (1<<(n))
#define Last(i) (i & -i)
#define INF 500000000
#define maxN 10000010
#define VISITED 1
#define UNVISITED -1
#define P(p) const point &p
#define L(p0, p1) P(p0), P(p1)

int main()
{
    ios::sync_with_stdio(0);
    //cin.tie(0);
    //FileIn("in");
    //FileOut("out");
    llu n;
    llu sum=0;
    int l,r;
    cin>>n;
    for(int i = 0;i<n;i++)
    {
        cin>>l>>r;
        sum+=(r-l+1);
    }
    cout<<sum<<"\n";
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s;
  cin>>s;
  int i1=0,i2=0;
  for(int i=0;i<s.length();i++)
    if(s[i]=='1')
      i1++;
  else i2++;
  cout<<2*(min(i1,i2));
  return 0;
}

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

int main(){
  int n,k;
  cin >> n >> k;
  vector<int>a(n);
  vector<double>kit(n);
  for(int i=0;i<n;i++){
    cin >> a.at(i);
    kit.at(i)=(a.at(i)+1.0)/2;
  }
  double ans=0,bf=0;
  for(int i=0;i<k;i++)
    bf+=kit.at(i);
  ans=bf;
  for(int i=k;i<n;i++){
    bf+=kit.at(i)-kit.at(i-k);
    ans=max(ans,bf);
  }
  cout << setprecision(9) << ans << endl;
  return 0;
}

Measured memory_bytes: 5640
n = int(input())
a = list(map(int,input().split()))
if a[0]==1 and n==0:
    print(1)
    exit()
if a[0]!=0:
    print(-1)
    exit()
c = 1
for i in range(1,n+1):
    c = c*2
    if a[i]>c:
        print(-1)
        exit()


x = [0]*(n+1)
x[0] = 1
for i in range(n):
    x[i+1] = 2*(x[i]-a[i])
    if x[i+1]<0:
        print(-1)
        exit()

if x[-1]<a[-1]:
    print(-1)
    exit()
x[-1] = a[-1]

for i in range(n-1,-1,-1):
    if a[i]>x[i]:
        print(-1)
        exit()
    x[i] = min(x[i],x[i+1]+a[i])


print(sum(x))




Measured memory_bytes: 674560
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  bool flag=1;
  for(int i=0;i<n;i++)
  {
    int x;
    cin>>x;
    if(x%2==0 && (x%3!=0 && x%5!=0))
       flag=0;
       }
       if(flag)
        cout<<"APPROVED";
     else
        cout<<"DENIED";
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define N 100000
typedef long long ll;
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) int(x.size())
#define OUT(a) cout<<(a)<<endl
#define VECIN(type, c, n) vector<type> c(n);for(auto& i:c) cin>>i;

int main(){
    int a,b;
    cin>>a>>b;
    OUT(6-a-b);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <cstdio>
#include <cmath>

using namespace std;

int main(){
    int n;
  cin>>n;
  int sum=0;
  for(int i=0;i<n;i++){
	int a,b;
    cin>>a>>b;
    sum=sum+b-a+1;
  }
  cout<<sum;
    return 0;
}


Measured memory_bytes: 256
#include "iostream"
using namespace std;
int N,count=0;
void f(long long k,bool flag3,bool flag5,bool flag7)
{
	if(k<=N)
	{
		if(flag3&&flag5&&flag7)
			count++;
		f(k*10+3,true,flag5,flag7);  //末尾加3
		f(k*10+5,flag3,true,flag7);  //末尾加5
		f(k*10+7,flag3,flag5,true);  //末尾加7
	}
}

int main()
{
	cin>>N;
	f(0,false,false,false);
	cout<<count<<endl;
	system("pause");
}

Measured memory_bytes: 504
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// TODO ?????????????????????????????????????????????

		Scanner scan = new Scanner(System.in);
		int W = scan.nextInt();
		int H = scan.nextInt();
		int x = scan.nextInt();
		int y = scan.nextInt();
		int r = scan.nextInt();
		
		if(x - r >= 0 && y - r >=0 && x + r <= W && y + r <= H){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
	
	}
	
}

Measured memory_bytes: 26320
#include <stdio.h>

int main()
{
  int N;
  scanf("%d",&N);
  int X[N];
  int i;
  i = 0;
  while (i < N)
  {
    scanf("%d",&X[i]);
    i++;
  }
  quicksort(N, X, 0, N - 1);
  int len;
  len = X[N-1] - X[0] + 1;
  int Y[len];
  initialize(len, Y);
  int p;
  int j;
  p = X[0];
  j = 0;
  while (j < len)
  {
    i = 0;
    while (i < N)
    {
      Y[j] += (p - X[i])*(p - X[i]);
      i++;
    }
    p++;
    j++;
  }
  quicksort(len, Y, 0, len - 1);
  printf("%d",Y[0]);
}

void quicksort(int len, int X[len], int first, int last)
{
  int threshold;
  int i,j;
  int tmp;
  i = first;
  j = last;
  threshold = X[(first + last) / 2];
  while (1)
  {
    while (threshold > X[i])
    {
      i++;
    }
    while (threshold < X[j])
    {
      j--;
    }
    if (i >= j)
    {
      break;
    }
    tmp = X[i];
    X[i] = X[j];
    X[j] = tmp;
    i++;
    j--;
  }
  if (first < i - 1)
  {
    quicksort(len, X, first, i - 1);
  }
  if (last > j + 1)
  {
    quicksort(len, X, j + 1, last);
  }
}

void initialize(int len, int Y[len])
{
  int i;
  i = 0;
  while (i < len)
  {
    Y[i] = 0;
    i++;
  }
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n; cin >> n;
	vector<long long> a(n);
	long long sum = 0, cur = 0;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		sum += a[i];
	}
	long long ans = sum;
	for(int i = 0; i < n; i++){
		cur += a[i];
		ans = min(ans, abs(sum - 2 * cur));
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1792
MOD = 1_000_000_007

def modcomb(n,k)
  modn = k.times.inject(1){|s,i| (s * (n - i)) % MOD }
  modk = (1 .. k).inject(1){|s,i| (s * i) % MOD}
  (modn * modpow(modk, MOD - 2)) % MOD
end

def modpow(n,k)
  if k == 0
    1
  elsif k.odd?
    (n * (modpow(n, k / 2) ** 2)) % MOD
  else
    (modpow(n, k / 2) ** 2) % MOD
  end
end

N, A, B = gets.split.map(&:to_i)
puts (modpow(2, N) - modcomb(N,A) - modcomb(N,B) - 1) % MOD


Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,f[300009],xr[64],cnt[64],ecnt[64],mod=1000000007,pas;
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a;
    for(b=1; b<=a; b++) cin>>f[b];
    xr[0]=1;
    for(b=1; b<=62; b++){
        xr[b]=xr[b-1]*2;
    }
    for(b=1; b<=a; b++){
        for(c=0; c<=61; c++){
            if((xr[c]&f[b])!=0) cnt[c]++; else ecnt[c]++;
        }
    }
    for(c=0; c<=61; c++){
        d=xr[c]%mod;
        d*=cnt[c];d%=mod;
        d*=ecnt[c];d%=mod;
        pas+=d;
        pas%=mod;
    }
    cout<<pas;
    return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define lld long int
int main()
{
    ll n;
    cin>>n;
    string s;
    cin>>s;
    string ans="";
    ans+=s[0];
    for(int i=1;s[i];i++){
        if(s[i]!=s[i-1])ans+=s[i];
    }
    cout<<ans.size()<<endl;
}


Measured memory_bytes: 640
'use strict'

const main = arg => {
    const input = arg.trim().split("\n");
    const nums = parseInt(input[0], 10);
    const cards = input.slice(1).slice(0, nums);
    const fullCards = [];
    const emptyCards = [];

    ["S","H","C","D"].forEach(suit => {
        [...Array(13)].forEach((obj, i) => {
            fullCards.push(suit+ ` ${i+1}`);
        });
    })

    fullCards.forEach(fcard => {
        if(!cards.includes(fcard)){ emptyCards.push(fcard); }
    })

    if(emptyCards.length > 0){
     console.log( emptyCards.join("\n") );
    }
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));


Measured memory_bytes: 15384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define repb(i, n) for(ll i = (n)-1; i >= 0; i--)
#define repr(i, a, b) for(ll i = (a); i < (b); i++)
#define reprb(i, a, b) for(ll i = (b)-1; i >= (a); i--)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((ll)(x).size())
const ll MOD = 1000000007;
const ll INF = 100000000000000000LL;
inline ll GCD(ll a, ll b){ return b?GCD(b, a % b):a; }
inline ll LCM(ll a, ll b){ return a/GCD(a, b)*b; }
inline ll powmod(ll x, ll y, ll m = MOD){ ll r=1; while(y){ if(y&1) r*=x; x*=x; r%=m; x%=m; y>>=1; } return r; }
template<class S, class T>bool chmax(S &a, const T &b){ if(a<b) { a=b; return 1; } return 0; }
template<class S, class T>bool chmin(S &a, const T &b){ if(b<a) { a=b; return 1; } return 0; }
#ifdef OJ_LOCAL
#include "dump.hpp"
#else
#define dump(...) ((void)0)
#endif

const int M = 100010;
ll n;
vll x;
int d[18][M];

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    cin >> n;
    x.resize(n);
    rep(i, n){
        cin >> x[i];
    }
    ll l;
    cin >> l;
    
    rep(j, n){
        d[0][j] = upper_bound(ALL(x), x[j] + l) - x.begin() - 1;
    }
    repr(i, 1, 18)rep(j, n){
        d[i][j] = d[i-1][d[i-1][j]];
    }
    /*
    rep(i, 18)rep(j, n){
        cout << d[i][j] << " \n"[j+1==n];
    }
    cout << endl;
    */
    ll q;
    cin >> q;
    ll a, b;
    rep(qq, q){
        cin >> a >> b;
        a--;b--;
        if(a > b) swap(a, b);
        ll ans = 0;
        ll p = a;
        while(1){
            rep(i, 18){
                //cout << i << " " << p << endl;
                if(d[i][p] >= b){
                    if(i == 0){
                        ans++;
                        goto enendd;
                    }else{
                        ans += powmod(2, i-1);
                        p = d[i-1][p];
                        break;
                    }
                }
            }
        }
        enendd:
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 8704
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0;i < n;i++)
#define all(i) i.begin(), i.end()
template<class T, class U> bool cmax(T& a, U b) { if (a<b) {a = b; return true;} else return false; }
template<class T, class U> bool cmin(T& a, U b) { if (a>b) {a = b; return true;} else return false; }

template<class T>
struct CumulativeSum {
  vector<T> v;

  CumulativeSum(size_t n) : v(n) {};
  CumulativeSum(vector<T> v_) {
    v.resize(v_.size()+1);
    for (size_t i = 0; i < v_.size(); i++) v[i+1] = v_[i];
  };

  void add(size_t i, T x) {
    v[i] += x;
  }

  // O(N)
  void build() {
    for (size_t i = 0; i < v.size()-1; i++)
      v[i+1] += v[i];
  }

  // O(1) sum [l, r]
  T sum(size_t l, size_t r) const {
    return l == 0 ? v[r] : v[r]-v[l-1];
  }

  // O(1) sum [0, r]
  T sum(size_t r) const {
    return v[r];
  }

  T& operator[](size_t i) {
    return v[i];
  }

  const T& operator[](size_t i) const {
    return v[i];
  }
};

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

  ll n;
  string s;
  cin >> n >> s;

  CumulativeSum<ll> cs(n);
  rep(i, n) {
    if (s[i] == 'E') {
      cs[i]++;
    }
  }

  cs.build();

  ll ans = 1LL<<62;
  rep(i, n) {
    ll cnt = 0;
    if (i != 0) cnt += i-cs.sum(0, i-1);
    cnt += cs.sum(i+1, n-1);
    cmin(ans, cnt);
  }
  cout << ans << endl;
}


Measured memory_bytes: 2964
#include<stdio.h>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
using namespace std;
char in[50];
char L[50];
char R[50];
int p[5100];
int q[5100];
int UF[500];
int FIND(int a){
	if(UF[a]<0)return a;
	return UF[a]=FIND(UF[a]);
}
void UNION(int a,int b){
	a=FIND(a);b=FIND(b);if(a==b)return;UF[a]+=UF[b];UF[b]=a;
}
int g[310][310];
int g2[310][310];
int main(){
	int a;
	while(scanf("%d",&a),a){
		map<string,int>m;
		int n=0;
		for(int i=0;i<500;i++)UF[i]=-1;
		for(int i=0;i<a;i++){
			scanf("%s",in);
			int at=0;
			int j;
			for(j=0;in[j]!='-';j++){
				L[at]=in[j];at++;
			}L[at]=0;
			at=0;
			j++;
			for(;in[j];j++){
				R[at]=in[j];at++;
			}R[at]=0;
	//		printf("%s %s\n",L,R);
			string l=L;
			string r=R;
			if(m.count(l))p[i]=m[l];
			else{
				m[l]=n;
				p[i]=n++;
			}
			if(m.count(r)){
				q[i]=m[r];
			}else{
				m[r]=n;q[i]=n++;
			}
		}
		for(int i=0;i<n;i++)for(int j=0;j<n;j++)g[i][j]=0;
		for(int i=0;i<a;i++)g[p[i]][q[i]]=1;
		for(int i=0;i<n;i++)for(int j=0;j<n;j++)g2[i][j]=0;
		for(int i=0;i<n;i++)g2[i][i]=1;
		for(int i=0;i<a;i++)g2[p[i]][q[i]]=1;
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++){
				bool ok1=false;
				bool ok2=true;
				for(int k=0;k<n;k++){
					if(g[i][k]&&g[j][k])ok1=true;
					if(g[k][i]&&g[k][j])ok1=true;
					if(g[i][k]&&g[k][j])ok2=false;
					if(g[j][k]&&g[k][i])ok2=false;
				}
				if(ok1&&ok2)g2[i][j]=g2[j][i]=1;
			}
		}
		for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)
			g2[i][j]|=g2[i][k]&g2[k][j];
		printf("%d\n",n);
		for(int i=0;i<a;i++){
			UNION(p[i]*2,q[i]*2+1);UNION(p[i]*2+1,q[i]*2);
		}
		int b;scanf("%d",&b);
		for(int i=0;i<b;i++){
			scanf("%s",in);
			int at=0;int j;
			for(j=0;in[j]!='-';j++){
				L[at]=in[j];at++;
			}L[at]=0;
			at=0;
			j++;
			for(;in[j];j++){
				R[at]=in[j];at++;
			}R[at]=0;
			string l=L;string r=R;
			if(!m.count(l)||!m.count(r)){printf("NO\n");continue;}
			int P=m[l];
			int Q=m[r];
			if(FIND(P*2)!=FIND(Q*2+1)||FIND(P*2+1)!=FIND(Q*2)){printf("NO\n");continue;}
			if(g2[P][Q])printf("YES\n");
			else printf("NO\n");
		}
	}
}

Measured memory_bytes: 1616
x500=gets.to_i
x100=gets.to_i
x50=gets.to_i
x=gets.to_i
n=0
i=0
while i<=x500&&x>=i*500
  j=0
while j<=x100&&x>=i*500+j*100
if (x-i*500-j*100)/50<=x50
n+=1
end
  j+=1
end
i +=1
end
p n

Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
typedef long long int uli;
int main(){
   int x,y,s;
   while(scanf("%d %d %d",&x,&y,&s)){
      if(x==0)break;
      int ans=0;
      for(int q1=1;q1<=s-1;q1++){
         for(int q2=1;q2<=s-1;q2++){
            if(((100+x)*q1)/100+((100+x)*q2)/100==s){
               int bet= ((100+y)*q1)/100+((100+y)*q2)/100;
               ans=max(ans,bet);
            }
         }
      }
      printf("%d\n",ans);
   }
   return 0;
}

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

int main(){
    int n, m;
    cin >> n >> m;
    vector<pair<int, string>> ps(m);
    rep(i, m){
        int a;
        string b;
        cin >> a >> b;
        ps[i] = make_pair(a, b);
    }
    vector<int> ac(n + 1, 0), wa(n + 1 ,0);
    rep(i, m){
        if(ps[i].second == "AC"){
            if(ac[ps[i].first] == 0){
                ac[ps[i].first]++;
            }
        }else{
            if(ac[ps[i].first] == 0){
                wa[ps[i].first]++;
            }
        }
    }
    int a = 0, w = 0;
    rep(i, n + 1){
        if(ac[i] != 0){
            a += ac[i];
            w += wa[i];
        }
    }
    cout << a << " " << w << endl;
    return 0;
}

Measured memory_bytes: 7880
# https://atcoder.jp/contests/abc152/submissions/9693323

import sys
read = sys.stdin.read

N, *A = map(int, read().split())
mod = 10 ** 9 + 7


def min_factor(n):
    sieve = list(range(n + 1))
    sieve[2::2] = [2] * (n // 2)
    for i in range(3, int(n ** 0.5) + 2, 2):
        if sieve[i] == i:
            sieve[i * i::2 * i] = [i] * ((n - i * i) // (2 * i) + 1)
    return sieve


def prime_factorize(n):
    a = {}
    while n != 1:
        b = table[n]
        if b in a:
            a[b] += 1
        else:
            a[b] = 1
        n //= b
    return a


table = min_factor(max(A))

dic = {}
for i in A:
    for key, value in prime_factorize(i).items():
        if key in dic:
            dic[key] = max(dic[key], value)
        else:
            dic[key] = value

lcm = 1
for i, j in dic.items():
    lcm *= pow(i, j, mod)
    lcm %= mod

answer = sum(lcm * pow(i, mod - 2, mod) for i in A) % mod
print(answer)


Measured memory_bytes: 51572
#include "bits/stdc++.h"
using namespace std;

/* macro */
#define rep(i,a,b) for(int i=a;i<b;i++)
#define revrep(i,a,b) for(int i = a; i > b; i--)
#define int long long
#define exist(s,e) ((s).find(e)!=(s).end())
#define all(v) (v).begin(), (v).end()
#define each(s,itr) for(auto (itr) = s.begin(); (itr) != s.end(); (itr)++)
#define sum(v) accumulate(all(v), (0LL))
#define pb push_back


/* alias */


template<class T> using vec = vector<T>;
typedef vector<int> vi;
typedef pair<int, int> pi;


/* constant */
const int inf = 1000100010010010;
const int mod = 1e9 + 7;
int dx[8]={1,0,-1,0,-1,1,-1,1};
int dy[8]={0,1,0,-1,-1,-1,1,1};
const string alpha = "abcdefghijklmnopqrstuvwxyz";

/* io_method */
int input(){int tmp;cin >> tmp;return tmp;}
string raw_input(){string tmp;cin >> tmp;return tmp;}
string readline(){string s;getline(cin, s);return s;}
template<class T> void printx(T n){cout << n;}
template<class T, class U> void printx(pair<T, U> p){cout << "(" << p.first << "," << p.second << ")";}
template<class T> void printx(vector<T> v){cout << "{";rep(i,0,v.size()){printx(v[i]);if(i != v.size()-1)printx(",");}cout << "}";}
template<class T> void print(T n){printx(n);cout << endl;}
template<class T> void print(set<T> s){cout << "{";each(s, e){if(e != s.begin()) printx(",");printx(*e);}cout << "}" << endl;}
template<class T, class U> void print(map<T, U> mp){cout << "{";each(mp, e){cout << "(" << e -> first << "," << e -> second << ")";}cout << "}" << endl;}


/* general_method */
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }




/* main */

int n, w;
int weight[100];
int value[100];
int dp[100][100010];

int dfs(int i, int sum){

	if(i == n) return 0;

	if(dp[i][sum] > -1) return dp[i][sum];

	int ans = 0;

	if(weight[i] <= w - sum) 
		chmax(ans, value[i] + dfs(i + 1, sum + weight[i]));

	chmax(ans, dfs(i + 1, sum));

	return dp[i][sum] = ans;


}



signed main(){


    cin.tie(0);
    ios::sync_with_stdio(false);

	cin >> n >> w;
	rep(i,0,n){
		int wei, val; cin >> wei >> val;
		weight[i] = wei;
		value[i] = val;
	}

	memset(dp, -1, sizeof(dp));

	print(dfs(0, 0));



	




	




    



	








    



    





    


    

}



Measured memory_bytes: 78464
### main

loop do
  n = gets.to_i
  break if n == 0

  stars = []
  n.times do
    sx, sy, sz = gets.split.map(&:to_f)
    len = Math.sqrt(sx * sx + sy * sy + sz * sz)
    stars << [sx, sy, sz, len]
  end

  m = gets.to_i
  tss = []
  m.times do
    tx, ty, tz, th = gets.split.map(&:to_f)
    len = Math.sqrt(tx * tx + ty * ty + tz * tz)
    tss << [tx, ty, tz, len, Math.cos(th)]
  end
  #p [stars, tss]

  count = 0

  stars.each do |sx, sy, sz, slen|
    tss.each do |tx, ty, tz, tlen, cth|
      stc = (sx * tx + sy * ty + sz * tz) / (slen * tlen)
      if stc > cth
        count += 1
        break
      end
    end
  end
  
  puts count
end

Measured memory_bytes: 6156
n = int(input())
ans = float('inf')


def make_divisors(n):
    divisors = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)

    # divisors.sort()
    return divisors


candidate = make_divisors(n)
for i in range(len(candidate)):
    a = str(candidate[i])
    b = str(n // candidate[i])
    ans = min(ans, max(len(a), len(b)))
print(ans)

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

const int INF = 1e+9;


int main()
{
    int N, M;
    cin >> N >> M;
    vector<int> a(M), b(M), c(M); 
    for( int i = 0; i < M; ++i ) cin >> a[i] >> b[i] >> c[i];


    int minimumLength[101][101];
    for( int i = 1; i <= N; ++i ){
        for( int j = 1; j <= N; ++j ){
            if( i == j ) minimumLength[i][j] = 0;
            else minimumLength[i][j] = INF;
        }
    }
    for( int i = 0; i < M; ++i ){
        minimumLength[a[i]][b[i]] = c[i];
        minimumLength[b[i]][a[i]] = c[i];
    }
    
    for( int k = 1; k <= N; ++k ){
        for( int i = 1; i <= N; ++i ){
            for( int j = 1; j <= N; ++j ){
                minimumLength[i][j] = min( minimumLength[i][j], minimumLength[i][k] + minimumLength[k][j] );
            }
        }
    }

    int ans = 0;
    for( int i = 0; i < M; ++i ){
        if( minimumLength[a[i]][b[i]] != c[i] ) ++ans;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template <typename T> using vec = vector<T>;
template <typename T> using vvec = vector<vector<T>>;

constexpr int64_t mpow(int64_t a, int64_t b, int64_t mod = 1000000007) {
    if (b <= 0) { return 1; } if (b == 1) { return a % mod; } if (b == 2) { return (a * a) % mod; }
    return (max(a * (b & 1), (int64_t)1) * mpow(mpow(a, b / 2, mod), 2, mod)) % mod;
}
constexpr int64_t mdiv(int64_t a, int64_t b, int64_t mod = 1000000007) {
    return (a * mpow(b, mod - 2, mod)) % mod;
}

int main() {
    int n, l; cin >> n >> l;
    int all = n * (n - 1) / 2 + l * n;
    if (0 <= l) {
        cout << all - l << endl;
        return 0;
    }
    if (abs(l) < n) {
        cout << all << endl;
        return 0;
    }
    cout << all - (l + n - 1) << endl;
}



Measured memory_bytes: 3640
using System;

namespace ITP1_7_D
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] strs = Console.ReadLine().Split(' ');
            int n = int.Parse(strs[0]);
            int m = int.Parse(strs[1]);
            int l = int.Parse(strs[2]);
            int[,] a = ReadMatrix(n, m);
            int[,] b = ReadMatrix(m, l);
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < l; j++)
                {
                    long sum = 0;
                    for (int k = 0; k < m; k++) sum += (long)a[i, k] * b[k, j];
                    Console.Write(sum);
                    if (j < l - 1) Console.Write(" ");
                }
                Console.WriteLine();
            }
        }

        static int[,] ReadMatrix(int r, int c)
        {
            int[,] m = new int[r, c];
            for (int i = 0; i < r; i++)
            {
                string[] strs = Console.ReadLine().Split(' ');
                for (int j = 0; j < c; j++) m[i, j] = int.Parse(strs[j]);
            }
            return m;
        }
    }
}

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

typedef long long int lli;
typedef pair <int, int> ii;
typedef vector <int> vi;
typedef vector <ii> vii;

#define INF 1000000000
#define fastIO ios::sync_with_stdio(false);cout.tie(0);cin.tie(0);
#define endl '\n'
#define foreach(v,c) for(typeof((c).begin()) v=(c).begin();v!=(c).end();++v)
#define all(a) a.begin(),a.end()
#define in(a,b) ((b).find(a)!=(b).end())
#define fill(a,v) memset(a,v,sizeof a)
#define sz(a) ((int)(a.size()))
#define mp make_pair
#define pb push_back

int n, W;
lli dp[110000][110];
lli v[110];
lli w[110];
int main(){
  fastIO
  cin>>n>>W;
  for(int i = 1; i <= n; i++){
    cin>>w[i]>>v[i];
  }
  for(int j = 1; j <= n; j++){
    for(int i = 1; i <= W; i++){
      if(i >= w[j])dp[i][j] = max(dp[i][j - 1], dp[i - w[j]][j - 1] + v[j]);
      else dp[i][j] = dp[i][j - 1];
    }
  }
  cout<<dp[W][n]<<endl;
}

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

int main(void){
    int n,num,h,w;
    
    while(1){
        double best = 22,tmp;
        int bn;
        
        cin >> n;
        if(!n) break;
        
        for(int i = 0 ; i < n ; i++){
            cin >> num >> h >> w;
            
            double nh = (double)h / 100;
            double BMI = (double)w / (nh*nh);
            if(!i){
                tmp = fabs(BMI-best);
                bn = num;
                continue;
            }
            
            if(tmp > fabs(BMI-best)){
                tmp = fabs(BMI-best);
                bn = num;
            }
        }
        cout << bn << endl;
    }

    return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>
#include <iomanip>

#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
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 int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;
struct INIT { INIT(){
  cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;

int powMod(int n, int p, int mod) {
  int res = 1;
  while (p) {
    if (p & 1) (res *= n) %= mod;
    (n *= n) %= mod;
    p >>= 1;
  }
  return res;
}

signed main() {
  int N;
  cin >> N;
  
  string s;
  cin >> s;

  vector<int> one;
  REP(i, N) if(s[i] == '1') one.emplace_back(i);

  int a = 0, b = 0;
  int aa = 1, bb = 1;
  RREP(i, N){
    if(s[i] == '1'){
      (a += aa) %= (one.size()+1);
      if((int)one.size()-1 >= 1){
        (b += bb) %= (one.size()-1);
      }
    }
    (aa *= 2) %= (one.size()+1);
    if((int)one.size()-1 >= 1){
      (bb *= 2) %= (one.size()-1);
    }
  }

  vector<int> dp(N+1, 1);
  FOR(i, 1, N+1){
    int cnt = __builtin_popcountll(i);
    dp[i] = dp[i%cnt]+1;
  }

  vector<int> ans;
  aa = 1; bb = 1;
  RREP(i, N){
    if(s[i] == '1'){
      if(one.size() == 1) ans.emplace_back(0);
      else{
        int t = (b-bb)%((int)one.size()-1);
        if(t < 0) t += one.size()-1;
        ans.emplace_back(dp[t]);
      }
    }else{
      int t = (a+aa)%((int)one.size()+1);
      ans.emplace_back(dp[t]);
    }
    (aa *= 2) %= (one.size()+1);
    if((int)one.size()-1 >= 1){
      (bb *= 2) %= (one.size()-1);
    }
  }

  RREP(i, N){
    cout << ans[i] << "\n";
  }

  return 0;
}


Measured memory_bytes: 7880