akhauriyash/Code-Regression huggingface dataset:
using System;

namespace ABC090
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] hoge = Read().Split(' ');
            var a = int.Parse(hoge[0]);
            var b = int.Parse(hoge[1]);
            var cnt = 0;
            for(int i = a; i <= b; i++)
            {
                var str = i.ToString();
                if (str[0] == str[4] && str[1] == str[3]) cnt++;
            }


            Console.WriteLine(cnt);
         }

        public static string Read() { return Console.ReadLine(); }
    }
}


Measured memory_bytes: 15188
# include <algorithm>
# include <iostream>
# include <map>
# include <queue>
# include <string>
# include <vector>

typedef long long ll;
using namespace std;

const ll mod = 1e9 + 7;
int n;
string orig[4] = { "A", "G", "C", "T" };
map<string, ll> memo[101];

bool isNotValid(string lastFour) {
    return (lastFour[0] == 'A' && lastFour[1] == 'G' && lastFour[3] == 'C') || (lastFour[0] == 'A' && lastFour[2] == 'G' && lastFour[3] == 'C');
}

ll dfs(int curLen, string lastThree) {
    if (memo[curLen].find(lastThree) != memo[curLen].end()) return memo[curLen].at(lastThree);
    if (curLen == n) return 1;
    ll ret = 0;
    for (auto& o : orig) {
        string next = lastThree+o;
        if (!isNotValid(next) && next.substr(1, 3) != "AGC" && next.substr(1, 3) != "GAC" && next.substr(1, 3) != "ACG") ret += dfs(curLen+1, next.substr(1, 3));
    }
    memo[curLen].insert({ lastThree, ret % mod });
    return ret % mod;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    ll ans = dfs(0, "TTT");
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 896
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		sc.close();
		
		if (K==1)
			System.out.println(0);
		else
			System.out.println(N-K);
		
		

	}

}


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


string s1[55],s2[55];
int main()
{
  int  n,m;
  cin>>n>>m;
  for(int i=0;i<n;++i)
   cin>>s1[i];
  for(int i=0;i<m;++i)
   cin>>s2[i];
      for(int c1=0;c1<n-m+1;++c1){
       for(int c2=0;c2<n-m+1;++c2){
        bool f=true;
         for(int i=0;i<m;++i){
          for(int j=0;j<m;++j){
              if(s1[i+c1][j+c2]!=s2[i][j]){
                f=false;
                break;
              }
          if(f==false)
                break;
         }
      }
      if(f){
        cout<<"Yes"<<endl;
        return 0;
      }
      }
    }
      cout<<"No"<<endl;
return 0;
}


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

using namespace std;

int main()
{
    int n,k;
    cin >>n >>k;
    int ct= 0;
    for(int i=1 ;i<=n;++i)
    {
        int x; cin >> x;
        if(x>=k)
            ct++;
    }
    cout << ct;
}


Measured memory_bytes: 256
n = int(input())
pair = []
ns = []
for i in range(n-1):
    c,s,f = map(int, input().split())
    pair.append((c,s,f))

