akhauriyash/Code-Regression huggingface dataset:
/**
 * All Pairs Shortest Paths (全点間最短パス)
 * 
 * O(|E||V| + |V|^2 log|V|)
 */


/**
 * Feasible Potential
 * 
 * O(|E||V|)
 */

#include <vector>
#include <algorithm>
using namespace std;

using Int = long long;
struct edge{
    int to;
    Int cost;
};

vector<Int> Potential(const vector<vector<edge>>& G){
    vector<Int> dist(G.size(),0);
    for(int i = 1;i < G.size();i++){
        for(int v = 0;v < G.size();v++){
            for(auto & e : G[v]){
                dist[e.to] = min(dist[e.to],dist[v] + e.cost);
            }
        }
    }
    for (int v = 0; v < G.size(); v++) {
      for (auto &e : G[v]) {
          if(dist[e.to] > dist[v] + e.cost){
              return vector<Int>();
          }
      }
    }
    return dist;
}


/**
 * Potential Dijkstra
 *
 * O(|E| + |V|log|V|)
 */

#include <functional>
#include <queue>
#include <set>
#include <vector>
using namespace std;

Int INF = 1LL << 40;
using Pii = pair<Int, int>;

vector<Int> Potential_Dijkstra(const vector<vector<edge>> &G, const vector<Int> &pot,int s) {
  vector<Int> dist(G.size(), INF);
  dist[s] = 0;
  priority_queue<Pii, vector<Pii>, greater<Pii>> que;
  que.emplace(dist[s], s);
  while (!que.empty()) {
    auto d = que.top().first;
    auto v = que.top().second;
    que.pop();
    if (dist[v] < d)
      continue;
    for (auto &e : G[v]) {
      Int co = e.cost + pot[v] - pot[e.to];
      if (dist[e.to] > d + co) {
        dist[e.to] = d + co;
        que.emplace(dist[e.to], e.to);
      }
    }
  }
  return dist;
}

vector<vector<Int>> AllPairsShortestPaths(const vector<vector<edge>> &G){
    vector<vector<Int>> res(G.size());
    auto pot = Potential(G);
    if(pot.empty()) return vector<vector<Int>>();
    for(int s = 0;s < G.size();s++){
        res[s] = Potential_Dijkstra(G,pot,s);
        for(int t = 0;t < G.size();t++){
          if(res[s][t] == INF) continue;
          res[s][t] += pot[t] - pot[s];
        }
    }
    return res;
}

#include <iostream>

int main(){
  int v,e;
  cin >> v >> e;
  vector<vector<edge>> G(v);

  for(int i = 0;i < e;i++){
    int s,t;
    Int d;
    cin >> s >> t >> d;
    G[s].push_back({t,d});
  }

  auto res = AllPairsShortestPaths(G);

  if(res.empty()){
    cout << "NEGATIVE CYCLE" << endl;
    return 0;
  }

  for(auto & d : res){
    for(int i = 0;i < G.size();i++){
      if(d[i] == INF) cout << "INF";
      else cout << d[i];
      cout << " \n"[i + 1 == G.size()];
    }
  }
}


