akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <sstream>
#include <functional>
#include <numeric>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;

const int INF = 1 << 29;
typedef pair<char, int> P;

string s;

int main(void)
{
	map<char, int> m;
	m['J'] = 0;
	m['O'] = 1;
	m['I'] = 2;
	while(cin >> s && s != "")
	{
		int size = s.size();
		int jc = 0, oc = 0, ic = 0;
		int maxk;
		vector<P> ps;
		int psi = 0;
		ps.push_back(P(s[0],1));
		for (int i = 0; i + 1 < size; i++)
		{
			if(s[i + 1] == s[i])
				ps[psi].second++;
			else
			{
				ps.push_back(P(s[i+1],1));
				psi++;
			}
		}

		int psize = ps.size();
		int ans = 0;
		for (int i = 0; i + 2 < psize; i++)
		{
			if(ps[i].first != 'J' || ps[i + 1].first != 'O' || ps[i + 2].first != 'I')
				continue;
			if(ps[i].second >= ps[i+1].second && ps[i+1].second <= ps[i+2].second)
				ans = max(ans, ps[i+1].second);
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 12124
#include<stdio.h>

#define N 101

int main()
{
  int i,j,n,u,k,v;
  int gr[N][N];
  
  scanf("%d",&n);

  for(i=1; i<=n; i++)
    {
      for(j=1; j<=n; j++)
	{
	  gr[i][j]=0;
	}
    }

  for(i=0; i<n; i++)
    {
      scanf("%d%d",&u,&k);

      for(j=0; j<k; j++)
	{
	  scanf("%d",&v);

	  gr[u][v]=1;
	}
    }

  for(i=1; i<=n; i++)
    {
      for(j=1; j<=n; j++)
	{
	  printf("%d",gr[i][j]);
	  if(j != n)printf(" ");
	}
      printf("\n");
    }

  return 0;
}
	    
	    
	   



Measured memory_bytes: 2088
//reference:wtl666wtl
# include <stdio.h>
int a[103], b[103];
int main()
{
    int p1=0, p2=0, m=100;
    long long n;
    scanf("%lld",&n);
    ++n;
    while(n > 1)
    {
        if(n&1) a[++p1] = m--, --n;
        else b[++p2] = m--, n>>=1;
    }
    printf("%d\n",p1+p2<<1);
    for(int i=1; i<=p1; ++i)
        printf("%d ",a[i]);
    for(int i=p2; i>=1; --i)
        printf("%d ",b[i]);
    for(int i=101-p1-p2; i<=100; ++i)
        printf("%d ",i);
    puts("");
    return 0;
}


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

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int a,b,br=0;
    cin >> a >> b;
    br=a*(a-1)/2+b*(b-1)/2;
    cout << br;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f(i,a,b) for(int i(a);i<b;i++)
#define rep(i,n) for(int i(0);i<n;i++)
#define fast  ios_base::sync_with_stdio(0); cin.tie(0);
#define pres(x) cout<<fixed; cout<<setprecision(x);
#define open freopen("input.txt","r",stdin) ; freopen("output.txt","w",stdout);
#define watch(x) cout<<(#x)<<" is "<<x<<"\n";
#define mod 1000000007

int32_t main(){
	
	fast;
	//open;
	bool flag=false;
	string s;
	cin>>s;
	if((s[0]==s[1])&&(s[2]==s[3])&&(s[0]!=s[2]))flag = true;
	else if((s[0]==s[2])&&(s[1]==s[3])&&(s[0]!=s[1]))flag = true;
	else if((s[0]==s[3])&&(s[2]==s[1])&&(s[0]!=s[2]))flag = true;

	if(flag)cout<<"Yes";
	else cout<<"No";

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <map>
#include <utility>
#include <numeric>
#include <typeinfo>

using namespace std;

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

  vector<bool> x(N+1,false);
  for(int i=0;i<M;i++){
    if(a.at(i)==1)  x.at(b.at(i))=true;
    if(b.at(i)==1)  x.at(a.at(i))=true;
  }

  vector<bool> y(N+1,false);
  for(int i=0;i<M;i++){
    if(a.at(i)==N)  y.at(b.at(i))=true;
    if(b.at(i)==N)  y.at(a.at(i))=true;
  }

  bool flag=false;
  for(int i=0;i<N+1;i++){
    if(x.at(i)==true && y.at(i)==true)  flag=true;
  }
  
  if(flag)  cout << "POSSIBLE" << endl;
  else  cout << "IMPOSSIBLE" << endl;

  return 0;
}


Measured memory_bytes: 1920
import math
i = input()
a = int(i.split(' ')[0])
b = int(i.split(' ')[1])
x = int(i.split(' ')[2])
if 2*x>=b*a*a:
  print(math.degrees(math.atan(2*b/a - 2*x/ (a*a*a))))
else:
  print(math.degrees(math.atan(b/(2*x/(a*b)))))

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

#define int long long
#define INF 9223372036854775807

vector<int> Graph[100009];
vector<bool> visited(100009, false);
vector<int> topo(0);
vector<int> dist(100009,-1);

void dfs(int node){
    visited[node] = true;
    for(int a : Graph[node]){
        if(visited[a]) continue;
        else dfs(a);
    }
    topo.push_back(node);
}

int diam(int node){
    if(dist[node] != -1) return dist[node];
    int tot = 0;
    visited[node] = true;
    for(int a : Graph[node]){
        //if(visited[a]) continue;
        tot = max(tot, diam(a)+1);
    }
    return dist[node] = tot;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        Graph[a].push_back(b);
    }
    for(int i = 1; i<= n; i++){
        if(!visited[i]){
            dfs(i);
        }
    }
    for(int i =0 ; i < 100009; i++)visited[i] = false;
    for(int i = 1; i < n; i++){
        if(!visited[topo[i]]){

            diam(topo[i]);
            //cout << "hhe " << dist[topo[i]] << endl;
        }
    }
    int tot = -INF;
    for(int i = n; i>=1; i--){
        tot = max(tot, dist[i]);
    }
    cout << tot << endl;
}


Measured memory_bytes: 9720
import sys
import numpy as np
from collections import defaultdict



#input = sys.stdin.readline

def main():
    N, K = map(int,input().split())
    A = list(map(int,input().split()))
    A = [0] +A  #transporter
    visited = [0] * (N+1)
    town = 1
    cycle = 0
    for i in range(1,K+1):
        town = A[town]
        if visited[town] ==0:
            visited[town] = i
        else:
            cycle = i - visited[town]
            place = (K - visited[town]) % cycle + visited[town]
            print(visited.index(place))
            exit()
    print(town)




if __name__ == "__main__":
    main()

Measured memory_bytes: 51056
#!/usr/bin/env python
# coding: utf-8

# In[11]:


import math
from functools import reduce


# In[17]:


N,K = map(int, input().split())
A = list(map(int, input().split()))


# In[18]:


def gcd_list(numbers):
    return reduce(math.gcd, numbers)


# In[19]:


g = gcd_list(A)
if K <= max(A) and K%g == 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")


# In[ ]:






Measured memory_bytes: 20320
function Main(input) {
    const args = input.split(' ');
    const a = parseInt(args[0]);
    const b = parseInt(args[1]);

    var result = 10;
    if (a < b) result = 0;

    console.log(result);
}

// main("3 5");

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

using namespace std;

#define int long long

main() {
#ifdef HOME
    //freopen("input.txt", "r", stdin);
#endif // HOME
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int a, b, n, ans = 0;
    cin >> a >> b >> n;
    for (int i = n; i <= n; ++i) ans = max(ans, a * i / b - a * (i / b));
    if (n >= b - 1 && b > 1) {
        int x = b - 1 + (n - b + 1) / (b - 1) * (b - 1);
        ans = max(ans, a * x / b - a * (x / b));
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 3668
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
using namespace std;
#define INF 1010101010
#define MOD 1000000007
#define LL long long

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

    bool even = s.size() % 2 == 0;
    bool same = s[0] == s[s.size()-1];

    cout << (even == same ? "First" : "Second") << endl;
}

Measured memory_bytes: 512
from math import sqrt
n = int(input())
XY = [list(map(int, input().split())) for i in range(n)]

ans = []
for i in range(0,n):
  for j in range(0,n):
    k = sqrt((XY[i][0]-XY[j][0])**2 + (XY[i][1]-XY[j][1])**2)
    ans.append(k)
    
print(sum(ans)/n)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;

int n,a[305],ans,m,num,frc=1;
int f[2][305][305],typ[605];

inline void ad(int &x,int y){x+=y;if(x>=mod) x-=mod;}

int main(){
	int i,j,k,pr=0;
	scanf("%d",&n);m=n+n;
	for(i=1;i<=m;++i) scanf("%d",&a[i]);
	for(i=1;i<=m;i+=2)
	  if((a[i]==-1)||(a[i+1]==-1)){
		num+=(((~a[i])||(~a[i+1]))^1);
		if(~a[i]) typ[a[i]]=1;if(~a[i+1]) typ[a[i+1]]=1;
	  }else typ[a[i]]=typ[a[i+1]]=2;
	for(i=1;i<=num;++i) frc=(ll)frc*i%mod; 
	f[0][0][0]=1;num=0;
	
	
	
//1 0 1 0 0 1 	
	for(i=m;i;--i) if(typ[i]!=2){
		pr^=1;memset(f[pr],0,sizeof(f[pr]));
		for(j=0;j<=num;++j)
		  for(k=0;j+k<=num;++k) if(f[pr^1][j][k]){
			 if(typ[i]){
			 	ad(f[pr][j][k+1],f[pr^1][j][k]);
			 	if(j) ad(f[pr][j-1][k],(ll)f[pr^1][j][k]%mod);
			 }else{
			 	ad(f[pr][j+1][k],f[pr^1][j][k]); 
			 	if(k) ad(f[pr][j][k-1],(ll)k*f[pr^1][j][k]%mod);

			 	if(j) ad(f[pr][j-1][k],f[pr^1][j][k]);
			 }
		  }
		num=min(num+1,m>>1);
//		for(j=0;j<=num;++j)
//		 for(k=0;k+j<=num;++k) if(f[pr][j][k]){
//		 	printf("%d %d %d:%d\n",i,j,k,f[pr][j][k]);
//		 }
//		puts("");
	}
	printf("%d",(ll)frc*f[pr][0][0]%mod);
}
/*
0 1 1
1 0 0
1 0 0
*/

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using llu=unsigned long long;
#define mod 1000000007
#define mode 998244353
#define PI 3.14159265358979323846
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define mms(x,y) memset(x,y,sizeof(x))
#define pqm priority_queue<ll,vector<ll>,greater<ll>>
#define pb push_back
#define um unordered_map
#define pr pair
#define mm multimap
#define ms multiset
#define mp make_pair
#define vr vector
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define inf INT_MAX
#define ninf INT_MIN
#define ff first
#define ss second
#define gcd __gcd
int main()
{
    fast;
    ll t,n,m,i,j,k;
    cin>>n>>k;
    ll a[n];
    for(i=0;i<n;i++)cin>>a[i];
    ll dp[n+1][k+1];
    mms(dp,0);
    for(i=0;i<=n;i++)dp[i][0]=1;
    for(i=1;i<=n;i++)
    {
        ll dp1[k+1];
        dp1[0]=dp[i-1][0];
        for(j=1;j<=k;j++)
        {
            dp1[j]=(dp1[j-1]+dp[i-1][j])%mod;
            if(j<=a[i-1])
            {
                dp[i][j]=dp1[j];
            }
            else
            {
                dp[i][j]=dp1[j];
                if(j-a[i-1]>0)dp[i][j]=(dp[i][j]-dp1[j-a[i-1]-1]+mod)%mod;
            }
        }
    }
    cout<<dp[n][k];
}


Measured memory_bytes: 80000
#include<stdio.h>
int main()
{
    int n,i,f1=0;
    char a[110];
    scanf("%d",&n);
    getchar();
    for(i=0;i<n;i++)
    {
        if(i<n-1)
        {
            scanf("%c",&a[i]);
            getchar();
            if(a[i]=='Y')
                f1=1;
        }
        else
        {
            scanf("%c",&a[i]);
            if(a[i]=='Y')
                f1=1;
        }

    }
    if(f1==1)
        printf("Four\n");
    else
        printf("Three\n");
    return 0;
}


Measured memory_bytes: 128
#include <stdio.h>
#include <string.h>
int min(int a,int b){return a<b?a:b;}
int main(void){
    int a,b,count=50;
    scanf("%d%d",&b,&a);
    printf("100 100\n");
    char t[120],s[120]="....................................................................................................";
    strcpy(t,s);
    a--;
    while(a>0){
        int p=min(50,a);
        for (int i=0; i<p; i++){
            t[i*2]='#';
        }
        printf("%s\n%s\n",t,s);
        strcpy(t,s);
        a-=50;
        count-=2;
    }
    for (int i=0; i<count; i++){
        printf("%s\n",s);
    }
    
    char v[120],u[120]="####################################################################################################";
    strcpy(v,u);
    b--;
    count=50;
    while(b>0){
        int p=min(50,b);
        for (int i=0; i<p; i++){
            v[i*2]='.';
        }
        printf("%s\n%s\n",u,v);
        strcpy(v,u);
        b-=50;
        count-=2;
    }
    for (int i=0; i<count; i++){
        printf("%s\n",u);
    }
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>


using namespace std;
using namespace __gnu_pbds;


#define INF (1<<30)
#define INFll (1ll<<62)
#define F first
#define S second
#define MOD 1000000007
#define mkp(a, b) make_pair(a, b)


typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;


#define FOR(I, A, B) for(int (I) = (A); (I) < (B); (I)++)
#define ROF(I, A, B) for(int (I) = (A); (I) >= (B); (I)--)
#define SQR(A) 1ll*(A)*(A)


typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


const char array_sep[] = " ";
const char array_end[] = "";


const char pair_sep[] = " ";
const char pair_end[] = "";


const char map_sep[] = "->";
const char map_end[] = "\n";


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


template<typename A> ostream & operator<<(ostream & os, const vector<A> & x)
{
    for(int i = 0; i < x.size(); i++)
      os << x[i] << array_sep;
    os << array_end;
    return os;
}


template<typename A, typename B> ostream & operator<<(ostream & os, const pair<A, B> & x)
{
    os << x.first << pair_sep << x.second << pair_end;
    return os;
}


template<typename A> istream & operator>>(istream & is, vector<A> & x)
{
    for(int i = 0; i < x.size(); i++)
        is >> x[i];
    return is;
}


template<typename A, typename B> istream & operator>>(istream & is, pair<A, B> & x)
{
    is >> x.first >> x.second;
    return is;
}


template<typename _key, typename _val> ostream & operator<<(ostream & os, map<_key, _val> & mp)
{
    for(auto it : mp)   // not for C++98 or earlier
        os << it->F << map_sep << it->S << map_end;
    return os;
}


template<typename _response> void die(_response ans)
{
	cout << ans << endl;
	exit(0);
}

//typedef pair<pair<int, int >, int > query;
string s;

int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
//	freopen("errlog.log", "w", stderr);
	ios_base::sync_with_stdio(0);
//	cout << fixed << setprecision(10);
//	srand(time(0));

    cin >> s;

    map<char, vector<int > > p;
    for(int i = 0; i < s.size(); i++)
        p[s[i]].push_back(i);

    for(auto& pr : p)
    {
        auto& ar = pr.S;
        for(int i = 0; i < pr.S.size()-1; i++)
        {
            if(ar[i+1] - ar[i] <= 2)
            {
                cout << ar[i]+1 << " " << ar[i+1]+1 << endl;
                exit(0);
            }
        }
    }
    cout << -1 << " " << -1 << endl;
	return 0;
}


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

#define int long long
#define double long double
#define ff first
#define ss second
#define endl '\n'
#define ii pair<int, int>
#define mp make_pair
#define mt make_tuple
#define DESYNC                      \
  ios_base::sync_with_stdio(false); \
  cin.tie(0);                       \
  cout.tie(0)
#define pb push_back
#define vi vector<int>
#define vii vector<ii>
#define all(x) x.begin(), x.end()
#define EPS 1e-9
#define INF 1e18
#define ROOT 1
#define M 1000000007
#define curtime chrono::steady_clock::now().time_since_epoch().count
#define rep(i, beg, n, s) for (int i = beg; i < n; i += s)
const double PI = acos(-1);

using namespace std;

inline int mod(int n, int m = M) {
  int ret = n % m;
  if (ret < 0) ret += m;
  return ret;
}

int exp(int n, int k) {
  if (k == 0) return 1;
  if (k == 1) return n;
  int ax = exp(n, k / 2);
  ax = mod(ax * ax);
  if (k % 2) ax = mod(ax * n);
  return ax;
}

int gcd(int a, int b) {
  if (a == 0)
    return b;
  else
    return gcd(b % a, a);
}
//#define MULTIPLE_TEST_CASE
void solution() {
  vector<int> f(10001, 0);
  for (int x = 1; x <= 250; x++) {
    for (int y = 1; y <= 250; y++) {
      for (int z = 1; z <= 250; z++) {
        int ans = x * x + y * y + z * z + x * z + y * z + x * y;
        if (ans <= 10000) f[ans]++;
      }
    }
  }
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) cout << f[i] << endl;
}

int32_t main() {
  DESYNC;
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  int t = 1;
#ifdef MULTIPLE_TEST_CASE
  cin >> t;
#endif
  while (t--) solution();
}


Measured memory_bytes: 3688
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        try (Scanner in = new Scanner(System.in)) {
            int N = in.nextInt();
            int K = in.nextInt();
            int[] a = new int[N];
            for (int i = 0; i < N; i++) {
                a[i] = in.nextInt();
            }

            long[] cumsum = new long[N + 1];
            for (int i = 1; i <= N; i++) {
                cumsum[i] = a[i - 1] + (i - 1 >= 0 ? cumsum[i - 1] : 0);
            }
//            Utils.debug(cumsum);

            ArrayList<Long> beauty = new ArrayList<>();
            for (int l = 0; l < N + 1; l++) {
                for (int r = l + 1; r < N + 1; r++) {
                    beauty.add(cumsum[r] - cumsum[l]);
                }
            }
            Collections.sort(beauty);
//            Utils.debug(beauty);

            long max = 0;
            for (int shift = 60; shift >= 0; shift--) {
                long mask = 1L << shift;
                int count = 0;
                for (int i = beauty.size() - 1; i >= 0; i--) {
                    if ((beauty.get(i).longValue() & mask) == 0) {
                        continue;
                    }
                    count++;
                }
                if (count >= K) {
                    max |= mask;
                    ArrayList<Long> tmp = new ArrayList<>();
                    for (int i = beauty.size() - 1; i >= 0; i--) {
                        if ((beauty.get(i).longValue() & mask) == 0) {
                            continue;
                        }
                        tmp.add(beauty.get(i).longValue());
                    }
                    beauty.clear();
                    beauty.addAll(tmp);
                }
            }

            System.out.println(max);
        }
    }
}


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

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	long long n;
	cin>>n;

	if(n%2!=0)
		cout<<0;

	else
	{
		long long ans=0,div=10;
		while(div <= n)
		{
			ans+=(n/div);
			div*=5;
		}

		cout<<ans;
	}
	return 0;
}

