akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#define mod 1000000007
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
inline void write(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
inline void pr1(int x){write(x),putchar(' ');}
inline void pr2(int x){write(x),puts("");}
char ss[100010];
int f[100010][15];
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
   	scanf("%s",ss+1);int len=strlen(ss+1);
   	int now=1;f[len+1][0]=1;
   	for(int i=len;i>=1;i--)
   	{
   		if(ss[i]=='?')
   		{
   			for(int k=0;k<10;k++)
   			{
   				int uf=k*now%13;
   				for(int j=0;j<13;j++)(f[i][(j+uf)%13]+=f[i+1][j])%=mod;
   			}
   		}
   		else
   		{
   			int uf=(ss[i]-'0')*now%13;
   			for(int j=0;j<13;j++)(f[i][(j+uf)%13]+=f[i+1][j])%=mod;
   		}now=now*10%13;
   	}pr2(f[1][5]);	
	return 0;
}

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

ll n,s,ans,dp[10000];
const int MOD=998244353;
void pl(ll &a,ll b){a=(a+b)%MOD;}

int main(){
  cin>>n>>s;
  vector<int> v(n);
  for(int i=0;i<n;i++)cin>>v[i];
  dp[0]=1;
  for(int i=0;i<n;i++){
    for(int j=s;j>=0;j--)pl(dp[j+v[i]],dp[j]);
    pl(dp[v[i]],i);
    pl(ans,dp[s]);
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <atcoder/all>
template<class T> inline bool chmin(T&a, T b){if(a > b){a = b; return true;}else{return false;}}
template<class T> inline bool chmax(T&a, T b){if(a < b){a = b; return true;}else{return false;}}
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1.0)
#define P pair<int,int>
#define PiP pair<ll,pair<ll,ll>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int main(){
    int n, q;
    cin >> n >> q;
    atcoder::dsu uf(n);
    rep(i, q){
        int t, u, v;
        cin >> t >> u >> v;
        if(!t)uf.merge(u, v);
        else cout << uf.same(u, v) << endl;
    }
}

Measured memory_bytes: 3968
#include<iostream>
using namespace std;
int main()
{
  char s;
  cin>>s;
  if(s=='A')
    cout<<'T'<<endl;
  else if(s=='T')
    cout<<'A'<<endl;
  else if(s=='G')
    cout<<'C'<<endl;
  else if(s=='C')
    cout<<'G'<<endl;
}

Measured memory_bytes: 256
n = int(input())
s = sorted([sorted(input()) for _ in range(n)])
cnt = 1
ans = 0
for i in range(n-1):
    if s[i] == s[i+1]:
        cnt += 1
    else:
        ans += cnt*(cnt-1)//2
        cnt = 1
ans += cnt*(cnt-1)//2
print(ans)


Measured memory_bytes: 25420
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int day = in.nextInt();
        int number = in.nextInt();
        int sum = 0;
        for(int i = 0; i < number; i++){
            sum += in.nextInt();
        }
        if(sum<=day){
            System.out.print(day-sum);
        }
        else{
            System.out.print(-1);
        }
    }
 
}

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

using namespace std;
typedef long long int lld;


int main(void){
	string a,b;
	cin >> a >> b;
	if((int)a.size()+1!=(int)b.size()) printf("No");
	else{
		int sz = (int)a.size();
		if(a==b.substr(0,sz)){
			printf("Yes");
		}else printf("No");
	}
	return 0;
}


Measured memory_bytes: 3720
#include <bits/stdc++.h>
#define r(i,a,n) for(int i=a;i<n;i++)
using namespace std;
int main(){
	int ww,n,c=1,p;
	while(cin>>ww,ww){
		cin>>n;
		int w[n+1],v[n+1],dp[n+1][ww+1];
		r(i,0,n+1)r(j,0,ww+1)dp[i][j]=0;
		r(i,1,n+1)scanf("%d,%d",&v[i],&w[i]);
		r(i,1,n+1){int p=1;
			r(j,1,ww+1){
				if(j<w[i])dp[i][j]=dp[i-1][j];
				else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
			}
		}
		r(i,0,ww+1)if(dp[n][i]<dp[n][ww])p=i;
		printf("Case %d:\n%d\n%d\n",c++,dp[n][ww],p+1);
	}
}

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

int main() {
	int l=0,r=0,d=0;
	cin>>l>>r>>d;
	int c=0;
	while(l<=r){
	    if(l%d==0){
	        c++;
	        l+=d;
	    }else{
	    l++;
	    }
	}
	cout<<c<<endl;
	return 0;
}


Measured memory_bytes: 3588
/*
  kadai4_3 stone_monument
  unomi
*/
#include <stdio.h>
#include <math.h>

int convert_snow_height(int east_height, int west_height){
    int east_tower_height=0, diff_height=0;
    // (east_height - west_height)本目(東側)と(east_height - west_height - 1)本目(西側)の間で高さ測定
    diff_height = east_height - west_height;
    // 1 ~ nまでの和を計算 -> 東側の(east_height - west_height)本目の塔の高さ
    east_tower_height = diff_height*(1+diff_height)/2;
    // 積雪の高さ = 東側の塔の高さ - 東側の雪に埋もれていない部分の高さ
    return east_tower_height - east_height;
}

