akhauriyash/Code-Regression huggingface dataset:
///mAAria...
#include<bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(v) v.begin(),v.end()
#define ld long double
#define ff first
#define ss second
#define pii pair<int,int>
#define pi 3.1415926535897932384626433832
#define mod 1000000007
#define inf 1000000000
#define pr1(a) cout << a << endl
#define pr2(a,b)cout << a <<  " " <<b<< endl
#define pr3(a,b,c) cout << a <<" " << b << " " << c << endl

const long double PI = acos(-1);

int powm(int a, int b) {
    int res=1;
    while(b) {
        if(b&1)
            res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
int gcd(int a, int b){
    if(b==0)return a;
    gcd(b,a%b);
}

char maze[25][25];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, 1, -1};
int r,c;
int vis[25][25];
int ii, jj;

pair<pair<int,int>, int> bfs(int x, int y){

    int dist[25][25];
    memset(dist, -1, sizeof(dist));

    dist[x][y] = 0;

    queue<pii> q;
    q.push({x,y});

    while(!q.empty()){

        auto p = q.front(); q.pop();
        x = p.first;
        y = p.second;

        for(int i = 0;i<4;i++){
            int tx = x+dx[i];
            int ty = y+dy[i];

            if(tx<=r && tx>=1 && ty<=c && ty>=1 && dist[tx][ty]==-1 && maze[tx][ty]=='.'){
                q.push({tx,ty});

                dist[tx][ty] = dist[x][y]+1;
            }
        }
    }

    int mx = 0;
    pii idx;

    for(int i = 1;i<=r;i++){
        for(int j = 1;j<=c;j++){
            if(maze[i][j]=='.'){
                if(dist[i][j]>mx){
                    mx = dist[i][j];
                    idx.first = i;
                    idx.second = j;
                }
            }
        }
    }

    return {idx, mx};

}

void find(){
    pair<pii,int> t1,t2,t3;

    
    for(int i =1;i<=r;i++){
        for(int j = 1;j<=c;j++){
            if(maze[i][j]=='.'){
                t3 = bfs(i,j);
                if(t1.second<t3.second){
                    t1 = t3;
                }
            }
        }
    }
    t2 = bfs(t1.first.first, t1.first.second);

    cout << t2.second << endl;
}

void solve(){
   //int r,c;
   cin >> r >> c;

   bool flag = true;
   //int ii,jj;

   for(int i = 1;i<=r;i++){
    for(int j = 1;j<=c;j++){
        cin >> maze[i][j];
        
    }
   }

   find();



} 

signed main() 
{   
    IOS;
    int t = 1;
    //cin >> t;

    for(int i = 1;i<=t;i++){
        solve();
    }
    return 0;
} 

 


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int t,n,a[N],b[N],num[N],tot,c;
map<int,int>cnt,tmp;
void solve()
{
	if(tot>3)
	{
		puts("No");
		return;
	}
	else if(tot==1)
	{
		if(num[0]==0)
		{
			puts("Yes");
			return;
		}
		else
		{
			puts("No");
			return;
		}
	}
	else
	{
		bool ok=1;
		do
		{
			ok=1;
			tmp=cnt;
			b[1]=num[0];tmp[num[0]]--;
			b[2]=num[1];tmp[num[1]]--;
			for(int i=3;i<=n&&ok;++i)
			{
				bool upd=0;
				for(int j=0;j<3&&!upd;++j)
				{
					if(tmp[num[j]]>0&&(num[j]^b[i-2])==b[i-1])
					{
						b[i]=num[j];
						tmp[num[j]]--;
						upd=1;
					}
				}
				if(!upd)ok=0;
			}
			if(ok&&(b[n]^b[n-1])!=b[1])ok=0;
			if(ok)break;
		}while(next_permutation(num,num+tot));
		if(ok)puts("Yes");
		else puts("No");
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		if(!cnt.count(a[i]))num[tot++]=a[i];
		cnt[a[i]]++;
	}
	solve();
	return 0;
}

Measured memory_bytes: 4480
N = int(input())

w = list(input() for i in range(N))
a = {}
a[w[0]] = 1
flag = 0
for i in range(1,N):
    if w[i-1][-1] != w[i][0]:
        flag = 1
        break
    if w[i] in a:
        flag = 1
        break
    a[w[i]] = 1
if flag == 0:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 38256
#include<bits/stdc++.h>
using namespace std;
int p,a[3005];
int iC[3005][3005];
int inv[3005],ans;
int xs[3005][3005];
int g[3005];

int main(){
    scanf("%d",&p);
    for(int i=0;i<p;i++) scanf("%d",&a[i]);
    iC[0][0]=1;
    for(int i=1;i<=3000;i++){
        iC[i][0]=iC[i][i]=1;
        for(int j=1;j<i;j++) iC[i][j]=iC[i-1][j-1]+iC[i-1][j],iC[i][j]%=p;
    }
    for(int i=1;i<=3000;i++){
        for(int j=0;j<=i;j++) if((j&1)^(i&1)) iC[i][j]=p-iC[i][j];
    }
    inv[1]=1;
    for(int i=2;i<p;i++) inv[i]=(p-p/i)*inv[p%i]%p;
    inv[0]=1;
    for(int i=1;i<p;i++) inv[i]=inv[i]*inv[i-1]%p;
    for(int i=1;i<p;i++) xs[1][i]=1;
    for(int i=2;i<p;i++){
        for(int j=i;j<p;j++) xs[i][j]=(xs[i-1][j-1]+xs[i][j-1])*i%p;
    }
    for(int i=p-1;i>=1;i--){
        ans=0;
        for(int j=0;j<=i;j++) ans=(ans+iC[i][j]*a[j])%p;
        for(int j=i+1;j<p;j++){
            ans=(ans-xs[i][j]*g[j]%p+p)%p;
        }
        g[i]=ans*inv[i]%p;
    }
    g[0]=a[0];
    for(int i=0;i<p;i++) printf("%d ",g[i]);

    return 0;
}

Measured memory_bytes: 70912
#include <bits/stdc++.h>
#define INF 1e9
#define INFLL 1ull<<60u
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
typedef long long ll;

void solve() {
    int x;
    cin >> x;
    bool y = x;
    cout << !y << endl;
}

int main() {
    solve();
    return 0;
}

Measured memory_bytes: 3644
H, W = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))