Measured memory_bytes: 3612
#pragma GCC optimize "03"
#include "bits/stdc++.h"
using namespace std;
 
#define int long long int
#define ld long double
#define pi pair<int, int>
#define pb push_back
#define fi first
#define se second
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#ifndef LOCAL
#define endl '\n'
#endif
 
const int N = 4e3 + 5;
const int mod = 998244353;
const int inf = 1e9 + 9;

int c[N][N], p2[N];
 
signed main() {
	IOS;
	#ifdef LOCAL
		freopen("input.txt","r", stdin);
		freopen("output.txt","w",stdout);
	#endif
	c[0][0] = 1;
	p2[0] = 1;
	for(int i = 1; i < N; i++){
		p2[i] = (p2[i-1]*2) % mod;
		c[i][0] = 1;
		for(int j = 1; j < N; j++)
			c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
	}
	int n, k;
	cin >> k >> n;
	for(int i = 2; i <= 2*k; i++){
		int ans = 0;
		int p = 0;
		for(int j = 1; j <= min(i, k); j++){
			if(j <= k && i-j <= k && i != j && j <= i-j)
				p++;
		}
		int rem = k - 2*p;
		if(!(i&1))	rem++, p--;
		for(int q = 0; q <= p; q++){
			int z = (c[p][q]*p2[q]) % mod;
			int y = c[n+rem-1][q+rem-1];
			if(!(i&1))
				y = (y + c[n+rem-2][q+rem-1]) % mod;
			ans = (ans + z*y) % mod;
		}
		cout << ans << endl;
	}	
	return 0;
}