Measured memory_bytes: 3292
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int main()
{
	long long int  n,s,i,j,x;
	scanf("%lld",&n);
	s=n;
	x=1;
	for(i=2;i<=sqrt(n);i++)
	{
		if(n%i==0)
		{
			j=n/i;
			if(s>=(i+j))
			{
				x=i;
				s=i+j;
			}
		}
	}
	if(x==1)
	s-=1;
	else 
	s-=2;
	printf("%lld",s);
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const long long INF = (1LL << 60);
long long cap[102][102];

long long search(int n, const vector<int>& level, vector<int>& itr, int cur, int t, long long f){
	if(cur == t) return f;
	for(int i=itr[cur];i<n;i++){
		if(cap[cur][i] > 0 && level[cur] < level[i]){
			long long d = search(n, level, itr, i, t, min(cap[cur][i], f));
			if(d > 0){
				itr[cur] = i;
				cap[cur][i] -= d;
				cap[i][cur] += d;
				return d;
			}
		}
	}
	itr[cur] = n;
	return 0;
}

long long maximumFlow(int n, int s, int t){
	long long res = 0;
	while(true){
		queue<int> qu; qu.push(s);
		vector<int> level(n, -1); level[s] = 0;
		vector<int> itr(n, 0);
		while(!qu.empty()){
			int cur = qu.front(); qu.pop();
			for(int i=0;i<n;i++){
				if(cap[cur][i] > 0 && level[i] == -1){
					level[i] = level[cur]+1;
					qu.push(i);
				}
			}
		}
		if(level[t] == -1) break;
		for(long long f;(f=search(n, level, itr, s, t, INF)) > 0;res+=f);
	}
	return res;
}

int main(){
	int N;
	while(cin >> N){
		for(int i=0;i<=N+1;i++){
			for(int j=0;j<=N+1;j++) cap[i][j] = 0;
		}
		long long sum = 0;
		for(int i=1;i<=N;i++){
			int a; cin >> a;
			sum += max(0, a);
			if(a < 0){
				cap[0][i] = -a;
			} else {
				cap[i][N+1] = a;
			}
		}
		for(int i=1;i<=N;i++){
			for(int j=2*i;j<=N;j+=i) cap[i][j] = INF;
		}
		cout << sum - maximumFlow(N+2, 0, N+1) << endl;
	}
}


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

// #include<cstdio>

int main(){
  int a[100][100],b[100][100];
  long long c[100][100]={};
  int n, m, l;

  cin >> n >> m >> l;

  for (int i=0; i<n; i++){
    for (int j=0; j<m; j++){
      cin >> a[i][j];
    }
  }
  for (int i=0; i<m; i++){
    for (int j=0; j<l; j++){
      cin >> b[i][j];
    }
  }
  for (int i=0; i<n; i++){
    for (int j=0; j<l; j++){
      for (int k=0; k<m; k++){
	c[i][j]+=a[i][k]*b[k][j];
      }
      cout << c[i][j];
      if (j==l-1) continue;
      cout << ' ';
    }
    cout << "\n";
  }
  

  return 0;
}

Measured memory_bytes: 3192
/*
ID: iCoder0020
PROG: LCS
LANG: C++                  
*/

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define INF 1e9

template <typename T> void max_self(T &a, T b)
{
	a = max(a, b);
}

int32_t main()
{
	string S,T;
	cin>>S>>T;
	int N = S.length(), M = T.length();
	vector<vector<pair<int,pair<int,int>>>> 
	dp(N+1, vector<pair<int,pair<int,int>>>(M+1, {-INF, {0,0}}));
	dp[0][0] = {0, {0,0}};
	for(int i = 0; i<N; i++)
	{
		for(int j = 0; j<M; j++)
		{
			if(S[i] == T[j])
				max_self(dp[i+1][j+1], {dp[i][j].first+1, {i,j}});
			max_self(dp[i+1][j], {dp[i][j].first, {i,j}});
			max_self(dp[i][j+1], {dp[i][j].first, {i,j}});
		}
	}
	auto answer = dp[0][0];
	for(int i = 0; i<=N; i++)
		for(int j = 0; j<=M; j++)
			max_self(answer, {dp[i][j].first, {i,j}});
	string str = "";
	pair<int,int> cur = answer.second;
	while(cur.first != 0 && cur.second != 0)
	{
		int i = cur.first;
		int j = cur.second;
		pair<int,int> prev = dp[i][j].second;
		if(prev == make_pair(i-1, j-1))
			str = S[i-1] + str;
		cur = prev;
	}
	cout<<str<<endl;
	return 0;	
}

Measured memory_bytes: 211456
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define pb push_back
#define fr(i,n) for(int i=0;i<n;i++)
#define Fr(i,n) for(int i=0;i++<n;)
#define ifr(i,n) for(int i=n-1;i>=0;i--)
#define iFr(i,n) for(int i=n;i>0;i--)

int main(){
  ll k,p,q;
  cin>>k;
  cout<<50<<endl;
  p=(k-1)/50+1;
  q=50*p-k;
  fr(i,q) cout<<p+q-2<<" ";
  fr(i,50-q) cout<<p+q+49<<" ";
  cout<<endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define Sort(Array) sort(Array.begin(), Array.end())
#define Reverse(a) reverse(a.begin(), a.end())
#define out(ans) cout << ans << endl;
const int MOD = 1000000007;
const int INF = 2147483647;
const ld PI = 3.14159265358979323846;

//------------↓------------- M -------------- E ---------------- M --------------- O ---------------↓--------------//
// コンパイル 
// g++ -std=c++1z
//
// -------型変換--------
// int を string に変換
// string s = to_string(n);
// string を int に変換
// int n = stoi(s);
//
// -------二分探索---------
// k以上の値が最初に現れる時のイテレータ
// lower_bound(data.begin(), data.end(), k)
// kより大きい値が最初の現れる時のイテレータ O(logN)
// upper_bound(data.begin(), data.end(), k)
// kがdataに存在するかをtrue or falseで返す O(logN)
// binary_search(data.begin(), data.end(), k)
// 
//
//
//
//
//
// 
//------------↑------------- M -------------- E ---------------- M --------------- O ---------------↑--------------//






int main(void) {
    
    ld a, b, h, m; cin >> a >> b >> h >> m;
    ld alpha = ( (h / 12.0) + (m / 12 / 60) ) * 2 * PI;
    ld beta = m / 60 * 2 * PI;
    ld ans = pow(pow(a*cos(alpha) - b*cos(beta), 2) + pow(a*sin(alpha) - b*sin(beta), 2), 0.5);
    printf("%.12Lf\n", ans);


    
    return 0;
}






Measured memory_bytes: 4168
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < n; i++) 
using namespace std;

int main() {
  
  int a,b,c;
  cin >> a >> b >> c;
  
  if (a == b) cout << c << endl;
  else if (a == c) cout << b << endl;
  else cout << a << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	int a, b, c, k;
	cin >> a >> b >> c >> k;
	int z=0, y=0, x=0;
	if(k-a<0){
		x=k;
		k=0;
	}
	else{
		x=a;
		k-=a;	
	}
	if(k-b<0){
		y=k;
		k=0;
	}
	else{
		y=b;
		k-=b;
	}
	if(k-c<0){
		z=k;
		k=0;
	}
	else{
		z=c;
	}
	cout << x*1+y*0+z*(-1);
}


Measured memory_bytes: 3608
n, m = [int(i) for i in input().split()]
wrong_count = [0 for i in range(n)]
correct_count = [0 for i in range(n)]
for i in range(m):
    p, s = input().split()
    if s == 'AC':
        correct_count[int(p)-1] = 1
    elif correct_count[int(p)-1] == 0:
        wrong_count[int(p)-1] += 1
penalty_count = sum([wrong_count[i] for i in range(n) if correct_count[i] == 1])
print(sum(correct_count), penalty_count)

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

typedef long long int ll;

int main()
{
    ll n, m, ans = 0;
    cin >> n >> m;
    ll s = (n - m) * 100 + m * 1900, k = pow(2, m);
    ans = s * k;
    cout << ans;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
    int n,a,b,p,q1=0,q2=0,q3=0;
    cin >> n;
    cin >> a >> b;
    for (int i=0;i<n;i++) {
        cin >> p;
        if (p <= a) {q1++;}
        else if (p > a && p <=b) {q2++;}
        else {q3++;}
    }
    cout << min({q1,q2,q3}) << endl;
    return 0;
}

Measured memory_bytes: 256
import math
import copy
import sys
import fractions
import numpy as np
from functools import reduce

# ===FUNCTION===

def getInputNum():
    inputNum = int(input())
    return inputNum

def getInputListInt():
    outputoData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData

def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList

def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList

# ===CODE===

n, A, B, C = map(int, input().split())
data = getSomeInputInt(n)

def dfs(cnt, a, b, c):
    if cnt == n:
        return abs(a-A)+abs(b-B)+abs(c-C)-30 if min(a,b,c) > 0 else sys.maxsize

    nothing = dfs(cnt+1, a, b, c)
    ap = dfs(cnt+1, a+data[cnt], b, c) + 10
    bp = dfs(cnt+1, a, b+data[cnt], c) + 10
    cp = dfs(cnt+1, a, b, c + data[cnt]) + 10

    return min(nothing, ap, bp, cp)

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

Measured memory_bytes: 13740
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Scan()
	ss := strings.Fields(sc.Text())
	n, _ := strconv.Atoi(ss[0])
	q, _ := strconv.Atoi(ss[1])

	que := newQueue()
	for i := 0; i < n; i++ {
		sc.Scan()
		ss := strings.Fields(sc.Text())
		cputime, _ := strconv.Atoi(ss[1])
		que.enqueue(&process{name: ss[0], time: cputime})
	}

	timer, c := 0, 0
	for que.head != nil {
		u := que.dequeue()
		c = min(q, u.time)
		u.time -= c
		timer += c
		if u.time > 0 {
			que.enqueue(u)
			continue
		}
		fmt.Println(u.name, timer)
	}
}