int main(void){
    int west_height=0,east_height=0;
    // west_height(a), east_height(b) の入力を取得
    scanf("%d %d",&west_height, &east_height);

    printf("%d\n",convert_snow_height(east_height, west_height));

    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;
typedef long long ll;

int main() {
	int K, N;
	cin >> K >> N;
	vector<int> A(N);
	for (int i = 0; i < N; i++) cin >> A[i];
	int M = K - A[N - 1]+A[0];
	int ans = 0;
	bool dis = false;
	for (int i = 0; i < N - 1; i++) {
		int d = A[i + 1] - A[i];
		ans += d;
		if (M < d) {
			M = d;
			dis = true;
		}
	}
		if (dis) {
			cout << ans - M + K - A[N - 1]+A[0] << endl;
		}
		else {
			cout << ans << endl;
		}
}


Measured memory_bytes: 4016
#include <stdio.h>

void check(double eye, int table[4]);

int main(void)
{
	int right[4] = {0};
	int left[4] = {0};
	double r, l;
	int i;
	
	while (scanf("%lf %lf", &l, &r) != EOF){
		check(r, right);
		check(l, left);
	}
	for (i = 0; i < 4; i++){
		printf("%d %d\n", left[i], right[i]);
	}
	
	return 0;
}

void check(double eye, int table[4])
{
	if (eye >= 1.1){
		table[0]++;
	}
	else if (eye >= 0.6){
		table[1]++;
	}
	else if (eye >= 0.2){
		table[2]++;
	}
	else {
		table[3]++;
	}
}

Measured memory_bytes: 628
#include <stdio.h>

long long sqrt(long long x)
{
	long long l = 0, r = 1000000001;
	while (l + 1 < r){
		long long m = (l + r) / 2;
		if (m * m <= x) l = m;
		else r = m;
	}
	return l;
}

int main()
{
	int Q; scanf ("%d",&Q); while (Q--){
		long long a,b; scanf ("%lld %lld",&a,&b);
		long long s = a * b - 1, q = sqrt(s);
		long long ans = q * 2;
		if (s){
			if (a <= q) ans--;
			if (b <= q) ans--;
			if ((a != q || b != q) && q == s / q) ans--;
		}
		printf ("%lld\n",ans);
	}

	return 0;
}

Measured memory_bytes: 128
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <tuple>
#include <utility>
#include <vector>
#define ll long long
#define itn int
#define endl '\n'
#define co(ans) cout<<ans<<endl
#define COYE cout<<"YES"<<endl
#define COYe cout<<"Yes"<<endl
#define COye cout<<"yes"<<endl
#define CONO cout<<"NO"<<endl
#define CONo cout<<"No"<<endl
#define COno cout<<"no"<<endl
#define FORE(i,a) for(auto &i:a)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define PB push_back
#define MP make_pair
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define EACH(V,i) for(typeof((V).begin()) i=(V).begin();i!=(V).end();++i)
#define equals(a,b) (fabs((a)-(b))<EPS)
#define INF ((1LL<<62)-(1LL<<31))
#define EPS 1e-10
#define PI 3.141592653589793238
#define MOD 1000000007
#define MAX 5100000
using namespace std;
using Graph=vector<vector<int>>;
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T>inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
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;}
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(){
  int N;
  cin>>N;
  
  if(N==3){
    cout<<2<<" "<<5<<" "<<63<<endl;
    return 0;
  }
  
  vector<int> A;
  A.PB(3);
  A.PB(9);
  A.PB(2);
  A.PB(4);
  for(int i=1; i<=2499; ++i){
    A.PB(3+12*i);
    A.PB(9+12*i);
  }
  for(int i=1; i<=4999; ++i){
    A.PB(2+6*i);
    A.PB(4+6*i);
  }
  for(int i=1; i<=5000; ++i){
    A.PB(6*i);
  }
  
  if(N>=15000 || N%2==0){
    REP(i,N) cout<<A[i]<<" ";
    cout<<endl;
    return 0;
  }
  else{
    REP(i,N-1) cout<<A[i]<<" ";
    cout<<6<<endl;
    return 0;
  }
  return 0;
}

Measured memory_bytes: 512
#include<stdio.h>
#include<algorithm>
using namespace std;
int MOD=100000;
int dp[2001][3001];
int sum[2001][3001];
int main(){
	int a,b,c;
	while(scanf("%d%d%d",&a,&b,&c),a+b+c){
		for(int i=0;i<2001;i++)
			for(int j=0;j<3001;j++)
				dp[i][j]=dp[i][j]=sum[i][j]=0;
		dp[0][0]=1;
		for(int i=0;i<=b;i++){
			sum[i][0]=1;
		}
		for(int i=1;i<=a*a;i++){
		//	printf("%d %d\n",i,min(b,(a*a-i)?(c/(a*a-i)):b));
			for(int j=i;j<=min(b,(a*a-i)?(c/(a*a-i)):b);j++){
				for(int k=i*(i+1)/2;k+(a*a-i)*j<=c;k++){
					dp[j][k]=sum[j-1][k-j];
				}
			}
			for(int j=i-1;j<=min(b,(a*a-i)?(c/(a*a-i)):b);j++)
				for(int k=0;k+(a*a-i)*j<=c;k++)
					sum[j][k]=0;
			for(int j=i;j<=min(b,(a*a-i)?(c/(a*a-i)):b);j++){
				for(int k=i*(i+1)/2;k+(a*a-i)*j<=c;k++)
					sum[j][k]=(sum[j-1][k]+dp[j][k])%MOD;
			}
		}
		printf("%d\n",sum[b][c]);
	}
}

Measured memory_bytes: 0
import sys
import math
import itertools

N=int(input())
if(N%4==0):
    x=3*N//4
    print(x,x,x)
    exit()
for x in range(3501):
    if(4*x-2*N>0 and (N*x)%(4*x-2*N)==0):
        h=(N*x)//(4*x-2*N)
        print(h,x,x)
        exit()