color = 1
color_count = A[color-1]

grid = [[None] * W for _ in range(H)]
for i in range(H):
    if i % 2 == 0:
        rng = range(W)
    else:
        rng = range(W-1,-1,-1)
    for j in rng:
        if color_count == 0:
            color += 1
            color_count = A[color-1]
        color_count -= 1
        grid[i][j] = color

for i in range(H):
    print(*grid[i], sep=' ')



Measured memory_bytes: 42480
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        long ans = 1;

        for (int i = 0; i < N; i++) {
            Long tmp = sc.nextLong();
            double tmpAns = ans;
            if (tmp == 0) {
                ans = 0;
                break;
            }
            if (tmp > (long) Math.pow(10, 18) || tmpAns * tmp > Math.pow(10, 18)) {
                ans = -1;
            }
            if (ans != -1) {
                ans *= tmp;
            }
        }
        sc.close();

        if (ans > (long) Math.pow(10, 18)) {
            ans = -1;
        }
        System.out.println(ans);
    }
}


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

int main() {
  int N;

  cin >> N;

  vector<string> s(N);

  for (int i = 0; i < N; i++) {
    cin >> s.at(i);
  }

  int M;

  cin >> M;

  vector<string> t(M);

  for (int i = 0; i < M; i++) {
    cin >> t.at(i);
  }

  vector<int> m(N);

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (s.at(i) == s.at(j)) {
        m.at(i)++;
      }
    }

    for (int j = 0; j < M; j++) {
      if (s.at(i) == t.at(j)) {
        m.at(i)--;
      }
    }
  }

  int max = 0;
  for (int i = 0; i < N; i++) {
    if (max < m.at(i)) {
      max = m.at(i);
    }
  }

  cout << max << endl;

}


Measured memory_bytes: 3632
n = int(input())

days = []
for _ in range(n):
  a = list(map(int,input().split()))
  days.append(a)
  
dp = [0]*3

for i in range(3):
  dp[i] = days[0][i]

for cur_day in range(1,n):
  m = [0]*3
  for i in range(3):
    for j in range(3):
      if i!=j:
        m[i] = max(m[i],dp[j]+days[cur_day][i])
  dp = m