type queue struct {
	head, tail *node
	len        int
}

type node struct {
	proc *process
	next *node
}

type process struct {
	name string
	time int
}

func (p *process) String() string {
	return fmt.Sprint(p.name + " " + strconv.Itoa(p.time))
}

func newQueue() *queue {
	return &queue{head: nil, tail: nil, len: 0}
}

func (q *queue) dequeue() *process {
	if q.len == 0 {
		return nil
	}
	headPtr := q.head
	q.head = headPtr.next
	if q.len == 1 {
		q.head, q.tail = nil, nil
	}
	q.len--
	return headPtr.proc
}

func (q *queue) enqueue(proc *process) {
	n := &node{proc: proc, next: nil}
	if q.len == 0 {
		q.head = n
		q.tail = n
	} else {
		q.tail.next = n
		q.tail = n
	}
	q.len++
}

func (q *queue) peek() *process {
	if q.len == 0 {
		return nil
	}
	return q.head.proc
}

func (p *process) consume(time *int) *process {
	if p.time < *time {
		p.time = 0
		*time -= p.time
		return p
	}
	p.time = p.time - *time
	*time = 0
	return p
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}



Measured memory_bytes: 7496
N, Y = map(int, input().split())
for a in range(N + 1):
  for b in range(N - a + 1):
    c = N - a - b
    if (a * 10000) + (b * 5000) + (c * 1000) == Y:
      print(a, b, c)
      exit()
print(-1, -1, -1)

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

int main() {
  int N, K;
  cin >> N >> K;
  vector<int>H(N);
  for(int i = 0; i < N; i++) {
    cin >> H[i];
  }
  sort(H.begin(), H.end(), std::greater<int>());

  long long res = 0;
  for (int i = 0; i < N; i++) {
    if (K > 0) {
      K--;
      continue;
    }
    res += H[i];
  }

  cout << res;
}


Measured memory_bytes: 1024
#include <iostream>//
#include <stack>
using namespace std;

stack<char> s;

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        char t;
        cin >> t;
        if (s.empty())
            s.push(t);
        else if (t == s.top())
            ;
        else
            s.push(t);
    }

    cout << s.size();

    return 0;
}
// Created by Kevin Weng on 2019/10/28.
//



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