if(N>2000):st=-1
else:st=1
for h,n in itertools.product(range(1,3501)[::st],range(1,3501)[::st]):
    x=N*h*n
    y=4*n*h-N*n-N*h
    if(y>0 and x%y==0):
        print(h,n,x//y)
        break
"""
4/N=1/h+1/n+1/w
4/N=(nw+hw+hn)/nhw
4nhw/N=nw+hw+hn
4nhw=Nnw+Nhw+Nhn
(4nh-Nn-Nh)w=Nhn
w=Nhn/(4nh-Nn-Nh)

4/N=3/x
4x/N=3
4x=3N
h,n,w=3N/4  (N%4==0)

4/N=1/h+2/x
4/N-2/x=1/h
(4x-2N)/Nx=1/h
h=Nx/(4x-2N)
"""


Measured memory_bytes: 41708
n, k = map(int, input().split())
a = list(map(int, input().split()))
visited = [False for i in range(n)]
town = []

now_town = 0
step = 0
while step <= k:
    visited[now_town] = step
    next_town = a[now_town] - 1
    town.append(now_town)
    if visited[next_town] is False:
        now_town = next_town
        step += 1
    else:
        break

pre_step = visited[next_town]
loop_step = step - pre_step + 1
loop = town[pre_step:(step+1)]
loop.append(town[0])

index = (k - pre_step) % loop_step
ans =loop[index] + 1
print(ans)

Measured memory_bytes: 106720
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORS(i, m, n) for (int i = m; i <= n; i++)
#define BIT(n) (1LL << (n))
#define INF 2e9
#define MOD (1000000007)
#define EPS 1e-9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long long int lli;
vector<int> h;
int operation(vector<int> &v)
{

    if (v.size() == 0)
        return 0;
    else if (v.size() == 1)
        return v[0];
    else if (v.size() == 2)
        return max(v[0], v[1]);
    else
    {
        auto itr = min_element(ALL(v));
        //vector<int>::iterator;
        int minVal = *itr;
        int minInd = distance(v.begin(), itr);
        REP(i, (int)(v.size()))
        {
            v[i] -= minVal;
        }
        //cout << minVal << " " << minInd << "\n";
        int val = minVal;

        vector<int> v0 = vector<int>(v.begin(), v.begin() + minInd);
        val += operation(v0);

        vector<int> v1 = vector<int>(v.begin() + (minInd + 1), v.end());
        val += operation(v1);

        return val;
    }
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    REP(i, N)
    {
        int p;
        cin >> p;
        h.push_back(p);
    }
    cout << operation(h) << "\n";
}

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

def f(pi,num):
    s = str(pi).zfill(6)+str(num+1).zfill(6)
    return s

shi = []
for i in range(0,m):
    shi.append([i]+list(map(int,input().split())))
shi.sort(key=lambda x:x[1])
p = shi[0][1]
pm = []
ans = []
for i in range(0,m):
    if shi[i][1] == p:
        pm.append([shi[i][0],shi[i][2]])
    else:
        pm.sort(key=lambda x:x[1])
        for j in range(0,len(pm)):
            ans.append([pm[j][0],f(shi[i-1][1],j)])
        pm = []
        pm.append([shi[i][0],shi[i][2]])
        p = shi[i][1]
pm.sort(key=lambda x:x[1])
for j in range(0,len(pm)):
    ans.append([pm[j][0],f(shi[m-1][1],j)])

ans.sort(key=lambda x:x[0])
for a in ans:
    print(a[1])

Measured memory_bytes: 51648
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  long long a[n];
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  
  long long s=a[0];
  long long cnt=0;
  if(s==0){
    if(a[1]>0){
      s=-1;
      cnt++;
    }
    else {
      s=1;
      cnt++;
    }
  }
  
  for(int i=1;i<n;i++){
    if(s>0){
      if(s+a[i]<0) s+=a[i];
      else {
        cnt+=abs(s+a[i])+1;
        s=-1;
      }
    }
    else {
      if(s+a[i]>0) s+=a[i];
      else {
        cnt+=abs(s+a[i])+1;
        s=1;
      }
    }
  }
  long long cnt2=0;
  s=a[0];
  if(s==0){
    if(a[1]>0){
      s=1;
      cnt2++;
    }
    else {
      s=-1;
      cnt2++;
    }
  }
  else if(s>0){
    cnt2+=s+1;
    s=-1;
  }
  else {
    cnt2+=abs(s)+1;
    s=1;
  }
  
  for(int i=1;i<n;i++){
    if(s>0){
      if(s+a[i]<0) s+=a[i];
      else {
        cnt2+=abs(s+a[i])+1;
        s=-1;
      }
    }
    else {
      if(s+a[i]>0) s+=a[i];
      else {
        cnt2+=abs(s+a[i])+1;
        s=1;
      }
    }
  }
  
  
  cout<<(cnt<cnt2? cnt:cnt2); 
}

Measured memory_bytes: 1024
N, Y = [int(_) for _ in input().split()]
x = 0
y = 0
z = 0
isOK = False


def sumMoney(x, y, z):
    return x*10000+y*5000+z*1000


for z in range(N+1):
    for y in range(N-z+1):
        x = N-z-y
        if sumMoney(x, y, z) == Y:
            print(x, y, z)
            isOK = True
            break
    if isOK:
        break


if not isOK:
    print(-1, -1, -1)

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

//template
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll;
const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;
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;}
//end

template<unsigned mod=1000000007>struct fp {
   unsigned v;
   static unsigned get_mod(){return mod;}
   unsigned inv() const{
      int tmp,a=v,b=mod,x=1,y=0;
      while(b)tmp=a/b,a-=tmp*b,swap(a,b),x-=tmp*y,swap(x,y);
      if(x<0)x+=mod; return x;
   }
   fp():v(0){}
   fp(ll x):v(x>=0?x%mod:mod+(x%mod)){}
   fp pow(ll t){fp res=1,b=*this; while(t){if(t&1)res*=b;b*=b;t>>=1;}return res;}
   fp& operator+=(const fp& x){if((v+=x.v)>=mod)v-=mod;return *this;}
   fp& operator-=(const fp& x){if((v+=mod-x.v)>=mod)v-=mod; return *this;}
   fp& operator*=(const fp& x){v=ll(v)*x.v%mod; return *this;}
   fp& operator/=(const fp& x){v=ll(v)*x.inv()%mod; return *this;}
   fp operator+(const fp& x)const{return fp(*this)+=x;}
   fp operator-(const fp& x)const{return fp(*this)-=x;}
   fp operator*(const fp& x)const{return fp(*this)*=x;}
   fp operator/(const fp& x)const{return fp(*this)/=x;}
   bool operator==(const fp& x)const{return v==x.v;}
   bool operator!=(const fp& x)const{return v!=x.v;}
}; using Fp=fp<>;
template<typename T>struct factorial {
   vector<T> Fact,Finv,Inv;
   factorial(int maxx){
      Fact.resize(maxx); Finv.resize(maxx); Inv.resize(maxx);
      Fact[0]=Fact[1]=Finv[0]=Finv[1]=Inv[1]=1; unsigned mod=Fp::get_mod();
      rep(i,2,maxx){
         Fact[i]=Fact[i-1]*i;
         Inv[i]=Inv[mod%i]*(mod-mod/i);
         Finv[i]=Finv[i-1]*Inv[i];
      }
   }
   T fact(int n,bool inv=0){if(inv)return Finv[n];else return Fact[n];}
   T inv(int n){return Inv[n];}
   T nPr(int n,int r){if(n<0||n<r||r<0)return Fp(0);else return Fact[n]*Finv[n-r];}
   T nCr(int n,int r){if(n<0||n<r||r<0)return Fp(0);else return Fact[n]*Finv[r]*Finv[n-r];}
};

Fp dp[210][101000];

int main(){
   int n,m; scanf("%d%d",&n,&m);
   vector<int> a(n); rep(i,0,n)scanf("%d",&a[i]);
   sort(ALL(a)); rep(i,0,m+1)dp[0][i]=i;
   rep(i,0,n)rep(j,0,m+1){
      dp[i+1][j]=dp[i][j]*i+dp[i][j%a[i]];
   }
   printf("%d\n",dp[n][m].v);
   return 0;
}