print(max(dp))
        
        
        
        
        

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
using P = pair<ll, ll>;
using V = vector<ll>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep1(i, n) for(ll i=1;i<=(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rep3(i, m, n) for(ll i=m;i<=(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define MOD 1000000007
#define INF 1000000000
#define LLINF 1e18

void solve_abc_d() {
	ll n, m;
	//ll a, b;
	ll x, y, z;
	//ll h, w;
	ll k;
	string s, rs;
	ll l_ans = 0;

	cin >> n;
	cin >> s;

	rs = s;
	reverse(ALL(rs));

	V r, w;
	rep(i, n) {
		if (s[i] == 'W') {
			w.push_back(i);
		}
	}
	rep(i, n) {
		if (rs[i] == 'R') {
			r.push_back(i);
		}
	}

	if ((w.size() == n) || (r.size() == n)) {
		cout << 0 << "\n";
		return;
	}

	auto itr_w = w.begin();
	auto itr_r = r.begin();
	rep(i, n) {
		if (s[i] == 'W') {
			if (*itr_w > n - 1 - *itr_r) {
				break;
			}
			itr_w++;
			itr_r++;
			l_ans++;
		}
	}
	
	cout << l_ans << "\n";

	return;
}

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

	solve_abc_d();

	return 0;
}


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

int k, t, n;
int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0);
	std::cin >> k, t = k; while (t & 3) t += t & -t;
	if (k == 1) return std::cout << 1 << '\n' << 1 << '\n', 0;
	std::cout << (n = t >> 1) << '\n';
	for (int i = 0; i < n; ++i, std::cout << '\n')
		for (int j = 0; j < n; ++j) {
			int t = (i + j) % n + (i & 1 ? n : 0) + 1;
			if (t > k) t -= n;
			std::cout << t << ' ';
		}
	return 0;
}

Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b;
  cin >> a >> b;
  
  if(a%3 == 0 ||b%3 == 0 || (a+b)%3 == 0)
    cout << "Possible" << endl;
  else
    cout << "Impossible" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <cassert>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <stack>
#include <iomanip>
#include <utility>
#include <functional> 

using namespace std;

#define mp make_pair
#define pb push_back
#define pf push_front
#define X first
#define Y second
#define rg register
#define il inline
#define lch(x) ((x)<<1)
#define rch(x) ((x)<<1^1)
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define rep0(i,n) for(register int (i)=0;(i)<(n);++(i))
#define rep(i,st,ed) for(register int (i)=(st);(i)<=(ed);++(i))
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef double dbl;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<typename T> inline T qmin(const T a,const T b) {return a<b?a:b;}
template<typename T> inline T qmax(const T a,const T b) {return a>b?a:b;}
template<typename T> inline void getmin(T &a,const T b) {if(a>b) a=b;}
template<typename T> inline void getmax(T &a,const T b) {if(a<b) a=b;}

inline void fileio(string s){
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}

const int inf=1e9+7;
const ll linf=1e17+7;

const int N=1e5+7,Node=N<<2;
const int mod=1000000007;

int a[N],val[N],n;

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",a+i);
	a[0]=-1;
	for(int i=1,cur=n,j;i<=n;i=j,--cur){
		int begin=2*(i-1-(n-cur));
	//	cerr<<"begin="<<begin<<endl;
		for(j=i;j<=n&&(j==i||a[j-1]-begin+1>=2*(j-i));++j){
			val[j]=cur;
		}
	}
	ll ans=1;
//	for(int i=1;i<=n;++i) eprintf("%d ",val[i]);eprintf("\n");
	for(int i=1;i<=n;++i) ans=ans*(ll)(val[i]-n+i)%mod;
	printf("%lld\n",ans);
	return 0;
} 

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

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    String s = in.readLine();
    int ans = 0;
    
    for(int i = 0; i<s.length()+1; i++) {
      for(int j = i + 1; j < s.length()+1; j++) {
        String sub = s.substring(i,j);
        int tmpLen = 0;
        for(int k = 0; k < sub.length(); k++) {
          if(sub.charAt(k) == 'A'||sub.charAt(k) == 'C'||
             sub.charAt(k) == 'G'||sub.charAt(k) == 'T') {
            tmpLen++;
          } else {
            break;
          }
        }
        ans = Math.max(ans, tmpLen);
      }
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 23124
#include<bits/stdc++.h>
#include<atcoder/dsu>

int main(){
  int n, q, p, a, b;
  scanf("%d %d", &n, &q);
  atcoder::dsu uf(n);
  for(int i=0; i<q; i++){
    scanf("%d %d %d", &p, &a, &b);
    if(p==0) uf.merge(a, b);
    else{
      if(uf.same(a, b)){
        puts("1");
      }else{
        puts("0");
      }
    }
  }
  return 0;
}

Measured memory_bytes: 3896
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define MAXN 50
struct Matrix{ ll v[MAXN][MAXN]; }a;
ll n, k, mod=1e9+7, cnt;
Matrix matrixmul(Matrix a, Matrix b){
    Matrix c;
    memset(c.v, 0, sizeof(c.v));
    for(int k=0; k<n; k++)
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                c.v[i][j] = (c.v[i][j] + a.v[i][k]*b.v[k][j])%mod;
    return c;
}
Matrix matrixpow(Matrix m, ll k){
    Matrix c;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            c.v[i][j] = (i==j);
    for(; k; k>>=1){
        if(k&1) c=matrixmul(c, m);
        m = matrixmul(m, m);
    }
    return c;
}

int main(){
    cin >> n >> k;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cin >> a.v[i][j];
    a = matrixpow(a, k);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cnt = (cnt + a.v[i][j]) % mod;
    cout << cnt << endl;
}

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;
using P = pair<int, int>;

const int INF = 1001001001;

int a[12][12];

int main()
{
    int n, m, x;
    cin >> n >> m >> x;
    vector<int> c(n);
    rep(i, n)
    {
        cin >> c[i];
        rep(j, m) cin >> a[i][j];
    }

    int ans = INF;
    int MX = pow(2, n);
    for (int s = 1; s < MX; ++s)
    {
        int cost = 0;
        vector<int> skil(m, 0);
        rep(i, n)
        {
            if (s >> i & 1)
            {
                cost += c[i];
                rep(j, m) skil[j] += a[i][j];
            }
        }
        bool ok = true;
        rep(k, m) if (skil[k] < x) ok = false;
        if (ok)
        {
            ans = min(cost, ans);
        }
    }
    if (ans == INF)
        cout << -1 << endl;
    else
        cout << ans << endl;
    return 0;
}


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

using namespace std;

int64_t solve(int64_t r) { return r * r * 3; }

int main() {
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
  int64_t r;
  std::cin >> r;
  auto const res = solve(r);
  std::cout << res << std::endl;
  return 0;
}


Measured memory_bytes: 256
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        h: usize,
        w: usize,
        a: [chars; h],
    }
    for _ in 0..w+2 { print!("#"); }
    println!();
    for i in 0..h {
        print!("#");
        for j in 0..w {
            print!("{}", a[i][j]);
        }
        print!("#");
        println!();
    }
    for _ in 0..w+2 { print!("#"); }
    println!();
}

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

const ll mod=1e9+7;
ll h[1000000]{0};
ll dp[1000000]{0};
ll n;
ll solve(ll i){
    if(i==n) return 0;
    if(i>n) return INT_MAX;
    if(dp[i]!=-1) return dp[i];
    ll ans=INT_MAX;
    ans=solve(i+1)+abs(h[i+1]-h[i]);
    if(i+2<=n){
        ans=min(ans,solve(i+2)+abs(h[i+2]-h[i]));
    }
    return dp[i]=ans;
}

int main() {

    memset(dp,-1,sizeof(dp));
    cin>>n;
    for(ll i=0;i<n;i++){
        cin>>h[i+1];
    }
    cout<<solve(1)<<endl;

}


Measured memory_bytes: 13568
import java.io.*;
import java.math.*;
import java.util.*;
public class Main { //FILTER PRIMES
 