ans = []
for i in range(n-1):
    c,s,f = pair[i]
    cnt = s + c
    for j in range(i+1,n-1):
        c,s,f = pair[j]
        s_ = max(s,((cnt - 1)//f+1)*f)
        cnt = s_ + c
    print(cnt)
print(0)

Measured memory_bytes: 3188
/*
ID: anonymo14
TASK: wormhole
LANG: C++                 
*/
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpii;

#define F first
#define S second
#define PU push
#define PUF push_front
#define PUB push_back
#define PO pop
#define POF pop_front
#define POB pop_back

#define REP(i,a,b) for(int i=a; i<=b; i++)

#define MOD 1000000007

void solve(int test_case) {//227
	int n;
	double t,a;
	cin>>n>>t>>a;
	double nearVal = INT_MAX;
	int nI = 0;
	REP(i,1,n) {
		double h;
		cin>>h;
		h=abs(t-h*0.006-a);
		if(h<nearVal) {
			nearVal=h;
			nI=i;
		}
	}
	cout<<nI;
}

int main() {
	
	////// FILE BASED IO////
	//freopen("wormhole.in", "r", stdin);
	//freopen("wormhole.out", "w", stdout);
	///////////////
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin>>t;
	REP(i,1,t) {
		solve(i);
	}
	return 0;
}	


Measured memory_bytes: 3804
#include<bits/stdc++.h>
#define ll long long
using namespace std;
signed main() {
  ll a,b;
  ll cun = 0;
  cin >> a;
  for (int i = 1; i <= a; i++ ){
    cin >> b;
    if (i % 2 != 0 && b % 2 != 0) {
      cun++;
    }
  }

  cout << cun << "\n";
  return 0;
}


Measured memory_bytes: 3632
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define qmax(x,y) (x=max(x,y))
#define qmin(x,y) (x=min(x,y))
#define mp(x,y) make_pair(x,y)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
inline int read(){
	int ans=0,fh=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
		ans=ans*10+ch-'0',ch=getchar();
	return ans*fh;
}
const int maxn=2e5+100,inf=2e9;
struct node{
	int x,y,z;
}e[maxn<<1];
int n,a[maxn],m,q,fa[maxn];
ll Ans;
bool cmp(node x,node y){return x.z<y.z;}
int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
int main(){
//	freopen("nh.in","r",stdin);
//	freopen("zhy.out","w",stdout);
	n=read(),q=read();
	for(int i=0;i<n;i++) a[i]=inf;
	for(int i=1;i<=q;i++){
		int x=read(),y=read(),z=read();
		e[++m]=(node){x,y,z};
		qmin(a[x],z+1),qmin(a[y],z+2);
	}
	for(int i=0;i<n;i++) qmin(a[i],a[(i-1+n)%n]+2);
	for(int i=0;i<n;i++) qmin(a[i],a[(i-1+n)%n]+2);
	for(int i=0;i<n;i++) e[++m]=(node){i,(i+1)%n,a[i]};
	for(int i=0;i<n;i++) fa[i]=i;
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++){
		int x=getfa(e[i].x),y=getfa(e[i].y);
		if(x==y) continue;
		fa[x]=y,Ans+=e[i].z;
	}
	printf("%lld\n",Ans);
	return 0;
}












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

int main() {
  string s,ans;
  cin >> s;
  for(int i=0;i<s.size();i++) {
    if(s[i]=='B') {
      if(ans.size()>0) ans.pop_back();
    }else{
      ans += s[i];
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define Red ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i, n) for(int i =0 ; i < n; ++i)
#define Rep(i,a,b) for(int i=a;i<=b;i++)
#define pii pair < int, int >
typedef vector<int> vi;
typedef  long long ll;
const int mod =1e9+7;
const int N = (int)2e5 + 5;


void solve(){
	int n,x;
	cin>>n>>x;
	int d=n/500;
	n-=d*500;
	if(x>=n)cout<<"Yes";
	else cout<<"No";

}

int main(){
	Red;
	int t=1;
	//cin>>t;
	while(t--)
	solve();
	return 0;
}

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

class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringBuilder builder = new StringBuilder();

		String str1 = br.readLine();

		String str2 = br.readLine();


		if(kmpSearch(str1+str1, str2)== -1){
			System.out.println("No");

		}else {
			System.out.println("Yes");
		}


	}


 private static int kmpSearch(String text, String pattern){
  int textIndex = 1;
  int patternIndex = 0;
  int[] cacheTable = new int[pattern.length() + 1];
  cacheTable[0] = cacheTable[1] = 0;

  while(pattern.length() > textIndex ){
   if(pattern.charAt(textIndex) == pattern.charAt(patternIndex)){

    textIndex++;
    patternIndex++;
    cacheTable[textIndex] = patternIndex;
   } else if (patternIndex == 0){

    textIndex++;
    cacheTable[textIndex] = 0;
   } else {

    patternIndex = cacheTable[patternIndex];
   }
  }

  int i = 0;
  int n = 0;
  while(n < text.length()) {

   if(text.charAt(n) == pattern.charAt(i)){
    ++n;
    ++i;
    if(pattern.length() == i){

     return n - pattern.length();
    }
   } else if ( i == 0){

    ++n;
   } else {

    i = cacheTable[i];
   }
  }

  return -1;
 }

}

Measured memory_bytes: 24192
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

mt19937 mrand(random_device{} ()); 

int rnd(int x) {
  return mrand() % x;
}

typedef long double ld;
typedef long long ll;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define pb push_back
#define mp make_pair
#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const ld eps = 1e-9;
const ld pi = acos((ld) -1.0);

void precalc() {
}

const int maxn = (int) 1e5 + 10;
char s[maxn];
int n;

int read() {
  if (scanf("%s%d", s, &n) < 2) {
    return 0;
  }
  return 1;
}

void solve() {
  int len = (int) strlen(s);
  for (int i = 0; i < len; ++i) {
    if (s[i] == 'a') {
      continue;
    }
    int need = 'a' - s[i] + 26;
    if (n >= need) {
      s[i] = 'a';
      n -= need;
    }
  }
  s[len - 1] = (s[len - 1] - 'a' + n) % 26 + 'a';
  printf("%s\n", s);
}

int main() {
  precalc();
#ifdef LOCAL
  freopen(TASK ".out", "w", stdout);
  assert(freopen(TASK ".in", "r", stdin));
#endif

  while (1) {
    if (!read()) {
      break;
    }
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100;
int a[N];

void read(int &x){
	x=0;int f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c-'0');c=getchar();}
	x*=f;
}

int main(){
	int n,x;
	read(n);read(x);
	int ans=0;
	for(int i=1;i<=n;i++) read(a[i]);
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++){
		if(x>=a[i]) x-=a[i],ans++;
		else break;
	}
	if(x>=a[1]) ans+=x/a[1];
	printf("%d",ans);
}

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

using namespace std;