Measured memory_bytes: 125568
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Scanner;

public class Main {
	InputStream in = System.in;
	PrintStream out = System.out;

	public void _main(String[] args) {
		Scanner sc = new Scanner(in);

		int a = sc.nextInt();
		int b = sc.nextInt();
		sc.close();

		int ans = a - 1;
		ans += a <= b ? 1 : 0;

		out.println(ans);

	}

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


Measured memory_bytes: 21972
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct Edge {
    int d, i, j;
    Edge(int d_, int i_, int j_) : d(d_), i(i_), j(j_) {}
    bool operator< (const Edge& right) const{
        return d > right.d;
    }
};
void calc(int t, vector<vector<pair<int, int > > >& G, vector<int>& distance){
    int new_black = t;
    priority_queue<Edge> temp;
    for (int i = 1; i < G.size(); i++) {
        for (int j = 0; j < G[new_black].size(); j++) {
            if (distance[G[new_black][j].first] != -1) continue;
            int dis = G[new_black][j].second + distance[new_black];
            temp.push(Edge(dis, new_black, G[new_black][j].first));
        }
        while (distance[temp.top().j] != -1) temp.pop();
        distance[temp.top().j] = temp.top().d;
        new_black = temp.top().j;
        temp.pop();
    }
}

int main(){
    int n;
    cin >> n;
    vector<vector<pair<int, int> > > G(n);
    for (int i = 0; i < n; i++) {
        int u, k;
        cin >> u >> k;
        G[u].resize(k);
        for (int j = 0; j < k; j++) {
            int v, c;
            cin >> v >> c;
            G[u][j] = make_pair(v, c);
        }
    }

    vector<int> distance(n, -1);
    distance[0] = 0;
    calc(0, G, distance);
    for (int i = 0; i < n; i++) {
        cout << i << " " << distance[i] << endl;
    }
    return 0;
}



Measured memory_bytes: 9784
#include <bits/stdc++.h>
#include <vector>
using namespace std;
 
int main(){
    int N;
    cin >> N;
    string S;
    cin >> S;
    for(int i = 0; i < S.size(); i++){
        S.at(i) += N;
        if(S.at(i) > 'Z'){
            S.at(i) -= 26;
        }
        cout << S.at(i);
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <list>
#include <utility>
#include <queue>
#include <memory>
#include <cstring>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>

using namespace std; 

int
main(int argc, char const *argv[])
{
    string s, t;
    cin >> s;
    cin >> t;

    int64_t ans = 0;

    for (int i = 0; i < 3; i++) {
	if (s[i] == t[i]) {
	    ans++;
	}
    }
    
    cout << ans << endl;
    return 0;
}
 


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <string.h>

int gcd(int a,int b){
    if(a<b){
        int now=a;
        a=b;
        b=a;
    }

    int r=a%b;
    while(r!=0){
        a=b;
        b=r;
        r=a%b;
    }

    return b;
}



/* 値を入れ替える関数 */
void swap (int *x, int *y) {
  int temp;    // 値を一時保存する変数

  temp = *x;
  *x = *y;
  *y = temp;
}

/***
* pivotを決め、
* 全データをpivotを境目に振り分け、
* pivotの添え字を返す
***/
int partition (int array[], int left, int right) {
  int i, j, pivot;
  i = left;
  j = right + 1;
  pivot = left;   // 先頭要素をpivotとする

  do {
    do { i++; } while (array[i] < array[pivot]);
    do { j--; } while (array[pivot] < array[j]);
    // pivotより小さいものを左へ、大きいものを右へ
    if (i < j) { swap(&array[i], &array[j]); }
  } while (i < j);

  swap(&array[pivot], &array[j]);   //pivotを更新

  return j;
}

/* クイックソート */
void quick_sort (int array[], int left, int right) {
  int pivot;

  if (left < right) {
    pivot = partition(array, left, right);
    quick_sort(array, left, pivot-1);   // pivotを境に再帰的にクイックソート
    quick_sort(array, pivot+1, right);
  }
}



int main(void){
    long int n;
    scanf("%ld",&n);

    char ans[100];

    int count=0;
    while(n>0){
        int d=n%26;
        if(d==0){//zに対応させたいとき
            n-=26;
            d+=26;
        }
        //d:='a'からどれくらい離れているか
        d--;
        char c='a'+d;
        ans[count]=c;
        count++;
        n/=26;
    }

    int i;
    for(i=count-1;i>=0;i--){
        printf("%c",ans[i]);
    }
    printf("\n");
}

Measured memory_bytes: 1640
using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
using System.Text;

public class Program
{

    public void Proc()
    {
        int inpt = int.Parse(Reader.ReadLine());
        int ans = inpt / 3;
        Console.WriteLine(ans);
        
    }




    public class Reader
    {
        static StringReader sr;
        public static bool IsDebug = false;
        public static string ReadLine()
        {
            if (IsDebug)
            {
                if (sr == null)
                {
                    sr = new StringReader(InputText.Trim());
                }
                return sr.ReadLine();
            }
            else
            {
                return Console.ReadLine();
            }
        }
        private static string InputText = @"


8



";
    }

    public static void Main(string[] args)
    {
#if DEBUG
        Reader.IsDebug = true;
#endif
        Program prg = new Program();
        prg.Proc();
    }
}


Measured memory_bytes: 11092
import java.util.*;
import java.math.RoundingMode;
import java.math.BigDecimal;
 
public class Main {
	
	
	 
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int d = sc.nextInt();
        if (a+b > c + d) {
        	System.out.println("Left");
        }
        else if (a+b < c + d) {
        	System.out.println("Right");
        }
        else {
        	System.out.println("Balanced");
        }
	}
}

Measured memory_bytes: 21972
//累積和を使った
#include <iostream>
#include <vector>
//#include<bits/stdc++.h>
#include <algorithm>
using namespace std;

int main(){
  int N,Q;
  string S;
  cin >> N >> Q >> S;
  vector<int> ans(Q),hoge;
  int cnt = 0;
  for(int i = 0; i < S.length()-1; i++){
    if(S[i] == 'A'&&S[i+1]=='C'){
      hoge.push_back(cnt++);
    }else{
      hoge.push_back(cnt);
    }
  }
  hoge.push_back(cnt);
  for( int i = 0; i < Q; i++){
    int tmpl,tmpr;
    cin >> tmpl >> tmpr;
    ans[i] = hoge[tmpr-1] - hoge[tmpl-1];
  }
  for( int i = 0; i < Q; i++){
    cout << ans[i] << endl;
  }
}

Measured memory_bytes: 1912
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string[] str = Console.ReadLine().Split();
		long A = long.Parse(str[0]);
		long B = long.Parse(str[1]);
		long[] C = new long[A];
		string[] str2 = Console.ReadLine().Split();
		for(var i=0;i<A;i++){
			C[i] = long.Parse(str2[i]);
		}
		Array.Sort(C);
		long sum = 0;
		long ans = -1;
		for(var i=0;i<A;i++){
			sum += C[i];
			if(sum > B){
				ans = i;
				break;
			}
		}
		if(ans == -1){
			if(sum == B){
				ans = A;
			} else {
				ans = A-1;
			}
		}
		Console.WriteLine(ans);
	}
}

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