	public static void main(String[] args) { 
		FastScanner input = new FastScanner();
		PrintWriter w = new PrintWriter(System.out);
		long ans = 0;
		int N = input.nextInt();
		int M = input.nextInt();
		long K = input.nextLong();
		long[] PN = new long[N+1];
		long[] PM = new long[M+1]; //Prefix sums
		for (int i = 0; i < N; i++) {
			PN[i+1]=PN[i];
			PN[i+1]+=input.nextLong();
		}
		for (int i = 0; i < M; i++) {
			PM[i+1]=PM[i];
			PM[i+1]+=input.nextLong();
		}
		/*for (int i = 0; i <= N; i++) {
			System.out.print(PN[i]+" ");
		}
		System.out.print("\n");
		for (int i = 0; i <= M; i++) {
			System.out.print(PM[i]+" ");
		}*/
		int lo = 1;
		int hi = N+M;
		while (lo<=hi) {
			int mid = (lo+hi)/2;
			if (Check(mid,PN,PM,K)) {
				lo=mid+1;
				ans=Math.max(ans, mid);
			}else hi=mid-1;
		}
		w.println(ans);
		w.flush();
	}
	public static boolean Check(int test, long[] PN, long[] PM,long K) {
		for (int i = 0; i <= Math.min(PN.length-1, test); i++) {
			if (test-i<=PM.length-1) {
				if (PN[i]+PM[test-i]<=K) return true;
			}
		}
		return false;
	}
	public static long GCD(long a, long b) {
		if (a==0||b==0) return Math.max(a,b);
		return GCD(Math.min(a, b),Math.max(a, b)%Math.min(a, b));
	}
	public static long FastExp(long base, long exp, long mod) {
		long ans=1;
		while (exp>0) {
			if (exp%2==1) ans*=base;
			exp/=2;
			base*=base;
			base%=mod;
			ans%=mod;
		}
		return ans;
	}
	public static long ModInv(long num,long mod) {return FastExp(num,mod-2,mod);}
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
}


Measured memory_bytes: 68116
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define bFOR(i,n1,n2) for(int i=n1;i>=n2;i--)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long int ll;
typedef pair<int,int> Pi;
const int INF=(ll)(1LL<<31)-1;
const double INFd=100000000000.0;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
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 dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int d[501000]={};

int main(){
	for(int i=1;i<=1000;i++){
		int sum=0;
		for(int j=i;j<=1000;j++){
			
				sum+=j;
				if(sum>1000)break;
				d[sum]++;
		}
	}
	while(1){
		int n;
		cin>>n;
		if(n==0)break;
		cout<<d[n]-1<<endl;
	}
	return 0;
}
		


Measured memory_bytes: 3092
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    String str;
    int num;
    boolean[] S = new boolean[13];
    boolean[] H = new boolean[13];
    boolean[] C = new boolean[13];
    boolean[] D = new boolean[13];

    for (int i = 0; i < 13; i++)
      S[i] = H[i] = C[i] = D[i] = false;

    for (int i = 0; i < n; i++) {
      str = sc.next();
      num = sc.nextInt();
      if (str.equals("S"))
        S[num - 1] = true;
      else if (str.equals("H"))
        H[num - 1] = true;
      else if (str.equals("C"))
        C[num - 1] = true;
      else if (str.equals("D"))
        D[num - 1] = true;
    }

    for (int i = 0; i < 13; i++)
      if (!S[i])
        System.out.println("S" + " " + (i + 1));
    for (int i = 0; i < 13; i++)
      if (!H[i])
        System.out.println("H" + " " + (i + 1));
    for (int i = 0; i < 13; i++)
      if (!C[i])
        System.out.println("C" + " " + (i + 1));
    for (int i = 0; i < 13; i++)
      if (!D[i])
        System.out.println("D" + " " + (i + 1));
  }
}

Measured memory_bytes: 26296
# -*- coding: utf-8 -*-


def conv_input(arr):
    ret = []
    for e in arr:
        ret.append((e[0], int(e[1])))
    return ret


def conv_output(conv_arr):
    ret = []
    for e in conv_arr:
        ret.append(e[0] + str(e[1]))
    return ret


def is_stable(arr1, arr2):
    ret = 'Stable'
    for a1, a2 in zip(arr1, arr2):
        if a1 == a2:
            continue
        else:
            ret = 'Not stable'
            break
    return ret


def bubble_sort(n, arr):
    flag = True
    while flag:
        flag = False
        for i in reversed(range(n)):
            if i is 0:
                break
            if arr[i][1] < arr[i - 1][1]:
                tmp = arr[i]
                arr[i] = arr[i - 1]
                arr[i - 1] = tmp
                flag = True
    return arr


def selection_sort(n, arr):
    for i in range(n):
        minj = i
        for j in range(i, n):
            if arr[j][1] < arr[minj][1]:
                minj = j
        if i != minj:
            tmp = arr[minj]
            arr[minj] = arr[i]
            arr[i] = tmp
    return arr

if __name__ == '__main__':
    n = int(input())
    arr1 = arr2 = [str(s) for s in input().split()]
    arr1 = conv_output(bubble_sort(n, conv_input(arr1)))
    print(' '.join(map(str, arr1)))
    print('Stable')
    arr2 = conv_output(selection_sort(n, conv_input(arr2)))
    print(' '.join(map(str, arr2)))
    print(is_stable(arr1, arr2))

Measured memory_bytes: 7768
h, w = map(int, input().split())
s = [input() for _ in range(h)] 
 
d = {(i, j):c for i, row in enumerate(s) for j, c in enumerate(row)}
 
def next_to_black(i, j):
    directions = ((-1, 0), (1, 0), (0, -1), (0, 1))
    surroundings = ((i + a, j + b) for a, b in directions)
    colors = (d.get(cell, '.') for cell in surroundings)
    return any(color == '#' for color in colors)
 