int main(){
    string s;
    cin >> s;
    if(s == "Sunny"){
        cout << "Cloudy" << endl;
    }
    else if(s == "Cloudy"){
        cout << "Rainy" << endl;
    }
    else{
        cout << "Sunny" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
def depthFirstSearch(i, Adj, d, f, t):
    if d[i - 1]:
        return t

    d[i - 1] = t
    t += 1

    for v in Adj[i - 1]:
        t = depthFirstSearch(v, Adj, d, f, t)

    f[i - 1] = t
    t += 1

    return t


n = int(input())
Adj = [list(map(int, input().split()))[2:] for _ in range(n)]

d = [0] * n
f = [0] * n

t = 1
for i in range(n):
    if d[i] == 0:
        t = depthFirstSearch(i + 1, Adj, d, f, t)

for i, df in enumerate(zip(d, f)):
    print(i + 1, *df)



Measured memory_bytes: 5712
from itertools import groupby

ans = premax = 0
# 文字列を連続した < か > のグループに分ける
for k, g in groupby(input()):
    # 連続している数分1ずつ増やして足していく
    for c, _ in enumerate(g, 1):
        ans += c
    # >の連続なら前回の<の最大値（最後の値）と今回の>の最後の値で小さい方を引く
    if k == '>':
        ans -= min(c, premax)
    premax = c
print(ans)

Measured memory_bytes: 44064
def merge(A,left,mid,right):
    L=A[left:mid]+[float("INF")]
    R=A[mid:right+1]+[float("INF")]
    i=0
    j=0
    global cnt
    for k in range(left,right+1):
        if L[i]<=R[j]:
            A[k]=L[i]
            i+=1
        else:
            A[k]=R[j]
            j+=1
            cnt+=len(L)-i-1
def mergeSort(A,left,right):
    if left<right:
        mid=(left+right)//2+1
        mergeSort(A,left,mid-1)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)
n=int(input())
S=list(map(int,input().split()))
cnt=0
mergeSort(S,0,n-1)
print(cnt)


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

int main() {
	int N, M, Q;
	cin >> N >> M >> Q;
	vector<int> A(Q), B(Q), C(Q), D(Q);
	for (int i = 0; i < Q; i++) {
		cin >> A[i] >> B[i] >> C[i] >> D[i];
		A[i]--, B[i]--;
	}
	vector<int> V;
	for (int i = 0; i < N; i++) V.push_back(0);
	for (int i = 0; i < M - 1; i++) V.push_back(1);
	long long ANS = 0;
	do {
		vector<int> X;
		int NOW = 0;
		for (int i = 0; i < V.size(); i++) {
			NOW += V[i];
			if (V[i] == 0) X.push_back(NOW);
		}
		long long COUNT = 0;
		for (int i = 0; i < Q; i++) {
			if (X[B[i]] - X[A[i]] == C[i]) COUNT += D[i];
		}
		ANS = max(ANS, COUNT);
	} while (next_permutation(V.begin(), V.end()));
	cout << ANS << endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

int main()
{
  cout << fixed << setprecision(10);
  ll N;
  cin >> N;
  ll A,B,C,D,E;
  cin >> A >> B >> C >> D >> E;
  ll F = min({A,B,C,D,E});
  if(N%F==0)
  {
    cout << N/F+4 << endl;
  }
  else{
  cout << N/F+5 << endl;
  }
  return 0;
}


Measured memory_bytes: 256
n=gets.to_i
word_arr=Array.new(n)
word_arr[0]=gets.chomp
flag=true
arr=word_arr[0].chomp.split("")
word1=arr[arr.size-1].chomp
for i in 1..n-1
	word=gets.chomp
	arr=word.chomp.split("")
	word2=arr[0].chomp
	if word_arr.index(word)!=nil or word1 !=word2
		flag=false
		break
	end
	word1=arr[arr.size-1]
	word_arr[i]=word
end
print (flag ? 'Yes': 'No')

Measured memory_bytes: 1916
#include<bits/stdc++.h>
using namespace std;
 
signed main(){
   for(int a=0;a<9;a++){
       for(int b=0;b<9;b++){
	   printf("%dx%d=%d\n",a+1,b+1,(a+1)*(b+1));
	   }
       }
}

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

using namespace std;

int main ()
{
  string s;
  cin >> s;
  int i = 0;
  while(i < 3)
  {
   	if(s[i] == s[i + 1])
    {
      cout << "Bad" << endl;
      return 0;
    }
    i++;
  }
  cout << "Good" << endl;
  return 0;
}


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

int main(){
    int n,x,d=0,l,c=1;
    cin>>n>>x;
    for(int i=0;i<n;i++){
        cin>>l;
        d+=l;
        if(d<=x) c++;
        else break;
    }
    cout<<c<<endl;
    return 0;
}

Measured memory_bytes: 256
from collections import deque


def solve(N, K, ABs):
    if N == 1:
        return K

    Ds = [-1 for _ in range(N + 1)]
    Ws = {i: [] for i in range(N + 1)}
    for a, b in ABs:
        Ws[a].append(b)
        Ws[b].append(a)

    for i in range(1, N + 1):
        if Ds[i] == -1:
            Ds[i] = K

            if Ws[i]:
                s = Ws[i][0]
                Ds[s] = K - 1

                queue = deque()
                queue.append(i)
                queue.append(s)

                while queue:
                    s = queue.popleft()
                    k = K - 2
                    for w in Ws[s]:
                        if Ds[w] == -1:
                            Ds[w] = k
                            k -= 1
                            queue.append(w)

    ans = 1
    for i in range(1, N + 1):
        if Ds[i] <= 0:
            return 0
        ans *= Ds[i]
        ans %= 1000000007
    return ans % 1000000007

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(N - 1)]
    print(solve(N, K, ABs))


Measured memory_bytes: 42700
#define _USE_MATH_DEFINES  

#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>

int main(){
    double r;
    std::cin >> r;

    std::cout << std::to_string(std::pow(r, 2) * M_PI) << " " << std::to_string(2 * r * M_PI) << std::endl;
    
    return 0;
}


Measured memory_bytes: 3272
#include <stdio.h>
#include <math.h>

int main(int argc, const char * argv[]) {

    int n,i;
    double x[100],y[100];
    double p1,p2,p22,p3,p33,p4,a;
    
    scanf("%d", &n);
    
    for(i=0; i<n; i++) scanf("%lf",&x[i]);
    for(i=0; i<n; i++) scanf("%lf",&y[i]);
    
    p1=0;
    for(i=0; i<n; i++) p1 += fabs(x[i]-y[i]);
    
    p2=0;
    for(i=0; i<n; i++) p2 += pow(fabs(x[i]-y[i]),2);
    
    p3=0;
    for(i=0; i<n; i++) p3 += pow(fabs(x[i]-y[i]),3);
    
    p4=0;
    
    for(i=0; i<n; i++) {
        a = fabs(x[i]-y[i]);
        if(a>p4) p4=a;
    }
    
    
    p22 = sqrt(p2);
    p33 = pow(p3, 1.0/3.0);

    
    printf("%lf\n%lf\n%lf\n%lf\n", p1, p22, p33 , p4);
    return 0;
}



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

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

#define pb push_back
#define rep(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, n) for(int i = a; i < (n); i++)
#define mod (ll)(1e9+7)
#define int ll
const int INF = 1000000000;

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

signed main() {
	ll n, s, sum = 0, sub = INF;
  cin >> n;
  rep(i, n) {
    cin >> s;
    sum += s;
    if (s % 10) sub = min(sub, s);
  }
  if (sum % 10) cout << sum << endl;
  else if (sub == INF) cout << 0 << endl;
  else cout << sum - sub << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	string S;
	cin >> S;
	int L = S.length();
	bool result = true;
	for(int i = 0; i < L; i++) {
		switch(S[i]) {
			case 'd':
				if(S[L - i - 1] != 'b') result = false;
				break;
			case 'b':
				if(S[L - i - 1] != 'd') result = false;
				break;
			case 'p':
				if(S[L - i - 1] != 'q') result = false;
				break;
			case 'q':
				if(S[L - i - 1] != 'p') result = false;
				break;
		}
	}
	cout << (result ? "Yes" : "No") << endl;
	return 0;
}

Measured memory_bytes: 512
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include<stdio.h>
#include<string.h>
int main() {
	char str[50], *pt = str;
	int flg,x,i,n;
	while (fgets(str, sizeof(str), stdin)) {
		if (str == NULL)break;
		flg = 0;
		x = strlen(str);
		for (i = 0; i < x; i++) {
			if (str[i] != '@') printf("%c", str[i]);
			else {
				i++;
				n = str[i++] - '0';
				for (n; n > 0; --n) printf("%c", str[i]);
			}
		}
	}
	return 0;
}

Measured memory_bytes: 524
N = int(input())
A = list(map(int, input().split()))
 
cnt = 0
r = True
while r == True:
    for i in range(N):
        if A[i] % 2 == 1:
            r = False
        else:
            A[i] = A[i] / 2
    if r == True:
        cnt += 1
    else:
        next
print(cnt)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
const double PI = acos(-1);
using namespace std;
int main() {
    vector<int> test(3);
    while (1)
    {
        cin >> test.at(0) >> test.at(1) >> test.at(2);
        if(test.at(0) == -1 && test.at(1) == -1 && test.at(2) == -1 ){
            break;
        }
        if(test.at(0) == -1 || test.at(1) == -1){
            cout << "F" << endl;
        }
        if( test.at(2) == -1 && test.at(0) != -1 && test.at(1) != -1)
        {
            if(test.at(0) + test.at(1) >= 80){
                cout << "A" << endl;
            }
            else if(test.at(0) + test.at(1) >= 65 && test.at(0) + test.at(1) < 80){
                cout << "B" << endl;
            }
            else if(test.at(0) + test.at(1) >= 50 && test.at(0) + test.at(1) < 65){
                cout << "C" << endl;
            }
            else if(test.at(0) + test.at(1) >= 30 && test.at(0) + test.at(1) < 50){
                cout << "D" << endl;
            }
            else if(test.at(0) + test.at(1) <30){
                cout << "F" << endl;
            }
            
        }
        else if(test.at(2) != -1){
            if(test.at(2) >= 50){
                cout << "C" << endl;
            }
            else if(test.at(0) + test.at(1) >= 30 && test.at(0) + test.at(1) < 50){
                cout << "D" << endl;
            }
            else if(test.at(0) + test.at(1) <30){
                cout << "F" << endl;
            }

        }
        
        /* code */
    }
    

}
    


Measured memory_bytes: 3136
#include <queue>
#include <iostream>

using namespace std;

#define int long long

const int N = 1e3 + 10;

int dp[N][N];
char s[N][N];
bool vis[N][N];
int h, w, ch, cw;
int r[] = {0, 0, 1, -1};
int c[] = {1, -1, 0, 0};

void dijkstra() {
  priority_queue<pair<int, pair<int, int>>> q;
  q.push({0, {ch, cw}});
  while (!q.empty()) {
    auto z = q.top();
    int x = z.second.first;
    int y = z.second.second;
    q.pop();
    if (!vis[x][y]) {
      vis[x][y] = 1;
    } else if (dp[x][y] <= -z.first) {
      continue;
    }
    dp[x][y] = -z.first;
    for (int i = 0; i < 5; ++i) {
      for (int j = 0; j < 5; ++j) {
        int u = x - 2 + i;
        int v = y - 2 + j;
        if (u < 1 || u > h || v < 1 || v > w || s[u][v] == '#') {
          continue;
        }
        if (dp[u][v] > dp[x][y] + (abs(u - x) + abs(v - y) > 1)) {
          q.push({-(dp[x][y] + (abs(u - x) + abs(v - y) > 1)), {u, v}});
        }
      }
    }
  }
}

int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);    
  cin >> h >> w >> ch >> cw;
  int dh, dw;
  cin >> dh >> dw;
  for (int i = 1; i <= h; ++i) {
    cin >> s[i] + 1;
  }
  for (int i = 1; i <= h; ++i) {
    for (int j = 1; j <= w; ++j) {
      dp[i][j] = 1e18;
    }
  }
  dijkstra();
  if (dp[dh][dw] == 1e18) {
    cout << -1;
  } else {
    cout << dp[dh][dw];
  }
  return 0;
}