int main(){
    int max_A = 1000000;
    int A[max_A];

    cin >> A[0];

    int ans = 0;
    for (int i = 1; i < max_A; i++){
        if(A[i-1] % 2 == 0){
            A[i] = A[i-1] / 2;
        }
        else {
            A[i] = 3 * A[i-1] + 1;
        }
    }

    bool cons = false;
    for (int j = 0; j < max_A; j++){
        for (int k = j + 1; k < max_A; k++){
            int a = A[j];
            int b = A[k];

            if (a == b){
                ans = k;
                cons = true;
                break;
            }
        }
        if (cons){
            break;
        }
    }
    cout << ans + 1 << endl;
}


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

int main()
{
string n;
cin>>n;
char c;
int suma = 0;
for(int i = 0; i < n.size(); i++)
{
suma += n[i]-48;
}
if(atoi( n.c_str()) % suma == 0) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;

namespace ABC126_C
{
    class Program
    {
        static void Main(string[] args) {
            string[] input = Console.ReadLine().Split();
            int n = int.Parse(input[0]);
            int k = int.Parse(input[1]);

            double ans = 0;
            for (int i = 1; i <= n; i++) {
                long numberOfKakeru = 0;
                long nowNumber = i;

                //if (i < k) Console.WriteLine(i);
                while(nowNumber < k) {
                    nowNumber *= 2;
                    numberOfKakeru++;
                }

                //Console.Write(numberOfKakeru);
                ans += Math.Pow(0.5, numberOfKakeru);
            }
            ans /= n;

            Console.WriteLine(ans);
        }
    }
}

Measured memory_bytes: 13140
import sys
l, r = map(int, input().split())
ans = []
for i in range(l, r + 1):
    for j in range(i + 1, r + 1):
        ans.append((i * j) % 2019)
        if (i * j) % 2019 == 0:
            print(0)
            sys.exit()
print(min(ans))

Measured memory_bytes: 43504
object Main{
  def main(args: Array[String]){
    if (sys.env.getOrElse("TEST", "")=="1"){
      println(test());
    }else{
      val input=io.Source.stdin.getLines().mkString("\n");
      println(solve(input).trim());
    }
  }

  def solve(input:String):String={
    input.split("").filter(_ == "1").size.toString()
  }

  val tests=List("""3 9""" -> """12""",
    """31 32""" -> """63""",
    """1 2""" -> """3""",
    """-1 2""" -> """1""",
    """10 1""" -> """11""");

  def test():String= {
    return tests.map{case (i,o)=>(i.trim(),o.trim())}
      .zipWithIndex.map{
      case ((input,outputExpect),i)=>{
        val output=solve(input).trim();
        s"test${i+1}:"+(if(output==outputExpect){
          "Passed"
        }else{
          s"Failed\nexpect:\n${outputExpect}\noutput:\n${output}"
        })
      }}
      .mkString("\n");
  }
}


Measured memory_bytes: 25624
# https://atcoder.jp/contests/abc079/tasks/abc079_b

import itertools
import collections
import bisect

def main():
    N = int(input())

    L = [0] * 90
    L[0] = 2
    L[1] = 1
    for i in range(2, 87):
        L[i] = L[i-1] + L[i-2]
    print(L[N])


if __name__ == '__main__':
    main()


Measured memory_bytes: 3316
#include <algorithm>
#include <cstdio>

#define int long long
#define dotimes(i, n) for (int i : range(n))

using namespace std;

class range {
  class iterator {
    int i, s;
  public:
    iterator(int i, int s): i(i), s(s) {}
    int& operator*() {
      return i;
    }
    void operator++() {
      i += s;
    }
    bool operator!=(iterator const& that) {
      return i < that.i;
    }
  };
  iterator b, e;
public:
  range(int e): b({0, 1}), e({e, 1}) {}
  range(int b, int e): b({b, 1}), e({e, 1}) {}
  range(int b, int e, int s): b({b, s}), e({e, s}) {}
  iterator begin() {
    return b;
  }
  iterator end() {
    return e;
  }
};

int rint() {
  int n;
  scanf("%lld", &n);
  return n;
}

void wint(int n) {
  printf("%lld\n", n);
}

template<typename T>
inline int size(T container) {
  return static_cast<int>(container.size());
}

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

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

signed main() {
  for (;;) {
    int n = rint();
    int x = rint();
    if (!n && !x)
      break;
    int r = 0;
    for (int a : range(x / 3 + 1, min(x - 3, n) + 1)) {
      int s = x - a;
      r += min(s, a) - 1 - s / 2;
    }
    wint(r);
  }
  return 0;
}



Measured memory_bytes: 2716
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mkp make_pair
#define repr(i,a) for(int i=0;i<a;i++)
using namespace std;
int gcd(int a,int b)
{
    if(b==0)
        return a;
    return(a,b%a);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t=1;//cin>>t;
    while(t--)
    {
        ll k,m,sum=0,x=0; cin>>k;
        string str; cin>>str;
        if(str.size()<=k)
            cout<<str<<endl;
        else
        {
            string ptr=str.substr(0,k);
            ptr=ptr+"...";
            cout<<ptr<<endl;
        }

    }
    return 0;
}



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

int main()
{
    int h, w;
    for (;;) {
	cin >> h >> w;
	if (h == 0 && w == 0)
	    return 0;
	for (int c1 = 0; c1 < h; c1++) {
	    for (int c2 = 0; c2 < w; c2++) {
		if (c1 == 0 || c2 == 0 || c1 == h - 1 || c2 == w - 1)
		    cout << "#";
		else
		    cout << ".";
	    }

	    cout << endl;

	}
	cout << endl;
    }
}

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

using namespace std;

const int nax=88;
bool dp[nax][nax][nax*nax*2+77];
int ile[nax][nax];
int a[nax][nax];
int b[nax][nax];

int n,m;

int dodaj=nax*nax;

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) cin>>a[i][j];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) cin>>b[i][j];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            ile[i][j]=a[i][j]-b[i][j];
            if(ile[i][j]<0) ile[i][j]=-ile[i][j];
        }
    }
    dp[1][1][dodaj+ile[1][1]]=1;
    dp[1][1][dodaj-ile[1][1]]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(i==1 && j==1) continue;
            for(int k=0;k<=nax*nax*2+5;k++)
            {
                int val=k+ile[i][j];
                if(i-1>0 && val>=0 && val<=nax*nax*2+5)
                {
                    if(dp[i-1][j][val]==1) dp[i][j][k]=1;
                }
                if(j-1>0 && val>=0 && val<=nax*nax*2+5)
                {
                    if(dp[i][j-1][val]==1) dp[i][j][k]=1;
                }
                val=k-ile[i][j];
                if(i-1>0 && val>=0 && val<=nax*nax*2+5)
                {
                    if(dp[i-1][j][val]==1) dp[i][j][k]=1;
                }
                if(j-1>0 && val>=0 && val<=nax*nax*2+5)
                {
                    if(dp[i][j-1][val]==1) dp[i][j][k]=1;
                }
            }
        }
    }
    int res=1e9;
    for(int i=0;i<=2*nax*nax+5;i++)
    {
        if(dp[n][m][i]) res=min(res,abs(i-dodaj));
    }
    cout<<res;
    return 0;
}


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