int main() {
	
	int a, b;
	string s;
	cin >> a >> b >> s;
	string ans = "Yes";
	if(s[a] != '-') ans = "No";
	for(int i = 0; i < a; i++){
		if(s[i] == '-') ans = "No";
	}
	for(int i = a + 1; i <= a + b; i++){
		if(s[i] == '-') ans = "No";
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define pll  pair <long long,long long>
#define ss second
#define ff first
#define inf 9223372036854775807
#define maa 1000000007
#define ld long double
#define fast  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define bug(x) cout << #x <<": " << x << '\n';
const ll N=8001 ;
int main()
{
   fast ;
   string s,t ; cin>>s>>t ;

   if(s==t.substr(0,s.length())) cout<<"Yes" ;
   else cout<<"No" ;

}




Measured memory_bytes: 3652
### constant

MAX_INT = 1 << 30

### main

loop do
  n, m = gets.strip.split(' ').map{|s| s.to_i}
  break if (n | m) == 0

  ystones = n.times.map{[]}

  for y in (0...n)
    ks = gets.strip.split(' ').map{|s| s.to_i}
    k = ks.shift
    for i in (0...k)
      ystones[y] << [ks[2 * i], ks[2 * i + 1]]
    end
  end
  #p stones
  #p max_x

  dists = (n + 1).times.map{(m + 1).times.map{10.times.map{MAX_INT}}}

  dists[0][m] = 10.times.map{0}

  if m > 0
    dists[1][m - 1] = 10.times.map{0}
  end

  for y in (0...(n - 1))
    ysts0 = ystones[y]
    ysts1 = ystones[y + 1]
    ysts2 = ystones[y + 2]

    for m0 in (0..m)
      for i in (0...ysts0.length)
        dst0 = dists[y][m0][i]
        next if dst0 >= MAX_INT

        x0, d0 = ysts0[i]

        for j in (0...ysts1.length)
          x1, d1 = ysts1[j]
          dst1 = dst0 + (d0 + d1) * (x1 - x0).abs

          if (dists[y + 1][m0][j] > dst1)
            dists[y + 1][m0][j] = dst1;
          end
        end

        next if m0 == 0 || ysts2.nil?

        m1 = m0 - 1

        for j in (0...ysts2.length)
          x2, d2 = ysts2[j]
          dst2 = dst0 + (d0 + d2) * (x2 - x0).abs

          if (dists[y + 2][m1][j] > dst2)
            dists[y + 2][m1][j] = dst2;
          end
        end
      end
    end
  end

  min_gdist = MAX_INT

  for m0 in (0..m)
    gdist = dists[n - 1][m0].compact.min
    min_gdist = gdist if min_gdist > gdist
  end

  for m0 in (1..m)
    gdist = dists[n - 2][m0].compact.min
    min_gdist = gdist if min_gdist > gdist
  end

  puts min_gdist
end

Measured memory_bytes: 9132
#define s(a,b) t=a,a=b,b=t
f(int*a){*a=(*a&7)<<4|*a>>4;}char p[9];m,a,b,c,t,r;main(n){while(scanf("%d",&n),n){r=1,a=97,b=82,c=67;while(n--){scanf("%s",p);m=*p-76;t=m%6==0?(s(b,c),f(m?&c:&b)):1<m&&m<8?(s(a,b),f(m^7?&b:&a)):(s(a,c),f(m>0?&c:&a));r+=a&7;}printf("%d\n",r);}}

Measured memory_bytes: 0
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define ref(i,x,y)for(int i=x;i<=y;++i)
const int N=100001;
int n,m,cnt,res,head[N],du[N],q[N],t[N];
struct edge{int to,nxt;}e[N*2];
vector<int>s[N];bool vis[N];
bool cmp(int a,int b){return a>b;}
void add(int x,int y){e[++cnt]=(edge){y,head[x]};head[x]=cnt;}
int main(){
	scanf("%d",&n);
	ref(i,2,n){
		int x,y;scanf("%d%d",&x,&y);
		add(x,y),add(y,x);du[x]++,du[y]++;
	}
	res=1;
	ref(i,1,n)if(du[i]==1)q[++m]=i;
	ref(i,1,n){
		int x=q[i];vis[x]=1;
		if(s[x].empty())s[x].push_back(1);else{
			int p=0,r=1,sz=s[x].size()-1;
			if(t[x]>1){
				sort(s[x].begin(),s[x].end(),cmp);
				ref(i,1,sz)if(s[x][i]==s[x][i-1]){p=i;break;}
				if(p){
					r=s[x][p]+1;
					while(sz>=p-1)s[x].pop_back(),sz--;
				}
			}
			while(sz>=0&&s[x][sz]==r)s[x].pop_back(),r++,sz--;
			s[x].push_back(r);if(r>res)res=r;
		}
		int sz=s[x].size()-1;
		for(int j=head[x];j;j=e[j].nxt){
			int y=e[j].to;
			if(!vis[y]){
				ref(I,0,sz)s[y].push_back(s[x][I]);
				du[y]--;t[y]++;if(du[y]==1)q[++m]=y;
			}
		}
	}
	printf("%d\n",res-1);
}

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

using namespace std;

int main(void){
    int n;
    cin>>n;
    vector<int> p(n);
    for(int i=0;i<n;i++){
        cin>>p[i];
    }
    int count=0;
    for(int i=1;i<n-1;i++){
        if(p[i-1]<p[i]&&p[i]<p[i+1]) count++;
        if(p[i+1]<p[i]&&p[i]<p[i-1]) count++;
    }
    cout<<count<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int a,b,c,x,ans;
int main()
{
    cin>>a>>b>>c>>x;
    for(int i=0;i<=a;i++)
    {
        for(int j=0;j<=b;j++)
        {
            for(int k=0;k<=c;k++)
            {
                if(500*i+100*j+50*k==x) ans++;
            }
        }
    }
    cout<<ans; 
    return 0; 
} 

Measured memory_bytes: 256
import java.util.*;
import static java.lang.Integer.*;
import static java.lang.Long.*;
import static java.lang.Math.*;
import static java.lang.System.*;

public class Main {
	public static void main(String[] args) {
		int i,j;
		Scanner sc = new Scanner(in);
		long n = parseLong(sc.next());
		long a = parseLong(sc.next());
		long b = parseLong(sc.next());
		sc.close();
		out.println((b-a)%2==0?(b-a)/2:Math.min((a+b-1)/2,(2*n-a-b+1)/2));
	}
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define fi first
#define se second
#define mp make_pair
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
typedef long long llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl;
#define MOD llong(1e9+7)
#define MAX int(2 * 1e5 +5)
#define debug(x)  cout << #x << " = " << (x) << endl;
#define pi acos(-1.0)
#define int llong
#define INF llong(1e18 + 3)
template<class T> bool chmax(T &a,  T b) {if(a<b){a=b; return 1;} return 0;}
template<class T> bool chmin(T &a,  T b) {if(a>b){a=b; return 1;} return 0;}
bool Add(int &a,int b){a = (a + b) % MOD;}
void myprint(int* A,int A_num){
   REP(i,A_num) cout << A[i] << " ";
   cout << endl;
}

const int n_max = 3030303;

llong fac[n_max];  /// fac[n] = n!
llong finv[n_max]; /// (fac[n] * finv[n]) % MOD = 1
llong inv[n_max];  /// (n * inv[n]) % MOD = 1
 
void init() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  FOR (i, 2, n_max) {
    fac[i] = fac[i-1]*i % MOD;
    inv[i] = MOD - inv[MOD%i]*(MOD/i) % MOD;
    finv[i] = finv[i-1]*inv[i] % MOD;
  }
}
 
llong nCk (int n, int k) {
  if (n < k || k < 0 || n < 0) return 0;
  return fac[n]*finv[k]%MOD*finv[n-k]%MOD;
}


signed main(){
    init();
    int x,y;
    cin >> x >> y;
    if(x < y){
        swap(x,y);
    }
    if( (x + y) %3 != 0){
        cout << 0 << endl;
        return 0;
    }
    int sousa = (x + y) / 3;
    int a,b;
    if( (sousa - ( x - y)) %2 != 0   ){
        cout << 0 << endl;
        return 0;
    } 
    b = ( sousa - (x - y) ) / 2;
    a = sousa - b;
    /*
    debug(a);
    debug(b);
    */

    cout << nCk(a + b , a) << endl;
}

Measured memory_bytes: 71296
#include <algorithm>
#include <bitset>
#include <cctype>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;

#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define each(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define exist(s,e) ((s).find(e)!=(s).end())
#define range(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  range(i,0,n)
#define clr(a,b) memset((a), (b) ,sizeof(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const double eps = 1e-10;
const double pi  = acos(-1.0);
const ll INF =1LL << 62;
const int inf =1 << 29;

int main(void){
    for(int n, res; cin >> n, n; cout << res << endl){
        res = 0;

        rep(i, n / 4){
            int a; cin >> a;
            res += a;
        }
    }

	return 0;
}

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

const int maxn = 105;

string s[maxn];

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int n;
	cin >> n >> s[0];
	for (int i = 0; i < n; ++i)
		cin >> s[i];
	sort(s, s + n);
	for (int i = 0; i < n; ++i)
		cout << s[i];
	cout << '\n';
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip>//setprecision
#include<math.h>
#include <functional>
#include<climits>
using namespace std;
#define rep(i, n)        for(int i=0; i<(int)(n); ++i)
int main(){
  string a;cin>>a;
  vector<bool>b(26,true);
  rep(i,a.size()){
    b[a[i]-'a']=false;
  }
  rep(i,26){
    if(b[i]){
      cout<<(char)(i+'a');
      return 0;
    }
  }
  cout<<"None";
  }


Measured memory_bytes: 512
import java.util.*;
public class Main {
	public static void main(String[] args){
      Scanner sc = new Scanner(System.in);

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

      if((a*b)%2==0) {
        System.out.println("Even");
      }else {
        System.out.println("Odd");
      }
	}
}

Measured memory_bytes: 21844
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.util.Comparator;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author anand.oza
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CStreamline solver = new CStreamline();
        solver.solve(1, in, out);
        out.close();
    }

    static class CStreamline {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int m = in.nextInt();
            Long[] x = new Long[m];
            for (int i = 0; i < m; i++) {
                x[i] = in.nextLong();
            }
            Arrays.sort(x);

            Long[] diffs = new Long[m - 1];
            for (int i = 0; i < m - 1; i++) {
                diffs[i] = x[i + 1] - x[i];
            }
            Arrays.sort(diffs, Comparator.reverseOrder());
            int remove = n - 1;
            for (int i = 0; i < Math.min(remove, m - 1); i++) {
                diffs[i] = 0L;
            }
            long answer = 0;
            for (long d : diffs) {
                answer += d;
            }

            out.println(answer);
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

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

    }
}



Measured memory_bytes: 42484
import numpy as np
N =int(input())

A = np.zeros((N,2))


for i in range(N):
    A[i,0],A[i,1] = map(int,input().split())
    



B = A[A[:,1].argsort(),:]    


sa = B[0,0]
i = 0
while i < N-1 and sa <= B[i,1]:
    i +=1
    sa += B[i,0]


    
if i == N -1 and sa <=B[i,1]:
  
    print('Yes')
else:
    print('No')
 

Measured memory_bytes: 22684
# coding:utf-8                                                                                         

import math
                                                                                                       
def main(n,a):                                                                                         
    n = int(n)                                                                                         
    a = a.split()
    cnt = 0
    minus = 0                                                                                          
    b = []                                                                                             
    for i in a:                                                                                        
        a[cnt] = int(i)                                                                                
        b.append(abs(int(i)))                                                                          
        if a[cnt] < 0:
            minus += 1                                                                                 
        cnt += 1 
    if minus % 2 != 0: 
        mini = min(b)                                                                                  
    else:       
        mini = 0 
    total = 0   
    for i in b: 
        total += abs(i)
    total -= 2 * abs(mini)                                                                             
    print total     
    return total
                                                                                                       
if __name__ == "__main__":                                                                             
    n = raw_input()
    a = raw_input()                                                                                    
    main(n,a)

Measured memory_bytes: 10368
s=input()
n=len(s)
f=0
for i in range(1<<n-1):
    a=s[0]
    for j in range(n-1):
        if i&(1<<j):
            a+='+'+s[j+1]
        else:
            a+=s[j+1]
    f+=eval(a)
print(f)

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <math.h>
#include <utility>
#include <tuple>
#include <map>
#include <stack>
#include <queue>
#include <ctype.h>
#include <iomanip>
#include <bitset>
#include <set>
#include <ios>
#include <cstdlib>
using namespace std;
using ll = long long;
int main() {
    int N; cin >> N;
    vector<int> P(N);
    for (int i=0;i<N;i++) cin >> P[i];
    vector<int> Q = P;
    sort(Q.begin(),Q.end());
    int res = 0;
    for (int i=0;i<N;i++){
        if (P[i]!=Q[i])res++;
    }
    if (res==0||res==2) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	num, _ := strconv.Atoi(scanString())
	return num
}

func scanString() string {
	sc.Scan()
	return sc.Text()
}

func init() {
	sc.Split(bufio.ScanWords)
}

func main() {
	x, n := scanInt(), scanInt()
	hash := make(map[int]bool, n)
	for i := 0; i < n; i++ {
		hash[scanInt()] = true
	}

	var ans int
	for i := 0; i <= 100; i++ {
		if !hash[x-i] {
			ans = x - i
			break
		} else if !hash[x+i] {
			ans = x + i
			break
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 1776
import sys
input = sys.stdin.readline
n,T = map(int,input().split())
t = list(map(int,input().split()))
h = 0
for i in range(1,n):
    if t[i] - t[i-1] < T:
        h += T - (t[i] - t[i-1])
print(T*n - h)


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

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e18;
const int MAX_N = 100000;

ll arr[MAX_N+1];
int N, M, V, P;
vector<ll> vt;
ll sum[MAX_N+1];
int ans = 0;

int main(){
	scanf("%d%d%d%d", &N, &M, &V, &P);
	for(int i=1; i<=N; i++){
		scanf("%lld", &arr[i]);
		vt.pb(arr[i]);
	}
	sort(vt.begin(), vt.end());
	vt.pb(INFLL);
	sum[0] = vt[0];
	for(int i=1; i<vt.size(); i++){
		sum[i] = vt[i] + sum[i-1];
	}
	for(int i=0; i<N; i++){
		ll n = vt[i] + (ll)M;
		ll S=(ll)M;
		int idx = N-P;
		if(vt[N-P]>n)	continue;
		if(idx>i)	S += (ll)(idx-i) * n - sum[idx] + sum[i];
		S += (ll)(P-1) * (ll)M;
		S += (ll)min(i, N-P) * (ll)M;
		if(S>=(ll)M*(ll)V){
			ans++;
		}
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 2676
import java.util.Scanner

fun main() {
	val scn = Scanner(System.`in`)
	val arr = scn.next().map{ it.toString().toInt() }
	val n = arr.size
	val map = mutableMapOf(Pair(0, 1L))
	var bef = ModInt.ZERO
	var pow = ModInt.ONE
	repeat(n) {
		pow *= 10
		val v = pow*arr[n-1-it]+bef
		map[v.toInt()] = map.getOrDefault(v.toInt(), 0L) + 1
		bef = v
	}
	var ans = 0L
	map.forEach{i,v ->
		ans += v*(v-1)/2
	}
	println(ans)

}

class ModInt {
	var v: Long
		private set
	constructor(v: Int){
		this.v = when {
			v>=0 -> v.toLong() % MOD
			v==Int.MIN_VALUE -> 852516373
			else -> MOD.toLong() - (-v%MOD)
		}
	}
	constructor(v: Long){
		this.v = when {
			v>=0 -> v % MOD
			v==Long.MIN_VALUE -> 708828003
			else -> MOD - (-v%MOD)
		}
	}

	override fun toString() = v.toString()
	fun toInt() = v.toInt()
	fun toLong() = v
	override fun equals(other: Any?): Boolean {
		return if (other is ModInt) v == other.v else false
	}
	override fun hashCode() = 31*17 + v.hashCode()

	operator fun unaryPlus() = this
	operator fun unaryMinus() = ModInt(MOD-this.v)

	private operator fun plus(o: Long) = ModInt(this.v + o)
	operator fun plus(o: ModInt) = this.plus(o.v)
	operator fun plus(o: Int) = this.plus(o.toLong())
	private operator fun minus(o: Long) = this.plus(-o)
	operator fun minus(o: ModInt) = this.minus(o.v)
	operator fun minus(o: Int) = this.minus(o.toLong())
	private operator fun times(o: Long) = ModInt(this.v*o)
	operator fun times(o: ModInt) = this.times(o.v)
	operator fun times(o: Int) = this.times(o.toLong())
	private operator fun div(o: Long) = this.times(pow(o, MOD-2))
	operator fun div(o: ModInt) = this.div(o.v)
	operator fun div(o: Int) = this.div(o.toLong())

	operator fun inc() = this.plus(1)
	operator fun dec() = this.minus(1)

	companion object{
		const val MOD = 2019
		val ZERO = ModInt(0)
		val ONE = ModInt(1)

		private fun pow(b:Long, e: Int): ModInt{
			if (b==1L) return ModInt(1)
			var ans = 1L
			var b = b; var e = e
			while (e!=0){
				if (e%2==1) ans = (ans*b)%MOD
				b = (b*b)%MOD
				e /= 2
			}
			return ModInt(ans)
		}
		fun pow(b: Int, e: Int): ModInt = pow(b.toLong(), e)
		fun pow(b: ModInt, e: Int): ModInt = pow(b.v, e)
	}
}

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

#define NMIN 1
#define NMAX 100
#define AMIN 1
#define AMAX 100
int main(){
  int N,A[NMAX],i,j,subA,cnt=0,minj;
  scanf("%d",&N);
  if(N<NMIN||N>NMAX) exit(1);
  for(i=0;i<N;i++){
    scanf("%d",&A[i]);
  }
  
  for(i=0;i<N;i++){
 minj = i;
    for(j=i; j<N; j++)
      if(A[j] < A[minj]) {
	minj = j;
      }
    if(minj!=i){
    subA = A[i];
    A[i] = A[minj];
    A[minj] = subA;
    cnt++;
      }
  }
   for(i=0;i<N;i++){
       if(i==N-1)
     printf("%d\n",A[i]);
     else
     printf("%d ",A[i]);
   }
  printf("%d\n",cnt);
  return 0;
}



Measured memory_bytes: 2128
import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int[] a=new int[100];
		int[] flag= {0,0,0,0,0,0,0,0,0};
		int cnt=0;
		for(int i=0;i<n;i++) {
			a[i]=sc.nextInt();
			if(3200<=a[i]) {
				flag[8]++;
				continue;
			}
			else if(2800<=a[i]) {
				flag[7]=1;
				continue;
			}
			else if(2400<=a[i]) {
				flag[6]=1;
				continue;
			}
			else if(2000<=a[i]) {
				flag[5]=1;
				continue;
			}
			else if(1600<=a[i]) {
				flag[4]=1;
				continue;
			}
			else if(1200<=a[i]) {
				flag[3]=1;
				continue;
			}
			else if(800<=a[i]) {
				flag[2]=1;
				continue;
			}
			else if(400<=a[i]) {
				flag[1]=1;
				continue;
				
			}
			else if(1<=a[i]) {
				flag[0]=1;
				continue;
			}
		}
		for(int i=0;i<8;i++) {
			if(flag[i]==1)	cnt++;
		}
		/*for(int i=0 ;i < 8;i++){
		    System.out.println("frag"+i + flag[i]);
		}*/
		if(flag[8] == 0)	System.out.println(cnt+" "+cnt);	
		else if(cnt==0) {
			if(flag[8]+cnt <=8)	System.out.println(1 +" "+(cnt+flag[8]));
			else		System.out.println(1 + " " + (cnt+flag[8]));
		}
		else {	
			if(flag[8]+cnt <=8)	System.out.println(cnt +" "+(cnt+flag[8]));
			else		System.out.println(cnt + " " + (cnt+flag[8]));
		}
		
		
	}

}

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

using namespace std;
int n, m, k, l, dp[3002][3002], tab[150], tab2[105];
string slowo1, slowo2;
char a[3002], b[3002];
vector<char> wektor;
int main()
{
    ios_base::sync_with_stdio(false);
        cin>>slowo1>>slowo2;
        n=slowo1.size();
        m=slowo2.size();
        for(int i=1; i<=n; i++){
            a[i]=slowo1[i-1];
            dp[i][0]=0;
            tab[int(slowo1[i-1]-'a')]++;
        }
        for(int i=1; i<=m; i++){
            b[i]=slowo2[i-1];
            dp[0][i]=0;
            tab2[int(slowo2[i-1]-'a')]++;
        }


        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                if(a[i]==b[j]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }



        while((n>0)||(m>0)){
            if((dp[n][m]==dp[n-1][m])&&(dp[n-1][m]>0)){

            n--;
            }else  if((dp[n][m]==dp[n][m-1])&&(dp[n][m-1]>0)){

            m--;
            }else if((dp[n][m]-1==dp[n-1][m-1])&&(dp[n-1][m-1]>0)){
                wektor.push_back(a[n]);
                n--;
                m--;
            }else{
            break;
            }
        }
        //cout<<a[m]<<" "<<b[m]<<'\n';

        if(wektor.size()==0){
          for(int i=0; i<26; i++){
            //cout<<tab[i]<<" "<<tab2[i]<<'\n';
            if((tab[i]>0)&&(tab2[i]>0)){
              cout<<char(i+'a');
              break;
            }
          }
        //else{
          //cout<<" ";
        //}
        }else{
          cout<<b[m];
          for(int i=wektor.size()-1; i>=0; i--){
            cout<<wektor[i];
        }
      }
    return 0;
}


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

int N;
string S;
int ans=1;

int main() {
  cin >> N >> S;
  char pre = S[0];
  for(int i=1; i<N; i++) {
    if(pre != S[i]) {
      ans++;
      pre = S[i];
    }
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 512
#include <bits/stdc++.h>
#define REP(i, n) for(int i=0; i<(int)(n); ++i)
#define FOR(i, s, n) for(int i=(int)(s); i<(int)(n); ++i)
#define ALL(n) (n).begin(), (n).end()
#define pb push_back

using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> mat;

const ll MAX_V = 100000;
const ll INF = 1e9;
const ll MOD = 998244353;

int main(){
    int N, K; cin >> N >> K;
    double ans = 0.0;
    FOR(i, 1, N+1){
        if (i >= K){
            ans += (1.0/N);
        }else{
            int m = ceil(log(double(K)/double(i)) / log(2.0));
            ans += (1.0/N) * pow(0.5, m);
        }
    }
    cout << fixed;
    cout << setprecision(12) << ans << endl;
}

Measured memory_bytes: 512
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << #x << " = " << x << endl;


#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 100010


int main(){
  int n;
  int x[SIZE];

  scanf("%d",&n);

  for(int i=0;i<n;i++){
    scanf("%d",x+i);
  }


  ll ans = 1;
  int t = 1,s = 0;
  
  vector<int> vec;
  
  for(int i=0;i<n;i++){
    if(x[i] >= t){
      x[i] = t;
    }else{
      t = x[i];
    }
        
    if(x[i-1]+1 != x[i]){
      s = 0;
    }
    s ++;

    if(s%2 == 0){
      vec.push_back(i+1);
      t += 1;
    }else{
      t += 2;
    }
  }
  
  for(int i=0;i<n;i++){
    if(i < vec.size())
      ans = (ans*(vec[i]-i))%mod;
    else
      ans = (ans * (n - i))%mod;
  }

  printf("%lld\n",ans);
  
  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <utility>
#include <stdint.h>
#include <string>

using namespace std;

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

  int count = 0;
  
  for (int n=0; n<N-2; ++n) {
    if (S[n]=='A' && S[n+1] =='B' && S[n+2]=='C')
      ++count;
  }

  cout << count << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(){
  int n,a,b,i,j,k,ma=0,ret=0;
  int x[26]={};
  string s;
  cin >> n;
  cin >> s;
  for(i=0;i<n;i++){
    ma=0;
    for(j=0;j<26;j++)x[j]=0;
    for(j=0;j<i;j++){
      for(k=i;k<n;k++){
        if(s[j]==s[k] && x[s[j]-'a']==0){
          ma++;
          x[s[j]-'a']=1;
          break;
        }
      }
    }
    //cout << ma << endl;
    ret=max(ret,ma);
  }
  cout << ret << endl;
  return 0;
}


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

using namespace std;

#define pb push_back
#define fo(i, n) for(int i = 1; i <= n; ++i)

typedef long long ll;
typedef long double ld;

const int N = 500200;
const int mod = 1e9 + 7;

int a[N];
ll s[N], x[N], n, ans;
ll pre[N];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    fo(i, n) cin >> a[i], x[i] = x[i-1] ^ a[i], s[i] = s[i-1] + a[i];
    int last = 0;
    for(int i = 1; i <= n; ++i) {
        pre[i] = last;
        if(a[i] != 0) last = i;
    }
    fo(i, n) {
        int old = i, l = i - 1;
        for(l = i - 1; l >= 1; l = pre[l]) {
            if((x[i] ^ x[l-1]) == (s[i] - s[l-1])) {
                ans += old - l;
                old = l;
            }
            else {
                break;
            }
        }
        ans += max(0, old - l - 1);
    }
    cout << ans + n;
    return 0;
}

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

vector<int> ACdp(string S){
    int N = S.length();
    vector<int> res(N, 0);
    for(int i = 1; i < N; i++){
        res[i] = res[i - 1];
        if(S[i - 1] == 'A' && S[i] == 'C')res[i]++;
    }
    return res;
}

int main(){
    int N, Q;
    string S;
    cin >> N >> Q >> S;
    vector<int> dp(N);
    dp = ACdp(S);
    for(int i = 0; i < Q; i++){
        int a, b;
        cin >> a >> b;
        cout << dp[b - 1] - dp[a - 1] << endl;
    }
}

Measured memory_bytes: 1400
#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <vector>

const int mod = 1e9 + 7;
const int kmax = 510000;

long long fact[kmax], fact_inv[kmax], inv[kmax];

int gcd(int a, int b)
{
    if (!b) {
        return a;
    }

    return gcd(b, a % b);
}

void init_comb()
{
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < kmax; i++) {
        fact[i] = fact[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
    }
}

long long comb(int n, int r)
{
    if (n < r) {
        return 0;
    }

    if (n < 0 || r < 0) {
        return 0;
    }

    return fact[n] * (fact_inv[r] * fact_inv[n - r] % mod) % mod;
}

template <typename T, T N>
class UnionFind {
    T parent_[N];
    T rank_[N];
    T size_[N];

public:
    UnionFind();
    T Root(T idx);
    bool IsSame(T x, T y);
    void Unite(T x, T y);
    T GetSize(T idx);
};

template <typename T, T N>
UnionFind<T, N>::UnionFind()
{
    for (T i = 0; i < N; i++) {
        parent_[i] = i;
        rank_[i] = 0;
        size_[i] = 1;
    }
}

template <typename T, T N>
T UnionFind<T, N>::Root(T idx)
{
    return parent_[idx] == idx ? idx : parent_[idx] = Root(parent_[idx]);
}

template <typename T, T N>
bool UnionFind<T, N>::IsSame(T x, T y)
{
    return Root(x) == Root(y);
}

template <typename T, T N>
void UnionFind<T, N>::Unite(T x, T y)
{
    x = Root(x);
    y = Root(y);
    if (x == y) {
        return;
    }

    if (rank_[x] < rank_[y]) {
        parent_[x] = y;
        size_[y] += size_[x];
    } else {
        parent_[y] = x;
        size_[x] += size_[y];
        if (rank_[x] == rank_[y]) {
            rank_[x]++;
        }
    }
}

template <typename T, T N>
T UnionFind<T, N>::GetSize(T idx)
{
    return size_[Root(idx)];
}

int main()
{
    int n, r;
    std::cin >> n >> r;

    if (n >= 10) {
        std::cout << r << std::endl;
    } else {
        std::cout << r + 100 * (10 - n) << std::endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long 
using namespace std;
 
const int dx[2] = {1, 0};
const int dy[2] = {0, 1};

signed main(){

  int H, W;
  cin >> H >> W;
  vector<string> meiro(H);
  for (int i = 0; i < H; i++) cin >> meiro[i];

  vector<vector<int>> dp(H, vector<int>(W, 1000000));
  if( meiro[0][0] == '.' ) dp[0][0] = 0;
  else dp[0][0] = 1;
  
  for( int i = 0; i < H; i++ ){
    for( int j = 0; j < W; j++ ){
      for (int direction = 0; direction < 2; ++direction) {
        int next_x = i + dx[direction];
        int next_y = j + dy[direction];
        int A = 0;
        if (next_x < 0 || next_x >= H || next_y < 0 || next_y >= W) continue;
        if( meiro[next_x][next_y] == '#' && meiro[i][j] == '.' ) A++;
        dp[next_x][next_y] = min(dp[next_x][next_y], dp[i][j]+A);
      }
    }
  }
  cout << dp[H-1][W-1] << endl;
}


Measured memory_bytes: 384
def main():
    inf = float('inf')
    n,k=map(int,input().split())
    h = list(map(int,input().split()))
    dp=[0] + [inf] *(n-1)#初期化
    for i in range(1,n):
        for j in range(1,k+1):#iからj離れた場所から来る場合と比較
            if i >=j:
                dp[i] = min(dp[i],abs(h[i-j]-h[i])+dp[i-j])
            else:break
    print(dp[n-1])

if __name__ == '__main__':
    main()

Measured memory_bytes: 55392
#include<iostream>
#include<string>
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;

int moti[101] = {};

int main()
{
	int N;
	cin >> N;
	REP(i, N)
	{
		int tmp;
		cin >> tmp;
		moti[tmp] = 1;
	}
	int ans = 0;
	for (int i = 100; i >= 0; i--)
	{
		if (moti[i] == 1)
		{
			ans++;
		}
	}
	cout << ans << endl;

}

Measured memory_bytes: 256
fun main(arg: Array<String>) {
    val N = nextInt()
    val S1 = next()
    val S2 = next()
    val MOD = 1000000007L
    var ans = 1L
    var tate = false
    var n = 0
    var c = 0
    fun isTate(n: Int) = S1[n] == S2[n]
    while (n < N) {
        if (c == 0) {
            if (isTate(n)) {
                ans = 3
                tate = true
            } else {
                ans = 6
                tate = false
            }
        } else if (isTate(n)) {
            ans *= if (tate) 2 else 1
            tate = true
        } else {
            ans *= if (tate) 2 else 3
            tate = false
        }
        ans %= MOD
        c += 1
        n += if (tate) 1 else 2
    }
    println(ans)
}

fun next() = readLine()!!
fun nextInt() = next().toInt()
fun listOfString() = next().split(" ")
fun listOfLong() = listOfString().map { java.lang.Long.parseLong(it) }


Measured memory_bytes: 31880
n,m=map(int, input().split())
e=[[]for _ in range(n)]
for _ in range(m):
    ai,bi=map(int, input().split())
    ai-=1;bi-=1
    e[ai].append(bi);e[bi].append(ai)

nibu=[-1]*n
nibu[0]=0
from collections import deque,Counter
q=deque([0])
al=False
while q:
    u=q.popleft()
    for v in e[u]:
        if nibu[v]>=0:
            if nibu[u]==nibu[v]:
                al=True
                break
        else:
            nibu[v]=nibu[u]^1
            q.append(v)
        
    if al:
        break
if not al:
    c=Counter(nibu)
    ans=c[0]*c[1]
    ans-=m
else:
    ans=n*(n-1)//2-m
print(ans)

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

using namespace std;
int X,N;
int A[2000010]{};
bool B[2000010]{};
int AC=0,WA=0,TLE=0,RE=0;
vector <int> C;
int main()
{
  string A;
  cin>>N;
  for(int i=0;i<N;i++){
    cin>>A;
    if(A=="WA")WA++;
    else if(A=="AC")AC++;
    else if(A=="TLE")TLE++;
    else if(A=="RE")RE++;
   }
  cout<<"AC x "<<AC;
  cout<<"\nWA x "<<WA;
  cout<<"\nTLE x "<<TLE;
  cout<<"\nRE x "<<RE;
  return 0;
}


Measured memory_bytes: 3636