Measured memory_bytes: 14136
#include <bits/stdc++.h>
using namespace std;
int main(){
  
  int n,m;
  cin >> n >> m;
  
  vector<int> H(n,0);
  vector<bool> E(n,true);
  
  for(int i=0; i<n; i++){
    cin >> H.at(i);
  }
  
  for(int i=0;i<m;i++){
    
    int a,b;
    cin >> a >> b;
    
    if(H.at(a-1)<H.at(b-1)) E.at(a-1)=false;
  else if(H.at(a-1)==H.at(b-1)) {
    E.at(a-1)=false;
    E.at(b-1)=false;
  }
    else E.at(b-1)=false;
  }
  
  int count=0;
  
  for(int i=0;i<n;i++){
    if(E.at(i)) count += 1;
  }
  
  cout << count << endl;
}

Measured memory_bytes: 3784
n = int( input() )
x = input()
x_pop = x.count( "1" )
x_pls = x_pop + 1
x_mns = x_pop - 1

# 2の冪乗のリスト．ただし後々に備えてpopcountで割った余りにしてある
rp = [ pow( 2, i, x_pls ) for i in range( n + 1 ) ]
if x_mns > 0:
    rm = [ pow( 2, i, x_mns ) for i in range( n + 1 ) ]
else:
    rm = [ 0 ] * ( n + 1 )

x = x[ : : -1 ]
rem_p = 0
rem_m = 0
for i in range( n ):
    if x[ i ] == "1":
        rem_p += rp[ i ]
        rem_m += rm[ i ]

for i in range( n - 1, -1, -1 ):
    if x[ i ] == "0":
        tmp = ( rem_p + rp[ i ] ) % x_pls
    elif x_mns > 0:
        tmp = ( rem_m - rm[ i ] ) % x_mns
    else: # popcount( X_i ) == 0
        print( 0 )
        continue
    ans = 1
    while tmp > 0:
        tmp = tmp % bin( tmp ).count( "1" )
        ans += 1
    print( ans )

Measured memory_bytes: 24916
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define prtd(var, i) cout << fixed << setprecision(i) << var << endl;
#define ll long long
using namespace std;
#define INF 1e18LL

const ll MAX = 1000000000000000000; //1e18