using namespace std;

int main(){
	int n,x;
	cin >> n >> x;
	vector<int> m(n);
	int sum =0;
	int mini = x;
	for(int i=0;i<n;i++){
		cin >> m[i];
		x -= m[i];
		mini = min(mini,m[i]);
	}
	cout << (int)x/mini + n << endl;
	return 0;
}

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

int main(){
    int M[100][100];
    int n,u,k,v;
    
    cin >> n;//頂点数
    
    for (int i=0; i<n; i++){
        for (int j=0; j<n; j++){
            M[i][j]=0;
            //cout << M[i][j] << " ";
        }
        //cout << endl;
    }
    //cout << endl;
    
    for (int i=0; i<n; i++){
        cin >> u >> k; //uは頂点番号, kはuの出次数
        u--;
        for (int j=0; j<k; j++){
            cin >> v;//uに隣接する頂点番号
            v--;
            M[u][v]=1;
        }
        
    }
    
    for (int i=0; i<n; i++){
        for (int j=0; j<n; j++){
            if(j==n-1) cout << M[i][j];
            else cout << M[i][j] << " ";
        }
        cout << endl;
    }
}


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

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

    int minimum, maximum;
    if(a == 0 || b == 0) {
        maximum = minimum = 0;
    } else {
        maximum = min(a, b);
        if(n < a+b) minimum = a+b - n;
        else minimum = 0;
    }

    cout << maximum << " " << minimum << endl;
}

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