black_coords = (coord for coord, c in d.items() if c == '#')
paintable = all(next_to_black(*coord) for coord in black_coords)
print('Yes' if paintable else 'No')

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

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

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

ll N;

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

  cin>>N;
  cout<<N*(N-1)/2<<endl;

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main()
{
	int c[4] = { 0, };
	int t; scanf ("%d", &t); while (t--){
		char s[100];
		scanf ("%s", s);
		if (s[0] == 'A') c[0]++;
		if (s[0] == 'W') c[1]++;
		if (s[0] == 'T') c[2]++;
		if (s[0] == 'R') c[3]++;
	}
	printf ("AC x %d\n", c[0]);
	printf ("WA x %d\n", c[1]);
	printf ("TLE x %d\n", c[2]);
	printf ("RE x %d\n", c[3]);
	return 0;
}

Measured memory_bytes: 3236
#include<iostream>
#include<algorithm>
#include<math.h>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<functional>
#include<map>
#include<set>
#include <string>
#include <numeric>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
map<int, int> mp;
map<int, int>mm;
#define ll long long
#define ld long double
#define PI 3.14159265358979l

int gcd(int a, int b) {
	if (a < b) {
		int tmp = a;
		a = b;
		b = tmp;
	}
	int r = a % b;
	while (r != 0) {
		a = b;
		b = r;
		r = a % b;
	}
	return b;
}


int main() {
	ll n, a[26] = {0};
	string s;
	cin >> n >> s;
	rep(i, n) {
		a[s[i] - 'a']++;
	}
	ll ans = 1;
	rep(i, 26) {
		ans *= (a[i] + 1);
		ans %= 1000000007;
	}
	cout << ans - 1 << endl;
	return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define For(i,a,b) for(i=a;i<b;i++)
#define rep(i,N) For(i,0,N)
#define rep1(i,N) For(i,1,N)
#define all(v) (v).begin(),(v).end()
#define vsort(v) sort(all(v))
ll labs(ll a){return (a>0)?a:(0-a);}

int main(){
  ll i,j,X,N,ans=0;
  cin>>N>>X;
  vector<ll> v;
  for(i=1;i*i<=X;i++){
    if(X%i==0){v.push_back(i);v.push_back(X/i);}
  }
  vsort(v);
  ans=*lower_bound(all(v),N);
  ans=X/ans;
  cout<<ans<<endl;
  return 0;
}

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

int main(void){
	int n, q, i, j, t;
	int *S;
	int cnt = 0;

	scanf("%d", &n);
	S = (int*)malloc(sizeof(int)*n);
	for(i = 0; i < n; i++){
		scanf("%d", S+i);
	}
	
	scanf("%d", &q);

	for(i = 0; i < q; i++){
		scanf("%d", &t);
		for(j = 0; j < n; j++){
			if(S[j] == t){
				cnt++;
				break;
			}
		}
	}

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

	free(S);

	return 0;
}

Measured memory_bytes: 636
N, K = map(int, input().split())
A = list(map(int, input().split()))
toujou = [0] * N
toujou[0] = 1
kosuu = 1
tadoru = [1]
pin = 1
tmp = 1
while pin == 1:
    tmp = A[tmp-1]
    toujou[tmp-1] += 1
    if toujou[tmp - 1] == 2:
            break
    else:
        tadoru.append(tmp)
        kosuu += 1

loop_start = tadoru.index(tmp)
loop = kosuu - loop_start
if K < kosuu:
    print(tadoru[K])
else:
    K = K - loop_start
    a = K % loop
    print(tadoru[loop_start + a])

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

using i64=int64_t;

#define rep(i,x,y) for(i64 i=i64(x),i##_max_for_repmacro=i64(y); i<i##_max_for_repmacro; ++i)
#define debug(x) #x << "=" << (x)
 
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif
 
const int inf=1.01e9;
const i64 inf64=4.01e18;
const double eps=1e-9;
 
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
        os << v << ",";
    }
    os << "]";
    return os;
}

void solve(){
    int N;
    cin >> N;
    map<int,int> count;
    rep(i,0,N){
        int ai;
        cin >> ai;
        ++count[ai];
    }

    int ans=0;
    for(auto p:count){
        if(p.first>p.second) ans+=p.second;
        else ans+=p.second-p.first;
    }
    
    cout << ans << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}


Measured memory_bytes: 4736
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
//do {
//    print(v);
//  } while (std::next_permutation(v.begin(), v.end()));

int main(){
cin.tie(0);
ios::sync_with_stdio(false);
	int N;
	cin>>N;
	VI dpa(N);
	VI dpb(N);
	VI dpc(N);
	REP(i,N){
		int a,b,c;
		cin>>a>>b>>c;
		if(i==0){
			dpa[i]=a;
			dpb[i]=b;
			dpc[i]=c;
		}
		else{
			dpa[i]=max(a+dpc[i-1],a+dpb[i-1]);
			dpb[i]=max(b+dpc[i-1],b+dpa[i-1]);
			dpc[i]=max(c+dpa[i-1],c+dpb[i-1]);
		}
	}
	cout<<max(dpa[N-1],max(dpb[N-1],dpc[N-1]))<<endl;
	
	return 0;
}




















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

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

vector<int> g[100];

int main() {
    int n, m;
    cin >> n >> m;
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i = 0; i < n; ++i) {
        cout << g[i].size() << endl;
    }
    return 0;
}


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

from collections import deque
import heapq
import math
import bisect