int main(){
    int n; cin >> n;
    vector<string> w(n);
    bool exist = false;
    rep(i, n){
        cin >> w[i];
        rep(j, i){
            if(w[i] == w[j]){
                exist = true;
            }
        }
    }
    if(exist){
        cout << "No" << endl;
        return 0;
    }
    for(int i = 1; i < n; i++){
        string s1 = w[i-1];
        char c1 = s1[s1.size()-1];
        string s2 = w[i];
        char c2 = s2[0];
        if(c1 != c2){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;

}



Measured memory_bytes: 256
def gcd(x,y):
    while y>0:
        x,y = y,x%y
    return x
N = int(input())
T = [int(input()) for _ in range(N)]
ans = T[0]
for i in range(1,N):
    a = gcd(ans,T[i])
    ans = (ans//a)*T[i]
print(ans)

Measured memory_bytes: 38256
#include <iostream>
using namespace std;
int N;

void dfs(string s, char mx) {
    if (s.size() == N) {
        cout << s << endl;
    } else { 
        for (char c = 'a'; c <= mx; c++) {
            dfs(s+c, ((c==mx) ? (char)(mx + 1) : mx));
        }
    }
}

int main() {
    cin >> N;
    dfs("", 'a');
}

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

lis = []
for _ in range(Q):
    lis.append(int(input()))

point = [K] * N

for i in range(Q):
    num = lis[i]
    point[num-1] += 1

for j in range(N):
    point[j] -= Q



for i in range(N):
    if point[i] > 0:
        print('Yes')
    else:
        print('No')


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

typedef long long ll;
typedef long double ld;

#define pb push_back
#define sort(s) sort(s.begin(),s.end())
#define reverse(s) reverse(s.begin(),s.end())
#define rep(i,n) for(ll (i)=0;(i)<(n);(i)++)

int main(){
    int n,m,c; cin >> n >> m >> c;
    int B[m];
    rep(i,m){ cin >> B[i]; }
    int A[n][m];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> A[i][j];
        }
    }

    bool flag[n];
    rep(i,n){
        flag[i] = false;
    }

    for(int i=0;i<n;i++){
        int ans(0);
        for(int j=0;j<m;j++){
            ans = ans + A[i][j]*B[j]; 
        }
        ans += c;
        if(ans > 0){
            flag[i] = true;
        }
        
    }

    
    int count(0);
    rep(i,n){
        if(flag[i]==true){
            count++;
        }
        
    }
    cout << count << endl;


    //int l(0);
    //rep(i,n){
    //    if(flag[i]==false)l++;
    //}
    //if(l==n) cout << false << endl;

return 0;

}

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

int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int> > g;
	g.assign(n, vector<int>());
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}


	int ans[112345];
	for (int i = 1; i < n; i++) ans[i] = -1;
	ans[0] = 0;
	
	queue<int> que;
	que.push(0);
	ans[0] = 0;
	while(!que.empty()) {
		int v = que.front();
		que.pop();
		for (int i = 0; i < g[v].size(); i++) {
			if (ans[g[v][i]] == -1) {
				ans[g[v][i]] = v;
				que.push(g[v][i]);
			}
		}
	}
	cout << "Yes" << endl;
	for (int i = 1; i < n; i++) cout << ans[i]+1 << endl;
	return 0;
}

Measured memory_bytes: 10168
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n = II()
    ab = LIR(n)
    cd = LIR(n)
    ab.sort()
    cd.sort()
    check = [0 for i in range(n)]
    ans = 0
    #print(ab)
    for i, c in enumerate(cd):
        d = c[1]
        c = c[0]
        maxy = -1
        x = -1
        for k, a in enumerate(ab):
            b = a[1]
            a = a[0]
            if maxy < b and c > a and check[k] == 0 and d > b:
                maxy = b
                x = k
                #print(a,b,c,d)
        if x != -1:
            ans += 1
            check[x] += 1
    print(ans)


    return

#D
def D():
    n = II()
    ab = LI()
    cd = LI()
    binab = []
    bincd = []
    warerua = [0 for i in range(28)]
    wareruc = [0 for i in range(28)]
    warenaib = [0 for i in range(28)]
    warenaid = [0 for i in range(28)]
    for i in range(n):
        ab[i] = list(bin(ab[i]))[2:]
        ab[i] = ab[i][::-1]
        cd[i] = list(bin(cd[i]))[2:]
        cd[i] = cd[i][::-1]
    for i in range(n):
        for k in range(len(ab[i])):
            #print(warerua, warenaib, wareruc, warenaid,ab[i][k])
            if ab[i][k] == "1":
                warenaib[k] += 1
            else:
                warerua[k] += 1
        for k in range(len(ab[i]), 28):
            warerua[k] += 1
        for k in range(len(cd[i])):
            if cd[i][k] == "1":
                warenaid[k] += 1
            else:
                wareruc[k] += 1
        for k in range(len(ab[i]), 28):
            wareruc[k] += 1
    ans = 0
    print(warerua, warenaib, wareruc, warenaid)
    for i in range(28):
        kisu = warerua[i] * warenaid[i] + warenaib[i] * wareruc[i]
        gusu = warerua[i] * wareruc[i] + warenaib[i] * warenaid[i]
        if kisu % 2:
            ans += 1 << i
    print(ans)
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    C()