#define int long long
void solve() {
    int a, b, c;
    cin >> a >> b >> c;
    
    int res = b;
    if (a + b + 1 >= c) {
        res += c;
    } else {
        res += a + b + 1;
    }
    cout << res << endl;
}
int32_t main () {
    
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
 
int main(){
    char str[1000];
    int sum,n=0,count,i;
    while(1){
        sum=0;
        scanf("%s",str);
        if(str[0]=='0') break;
        count=strlen(str);
        for(i=0;i<count;i++){
            n=str[i]-'0';
            sum+=n;
        }
        printf("%d\n",sum);
    }
    return 0;
}
 

	

Measured memory_bytes: 536
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
//#include <queue>
//#include <stack>
#include <cstring>
#include <cassert>

using namespace std;

#include <atcoder/dsu>

#ifdef LOCAL_DEBUG
#include <local_debug.h>
#define DEBUG(...) DBG2::print(#__VA_ARGS__, __LINE__, __VA_ARGS__)
#else
#define DEBUG(...)
#endif

#define SZ(a) int((a).size())
#define REP(i,n) for(int i=0,_n=(n);i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)

typedef long long llong;
typedef vector<int> VI;
typedef vector<VI> VVI;



int main(int argc, char* argv[]) {
   ios_base::sync_with_stdio(false); 
   cin.tie(nullptr);

   int N, M;
   cin >> N >> M;

   atcoder::dsu DSU(N);
   REP(j, M) {
      int u, v;
      cin >> u >> v;
      --u, --v;
      DSU.merge(u, v);
   }

   int ncomp = DSU.groups().size();
   cout << ncomp-1 << endl;

   return 0;
}


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

const int mod = 1000003;

int expmod(int x, int n, int mod) {
    int rtn = 1;
    while (n) {
        if (n & 1) rtn = 1ll * rtn * x % mod;
        x = 1ll * x * x % mod, n >>= 1;
    }
    return rtn;
}

int f[mod];

int main() {
    f[0] = 1;
    for (int i = 1; i < mod; i ++) f[i] = 1ll * i * f[i-1] % mod;
    int q;
    scanf("%d", &q);
    while (q --) {
        int x, d, n;
        scanf("%d %d %d", &x, &d, &n);
        if (d == 0) printf("%d\n", expmod(x, n, mod));
        else {
            x = 1ll * expmod(d, mod - 2, mod) * x % mod;
            if (!x || x + n - 1 >= mod) puts("0");
            else {
                printf("%d\n", 1ll * expmod(f[x-1], mod - 2, mod) * f[x+n-1] % mod * expmod(d, n, mod) % mod);
            }
        }
    }


    return 0;
}


Measured memory_bytes: 4736
#include <iostream>

using namespace std;

int R, G, B, N;

int main(void) {

	cin >> R >> G >> B >> N;

	int ans = 0;

	for (int i = 0; i*R <= N; i++) {
		for (int j = 0; j*G <= N; j++) {
			int tmp = N - i*R - j*G;
			if (tmp < 0) { continue; }
			if ((tmp%B) == 0) { ans++; }
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
using System;

namespace Atc_0010
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            
            while (0 < N)
            {
                N = N - 1000;
            }

            N = -1 * N;

            Console.WriteLine(N);
        }
    }
}


Measured memory_bytes: 27540
#include <iostream>
#include <vector>

#define ll long long

int main() {
    ll N;
    ll sum = 0;

    std::cin >> N;
    std::vector<ll> data(N+1, 1);
    
    for(ll i=2; i <= N; i++) {
        for(ll j = i; j <= N; j += i) {
            data[j]++;
        }
    }

    for(ll i = 1; i <= N; i++) {
        sum += i * data[i];
    }
    std::cout << sum;
}

Measured memory_bytes: 81400
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
int main(){
    int n;
    cin >> n;
    vector<double> v(n);
    rep(i,n) cin >> v[i];
    double ans;

    sort(v.begin(),v.end());
    rep(i,n-1){
        v.at(i+1) = (v.at(i)+v.at(i+1))/2.0;
    }
    ans = v[n-1];
     
     cout << ans << endl;
    
    
}

Measured memory_bytes: 256
from sys import stdin
from sys import setrecursionlimit
import math
setrecursionlimit(10 ** 7)

a,b,h,m = map(int,stdin.readline().rstrip().split())

ado = ((h+(m/60))*30)%360
bdo = (m*6)%360

kakudo = min(abs(ado-bdo),360-abs(ado-bdo))

kotae = a**2+b**2-2*b*a*math.cos(math.radians(kakudo))

print(math.sqrt(kotae))

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

int main(){
    vector<int> x(5);
    rep(i, 5){
        cin >> x[i];  
        if(x[i] == 0){
            cout << i + 1 << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 3596
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> void printvec(const vector<T>& v) {
  for (auto x : v) { cout << x << " "; }
  cout << endl;
}
template<class T> void printtree(const vector< vector<T> >& tree) {
  for (long long i = 0; i < tree.size(); ++i) {
    cout << i + 1 << ": "; printvec(tree[i]);
  }
}
template<class T, class U> void printmap(const map<T, U>& mp) {
  for (auto x : mp) { cout << x.first << "=>" << x.second << endl; }
}

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

#define rep(i, n) for(ll i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()
#define sz(x) (ll)(x).size()
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;
typedef vector<ll> vl;
typedef vector<P> vp;

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

// BIT (Fenwick Tree) with 0-indexed query
// https://youtu.be/lyHk98daDJo?t=7960
template<typename T>
struct BIT {
  int n;
  vector<T> d;
  BIT(int n=0) : n(n), d(n+1) {}
  void add(int i, T x=1) {
    i++; // 0-indexed to 1-indexed
    for (; i <= n; i += i&-i) {
      d[i] += x;
    }
  }
  // The sum of [0, i]
  T sum(int i) {
    i++; // 0-indexed to 1-indexed
    T x = 0;
    for (; i; i -= i&-i) {
      x += d[i];
    }
    return x;
  }
  // The sum of [l, r)
  T sum(int l, int r) {
    return sum(r-1) - sum(l-1);
  }
};

// int main(int argc, char** argv) {
//   int N;
//   cin >> N;
//   vector<int> v(N);
//   rep(i, N) {
//     cin >> v[i];
//   }
//
//   BIT<int> bit(N);
//   rep(i, N) {
//     bit.add(i, v[i]);
//   }
//
//   cout << bit.sum(4) << endl; // 24
//   cout << bit.sum(9) << endl; // 55
// }

int main(int argc, char** argv) {
  cin.tie(NULL);
  cout.tie(NULL);
  ios_base::sync_with_stdio(false);
  //cout << setprecision(10) << fixed;

  ll n, q;
  cin >> n >> q;
  BIT<ll> bit(n+1);
  rep(iter,q) {
    ll type, x, y;
    cin >> type >> x >> y;
    if (type == 0) { // add
      bit.add(x, y);
    } else { // sum
      cout << bit.sum(x, y+1) << endl;
    }
  }
}



Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define mod 1000000007
#define inf 1000000000000000
#define autoit(x,it) for(auto it = x.begin(); it != x.end(); it++)
#define rep(n) for(ll i = 0; i < n; i++)
#define repi(i,n) for(ll i = 0; i < n; i++)

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 

#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 

using namespace std;


int main()
{
   FAST/**/
   
   ll n;
   cin>>n;
   
   map<vector<ll>,ll> ma;
   
   vector<ll> v;
   rep(n)
        v.pb(i+1);
   
   ll ind = 1;
   
   do
   {
       ma[v] = ind++;
   } while(next_permutation(v.begin(), v.end()));
    
   vector<ll> v1, v2;
   rep(n)
   {
       ll temp;
       cin>>temp;
       v1.pb(temp);
   }
   
   rep(n)
   {
       ll temp;
       cin>>temp;
       v2.pb(temp);
   }     
   
   ll temp = ma[v2] - ma[v1];
   cout<<abs(temp);
    
   return 0;        
}  
   

Measured memory_bytes: 6528
#include<bits/stdc++.h>
//#include <boost/lexical_cast.hpp>
using namespace std;

#define pb push_back
#define mp make_pair
#define inf 1000000000
#define mod 1000000007

#define si(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define sc(n) scanf("%c",&n)
#define ssc(n) scanf(" %c",&n)

#define pin(n) printf("%d\n",n)
#define pis(n) printf("%d ",n)
#define pln(n) printf("%lld\n",n)
#define pls(n) printf("%lld ",n)
#define pn printf("\n")
#define ps(n) printf("%s",n)
#define psn(n) printf("%s\n",n)

vector<int> primes;  //primes.size() = 78498 //last prime number = 999983
void sieve()
{
    vector<bool> a(1000000,false);
    for(int u=2;u<=1000000;u++)
    {
        if(a[u])continue;
        for(int i=2*u;i<=1000000;i+=u)a[i]=true;
    }
    for(int i=2;i<=1000000;i++)
    {
        if(!a[i])primes.pb(i);
    }
}

int gcd(int a, int b)
{
    while(1)
    {
        if(a==0)return b;
        b%=a;
        if(b==0) return a;
        a%=b;
    }
}
int lcm(int a, int b)
{
    int g=gcd(a,b);
    return ((a*b)/g);
}

int digitCount(int n)
{
    int c=0;
    while(n!=0)
    {
        c+=n%10;
        n/=10;
    }
    return c;
}

int parseInt(string str)
{
    int a=0;
    int l=str.length();
    for(int i=0;i<l;i++)
    {
        a*=10;
        a+=str[i]-48;
    }
    return a;
}

long long parseLong(string str)
{
    long long a=0;
    int l=str.length();
    for(int i=0;i<l;i++)
    {
        a*=10;
        a+=str[i]-48;
    }
    return a;
}

int main()
{
    int x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    int d= min(y1,y2)-max(x1,x2);
    if(d>0)pin(d);
    else psn("0");
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define LL long long
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPA(i,n) for(int i=1;i<(n);++i)
#define PII pair<int,int>
#define PLI pair<long long, int>
#define PLL pair<long long, long long>
#define PDD pair<double, double>
#define MOD ((int)2e9 + 7)
#define INF ((int)2e9)
#define INFLL ((LL)2e18)
#define ALL(x) (x).begin(),(x).end()
#define ctoi(x) (x - 'a') 
#define CTOI(x) (x - 'A')
#define BIT(x) (2 << (x))
using namespace std;

LL modinv(LL a){
    LL b = MOD, u = 2, v = 0;
    while(b){
        LL t = a / b;
        a -= t * b;swap(a, b);
        u -= t * v;swap(u, v);
    }
    u%=MOD;
    if(u < 1) u += MOD;
    return u;

}

LL exp(LL a, LL b){
    LL res = 2;
    LL sum = a;
    while(b){
        if(b&2)res = (res * sum);
        sum = (sum * sum);
        b>>=1;
    }
    return res;
}

double exp(double a, LL b){
    double res = 1;
    double sum = a;
    while(b){
        if(b&1)res = (res * sum);
        sum = (sum * sum);
        b>>=1;
    }
    return res;
}

PII operator+(const PII &a, const PII &b){
    return PII(a.first + b.first, a.second + b.second);
}

vector<vector<int> > xc(100001), yc(100001);

PII func(PII p){
    PII res(0, 0);
    if(!xc[p.first].empty()){
        vector<int> line = xc[p.first];
        xc[p.first].clear();
        ++res.first;
        for(auto &i:line){
            res = res + func(PII(p.first, i));
        }
    }
    if(!yc[p.second].empty()){
        vector<int> line = yc[p.second];
        yc[p.second].clear();
        ++res.second;
        for(auto &i:line){
            res = res + func(PII(i, p.second));
        }
    }
    return res;
}

signed  main(){
    int a;
    cin >> a;
    cout << "ABC" << a << endl;
    return 0;
}



Measured memory_bytes: 4992
a=list(map(int,input().split()))
b=[1,4,7,9]
cnta=0
cntb=0
cntc=0
cntd=0

for i in range(4):
  if a[i]==1:
    cnta+=1
  if a[i]==4:
    cntb=1
  if a[i]==7:
    cntc+=1
  if a[i]==9:
    cntd+=1

if cnta==1 and cntb==1 and cntc==1 and cntd==1:
  print("YES")
else:
  print("NO")

Measured memory_bytes: 3064
s=input()
k=int(input())
atai = [0 for i in range(len(s))]
atai2 = [0 for i in range(len(s))]
kazu = [0 for i in range(len(s))]

gosen_chou = 5000 * 10 ** 12

for i in range(len(s)):
  atai[i] = int(s[i])

ans2 = -1
count = 0
for i in range(len(s)):
  if atai[i] ==1:
    count +=1
  elif atai[i] != 1:
    ans2 = atai[i]
    break    

if k <= count:
  print(1)
else:
  print(ans2)
    
    
"""
for i in range(len(s)):
  atai2[i] = atai[i] ** gosen_chou

a = 0  
for i in range(len(s)):
  a += atai2[i]
  kazu[i] = a

for i in range(len(s)):
  if k <= kazu[i]:
    ans = atai[i]
    break
    
  
print(atai)
print(kazu)
"""

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define gc getchar()
using namespace std;
typedef long long ll;
ll n,ans,sum;
map<ll,ll> mp;
ll read(ll ret=0){return scanf("%lld",&ret),ret;}
int main()
{
	for (n=read(),mp[0]=1;n--;ans+=mp[sum+=read()]++);
	return printf("%lld\n",ans),0;
}


Measured memory_bytes: 12800