def main():
    N = int(input())
    V = list(map(int, input().split()))
    C = list(map(int, input().split()))

    ans = 0
    for i in range(N):
        if V[i] > C[i]:
            ans += V[i] - C[i]

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 38384
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<iomanip>
#include<set>
#include<numeric>
#include<sstream>
#include<random>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
const int inf = 1e9 + 7;
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};

int main() {
    int n; cin >> n;
    int hh = 0;
    int c = 0;
    rep(i, n) {
        int h; cin >> h;
        if (h >= hh) {
            hh = h;
            c++;
        }
    }
    cout << c << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	
	int a, b; cin >> a >> b;
	cout << (a < 10 && b < 10 ? a * b : -1) << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long 
#define scn(n) scanf("%d",&n)
#define lscn(n) scanf("%lld",&n)
#define lpri(n) printf("%lld",n)
#define pri(n) printf("%d",n)
#define pln() printf("\n")
#define priln(n) printf("%d\n",n)
#define lpriln(n) printf("%lld\n",n)
#define rep(i,init,n) for(int i=init;i<n;i++)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define gcd __gcd
#define inf INT_MAX
#define ninf INT_MIN
using namespace std;
const ll mod=1e9+7;
const int N=1e5+4;
int main()
{
    ll n,x;
    lscn(n);lscn(x);
    ll l[n];
    rep(i,0,n)
    lscn(l[i]);
    ll ans[n+4];
    ans[0]=0;
    rep(i,1,n+1)
    ans[i]=ans[i-1]+l[i-1];
    int sum=0;
    rep(i,0,n+1)
    {
        if(ans[i]<=x)
        sum++;
        else
        break;
    }
    pri(sum);
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
  int s,l[31]={0};
  for(int i=0;i<28;++i){
    cin>>s;++l[s];
  }
  for(int i=1;i<31;++i) if(!l[i]) cout<<i<<endl;
  return 0;
}

Measured memory_bytes: 1160
#include "bits/stdc++.h"
using namespace std;
/////////////////// TYPES & MACROS ///////////////////////////////
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define vv vector
#define exist(s,e) (s.find(e)!=s.end())
#define sz(x) ((int)(x).size())
// #define int ll
typedef long long ll; typedef long double ld; typedef double dd;typedef vector<int> vi; typedef pair<int, int> pii;typedef pair<ll,ll> pll;
ll INFLL=(ll)4e18, MOD=1e9+7; const int INF=0x3f6f6f6f;
//////////////////// DEBUG /////////////////////////////////////////
#define D(x) cerr<<#x<<" is:\t"<<x<<'\n';
#define DD(x,y) cerr<<'('<<#x<<','<<#y<<") are:\t"<<x<<' '<<y<<'\n';
#define DDD(x,y,z) cerr<<'('<<#x<<','<<#y<<','<<#z<<") are:\t"<<x<<' '<<y<<' '<<z<<'\n';
/////////////////// VARIABLES & FUNCTIONS//////////////////////////
vv<vv<int>> adj; vi vis, color, level; int dx8[]={0,1,1,1,0,-1,-1,-1}, dy8[]={1,1,0,-1,-1,-1,0,1},dx4[]={0,1,0,-1}, dy4[]={1,0,-1,0};
inline ll mexp(ll x,ll n,ll m=MOD){ll res=1;x%=m;while(n){if(n&1)res=(res*x)%m;n>>=1;x=(x*x)%m;}return res;}
inline bool ispow2(ll x){ return x && (!(x&(x-1)));}
inline ll gcd(ll a, ll b){while (a>0 && b>0){if(a>b)a%=b;else b%=a;}return a+b;}

//////////////////// MAIN STARTS //////////////////////////////////
int32_t main(void){
ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
cout<<fixed;cerr<<fixed; cout<<setprecision(10); cerr<<setprecision(3);
// mt19937 genr(chrono::high_resolution_clock::now().time_since_epoch().count());


ll n,p; cin>>n>>p;
ll ans=1;
for(ll i=2;i*i<=p;++i){
    int ct=0;
    while(p%i==0) ct++, p/=i;
    ct/=n;
    for(int j=0;j<ct;++j) ans*=i;
    DD(i,ct);
}
if(n==1) ans*=p;
cout<< ans <<'\n'; 

return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string.h>
#include<cmath>
using namespace std;
long long factor[100][2];
int fatCnt;
const int MAXN = 1e6+5;
bool is[MAXN];//is[i] 1 - i is prime 0 - i is not a prime
int prime[MAXN], cnt = 0;
void getprime()
{
	memset(is, 1, sizeof(is));
	is[0] = is[1] = 0;
	for(int i = 2; i < MAXN; i++)
	{
		if(is[i])
		{
			prime[cnt++] = i;
		}
		for(int j = 0; j < cnt; j++)
		{
			if(i * prime[j] > MAXN) break;
			is[i * prime[j]] = 0;
			if(i % prime[j] == 0) break;
		}
	}
}
int getFactors(long long x)
{
	fatCnt = 0;
	long long tmp = x;
	for (int i = 0; prime[i] <= tmp / prime[i]; i++)
	{
		factor[fatCnt][1] = 0;
		if (tmp % prime[i] == 0)
		{
			factor[fatCnt][0] = prime[i];
			while (tmp % prime[i] == 0)
			{
				factor[fatCnt][1]++;
				tmp /= prime[i];
			}
			fatCnt++;
		}
	}
	if (tmp != 1)
	{
		factor[fatCnt][0] = tmp;
		factor[fatCnt++][1] = 1;
	}
	return fatCnt;
}
int main()
{
	long long n,ans=0;
	cin>>n;
	getprime();
	getFactors(n);
	for(int i=0;i<fatCnt;i++)
	{
		int x=sqrt(factor[i][1]*2);
		if(x*(x+1)>factor[i][1]*2)
			x--;
		ans+=x;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 4928
import java.util.Scanner;

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

    public static void main(String[] args) {
        String N = sc.next();
        char n[] = N.toCharArray();
        if (n.length == 1){
            if (n[0]=='0'||n[0]=='1'||n[0]=='6'||n[0]=='8'){
                System.out.println("pon");
            } else if (n[0]=='2'||n[0]=='4'||n[0]=='5'||n[0]=='7'||n[0]=='9'){
                System.out.println("hon");
            } else if (n[0]=='3'){
                System.out.println("bon");
            }
        } else if (n.length == 2){
            if (n[1]=='0'||n[1]=='1'||n[1]=='6'||n[1]=='8'){
                System.out.println("pon");
            } else if (n[1]=='2'||n[1]=='4'||n[1]=='5'||n[1]=='7'||n[1]=='9'){
                System.out.println("hon");
            } else if (n[1]=='3'){
                System.out.println("bon");
            }
        } else if (n.length == 3){
            if (n[2]=='0'||n[2]=='1'||n[2]=='6'||n[2]=='8'){
                System.out.println("pon");
            } else if (n[2]=='2'||n[2]=='4'||n[2]=='5'||n[2]=='7'||n[2]=='9'){
                System.out.println("hon");
            } else if (n[2]=='3'){
                System.out.println("bon");
            }
        }
    }
}


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

using namespace std;
typedef long long ll;
typedef pair <ll, ll> l_l;
typedef pair<int, int> i_i;

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 EPS (1e-7)
# define INF (1e9)
# define PI (acos(-1))
//const ll mod = 1000000007;

int N;
int A;
int ans[100010];

int main() {
    cin >> N;
    for (int i = 1; i <= N; ++i) {
        cin >> A;
        ans[A-1] = i;
    }
    for (int i = 0; i < N; ++i) {
        cout << ans[i];
        if (i != N-1) {
            cout << " ";
        } else {
            cout << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 1152
import math
A, B = map(int, input().split())
arange = set(range(math.ceil(A*100/8), math.ceil((A+1)*100/8)))
brange = set(range(math.ceil(B*100/10), math.ceil((B+1)*100/10)))
ans_range = arange & brange
if len(ans_range) == 0:
    print(-1)
else:
    print(min(ans_range))


Measured memory_bytes: 62188
import java.util.*;

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

		int n = scan.nextInt();

		Map<Long,Long> map = new HashMap<>();

		long[] arr = new long[n+1];
		arr[0] = 0;
		for(int i = 0; i < n; i++) {
			arr[i+1] = (long)scan.nextInt()+arr[i];
			if(!map.containsKey(arr[i+1])) {
				map.put(arr[i+1],1L);
			}else {
				map.put(arr[i+1],map.get(arr[i+1])+1L);
			}
		}

		long ans = 0;

		for(Map.Entry<Long,Long> entry : map.entrySet()) {
			long lng = entry.getValue();
			//System.out.println(entry);
			if(lng<=1) continue;
			/*
			long plus = 1;
			for(int i = 2; i <= lng; i++) {
				plus *= i;
			}
			plus/=2;
			*/
			long plus = lng*(lng-1)/2;
			ans += plus;
		}

		if(map.containsKey(0L)) ans += map.get(0L);

		System.out.println(ans);
	}
}


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

typedef long long ll;
#define repi(i, a, b) for(ll i = ll(a); i < ll(b); ++i)
#define rep(i, n) repi(i, 0, n)
#define rerepi(i, a, b) for(ll i = ll(a)-1; i >= b; --i)
#define rerep(i, n) rerepi(i, n, 0)

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; }
template <class T>ostream &operator<<(ostream &o,const vector<T>&v) {o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

const long long INF = 1LL << 60;

// 降順ソート
// std::sort(data.begin(),data.end(),std::greater<ll>());
// 昇順ソート
// std::sort(data.begin(),data.end());

// vector型の「data」に xが存在するかを、True or Falseで返す
// vector_finder(data, x)
bool vector_finder(std::vector<ll> vec, ll number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return true;
  }
  else { // 発見できなかったとき
    return false;
  }
}

// ここから開始だよ！
ll X, Y;

int main() {
	// 呪文エリア
	cin.tie(0);
	ios::sync_with_stdio(false);
	// 詠唱完了
	
  cin >> X >> Y;
  cout << X + (Y/2) << endl;
	
	return 0;
}


Measured memory_bytes: 256
//Jai Bhole Ki
#include <bits/stdc++.h>
using namespace std;
#define fast static int fastline = []() { std::ios::sync_with_stdio(false); cin.tie(NULL); return 0; }();
#define ll long long
#define LL unsigned ll
#define pb push_back
#define pi pair<ll,ll>
#define debug(x) cout<<x<<"\n";
#define debug cout<<"debugged\n";
#define minval -2e9
#define maxval 2e9
long double PI =3.14159265358979323846;
 
const ll M=1e12;
const ll inf=1e18;
const ll ms=10000000;
fast;
ll n,m,k;
bool prime[ms];
void seive()
{
    for(int i=2;i<ms;i++)
        prime[i]=1;
    for(int i=2;i*i<ms;i++)
    {
        if(prime[i])
        {
            for(int j=i*i;j<ms;j+=i)
                prime[j]=0;
        }
    }
}
void solve()
{
    seive();
    cin>>n;
    for(ll i=n;i<ms;i++)
    {
        if(prime[i])
            {cout<<i<<endl;return;}
    }
}
int main()
{
 // freopen("input.txt","r",stdin);
//  freopen("output.txt","w",stdout);
    //int t;cin>>t;while(t--)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 9984
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  print(sc.nextInt, sc.nextInt)

  def print(h: Int, w: Int): Unit = {
    (h, w) match {
      case (0, 0) => sc.close()
      case _ => {
        for (i <- 1 to h) {
          println("#" * w)
        }
        println()
        print(sc.nextInt(), sc.nextInt())
      }
    }
  }
}

Measured memory_bytes: 46484
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007 

ll a[200010];
int main() {
	ll n,sum=0;
	cin>>n;
	for(int i=0;i<n;i++){
		int z;
		cin>>z;
		a[i]=z;
		sum+=z;
	}
	for(int i=1;i<n;i++){
		a[i]=a[i]+a[i-1];
	}
	ll kuma=sum;
	ll ans=INF;
	for(int i=0;i<n-1;i++){
		kuma=sum-a[i];
		ans=min(ans,abs(kuma-a[i]));
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 1792
a,b,c,d = map(int, input().split())

# a以上b以下でnで割り切れる物の数
def f(n):
    return b//n - (a-1)//n
from fractions import gcd
lc = c*d//gcd(c,d)

print((b-a+1) - (f(c)+f(d)-f(lc)))

Measured memory_bytes: 5688
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#define rep(i,n) for(int i = 0; i < n;i++)
#define ll long long
#include <bits/stdc++.h>
using namespace std;
 int main(){
 
  ll a, b, r, x, tmp;
  cin>>a>>b;
  x = a * b;
 
  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }
  r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
  cout<<x/b;

}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <queue>
#include <stack>
#include <list>
#include <functional>
#include <numeric>
#include <iostream>

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (n); ++i)

int main() {

	int N, A, B;
	scanf("%d%d%d", &N, &A, &B);

	int C = 0;
	rep(i, N) {
		int t = (i + 1) % 10 + (i + 1) / 10 % 10 + (i + 1) / 100 % 10 + (i + 1) / 1000 % 10 + (i + 1) / 10000 % 10;
		if (t >= A && t <= B) C += i + 1;
	}

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

	return 0;
}


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

int main(){

    string s,t;

    cin >> s >> t;

    rep(i,t.size()){
        if(s==t){
            cout << "Yes" << endl;
            return 0;
        }
        t=t.back()+t;
        t.pop_back();
    }
    cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 256
N = int(input())
X = list(map(int,input().split()))
X_sort = sorted(X)
N_half = int(N/2)
median_large = X_sort[N_half]
median_small = X_sort[N_half-1]
if median_large == median_small:
    for _ in range(N):
        print(median_large)
else:
    for i in range(N):
        if X[i] <= median_small:
            print(median_large)
        elif X[i] >= median_large:
            print(median_small)



Measured memory_bytes: 25472
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FRE freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define all(v) (v).begin(),(v).end()
#define endl "\n"
#define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,a,b) for(int i=a;i>b;i--)
#define vi vector<int>
#define pii pair<int,int>
#define mii map<int,int>
#define SET(A,VAL) memset(A, VAL, sizeof(A))
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
const int MAX = 1e6 + 8;
const int MOD = 1e9 + 7;
const int sz = 1e5 + 5;
void f_io(){
    #ifndef ONLINE_JUDGE
    FRE
    #endif
}


int32_t main(){
    // f_io();
    IOS;
    int tc = 1;
    //cin>>tc;
    while(tc--){
        int n; cin >> n;
        string s; cin >> s;
        int w = 0, r = 0;
        for(auto k : s) {
            if (k == 'W') w++;
            else r++;
        }
        int sc = 0;
        for(int i = n - 1; i >= n - w; --i) {
            if(s[i] == 'R') sc++;
        }
        // cout << sc << " " << w << " " << r << endl; 
        cout << min(sc, min(w, r));

    }
}

Measured memory_bytes: 3704
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define inf 998244353
#define LINF 100000000000000007LL
#define ll long long
using namespace std;
int ans[310][310];
signed main(){
	int h,w,k;
	cin>>h>>w>>k;
	vector<string> fie;
	for(int i=0;i<h;i++){
		string st;
		cin>>st;
		fie.pb(st);
	}
	int nex = 1;
	for(int i=0;i<h;i++){
		int cur = 0;
		for(int j=0;j<w;j++){
			if( fie[i][j] == '#' ){
				cur = nex;
				nex++;
			}
			ans[i][j] = cur;
		}
		for(int j=w-1;j>=0;j--){
			if( ans[i][j] == 0 ) ans[i][j] = ans[i][j+1];
		}
	}
	for(int i=1;i<h;i++){
		for(int j=0;j<w;j++){
			if( ans[i][j] == 0 ) ans[i][j] = ans[i-1][j];
		}
	}
	for(int i=h-1;i>=0;i--){
		for(int j=0;j<w;j++){
			if( ans[i][j] == 0 ) ans[i][j] = ans[i+1][j];
		}
	}
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			cout<<ans[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

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

int main(void){
		
	string s;
  	cin >> s;
  	int l = s.size();
  	int n;
  	int ans  = 0;
  	
  	if(l%2 == 0) n = l/2;
  	else n = (l - 1)/2;
  	for (int i = 0; i < n; i++){
		if(s[i] != s[l - i - 1]) ans++;
    }
  	cout << ans << endl;
	
  	
	return 0;
  
}

Measured memory_bytes: 384