Measured memory_bytes: 83200
#include <iostream>
#include <iomanip>
#include <cassert>

#include <cstring>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <limits>
#include <queue>
#include <unordered_map>
#include <list>
#include <set>
#include <numeric>
using namespace std;

using ll = long long;

#define rep_init(i, init, n) for(int i = (init); i < (n); ++i)
#define rep(i, n) rep_init(i, 0, n)

template<typename T>
constexpr T divide_ceil(T a, T b)
{
	T remainder = a % b;
	return remainder == 0 ? a / b : (a + (b - remainder)) / b;
}


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

	int oddZ = 0;
	int evenZ = 0;

	rep(i, S.size())
	{
		if (S[i] == '0')
		{
			if (i % 2 == 0) ++evenZ;
			else ++oddZ;
		}
	}

	int ans = min(evenZ + (S.size() / 2 - oddZ), oddZ + (divide_ceil(S.size(), static_cast<size_t>(2)) - evenZ));

	cout << ans << endl;
}

Measured memory_bytes: 3700
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define vi vector<int>
#define all(a) a.begin(),a.end()

signed main(){
    int n;cin>>n;cout<<(10000-n)%1000<<endl;
}

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

int main(){
  long int h,m,s,S;
  cin >> S;
  h = S/(60*60);
  m = (S%(60*60))/(60);
  s = ((S%(60*60))%(60));
  cout << h << ":" << m <<":" << s << endl;
  

return 0;
}


Measured memory_bytes: 3084
k=int(input())
q=[1,2,3,4,5,6,7,8,9]
for i in range(k):
    l=q[i]
    if l%10!=0:
        q.append(10*l+l%10-1)
    q.append(10*l+l%10)
    if l%10!=9:
        q.append(10*l+l%10+1)
print(l)

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

typedef long long ll;
const int maxn=1e6+7;
const int inf=INT_MAX;
const ll inff=1e18;
const ll mod=1e9+7;
#define pii pair<int,int>
#define mkp make_pair
#define F first
#define S second
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
//#define int ll

#ifdef HNO2
#define IOS
#else
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0);
#endif // HNO2

int32_t main()
{
    IOS
    int n;
    cin>>n;
    cout<<(n-1)/2<<endl;
}



Measured memory_bytes: 256
#include <stdio.h>

int selectionSort(int *, int);

int main(){
  int n, number[100], a, count;

  scanf("%d",&n);
  for(a = 0; a < n; a++){
    scanf("%d",&number[a]);
  }

  count = selectionSort(number,n);
  for(a = 0; a < n-1; a++){
    printf("%d ",number[a]);
  }
  printf("%d\n",number[a]);
  printf("%d\n",count);

  return 0;
}

int selectionSort(int *p, int n){
  int a, b, count=0, min, temp;
  for(a = 0; a < n; a++){
    min = a;
    for(b = a; b < n; b++){
      if(*(p+b) < *(p+min)){
	min = b;
      }
    }
    if(*(p+a) == *(p+min)) continue;
    else{
      temp = *(p+a);
      *(p+a) = *(p+min);
      *(p+min) = temp;
      count++;
    }
  }
  return count;
}



Measured memory_bytes: 2104
X, N = map(int, input().split())
if N != 0:
  P = list(map(int, input().split()))
else:
  print(X)
  exit()

for i in range(101):
  if X-i not in P:
    print(X-i)
    exit()
  elif X+i not in P:
    print(X+i)
    exit()

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

int partition(int A[], int p, int r){
    int x = A[r];
    int i = p-1;
    for(int j=p; j<r; j++){
        if(A[j] <= x){
            i++;
            swap(A[i], A[j]);
        }
    }
    swap(A[i+1], A[r]);
    return i+1;
}
int main(){
    int n, i;
    scanf("%d", &n);
    int A[n];
    for(i=0; i<n; i++){
        scanf("%d", &A[i]);
    }
    int keyindex = partition(A, 0, n-1);
    for(i=0; i<n-1; i++){
        if(i == keyindex){
            printf("[%d] ", A[i]);
        } else {
            printf("%d ", A[i]);
        }
    }
    if(i == keyindex){
        printf("[%d]\n", A[i]);
    } else {
        printf("%d\n", A[i]);
    }

    return 0;
}


Measured memory_bytes: 3548
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define int long long
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define fast  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mod 1000000007
// order_of_key and *find_by_order
int32_t main()
{
	fast;
	int n;
	cin >> n;
	int a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	map<int , int > m;
	for (int i = 0; i < n; i++) {
		m[a[i] + i + 1]++;
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		ans += m[i + 1 - a[i]];
	}

	// for (auto it : m) {
	// 	ans += (it.second * (it.second - 1)) / 2;
	// }
	cout << ans;






}

Measured memory_bytes: 27820
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")



#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// #include <ext/rope>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
// template <typename T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// #define Find order_of_key
// #define at find_by_order
#define x first
#define y second
#define ll long long
#define lll __int128
#define ull unsigned long long
#define ulll unsigned __int128
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#define gu getchar_unlocked()
#define pu putchar_unlocked()
#define all(x) x.begin(),x.end()
#define endl '\n'