Measured memory_bytes: 3824
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=100005;
int a[MAXN];
int b[MAXN];
int n,L;
int main()
{
	scanf("%d%d",&n,&L);
	int Min=0x3f3f3f3f,Tab=0,sum=0;
	for(int i=1;i<=n;i++)
		a[i]=L+i-1,sum+=a[i];
	for(int i=1;i<=n;i++)
		if(abs(a[i])<=Min)
			Tab=i,Min=abs(a[i]);
	printf("%d",sum-a[Tab]);
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
//long long int countt[200003];
#include<ext/pb_ds/assoc_container.hpp> // include the associative containers or group of templates such as set, multimap, map etc.
#include<ext/pb_ds/tree_policy.hpp> // include the tree_order_statistics_node update
using namespace __gnu_pbds; //necessary for the GNU based Policy based data structures.
typedef tree<pair<int,int> ,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

#define int long long
#define endl "\n"


signed main()
{
    FAST;
    
    int i=0,j=0,k=0,n=0,m=0,count=0,temp=0;
    int temp1=0,temp2=0,temp3=0,x=0,l=0,y=0,sum=0;
    int left=0,up=0,down=0,start=0,end=0,r=0,q=0,total=0;
    int maxx=0,minn=0,curr=0,ans=0,places=0,zeroes=0,low=0,high=0;
    int prev=0,mid=0,z=0,d=0,val=0,pos=0,shift=0,h=0,right=0,var=0;
    
    int a,b;
    cin>>a>>b>>n;
    
    if(n>=b-1) x=b-1;
    
    else
    {
        x=n;
    }
    
    temp = a*x;
    temp=temp/b;
    
    temp1=x/b;
    temp1=temp1*a;
    
    cout<<temp-temp1<<endl;
    
    
}

Measured memory_bytes: 3652
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()

using namespace std;

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

int nextInt() {int a; cin >> a; return a;}
char nextChar() {char a; cin >> a; return a;}
double nextDouble() {double a; cin >> a; return a;}
string nextString() {string a; cin >> a; return a;}

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

signed main() {
    string A, B;
    cin >> A >> B;

    rep(i, B.size()) {
	cout << A[i] << B[i];
    }
    if (A.size() != B.size()) cout << A[A.size() - 1];
    cout << endl;

    return 0;
}


Measured memory_bytes: 256
n,a,b,c,*l=map(int,open(0).read().split())
def dfs(x,y,z,r):
  if r==n:
    return abs(a-x)+abs(b-y)+abs(c-z)-30 if min(x,y,z)>0 else 10**9
  return min(
    dfs(x+l[r],y,z,r+1)+10,
    dfs(x,y+l[r],z,r+1)+10,
    dfs(x,y,z+l[r],r+1)+10,
    dfs(x,y,z,r+1)
  )
print(dfs(0,0,0,0))

Measured memory_bytes: 9164
#include<stdio.h>
int main()
{
int a,b,i;
scanf("%d %d",&a,&b);

if(a==b)
{
for(i=1;i<=a;i++)
printf("%d",a);
}

else if(a>b)
{
for(i=1;i<=a;i++)
printf("%d",b);
}

else
{
for(i=1;i<=b;i++)
printf("%d",a);
}

return 0;

}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int gcd(int x,int y){
  while(y){
    x %= y;
    swap(x,y);
  }
  return x;
}
int main(){
  int N;
  cin >> N;
  vector<int> line(N+1);
  for(int i=1;i<=N;++i){
    cin >> line[i];
  }
  if(N==2){
    cout << max(line[1],line[2]) << endl;
  }else{
    vector<int> x(N+2),y(N+2);
    x[0] = line[0];
    for(int i=1;i<=N;++i){
      x[i] = gcd(line[i],x[i-1]);
    }
    y[N+1] = line[N];
    for(int i=N;i>0;--i){
      y[i] = gcd(line[i],y[i+1]);
    }
    int ans = max(x[N-1],y[2]);
    for(int i=1;i<N-1;++i){
      ans = max(ans, gcd(x[i],y[i+2]));
    }
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 1408
#include <stdio.h>

int main(){
  int i,j=0,N=0,v,x;

  scanf("%d",&N);

  int A[N];

  for(i=0;i<N;i++)   scanf("%d",&A[i]);
  for(i=0;i<N-1;i++)  printf("%d ",A[i]);
  
  printf("%d",A[N-1]);
  printf("\n");

  for(i=1;i<N;i++){
    v = A[i];
    j=i-1;

    while(j >=0 && A[j] > v){
      A[j+1] = A[j];
      j--;
    }
    A[j+1] = v;

    for(x=0;x<N-1;x++){
      printf("%d ",A[x]);
    }

    printf("%d",A[N-1]);
    printf("\n");
  }

  return 0;
}
	   
    



Measured memory_bytes: 2112
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)n;i++)
using Graph = vector<vector<int> >;
using GraphC = vector<vector<char> >;
const int INF = 1000000000;
typedef pair<int, int> P;
const int MAX_N = 1000000000;
typedef int64_t ll;
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; }



int main() {
	string O, E;
	cin >> O >> E;
	rep(i, O.size()) {
		if (O.size()==E.size())
		{
			cout << O.at(i) << E.at(i);
		}
		else {
			if (i==O.size()-1)
			{
				cout << O.at(i);
			}
			else {
				cout << O.at(i) << E.at(i);
			}
		}
		
	}
}

Measured memory_bytes: 3596
#include <iostream>
#include <set>

using namespace std;

class Solver {
  public:
    int n, m;
    int a[10000], b[10000];
    int solve() {
      set<int> friends, friends_friends;
      for (int i = 0; i < m; ++i) {
        if (a[i] == 1) {
          friends.insert(b[i]);
        }
      }
      for (set<int>::iterator iter = friends.begin(); iter != friends.end(); ++iter) {
        for (int i = 0; i < m; ++i) {
          if (a[i] == *iter && b[i] != 1 && friends.count(b[i]) == 0) {
            friends_friends.insert(b[i]);
          } else if (b[i] == *iter && a[i] != 1 && friends.count(a[i]) == 0) {
            friends_friends.insert(a[i]);
          }
        }
      }
      return friends.size() + friends_friends.size();
    }
};

int main() {
  Solver s;
  while (true) {
    cin >> s.n >> s.m;
    if (s.n == 0) {
      return 0;
    }
    for (int i = 0; i < s.m; ++i) {
      cin >> s.a[i] >> s.b[i];
    }
    cout << s.solve() << endl;
  }
}

Measured memory_bytes: 1292
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef vector<vector<int>> Matrix;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
static const int INF = 2000000000;

vector<int> eq;