int main()
{
	int x;
	cin>>x;
	cout<<(!(x))<<endl;
	return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define REP(i,N) for(int i = 0; i < (int)N; i++)

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

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

typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<LD, LD> PDD;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define dbl(k, x) fixed << setprecision(k) << (x)

template <typename _T>
inline void _DBG(const char *s, _T x) {
  cerr << s << " = " << x << "\n";
}
template <typename _T, typename... args>
void _DBG(const char *s, _T x, args... a) {
  while (*s != ',') cerr << *s++;
  cerr << " = " << x << ',';
  _DBG(s + 1, a...);
}

#define _upgrade                \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0);
#define DBG(...) _DBG(#__VA_ARGS__, __VA_ARGS__)

// ********************** CODE ********************** //

const int N = 2e3 + 5;

vector<int> G[N];
int dist[N];

void bfs(int start_v) {
  vector<bool> vis(N, false);
  queue<PII> Q({{start_v, 0}});
  vis[start_v] = true;
  while (!Q.empty()) {
    auto p = Q.front();
    int v, d;
    tie(v, d) = p;
    for (auto u : G[v]) {
      if (!vis[u]) {
        dist[d + 1]++;
        vis[u] = true;
        Q.emplace(u, d + 1);
      }
    }
    Q.pop();
  }
}

int main() {
  _upgrade;
  int n, x, y;
  cin >> n >> x >> y;
  for (int i = 1; i < n; i++) {
    G[i].push_back(i + 1);
    G[i + 1].push_back(i);
  }
  G[x].push_back(y);
  G[y].push_back(x);
  for (int i = 1; i <= n; i++) {
    bfs(i);
  }
  for (int i = 1; i < n; i++) {
    cout << dist[i] / 2 << "\n";
  }
  return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
using ll=long long;
int main(){
    int n;
    cin>>n;
    vector<int>v(n);
    rep(i,n)cin>>v[i];
    sort(v.begin(),v.end());
    double x=double(v[0]+v[1])/2;
    for(int i=2; i<n; ++i){
        x=double(x+v[i])/2;
    }
    cout<<x<<endl;
    return 0;
}

Measured memory_bytes: 256
# coding: utf-8
# Your code here!

import bisect

N = int(input())
L = list(map(int, input().split()))

# print(N)
# print(L)

L_sorted = sorted(L)
# print(L_sorted)

count = 0
for i in range(0, N - 2):
    # print(i)
    for j in range(i + 1, N - 1):
        a = L_sorted[i]
        b = L_sorted[j]
        # print(j)
        # for k in range(j + 1, N):
        #     a = L_sorted[i]
        #     b = L_sorted[j]
        #     c = L_sorted[k]
            
        #     if a + b <= c:
        #         break
        #     # print('{}, {}, {}'.format(a, b, c))
        #     count += 1
        
        # print('{}, {},'.format(a, b))
        index = bisect.bisect_left(L_sorted, a + b, i + 1, N)
        # print(index)
        # print((index - 1) - j)
        count += ((index - 1) - j)
        
print(count)        

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

int main()
{
ll n ;
cin >> n ;
vector<string> s(n);
map<string,ll> m;
rep(i, n){
  cin >> s[i];
  m[s[i]]++;
}

cout <<m.size() << endl;
return 0;
}

Measured memory_bytes: 25040
using System;

public class Hello{
    public static void Main(){
        int n = int.Parse(Console.ReadLine());
        
        int num = (int)Math.Log10(n) + 1;
        int result1 = num % 2 == 1 ? 1 + n - (int)(Math.Pow(10, num - 1)) : 0;
        num--;
        
        while(true){
            if(num % 2 == 0){
                num--;
            }else{
                int res = (int)(Math.Pow(10, num) - Math.Pow(10, num - 1));
                result1 += res;
                num -= 2;
            }
            
            if(num <= 0){
                break;
            }
        }
        
        Console.WriteLine(result1);
    }
}


Measured memory_bytes: 11220
#include<iostream>
#include<string>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int Max = 1e3 + 7;
int lst[Max], ls[Max];
int n;

int main()
{
	int n;
	cin >> n;
	int sum = 0;
	map<char, int> ma;
	for (int i = 1; i <= n; i++)
	{
		char t;
		cin >> t;
		if (ma[t]) continue;
		else
		{
			ma[t]++;
			sum++;
		}
	}
	if (sum == 4) cout << "Four";
	else cout << "Three";
	 

}

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

using namespace std;

#define pb push_back
#define mp make_pair
#define MOD ((int)(1e9) + 7)
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define filename "lynext"
#define freop freopen(filename ".cik","w",stdout);freopen(filename ".gir","r",stdin)
const long long int N = ((long long int)1e5) + 5;
const long long int M = ((long long int)1e3) + 5;
const long long int llinf = (long long int)1e18;
const int inf = INT_MAX;
typedef long long int lli;

lli n,l;
lli arr[N];
lli ind = -1;

int main ()
{
	fast;
	//freop;
	cin >> n >> l;
	for (lli i = 1; i <= n; i++)
		cin >> arr[i];
	for (lli i = 1; i <= n - 1; i++)
	{
		if (arr[i] + arr[i + 1] >= l)
		{
			ind = i;
		}
	}
	if (ind == -1)
		return cout << "Impossible\n",0;
	cout << "Possible\n";
	for (lli i = 1; i < ind; i++)
	{
		cout << i << "\n";
	}
	for (lli i = n - 1; i >= ind + 1; i--)
	{
		cout << i << "\n";
	}
	cout << ind << "\n";
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
#define ll long long
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define rep1(i, n) for(int i = 1; i <= (n); ++i)
#define ms(x, v) memset(x, v, sizeof(x))
using namespace std;
const int N = 1e5 + 5, MOD = 1e9 + 7;
ll fac[N];
ll mabs(ll x)
{
    return x < 0 ? -x : x;
}
int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    ios::sync_with_stdio(0), cin.tie(0);
    fac[0] = 1;
    rep1(i, N - 1) fac[i] = fac[i - 1] * i % MOD;
    ll n, m;
    while(cin >> n >> m)
    {
        if(n == m)
        {
            cout << (2 * fac[n] * fac[m] % MOD) << endl;
        }
        else if(mabs(n - m) <= 1)
        {
            cout << (fac[n] * fac[m] % MOD) << endl;
        } else
        {
            cout << 0 << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define all(v) (v).begin(),v.end()
set<string> c;
const ll mod=1000000007;
const ll mod2=998244353;
const ll inf=100000000000000000;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
vector<int> dy={-1,0,1,0},dx={0,-1,0,1};
ll dp[200000][5];
int main(){
 string s;
 cin>>s;
 int n=s.size();
 dp[0][0]=1;
 for(int i=0;i<n;i++){
     for(int j=0;j<5;j++){
         if(s[i]!='?')dp[i+1][j]+=dp[i][j];
         else dp[i+1][j]+=dp[i][j]*3;
         dp[i+1][j]%=mod;
     }
     if(s[i]=='A'||s[i]=='?')dp[i+1][1]+=dp[i][0];
     if(s[i]=='B'||s[i]=='?')dp[i+1][2]+=dp[i][1];
     if(s[i]=='C'||s[i]=='?')dp[i+1][3]+=dp[i][2];
     for(int j=1;j<=3;j++){
           dp[i+1][j]%=mod;
     }
 }
 cout<<dp[n][3]<<endl;
}



Measured memory_bytes: 4608
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int N;
    cin>>N;
    vector<pair<int,int>> A(N);
    for (int i=0; i<N; i++)
    {
        cin>>A[i].first;
        A[i].second = i;
    }
    sort(A.begin(), A.end());
    int ans = 0;
    for (int i=0; i<N; i++)
        if (A[i].second%2 != i%2)
            ans++;
    cout<<ans/2<<endl;
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <stdlib.h>

#define WHITE 0
#define GRAY 1
#define BRACK 2

int matrix[101][101];
int color[101];
int dist[101];

int n;
int time;

int queue[101];
int head;
int tail;

void enqueue(int);
int dequeue(void);
void bfs(void);


int main(){
  int i,j,u,k,v;

  scanf("%d",&n);

  // queue = malloc((n+1) * sizeof(int));
  //color = malloc((n+1) * sizeof(int));
  //dist = malloc((n+1) * sizeof(int));
 
  
  //matrix = malloc((n+1) * sizeof(int *));
  //for(i=0;i<n+1;i++) matrix[i] = malloc((n+1) * sizeof(int));


  for(i=1;i<n+1;i++) dist[i] = -1;
  
  for(i=1;i<n+1;i++)
    for(j=1;j<n+1;j++)
      matrix[i][j] = 0;
  
  
  for(i=0;i<n;i++){
    scanf("%d",&u);
    scanf("%d",&k);
    for(j=0;j<k;j++){
      scanf("%d",&v);
      matrix[u][v] = 1;
    }
  }


  bfs();
 

  for(i=1;i<n+1;i++) printf("%d %d\n",i,dist[i]);

  //for(i=0;i<n+1;i++)
  //  free(matrix[i]);
  //free(matrix);
  //free(queue);
  //free(dist);
  //free(color);

  return 0;
}

void bfs(){
  int u,i;

  head = tail = 0;
  color[1] = GRAY;
  dist[1] = 0;
  enqueue(1);
  
  while(head != tail){
    u = dequeue();
    for(i=1;i<n+1;i++){
      if(matrix[u][i] == 1 && color[i] == WHITE){
	color[i] = GRAY;
	dist[i] = dist[u] + 1;
	enqueue(i);
      }
    }
    color[i] = BRACK;
  }
}

void enqueue(int q){
  
  queue[tail] = q;
  if(++tail == (n+1)) tail = 0;
  
}

int dequeue(){
  int v;
  
  v = queue[head];
  if(++head == (n+1)) head=0;
  return v;

}

Measured memory_bytes: 636
N, K = map(int, input().split())

# x_1 + x_2 + ... x_k = n
# x_i >= 0
# k個の箱にn個のボールを入れる重複組み合わせ　n+k-1_C_k-1
# n個の玉とk-1個の仕切りを並べる

# x_1 + x_2 + ... x_k = n
# x_i >= 1
# k個の箱にn個のボールを1個以上入れる重複組み合わせ　n-1_C_k-1
# n個の玉の仕切りn-1個の中に、k-1箇所仕切りを入れる

from math import factorial

# k = 1,2,...,K
for k in range(1, K + 1):
    if k > N - K + 1:
        print(0)
        continue

    # k = 1,2,...,K
    # K個の青いボールをk個に分割する方法
    # K-1_C_k-1
    c1 = factorial(K - 1) // (factorial(K - k) * factorial(k - 1))
    c1 = int(c1) % (10 ** 9 + 7)

    # N-K個の赤いボールの分割
    # k+1個に分割(しかし両端はなくても良い)
    # N-K+1_C_k

    # x_1 + x_2 + ... + x_k + x_k+1 = N−K
    # x1 >= 0
    # x_2,x_3,...,x_k >= 1
    # x_k + 1 >= 0

    c2 = factorial(N - K + 1) // (factorial(N - K - k + 1) * factorial(k))
    c2 = int(c2) % (10**9 + 7)

    ans = c1 * c2 % (10**9 + 7)
    print(ans)


Measured memory_bytes: 9184
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
map<long long,int> mp;
int main()
{
	int n;
	cin>>n;
	long long ret=0,sum=0;
	mp[0]++;
	for(int i=0;i<n;i++)
	{
		long long a;
		cin>>a;
		sum+=a;
		ret+=mp[sum];
		mp[sum]++;
	}
	cout<<ret<<endl;
	return 0;
}

Measured memory_bytes: 12800
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <iomanip>
using namespace std;
#define INF 1e9
#define PI acos(-1)
typedef long long ll;


int main() {
	int n;
	cin >> n;
	vector<ll> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		a[i] -= i + 1;
	}
	sort(a.begin(), a.end());

	ll ans = LLONG_MAX;
	int left = 0, right = n;
	for (int i = 0; i < 101;i++) {
		int mid = (left + right) / 2;
			ll sum = 0;
			for (int j = 0; j < n; j++) {
				sum += abs(a[j] - a[mid]);
			}
			if (sum < ans) {
				ans = sum;
				left = mid;
			}
			else right = mid;
		}

	cout << ans << endl;
}

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

const int MOD = 1000000007;
struct modint {
  long long val;
  modint(long long val=0) : val((val % MOD + MOD) % MOD){}
  modint operator-() const { return modint(-val); }
  modint& operator+=(const modint a) { if ((val += a.val)     >= MOD) val -= MOD; return *this; }
  modint& operator-=(const modint a) { if ((val += MOD-a.val) >= MOD) val -= MOD; return *this; }
  modint& operator*=(const modint a) { (val *= a.val) %= MOD; return *this; }
  modint operator+(const modint a) const { return (modint)*this += a; }
  modint operator-(const modint a) const { return (modint)*this -= a; }
  modint operator*(const modint a) const { return (modint)*this *= a; }
  modint pow(long long n) const { modint r(1), m(val); while (n > 0) { if (n & 1) {r *= m;} m *= m; n >>= 1; } return r; }
  modint inv() const { return pow(MOD-2); }
  modint& operator/=(const modint a) { return (*this) *= a.inv(); }
  modint operator/(const modint a) const { return (modint)*this /= a; }
  bool operator==(const modint &p) const { return val == p.val; }
  bool operator!=(const modint &p) const { return val != p.val; }
  friend ostream &operator<<(ostream &os, const modint &p) { return os << p.val; }
  friend istream &operator>>(istream &is, modint &a) { long long t; is >> t; a = modint(t); return (is); }
};

struct mod_combination {
  /* initialize: O(n) */
  /* choose    : O(1) */
  vector<modint> fact, fact_inv, inv;
  mod_combination(int n) : fact(n+1, 1), fact_inv(n+1, 1), inv(n+1, 1) {
    for (int i = 2; i <= n; i++) {
      fact[i] = fact[i - 1] * i;
      inv[i] = -inv[MOD % i] * (MOD / i);
      fact_inv[i] = fact_inv[i - 1] * inv[i];
    }
  }
  modint choose(int n, int k) { return fact[n] * fact_inv[k] * fact_inv[n - k]; }
};

modint choose(modint n, int k, bool allow_duplicates=false) {
  /* O(k log MOD) */
  if(allow_duplicates) n = n+k-1;
  modint c = 1;
  for(int i=1; i<=k; i++) c *= (n-i+1) / i;
  return c;
}

signed main() {
#if 1 // https://atcoder.jp/contests/abc156/tasks/abc156_d
  int n,a,b;
  cin >> n >> a >> b;
  cout << modint(2).pow(n) - 1 - choose(n,a) - choose(n,b) << endl;
#elif 1 // https://atcoder.jp/contests/abc021/tasks/abc021_d
  int n,k; cin >> n >> k;
  cout << choose(n,k,true) << endl; 
#else // test mod_combination
  int n=1000;
  mod_combination mc(n);
  for( int i=1; i<=n; i++) for( int j=1; j<=i; j++) {
    if(i%100==0 && j==1) cerr << i << endl;
    modint c1 = mc.choose(i,j);
    modint c2 = choose(i,j);
    assert(c1==c2);
  }
#endif
}


Measured memory_bytes: 3620
a, b, m = list(map(int, input().split()))
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
sum_list = []

min_sum = min(a_list) + min(b_list)


for i in range(m):
    x, y, c = list(map(int, input().split()))
    sum = a_list[x - 1] + b_list[y - 1] - c
    sum_list.append(sum)

print(min(min(sum_list), min_sum))


Measured memory_bytes: 18740
#include<iostream>
#include<string>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> l;
  for (int i = 0; i < n; i++) {
    int li;
    cin >> li;
    l.push_back(li);
  }
  sort(l.begin(), l.end());
  
  int total = 0;
  for (int i = 0; i < n - 2; i++) {
  	for (int j = i + 1; j < n - 1; j++) {      
      int min = abs(l[j] - l[i]) + 1, imin = 0;
      for (int k = j; k < n; k++) {
        if (l[k] >= min) {
          imin = k;
          break;
        }
      }
      if (l[imin] >= std::min(l[i], l[j]))
        imin++;
      
      int max = l[i] + l[j] - 1, imax = n;
      for (int k = n - 1; k >= 0; k--) {
        if (l[k] <= max || k <= j) {
          imax = k;
          break;
        }
      }
      if (imax == std::max(i, j))
        imax--;
      
      total += std::max(imax - imin + 1, 0);
    }
  }
  
  cout << total << endl;
  
  return 0;
}


Measured memory_bytes: 256
# Dice I

d = [int(i) for i in input().rstrip().split()]

class Dice:
    def __init__(self, a1, a2, a3, a4, a5, a6):
        # サイコロを縦横にたどると書いてある数字(index1は真上、index3は真下の数字)
        self.face = [a1, a2, a3, a4, a5, a6]
        self.v = [a5, a1, a2, a6] # 縦方向
        self.h = [a4, a1, a3, a6] # 横方向
        self.det = 1
        # print(self.v, self.h)

    # サイコロの上面の数字を表示
    def top(self):
        return self.v[1]

    # サイコロを北方向に倒す
    def north(self):
        newV = [self.v[1], self.v[2], self.v[3], self.v[0]]
        self.v = newV
        self.h[1] = self.v[1]
        self.h[3] = self.v[3]
        return self.v, self.h

    # サイコロを南方向に倒す
    def south(self):
        newV = [self.v[3], self.v[0], self.v[1], self.v[2]]
        self.v = newV
        self.h[1] = self.v[1]
        self.h[3] = self.v[3]
        return self.v, self.h

    # サイコロを東方向に倒す
    def east(self):
        newH = [self.h[3], self.h[0], self.h[1], self.h[2]]
        self.h = newH
        self.v[1] = self.h[1]
        self.v[3] = self.h[3]
        return self.v, self.h

    # サイコロを西方向に倒す
    def west(self):
        newH = [self.h[1], self.h[2], self.h[3], self.h[0]]
        self.h = newH
        self.v[1] = self.h[1]
        self.v[3] = self.h[3]
        return self.v, self.h

    def searchFace(self, a):
        b = 0
        for i in range(6):
            if a == self.face[i]:
                # print('一致しました')
                b = i + 1
        return b

    def smallen(self, x): # a は 1 から 6 のどれか
        y = int(7 / 2 - abs(x - 7 / 2))
        if x != y:
            self.det *= -1
        # print(self.det)
        return y

    def rightSide(self, top, front):
        r = 0
        if top == 1 and front == 2:
            r = 3
        elif top == 2 and front == 3:
            r = 1
        elif top == 3 and front == 1:
            r = 2
        elif top == 1 and front == 3:
            r = 5
        elif top == 3 and front == 2:
            r = 6
        elif top == 2 and front == 1:
            r = 4
        if self.det == -1:
            r = 7 - r
        return r

dice1 = Dice(d[0], d[1], d[2], d[3], d[4], d[5])

# command = list(input().rstrip())
# print(command)

# for i, a in enumerate(command):
#     if a == 'N':
#         dice1.north()
#     elif a == 'S':
#         dice1.south()
#     elif a == 'E':
#         dice1.east()
#     elif a == 'W':
#         dice1.west()
# print(dice1.top())

questionAmount = int(input())
for i in range(questionAmount):
    # Initialize det
    dice1.det = 1
    question = [int(i) for i in input().rstrip().split()]
    a = dice1.searchFace(question[0])
    b = dice1.searchFace(question[1])
    # print(a, b)
    top = dice1.smallen(a)
    front = dice1.smallen(b)
    # print(top, front)
    position = dice1.rightSide(top, front)
    answer = dice1.face[position - 1]
    print(answer)



Measured memory_bytes: 5632
#include <iostream>

using namespace std;

#define ll long long

int main() {
	ll mod = 1e9 + 7;
	ll n, ans = 1;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		ans = ans * i % mod;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1000000007;

int main(){
  int sx,sy,tx,ty;
  cin>>sx>>sy>>tx>>ty;
  int dx=tx-sx,dy=ty-sy;
  string ans;
  for (int i=0;i<dx;i++) ans.push_back('R');
  for (int i=0;i<dy;i++) ans.push_back('U');
  for (int i=0;i<dx;i++) ans.push_back('L');
  for (int i=0;i<dy;i++) ans.push_back('D');
  ans.push_back('D');
  ans.push_back('R');
  for (int i=0;i<dx;i++) ans.push_back('R');
  for (int i=0;i<dy;i++) ans.push_back('U');
  ans.push_back('U');
  ans.push_back('L');
  ans.push_back('U');
  ans.push_back('L');
  for (int i=0;i<dx;i++) ans.push_back('L');
  for (int i=0;i<dy;i++) ans.push_back('D');
  ans.push_back('D');
  ans.push_back('R');
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <numeric>
using namespace std;

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<((x))<<endl
#define fi first
#define se second

#define INF 2147483600
#define long long long
#define EPS 1e-8

// ???????°???°???????????????
inline double add(double a, double b){
  if(abs(a+b) < EPS*(abs(a) + abs(b))) return 0;
  return a+b;
}

struct Point{
  double x,y;
  Point() {}
  Point(double nx, double ny) : x(nx), y(ny) {}
  inline Point operator + (const Point & p){ return Point(add(x, p.x), add(y, p.y)); }
  inline Point operator - (const Point & p){ return Point(add(x,-p.x), add(y,-p.y)); }
  inline Point operator * (double d){ return Point(x*d, y*d); }
  inline double dot(const Point & p){ return add(x * p.x, y*p.y); }  //??????
  inline double det(const Point & p){ return add(x * p.y, -y*p.x); } //??????
  inline double dist(const Point & p){ return sqrt((x-p.x)*(x-p.x) + (y-p.y)*(y-p.y)); }
  inline bool operator < (const Point & p) const {
    if(x != p.x) return x < p.x;
    else return y < p.y;
  }
  inline bool operator == (const Point & p) const {
    return (add(x, -p.x)==0) && (add(y, -p.y)==0);
  }
  friend ostream& operator<<(ostream& os, const Point& p) {
    os << "[" << p.x << "," << p.y << "]";
    return os;
  }
};

pair<Point, Point> calcCenter(Point &p1, Point &p2){
  if(add(p1.x, -p2.x)==0){
    double y = (p1.y + p2.y)/2;
    double dx = sqrt(1 - (p1.y - y)*(p1.y - y));
    return mp(Point(p1.x+dx, y), Point(p1.x-dx,y));
  }
  // 2???????????´???????????? Ax + By + C = 0 , A != 0
  double A = 2*(p1.x - p2.x);
  double B = 2*(p1.y - p2.y);
  double C = - p1.x*p1.x + p2.x*p2.x - p1.y*p1.y + p2.y*p2.y;
  // x = py+q
  double p = -B/A; double q = -C/A;

  // p1, p2 ??¨????????¢???1?????? ay^2 + 2by + c = 0
  double a = 1 + p*p;
  double b = p*q - p1.x*p - p1.y;
  double c = q*q - 2*p1.x*q + p1.x*p1.x + p1.y*p1.y - 1;

  double rt = sqrt(b*b-a*c);
  double y1 = (-b+rt)/a;
  double y2 = (-b-rt)/a;

  return mp(Point(p*y1+q, y1), Point(p*y2+q, y2));
}

int main(){
  int n;
  while(scanf("%d", &n), n){
    vector<Point> vec;
    rep(i,n){
      double x,y;
      scanf("%lf %lf", &x, &y);
      vec.pb(Point(x,y));
    }

    int res=1;
    rep(i,n) repl(j,i+1,n) if(vec[i].dist(vec[j]) <= 2+EPS){
      pair<Point, Point> pr = calcCenter(vec[i], vec[j]);
//      cout << pr.fi << pr.se << endl;
      int cnt=0;
      rep(k,n) if(pr.fi.dist(vec[k]) <= 1+EPS) cnt++;
      res = max(res, cnt);
      cnt=0;
      rep(k,n) if(pr.se.dist(vec[k]) <= 1+EPS) cnt++;
      res = max(res, cnt);
    }

    printf("%d\n", res);

  }
  return 0;
}

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

namespace ABC173
{
    class B
    {
        static void Main(string[] args)
        {
            //var CA = Enumerable.Repeat(0, (int)N).Select(_ => Console.ReadLine().Split().Select(long.Parse).ToArray()).ToArray();
            //var NMK = Console.ReadLine().Split().Select(long.Parse).ToArray();
            var N = long.Parse(Console.ReadLine());
            var S = new string[N];
            var Count = new long[4];
            for (int i = 0; i < N; i++)
            {
                S[i] = Console.ReadLine();
                if (S[i] == "AC") Count[0]++;
                if (S[i] == "WA") Count[1]++;
                if (S[i] == "TLE") Count[2]++;
                if (S[i] == "RE") Count[3]++;
            }

            Console.WriteLine("AC x " + Count[0]);
            Console.WriteLine("WA x " + Count[1]);
            Console.WriteLine("TLE x " + Count[2]);
            Console.WriteLine("RE x " + Count[3]);

        }
    }
}


Measured memory_bytes: 31420
S = input()
A = []
ans =0
for i in range(len(S)) :
    if i%2 == 0 :
        A.append(1)
    else :
        A.append(0)
for i in range(len(S)) :
    if int(S[i]) != int(A[i]) :
        ans +=1
print(min(ans, len(S)-ans))

Measured memory_bytes: 4084
#include <bits/stdc++.h>
#define rep(i,n) for (ll i = 0; i < n; ++i)
#define sz(x) int(x.size())
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())
#define FORV(i, v) for (auto i = v.begin(); i != v.end(); i++)
using namespace std;

using ll = long long;
using P = pair<int, int>;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const int INF = 1001001001;
const long long INFLL = LLONG_MAX / 3;
const double eps = (1e-9);

ll calc(vector<ll>& a, int n, int flag) {
  ll ans = 0;
  ll sum = 0;
  rep(i, n) {
    if (i % 2 == flag) {
      if (sum + a[i] < 1) {
        // 足した結果を +1 以上にしたい
        ans += 1 - (sum + a[i]);
        sum = 1;
      } else {
        sum += a[i];
      }
    } else {
      // 足した結果を -1 以下にしたい
      if (sum + a[i] > -1) {
        ans += (sum + a[i]) + 1;
        sum = -1;
      } else {
        sum += a[i];
      }
    }
  }
  return ans;
}

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

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

  ll ans = calc(a, n, 0);
  chmin(ans, calc(a, n, 1));

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1024