int main(){
  int n;
  string s;
  cin >> n >> s;
  eq = vector<int>(n, 0);
  for (int i = 1; i < n-1; i++){
    int t = min(i-1, n-i-2);
    for (int j = i-1; t >= 0; j--){
      if (s[i] != s[j] && s[j] != s[2*i-j] && s[2*i-j] != s[i]) {
        eq[i]++;
      }
      t--;        
    }
  }

  vector<int> R, G, B;
  R.push_back(-1);
  G.push_back(-1);
  B.push_back(-1);
  rep(i, n) {
    if (s[i] == 'R') R.push_back(i);
    else if (s[i] == 'G') G.push_back(i);
    else B.push_back(i);
  }

  int nr = R.size();
  int ng = G.size();
  int nb = B.size();
  ll ans = 0;
  for (int i = 1; i < n-1; i++){
    if (s[i] == 'R'){
      ll lg = lower_bound(ALL(G), i) - G.begin() - 1;
      ll lb = lower_bound(ALL(B), i) - B.begin() - 1;
      ll rg = upper_bound(ALL(G), i) - G.begin();
      ll rb = upper_bound(ALL(B), i) - B.begin();
      if (rg <= ng) rg = ng - rg;
      else rg = 0;
      if (rb <= nb) rb = nb - rb;
      else rb = 0;
      ll now = lg * rb + lb * rg - eq[i];
      if (now > 0)ans += now;
    } else if (s[i] == 'G') {
      ll lr = lower_bound(ALL(R), i) - R.begin() - 1;
      ll lb = lower_bound(ALL(B), i) - B.begin() - 1;
      ll rr = upper_bound(ALL(R), i) - R.begin();
      ll rb = upper_bound(ALL(B), i) - B.begin();
      if (rr <= nr) rr = nr - rr;
      else rr = 0;
      if (rb <= nb) rb = nb - rb;
      else rb = 0;
      ll now = lr * rb + lb * rr - eq[i];
      if (now > 0)ans += now;
    } else {
      ll lr = lower_bound(ALL(R), i) - R.begin() - 1;
      ll lg = lower_bound(ALL(G), i) - G.begin() - 1;
      ll rr = upper_bound(ALL(R), i) - R.begin();
      ll rg = upper_bound(ALL(G), i) - G.begin();
      if (rr <= nr) rr = nr - rr;
      else rr = 0;
      if (rg <= ng) rg = ng - rg;
      else rg = 0;
      ll now = lr * rg + lg * rr - eq[i];
      if (now > 0) ans += now;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 3656
import math

X = int(input())

def decompose(n):
	result = []
	half = math.floor(math.sqrt(n))
	i = 2
	while i <= half:
		if n % i == 0:
			result.append(i)
			n //= i
			half = math.floor(math.sqrt(n))
		else:
			i += 1
	if n > 1:
		result.append(n)
	return result

facts = decompose(X)

fact_table = {}
for f in facts:
	if f not in fact_table:
		fact_table[f] = 1
	else:
		fact_table[f] += 1

facts = list(fact_table.items())
facts.sort()

def bisearch_smallest(f, s, e = None):
	if e == None:
		e = s - 1
		s = 0
	else:
		e -= 1
	
	while s < e:
		m = (s + e) // 2
		if f(m):
			e = m
		else:
			s = m + 1
	
	if s == e and f(s):
		return s
	else:
		return -1

def find(num, n):
	if n >= len(facts):
		m = bisearch_smallest(lambda A: 5 * A ** 4 - 5 * (A - num) ** 4 >= 0, 0, 10 ** 9)
		i = bisearch_smallest(lambda A: A ** 5 - (A - num) ** 5 <= X, 0, m + 1)
		j = bisearch_smallest(lambda A: A ** 5 - (A - num) ** 5 >= X, m - 1, 10 ** 9)
		
		if i ** 5 - (i - num) ** 5 == X:
			return i, i - num
		if j ** 5 - (j - num) ** 5 == X:
			return j, j - num
	else:
		f, c = facts[n]
		for i in range(c + 1):
			ret = find(num, n + 1)
			if ret != None:
				return ret
			num *= f
	return None

A, B = find(1, 0)


print(A, B)


Measured memory_bytes: 9264
import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N = int(input())
A = [int(x) for x in input().strip().split()]
C = defaultdict(int)
for a in A:
    C[a] += 1

sum = 0
for i, c in C.items():
    sum += (c * (c-1)) // 2

for a in A:
    print(sum - (C[a]*(C[a]-1))//2 + ((C[a]-1)*(C[a]-2))//2)


Measured memory_bytes: 26780
from copy import copy
N, A, B, C = map(int, input().split())
L = []
for _ in range(N):
  L.append(int(input()))

INF = 10 ** 9
def dfs(cur, a, b, c, m):
  if cur == N:
    if min(a, b, c) == 0:
      return INF
    return abs(A-a)+abs(B-b)+abs(C-c)+(m-3)*10

  res0 = dfs(cur+1, a, b, c, m)
  res1 = dfs(cur+1, a+L[cur], b, c, m+1)
  res2 = dfs(cur+1, a, b+L[cur], c, m+1)
  res3 = dfs(cur+1, a, b, c+L[cur], m+1)

  return min(res0, res1, res2, res3)

print(dfs(0, 0, 0, 0, 0))


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

using ll = long long;

#define for_(i, a, b) for(int i = (a);i < (b);++i)
#define rfor_(i, a, b) for(int i = (b)-1;i >= (a);--i)
#define rep(i, n) for_(i, 0, n)
#define rrep(i, n) rfor_(i, 0, n)

int N;

ll S[200005];

ll c, t;

int main() {
  cin.tie(0);cout.tie(0);
  ios_base::sync_with_stdio(false);
  
  cin>>N;
  rep(i, N) {
    ll A;
    cin>>A;
    S[i+1] = A + S[i];
  }
  
  sort(S, S+N+1);
  
  rep(i, N) {
  	if(S[i+1]==S[i])c++;
  	else {
  		t += (c+1)*c/2;
  		c = 0;
  	}
  }
  t += (c+1)*c/2;
  
  cout<<t<<endl;
  
  return 0;
}


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

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

ll A[100];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    REP(i, N) {
        cin >> A[i];
    }

    ll ans = 1000;
    ll x = 0;
    REP(i, N) {
        if (i < N - 1) {
            if (A[i] < A[i + 1] && x == 0) {
                x = ans / A[i];
                ans %= A[i];
                continue;
            }
        }

        if (i > 0) {
            if (i == N - 1 || (A[i] > A[i + 1] && x > 0)) {
                ans += A[i] * x;
                x = 0;
                continue;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3652
#include <cstdio>
int P[201];
int main() {
  int m, nmin, nmax;
  while (true) {
    scanf("%d %d %d", &m, &nmin, &nmax);
    if (m == 0 && nmin == 0 && nmax == 0) break;
    for (int i=0;i<m;i++) scanf("%d", &P[i]);
    int max_gap = -1, max_n = -1;
    for (int n=nmin;n<=nmax;n++) {
      const int gap = P[n-1]-P[n];
      if (gap >= max_gap) {
        max_gap = gap;
        max_n = n;
      }
    }
    printf("%d\n", max_n);
  }
}


Measured memory_bytes: 2712
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define mp make_pair
#define ERASE(v,i) (v).erase(remove(all(v),i),(v).end())
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define each(it,c) for(typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
#define debug(x) cerr<<#x<<" = "<<(x)<<endl;
#define LINE cerr<<"LINE: "<<__LINE__<<endl;
inline int toInt(string s){int v;istringstream i(s);i>>v;return v;}
template<class T> inline string toString(T x){ostringstream o;o<<x;return o.str();}
template<class T> void pv(T a,T b){for(T it=a;it!=b;++it)cerr<<*it<<" ";cerr<<endl;}
const int INF = 1000000000;
const double EPS = 1e-10;

int main() {
	for(int x, y; cin >> x >> y, x || y;) {
		if(x < y) swap(x, y);
		int cnt = 0;
		while(y != 0) {
			x = x % y;
			swap(x, y);
			cnt++;
		}
		cout << x << " " << cnt << endl;
	}
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
 
using namespace std;
  
int main(void){
  int K, S;
  int i,j,k,count=0;
  
  cin >> K >> S;
  
  for(i=0;i<=K;i++){
	  if(i==S){
	   count++;
	   break;
	  }
      for(j=0;j<=K;j++){
		if(0 < S-i-j && S-i-j <= K){
			count++;
		}else if(S-i-j == 0){
			count++;
			break;
		}
		
      }
  }
  cout << count;
}

Measured memory_bytes: 256
#include <stdio.h>

int main (void)
{
	int a,b,c,count;
	scanf("%d",&a);
	scanf("%d",&b);
	scanf("%d",&c);
	count=0;
	while(a<=b)
	{
		if(c%a==0)
		{
			count++;
		}
		a++;
	}
	printf("%d\n",count);
	return 0;
}

Measured memory_bytes: 596
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;

signed main(){
    cin.tie(0); 
    ios::sync_with_stdio(false);
    int n;
    long long h[110];
    long long dev[110];
    long long temp;
    int count;
    int ans;
    cin>>n;
    while(n!=0){
        for(int i=0;i<n+1;i++){
            cin>>h[i];
        }
        for(int i=1;i<n+1;i++){
            dev[i-1] = h[i] - h[i-1];
        }
        count = 0;
        ans = 0;
        temp = dev[0];
        for(int i=1;i<n+1;i++){
            if(ans != 0){
                if(h[i]-temp*(i-1) != h[0]){
                    count++;
                    ans = i;
                }
            }else{
                if(h[i]-temp*i != h[0]){
                    count++;
                    ans = i;
                }
            }
        }
        if(count != 1){
            temp = dev[1];
            int c = 0;
            for(int i=2;i<n+1;i++){
                if(h[i]-temp*(i-1) != h[1]){
                    c++;
                }
            }
            if(c == 0){
                ans = 0;
            }else{
                ans = 1;
            }
        }
        cout<<h[ans]<<"\n";
        cin>>n;
    }
    return 0;
}




Measured memory_bytes: 3220
#include <bits/stdc++.h>
typedef long long ll;
typedef double db;
#define mk make_pair
#define pa pair<int,int>
using namespace std;

inline int rd() {
	int x=0,f=1;char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
	for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return x*f;
}
int A,B,C;
int ans;
//main=============================
int main() {
	A=rd(),B=rd(),C=rd();
	ans=max(A*10+B+C,B*10+A+C);
	ans=max(ans,C*10+A+B);
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
	long long N,a;
	cin >> N >> a;

	string s;
	//cin >> s;

	//int A[5]
	//sort(A, A + 5);

	if (true)
	{
		cout << N * a << endl;
	}
	else
	{
		cout << "false" << endl;
	}

}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
#define DE cout << "------" << endl
#define mems(a, b) memset(a, (b), sizeof a)
typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 200007;

int main(){
	int n;
	cin >> n;
	if(n < 1200) puts("ABC");
	else if(n < 2800) puts("ARC");
	else puts("AGC");
}


Measured memory_bytes: 256
numbers = gets.chomp
nowString = 0
numbersLength = numbers.length
nowDiffNumber = 0
numbersLength.times do |number|
  break if numbersLength - 3 < number
  tempString = numbers.slice(number,3)
  tempDiffNumber = (753 - tempString.to_i).abs
  if nowString == 0 || (nowDiffNumber.to_i > tempDiffNumber.to_i)
    nowString = tempString
    nowDiffNumber = (753 - nowString.to_i).abs
  end
end
puts nowDiffNumber

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
int main(){
  string a, b, c;
  cin >> a >> b >> c;
  if(a[a.size() - 1] == b[0] && b[b.size() - 1] == c[0]) printf("YES\n");
  else printf("NO\n");
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#define ll long long int
#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
using namespace std;

int mx8[] = {0,0,1,-1,-1,1,-1,1};
int my8[] = {-1,1,0,0,-1,-1,1,1};
int mx4[] = {1,-1,0,0};
int my4[] = {0,0,-1,1};
const int MOD = 1000000007;

int main() {
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    vector<char> S(n), T(m);
    rep(i, n) S[i] = s[i];
    rep(i, m) T[i] = t[i];
    sort(S.begin(), S.end());
    sort(T.rbegin(), T.rend());

    s = "", t = "";
    rep(i,n) s += S[i];
    rep(i,m) t += T[i];
    if(s < t) cout << "Yes" << endl;
    else cout << "No" << endl;
}





Measured memory_bytes: 3616
N,M=map(int,input().split())
ac = [0]*N
wa = [0]*N

pe=0

for i in range(M):
  num, result = map(str, input().split())
  num = int(num)-1
  
  if ac[num]==0 and result=='AC':
    ac[num] += 1
    pe += wa[num]
    
  elif ac[num]==0 and result=='WA':
    wa[num] +=1

print(sum(ac), pe)

Measured memory_bytes: 4596
s = gets.chomp
k = gets.chomp.to_i


# besides a, b
def alphabet(a, b)
  ("a".."z").each do |c|
    return c if a != c && b != c
  end
end

count = 0

s2 = s.dup

s.size.times do |i|
  next if i == 0
  if s[i] == s[i-1]
    count+=1
    if i+1 < s.size
      s[i] = alphabet(s[i-1], s[i+1])
    else
      s[i] = alphabet(s[i-1], s[0])
    end
  end
end

s2_count = 0

s2.size.times do |i|
  before = if i == 0
    s[-1]
  else
    s2[i-1]
  end
  after = if i+1 < s2.size
    s2[i+1]
  else
    s[0]
  end
  if before == s2[i]
    s2_count+=1
    s2[i] = alphabet(before, after)
  end
end

if s[0] == s[-1]
  if k >= 3 && s2[-1] == s[0]
    puts s2_count * (k-1) + count
  else
    l = k / 2
    m = k - l
    puts s2_count * l + count * m
  end

else
  puts count * k
end


Measured memory_bytes: 1788
from bisect import bisect_left
from collections import deque
N = int(input())
a = int(input())
ls = deque([a])
for i in range(N-1):
  c = int(input())
  ind = bisect_left(ls,c)
  if ind==0:
    ls.appendleft(c)
    continue
  ls[ind-1] = c
print(len(ls))

Measured memory_bytes: 7284