akhauriyash/Code-Regression huggingface dataset:
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2300

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>
#include<ctime>
#include<cstring>
#include<numeric>
#include<iomanip>

#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;

using namespace std;

struct Lab
{
	double L;
	double A;
	double B;
	Lab(double l, double a, double b):L(l),A(a),B(b){}
};

template <class BidirectionalIterator>
bool next_combination (
		BidirectionalIterator first1 ,
		BidirectionalIterator last1 ,
		BidirectionalIterator first2 ,
		BidirectionalIterator last2 )
{
	if (( first1 == last1 ) || ( first2 == last2 )) {
		return false;
	}
	BidirectionalIterator m1 = last1 ;
	BidirectionalIterator m2 = last2 ; --m2;
	while (--m1 != first1 && !(* m1 < *m2 )){
	}
	bool result = (m1 == first1 ) && !(* first1 < *m2 );
	if (! result ) {
		while ( first2 != m2 && !(* m1 < * first2 )) {
			++ first2;
		}
		first1 = m1;
		std :: iter_swap(first1 , first2 );
		++ first1;
		++ first2;
	}
	if (( first1 != last1 ) && ( first2 != last2 )) {
		m1 = last1 ; m2 = first2;
		while (( m1 != first1 ) && (m2 != last2 )) {
			std :: iter_swap (--m1 , m2 );
			++ m2;
		}
		std :: reverse(first1 , m1);
		std :: reverse(first1 , last1);
		std :: reverse(m2, last2);
		std :: reverse(first2, last2);
	}
	return ! result;
}

template <class BidirectionalIterator>
bool next_combination (
		BidirectionalIterator first ,
		BidirectionalIterator middle ,
		BidirectionalIterator last )
{
	return next_combination (first , middle , middle , last );
}

int main()
{
	cout << setprecision(20) << fixed;

	int N,M;
	cin >> N >> M;
	vector<Lab> colors;
	rep(nth,N)
	{
		double l,a,b;
		cin >> l >> a >> b;
		colors.push_back( Lab(l,a,b) );
	}

	vector<int> num;
	rep(i,N){
		num.push_back(i);
	}


	double ans=0.0;	
	do {
		
		double tmp=0.0;
		
		rep(i,M)
		{
			REP(j,i,M)
			{
				if(i != j)
				{
					double li = colors[num[i]].L - colors[num[j]].L;
					double ai = colors[num[i]].A - colors[num[j]].A;
					double bi = colors[num[i]].B - colors[num[j]].B;
					tmp	+= li*li + ai*ai + bi*bi;
				}
			}
		}
		ans = max(tmp,ans);
	
	} while ( next_combination (num.begin(), num.begin()+M, num.end()) );
	
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1316
#include <bits/stdc++.h>
#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 INF 2e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
 
//const int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
//const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
 
int main()
{
	pair<int, int> ans[3000];
	int a, b;
	while (1){
		cin >> a >> b;
		if (!a and !b) break;
		if (a < b) cout << a << " " << b << endl;
		else cout << b << " " << a << endl;
	}
}



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

const int inf = 1e8;
int n, m;
char S[100005];
int L[100005];
int R[100005];
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> S;
    multiset<int> mn;
    L[0] = 0;
    for (int i = 1; i <= n; i++) {
        mn.insert(L[i - 1]);
        if (i - m - 1 >= 0) mn.erase(mn.find(L[i - m - 1]));
        if (S[i] == '1') {
            L[i] = inf;
            continue;
        }
        L[i] = min(*mn.begin() + 1, inf);
    }
    if (L[n] == inf) {
        cout << -1;
        return 0;
    }
    mn.clear();
    R[n] = 0;
    for (int i = n - 1; i >= 0; i--) {
        mn.insert(R[i + 1]);
        if (i + m + 1 <= n) mn.erase(mn.find(R[i + m + 1]));
        if (S[i] == '1') {
            R[i] = inf;
            continue;
        }
        R[i] = min(*mn.begin() + 1, inf);
    }
    for (int i = 1; i < n; i++) {
        if (L[i] + R[i] != L[n]) S[i] = '1';
    }
    for (int i = 0; i < n; ) {
        for (int j = i + 1; j <= i + m; j++) {
            if (S[j] == '1' || L[j] - L[i] != 1) continue;
            cout << j - i << ' ';
            i = j;
            break;
        }
    }
}

Measured memory_bytes: 5632
//
// Created by yuu on 2019-06-30.
//

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <utility>
#include <math.h>
#include <stack>
#include <queue>
#include <cstdio>

using namespace std;

int L[100010];
int R[100010];

int retu[100010];

int main(void){
    int N, Q;
    cin>>N>>Q;
    string S;
    cin>>S;

    for (int i = 0; i < Q; ++i) {
        cin>>L[i]>>R[i];
    }

    retu[0] = 0;
    for (int i = 0; i < N-1; ++i) {
        if(S[i]=='A' && S[i+1]=='C'){
            retu[i+1] = retu[i] + 1;
        }else{
            retu[i+1] = retu[i];
        }
    }

    for (int i = 0; i < Q; ++i) {
//        int count = 0;
//        for (int k = 0; k < R[i]-L[i]; ++k) {
//            if(S[L[i]+k-1]=='A' && S[L[i]+k]=='C'){
//                count++;
//            }
//        }

//        cout<<count<<endl;
        cout<<retu[R[i]-1]-retu[L[i]-1]<<endl;
    }

//    for (int i = 0; i < N; ++i) {
//        cout<<retu[i]<<endl;
//    }


    return 0;
}

Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll N, ans;
map<ll, ll> a;
int main() {
    cin >> N;
    for(ll i{}; i < N; ++i) {
        ll aa; cin >> aa;
        ++a[aa];
    }
    for(auto& x : a) {
        if(x.first > x.second) ans += x.second;
        else ans += x.second - x.first;
    }
    cout << ans << endl;
}


Measured memory_bytes: 6272
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <tuple>
#include <vector>
using namespace std;
using ll = int64_t;
#define rep(i, j, n) for (int i = j; i < (int)n; ++i)

int main() {
  string s;
  ll k;
  cin >> s >> k;
  ll cnt = 1;
  int n = (int)s.size();
  rep(i, 0, n - 1) {
    if (s[i] == s[i + 1])
      ++cnt;
    else
      break;
  }
  if (cnt == n) {
    cout << cnt * k / 2 << '\n';
    return 0;
  }

  ll ans = 0;
  rep(i, 0, n - 1) {
    if (s[i] == s[i + 1]) {
      ans++;
      s[i + 1] = '.';
    }
  }
  ans *= k;
  if (s[0] == s[n - 1] && cnt % 2 == 1) ans += k - 1;
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 3600
#include <stdio.h>
#include <string.h>
int main(void){
    int A,B;
    scanf("%d %d",&A,&B);
    if(A<=5){
        printf("0\n");
    }
    else if(A>=13){
        printf("%d",B);
    }
    else{
        printf("%d",B/2);
    }
    
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
const unsigned int MOD = 1000000007;
#define ll long long
#define PI 3.1416
string day[]={"SUN","MON","TUE","WED","THU","FRI","SAT"};
vector<string>v;
void dfs(string str,string t="",int cnt=0){
    if(cnt==2){
        v.push_back(t);
        return;
    }else{
        for(int i=0;i<str.size();i++){
            dfs(str,t+str[i],cnt+1);
        }
    }
}
int main(){
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    string str;
    while(cin>>str){
        int rslt=700;
        for(int i=0;i<str.length();i++){
            if(str[i]=='o')rslt+=100;
        }
        cout<<rslt<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

X, Y = getNM()
for i in range(X + 1):
    crane = i
    turtle = X - i
    if (2 * crane) + (4 * turtle) == Y:
        print('Yes')
        exit()
print('No')

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

int main() {
  int A, B, X;
  cin >> A >> B;
  
  if(abs(A-B)%2 == 0) {
    X = max(A,B)-abs(A-B)/2;
    cout << X << endl;
  } else
    cout << "IMPOSSIBLE" << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int q,a,b,r,n,m,p[10010]={0};
  int d[10010]={0};
  scanf("%d %d",&n,&m);
  while(m--){
    scanf("%d %d %d",&q,&a,&b);
    for(r=++a;p[r];r=p[r]);
    for(;n=p[a];a=n)p[a]=r;
    for(r=++b;p[r];r=p[r]);
    for(;n=p[b];b=n)p[b]=r;
    if(q)printf("%d\n",a-b?0:1); 
    else if(a-b){
      d[a]<d[b]?(p[a]=b):(p[b]=a);
      if(d[a]==d[b])d[a]++;
    }
  }
  return 0;
}

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

int main(int argc, char const *argv[])
{
	char A[3];
	char B[3];
	int ans = 0;
	cin>>A;
	cin>>B;
	for(int i=0; i<3; i++){
		if(A[i]==B[i])
			ans++;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
from itertools import product
from sys import stdin
input = stdin.buffer.readline

def main():
    n, *abc = map(int, input().split())
    l = [int(input()) for _ in range(n)]

    ans = 10**9
    for prod in product([0, 1, 2, 3], repeat=n):
        cost = 10 * (n-3)
        lengths = [0, 0, 0]
        for i, x in enumerate(prod):
            if x < 3:
                lengths[x] += l[i]
            else:
                cost -= 10

        for i in lengths:
            if i == 0:
                break

        else:
            for i, x in enumerate(abc):
                cost += abs(x - lengths[i])
            if cost < ans:
                ans = cost

    print(ans)

main()

Measured memory_bytes: 73936
import java.io.{BufferedOutputStream, BufferedReader, InputStreamReader, PrintWriter}
import java.lang

import scala.reflect.ClassTag

object Main {
  def get[T: ClassTag](implicit in: BufferedReader, converter: String => T): T = {
    converter(in.readLine)
  }

  def getArray[T: ClassTag](implicit in: BufferedReader, converter: String => T): Array[T] = {
    get[String].split("\\s+").map(converter)
  }

  implicit val intConverter: String => Int = s => Integer.parseInt(s)
  implicit val longConverter: String => Long = s => lang.Long.parseLong(s)

  def get[T1, T2](
                   implicit in: BufferedReader,
                   converter1: String => T1,
                   converter2: String => T2
                 ): (T1, T2) = {
    getArray[String] match {
      case Array(v1, v2) => (converter1(v1), converter2(v2))
    }
  }

  def get[T1, T2, T3](
                       implicit in: BufferedReader,
                       converter1: String => T1,
                       converter2: String => T2,
                       converter3: String => T3
                     ): (T1, T2, T3) = {
    getArray[String] match {
      case Array(v1, v2, v3) => (converter1(v1), converter2(v2), converter3(v3))
    }
  }

  implicit class TimesInt(val n: Int) {
    def times(f: Int => Unit): Unit = {
      for (i <- 0 until n) {
        f(i)
      }
    }
  }

  def main(args: Array[String]): Unit = {
    implicit val in: BufferedReader = new BufferedReader(new InputStreamReader(System.in))
    val out = new PrintWriter(new BufferedOutputStream(System.out))
    val n = get[Int]
    val abs = Array.fill(n) {
      get[Int, Int]
    }.sortBy {
      case (a, b) => a + b
    }.reverse

    var sum = 0L
    n.times { i =>
      if (i % 2 == 0) {
        sum += abs(i)._1
      } else {
        sum -= abs(i)._2
      }
    }

    out.println(sum)

    out.flush()
  }
}

Measured memory_bytes: 82492
package main

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

var sc = bufio.NewScanner(os.Stdin)

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

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)

	h, w := nextInt(), nextInt()
	board := make([][]byte, h)
	for i := 0; i < h; i++ {
		r := next()
		board[i] = make([]byte, w)
		for j := 0; j < w; j++ {
			board[i][j] = r[j]
		}
	}

	max := 0
	// 全探索
	for i := 0; i < h; i++ {
		for j := 0; j < w; j++ {
			if board[i][j] == '#' {
				continue
			}

			d := maxDistance(board, i, j)

			if d > max {
				max = d
			}
		}
	}

	fmt.Println(max)
}

func maxDistance(board [][]byte, si, sj int) int {
	h, w := len(board), len(board[0])
	d := 0
	ds := make([][]int, h)
	for i := 0; i < h; i++ {
		ds[i] = make([]int, w)
		for j := 0; j < w; j++ {
			ds[i][j] = -1
		}
	}
	ds[si][sj] = 0

	queue := [][]int{{si, sj}}
	diffs := [][]int{{-1, 0}, {0, -1}, {1, 0}, {0, 1}}
	for len(queue) > 0 {
		s := queue[0]
		queue = queue[1:]

		dis := ds[s[0]][s[1]]
		for _, diff := range diffs {
			dx := s[0] + diff[0]
			dy := s[1] + diff[1]

			if dx >= 0 && dx < h && dy >= 0 && dy < w {
				if ds[dx][dy] == -1 && board[dx][dy] == '.' {
					queue = append(queue, []int{dx, dy})
					ds[dx][dy] = dis+1
					if d < dis+1 {
						d = dis+1
					}
				}
			}
		}
	}

	return d
}

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

const int MAXN=5e5+10;
const int INF=1e9+10;

int n,m;
int x[MAXN],y[MAXN],seg[4*MAXN];
int du[MAXN];
vector<int> edge[MAXN];
priority_queue<int,vector<int>,greater<int>> q;

void build(int u,int l,int r){
    seg[u]=INF;
    if (l==r) return;
    int mid=(l+r)/2;
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
}

void update(int u,int l,int r,int pos,int val){
    if (l==r){
        seg[u]=pos;
        return;
    }
    int mid=(l+r)/2;
    if (val<=mid) update(u*2,l,mid,pos,val);
    else update(u*2+1,mid+1,r,pos,val);
    seg[u]=min(seg[u*2],seg[u*2+1]);
}

int query(int u,int l,int r,int ql,int qr){
    if (l==ql && r==qr)
        return seg[u];
    int mid=(l+r)/2;
    if (qr<=mid) return query(u*2,l,mid,ql,qr);
    else{
        if (ql>mid) return query(u*2+1,mid+1,r,ql,qr);
        else return min(query(u*2,l,mid,ql,mid),query(u*2+1,mid+1,r,mid+1,qr));
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        du[i]=0;
        int a; scanf("%d",&a);
        x[a]=i;
    }
    build(1,1,n);
    for(int i=n;i>=1;i--){
        int l,r;
        l=x[i]+1; r=min(n,x[i]+m-1);
        if (l<=r){            
            int p=query(1,1,n,l,r);
            if (p!=INF){
                edge[x[i]].push_back(x[p]);
                du[x[p]]++;
            }
        }
        l=max(1,x[i]-m+1); r=x[i]-1;
        if (l<=r){
            int p=query(1,1,n,l,r);
            if (p!=INF){
                edge[x[i]].push_back(x[p]);
                du[x[p]]++;
            }
        }
        update(1,1,n,i,x[i]);
    }
    for(int i=1;i<=n;i++) if (du[i]==0) q.push(i);            
    int len=0;
    while(!q.empty()){
        int u=q.top(); q.pop();
        x[++len]=u;
        for(int i=0;i<edge[u].size();i++){
            int v=edge[u][i];
            du[v]--;
            if (du[v]==0) q.push(v);
        }
    }
    for(int i=1;i<=n;i++) y[x[i]]=i;
    for(int i=1;i<=n;i++) printf("%d\n",y[i]);
    return 0;
}



/*
4 5 7 8 3 1 2 6
3 5 7 8 4 1 2 6
2 5 7 8 4 1 3 6
1 5 7 8 4 2 3 6
1 4 7 8 5 2 3 6
1 3 7 8 5 2 4 6
1 2 7 8 5 3 4 6 
1 2 6 8 5 3 4 7
1 2 6 7 5 3 4 8

1 2 6 7 5 3 4 8
*/

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

int N, T, H, L;
int coins[101][2];

int solve() {
    int i = 0;
    int cur = 0;
    while (1) {
        if (coins[i][0]) {
            cur += 10; T++;
            coins[i][0]--;
            if (T > L) break;
            if (cur >= 90) {
                cur = 0;
            }
        }
        else if (coins[i][1]) {
            cur += 100; H++;
            coins[i][1]--;
            int c = (cur - 90) / 10;
            T -= c; coins[i][0] += c;
            cur = 0;
            if (T < 0) break;
        }
        else {
            break;
        }
        i = (i + 1) % N;
    }
    return i + 1;
}

int main() {
    while (cin >> N >> T >> H >> L) {
        for (int i = 0; i < N; i++) {
            cin >> coins[i][0] >> coins[i][1];
        }
        cout << solve() << endl;
    }
    return 0;
}

Measured memory_bytes: 1160
import java.util.*

fun main(args: Array<String>) {
    Scanner(System.`in`).use { sc ->
        val n = sc.nextInt()

        var tp = 0
        var xp = 0
        var yp = 0
        for (i in 0 until n) {
            val t = sc.nextInt()
            val x = sc.nextInt()
            val y = sc.nextInt()

            val step = t - tp
            val distance = Math.abs(x - xp) + Math.abs(y - yp)
            val rem = step - distance
            if (rem < 0 || rem % 2 == 1) {
                println("No")
                return
            }

            tp = t
            xp = x
            yp = y
        }
        println("Yes")
    }
}


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

int main(){
  int n;
  cin >> n;
  vi a(n), ans(n);
  rep(i, n){
    cin >> a[i];
    ans[a[i]-1]=i+1;
  }

  rep(i, n)cout << ans[i] << endl;

  return 0;
}

Measured memory_bytes: 3960
#include <bits/stdc++.h>
using namespace std;
int main(){
    string S, T;
    int cnt = 0;
    cin >>S >>T;
    for(int i=0; i < 3 ;++i){
        if(S[i]== T[i]){
            ++cnt;
        }
    }
    cout<< cnt;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
  int N; ll x; cin >> N >> x;
  vector<ll> a(N);
  for(int i = 0; i < N; i++) {
    cin >> a.at(i);
  }
  sort(a.begin(), a.end());
  for(int i = 0; i < N; i++) {
    x -= a.at(i);
    if(x < 0) {
      cout << i << endl;
      return 0;
    }
  }
  if(x == 0) {
    cout << N << endl;
  } else if(x > 0) {
    cout << N - 1 << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h> 
using namespace std;
int main(){
  vector<int> Nums(3);
  for(int i=0;i<3;i++)	cin>>Nums[i];
  sort(Nums.begin(), Nums.end());
  if((Nums[0]==5)&&(Nums[1]==5)&&(Nums[2]==7)) cout<<"YES";
  else cout<<"NO";
  return 0;
}

  
  


Measured memory_bytes: 256
import java.util.*;
class Main
{
    public static void main (String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();
        int[] a = new int[n];
        long[] b = new long[n];
        Map<Integer, Long> m = new HashMap<>();
        for(int i = 0; i < n; i++){
            a[i] = sc.nextInt() - 1;
            b[i] = sc.nextLong();
            if(!m.containsKey(a[i])) m.put(a[i], (long)0);
            m.put(a[i], m.get(a[i]) + b[i]);
        }
        Arrays.sort(a);
        for(int i = 0; i < n; i++)
            b[i] = m.get(a[i]);
        int j = 0;
        long tmp = 0;
        while(tmp < k){
            if(j > 0 && a[j] == a[j-1]){
                j++;
                continue;
            }
            tmp += b[j];
            j++;
        }
        System.out.println(a[j-1] + 1);
    }
}

Measured memory_bytes: 98820
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

class Program
{
    static void Main()
    {
        var NK = ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
        var (N, K) = (NK[0], NK[1]);
        var h = ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();

        void ChMin<T>(ref T min, T value)
            where T : IComparable
        {
            if (value.CompareTo(min) < 0)
                min = value;
        }
        
        int GetCost(int a, int b) => Math.Abs(a - b);

        var dp = Enumerable.Repeat(int.MaxValue, N).ToArray();
        dp[0] = 0;

        for (int i = 1; i < N; i++)
        {
            for (int j = 1; j <= K; j++)
            {
                if (0 <= i - j)
                {
                    ChMin(ref dp[i], dp[i - j] + GetCost(h[i], h[i - j]));
                }
            }
        }

        WriteLine(dp[N - 1]);
    }
}


Measured memory_bytes: 50696
#include <bits/stdc++.h> 
using namespace std;
#define N 15
#define M 1<<15
#define mod 1000000007
int g[N],f[M],t[M];
int read(){
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0' || ch>'9'){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0' && ch<='9'){
		x=x*10+ch-'0';ch=getchar();
	}
	return x*f;
}
inline int add(int x,int y){
	return x+y>=mod?x+y-mod:x+y;
}
inline int sub(int x,int y){
	return x-y<0?x-y+mod:x-y;
}
inline int mul(int x,int y){
	return 1LL*x*y%mod;
}
inline int calc(int x){
	return __builtin_popcount(x);
}
signed main(){
	int n=read(),m=read();
	f[0]=t[0]=1;
	for (int i=1;i<=m;++i) t[i]=(t[i-1]<<1)%mod;
	for (int i=1;i<=m;++i){
		int x=read()-1,y=read()-1;g[x]|=(1<<y);
	}
	for (int s=1;s<(1<<n);++s){
		if ((s&1)==(s>>1&1)){
			for (int u=s;u;u=u-1&s){
				if ((u&1)==(u>>1&1)){
					int ans=1;
					for (int i=0;i<n;++i){
						if (s>>i&1){
							if (u>>i&1) ans=mul(ans,t[calc(g[i]&(s^u))]);
							else ans=mul(ans,t[calc(g[i]&u)]-1);
						}
					}
					f[s]=add(f[s],mul(f[s^u],ans));
				}
			}
		}
	}
	cout<<sub(t[m],f[(1<<n)-1])<<endl;
	return 0;
}

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

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
#define dump(val) cerr << __LINE__ << ":\t" << #val << " = " << (val) << endl

using namespace std;

typedef long long int lli;

template<typename T>
vector<T> make_v(size_t a, T b) {
    return vector<T>(a, b);
}

template<typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v(ts...))>(a, make_v(ts...));
}

int main() {
    lli N, M;
    cin >> N >> M;
    vector<lli> A(N + 1, 0LL);
    REP(i, 0, N) {
        cin >> A[i + 1];
    }

    map<lli, lli> mp;
    lli ans = 0;
    REP(i, 0, N) {
        A[i + 1] = (A[i] + A[i + 1]) % M;
    }
    REP(i, 0, N + 1) {
        ans += mp[A[i]];
        mp[A[i]]++;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 4992
#include <iostream>
using namespace std;
bool valid(int a, int &c7, int &c5){
  if(a == 7){
    c7++;
    return true;
  }
  if(a == 5){
    c5++;
    return true;
  }
  return false;
}
int main(){
  	int A,B,C;
  	cin>>A>>B>>C;
    int c7 = 0, c5 =0;
  	if(valid(A,c7,c5) && valid(B,c7,c5) && valid(C,c7,c5)){
      if(c5 == 2 && c7 ==1){
        cout<<"YES"<<endl;
        return 0;
      }
    }
  	cout<<"NO"<<endl;
  	return 0;
}

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

int main() {
  int H, W;
  cin >> H >> W;

  vector<vector<char>> A(H, vector<char>(W));
  vector<vector<char>> B(H + 2, vector<char>(W + 2, '0'));

  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cin >> A.at(i).at(j);
      if (A.at(i).at(j) == '#') {
        for (int k = i; k < i + 3; k++) {
          for (int l = j; l < j + 3; l++) B.at(k).at(l)++;
        }
      }
    }
  }

  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (A.at(i).at(j) == '#') B.at(i + 1).at(j + 1) = '#';
    }
  }

  for (int i = 1; i < H + 1; i++) {
    for (int j = 1; j < W + 1; j++) {
      cout << B.at(i).at(j);
    }
    cout << "\n";
  }
}

Measured memory_bytes: 256
from fractions import gcd
 
def main():
    a,b,c,d = map(int,input().split(" "))
    n = b - a + 1
    cdiv = b//c - (a-1)//c
    ddiv = b//d - (a-1)//d
    cddiv = b//(c * d // gcd(c, d))  - (a-1)//(c * d // gcd(c, d))
    print(n - cdiv -ddiv + cddiv)
 
if __name__ == '__main__':
    main()

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

using namespace std;

typedef long long ll;

const ll LongINF=1e13+7;
const int INF=1e9+7;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template <class T, class Y>T GCD(T a, Y b){if(a<b){int c=a;a=b;b=c;}if (a % b == 0){return b;}return GCD(b, a % b);}
void clear(queue<pair<int, int>> &q){queue<pair<int, int>> empty;swap(q, empty);} //queueの中身の型は適時変更を忘れない

#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define rv reverse

int main(){
    string A;
    cin>>A;
    string K="keyence";
    int L=A.length();
    rep(i,8){
        string B=A.substr(0,i)+A.substr(A.length()-7+i);
        if(B==K)
        {
            cout<<"YES"<<endl;
            return 0;
        }
    }
    cout<<"NO"<<endl;

    return 0;
}

//a=97,z=122

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
#define fst first
#define snd second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define sz size()
#define FORN(i,j,n) for(long long i=j; i<(long long)n;i++) 
#define FOR(i,n) FORN(i,0,n)
#define FORIT(i,x) for( auto i = x.begin() ; i != x.end() ; i++ )
#define MOD 998244353LL
#define LIM 262150
#define ones(x) __builtin_popcount(x)
#define trace(x)    cerr << #x << ": " << x << endl;
#define trace2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
using namespace std;
 
typedef long long ll ;
typedef unsigned long long ull ;
typedef vector <int> vi;
typedef pair <int,int> ii;
typedef vector <string> vs;
typedef vector <ii> vii;
ll n; 
ll arr[3005];
ll dp[3005][3005];
int main() {
	fastio;
	cin>> n;
	FOR(i,n) cin>> arr[i];
	FORN(i,1,n+1){
		FOR(j,n){
			if(j+i > n) continue;
			if(i == 1){ dp[i][j] = arr[j]; continue; }
			dp[i][j] = max(arr[j]-dp[i-1][j+1],arr[j+i-1]-dp[i-1][j]);
		}
	}
	cout<< dp[n][0] << '\n';
	return 0;
}

Measured memory_bytes: 49800
#include <iostream>

#define endl '\n'
#define pb push_back
#define F first
#define S second
typedef long long ll;
typedef unsigned long long ull;

using namespace std;

void solve()
{
    int n;

    cin >> n;

    int sum = 0;

    int temp = n;

    while(temp != 0)
    {
        sum += temp%10;
        temp /= 10;
    }

    if(n % sum == 0)
        cout << "Yes";
    else
        cout << "No";

}

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

//    int t; cin >> t; while(t--){
        solve();
//    }
    return 0;
}


Measured memory_bytes: 3092
import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, core.bitop;

enum inf = 10L^^15;

void main() {
    int n, m;
    scan(n, m);

    auto adj = new int[][](n, 0);

    foreach (i ; 0 .. m) {
        int xi, yi;
        scan(xi, yi);
        xi--, yi--;
        adj[yi] ~= xi;
    }

    auto dp = new int[](n);
    dp[] = -1;

    int dfs(int v) {
        if (dp[v] != -1) {
            return dp[v];
        }
        dp[v] = 0;
        foreach (u ; adj[v]) {
            dp[v] = max(dp[v], dfs(u) + 1);
        }
        return dp[v];
    }

    int ans;
    foreach (i ; 0 .. n) {
        ans = max(dfs(i), ans);
    }
    writeln(ans);
}







void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}


void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

Measured memory_bytes: 16764
import math

n = int(input())

x_y = [[int(_) for _ in input().split(' ')] for _ in range(n)]

s = 0.0
for i in range(n):
    for j in range(i + 1, n):
        s += ((x_y[i][0] - x_y[j][0])**2.0 + (x_y[i][1] - x_y[j][1])**2.0)**0.5

print(s * 2 * (n - 1) * math.factorial(n - 2) / math.factorial(n))


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

int main() {
    int H, W, K, ans = 0;
    cin >> H >> W >> K;
    string c[H];
    rep(i, H) {
        cin >> c[i];
    }

    rep(h, (1 << H)) rep(w, (1 << W)) {
        int cnt = 0;
        rep(i, H) rep(j, W) {
            if ((h >> i & 1) && (w >> j & 1) && c[i][j] == '#') cnt++;
        }
        if (cnt == K) ans++;
    }
    cout << ans << endl;

}

Measured memory_bytes: 3560
#include <iostream>

using namespace std;

bool d[114514][46];
int M;
void f(int r, int s, int m)
{
	if (s > 45 || d[r][s])
		return;
	d[r][s] = true;
	if (!r && s && (!M || s < M))
		M = s;
	for (int i = 0; i < 10; i++)
		f((r * 10 + i) % m, s + i, m);
}

int main()
{
	int k;
	cin >> k;
	f(0, 0, k);
	cout << M << endl;
	return 0;
}


Measured memory_bytes: 159232
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=500000004;
int dp[510000];
char in[510000];
int cnt;
void dfs(int a,int b){
	dp[a]-=b;
	if(a==0)return;
	while(1){
	//	cnt++;
		if(dp[a-1]<=dp[a])return;
		int at=0;
		int sa=dp[a-1]-dp[a];
		for(int i=a-1;i>=0;i--){
			if(dp[i]!=dp[a-1])break;
			at++;
		}
		for(int i=a-at;i<a;i++){
			if(i-(a-at)<sa)dp[i]+=(i-(a-at))*9-1;
			else dp[i]+=sa*9;
		}
		dp[a]+=min(sa,at)*10;
		int t=dp[a-1];
		int nd=(dp[a-1]-dp[a]+10)/11;
		//if(a>=2&&dp[a-1]-nd<dp[a-2])nd=(dp[a-1]-dp[a]+20)/11;
		//printf("%d %d\n",a,nd);
		dfs(a-1,nd);
		dp[a]+=nd*10;
	}
}
int main(){
	scanf("%s",in);
	int n=strlen(in);
	for(int i=0;i<n;i++)dp[i]=in[i]-'0';
	for(int i=0;i<n;i++){
		dfs(i,0);
	//	for(int j=0;j<=i;j++)printf("%d ",dp[j]);
	//	printf("\n");
	}
	//printf("%d\n",cnt);
	printf("%d\n",(dp[n-1]+8)/9);
}

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

using namespace std;

int main() {
    int mod=1e9+7;
    int n;
    cin >> n;
    if (n==1) {
        cout<<2;
        return 0;
    }
    vector<int> d(n+1);
    vector<pair<int,int>> dp(n+1);
    vector<vector<int>> adj(n+1);
    for (int i=1;i<=n-1;++i){
        int a,b;
        cin >> a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        d[a]++;d[b]++;
    }
    queue<int> q;
    for (int i=1;i<=n;++i) if (d[i]==1) q.push(i);
    int last=0;
    while (!q.empty()){
        int a=q.front();q.pop();
        last=a;
        long black=1,white=1;
        for (int& b:adj[a]){
            if (d[b]==0){
                black=(black*dp[b].first)%mod;
                white=(white*((long)dp[b].first+dp[b].second))%mod;
            } else if (d[b]>1){
                d[b]--;
                if (d[b]==1) q.push(b);
            }
        }
        d[a]=0;
        dp[a]={white,black};
    }
    int ans=(dp[last].first+dp[last].second)%mod;
    cout << ans;
}

Measured memory_bytes: 10416
#include <stdio.h>
#include <math.h>
int v[10240][333],a[10],i,j,n,s;
int summing(int n,int s){
	int ans=0,i,max=0,min=0,m,k;
	if(s>332)return 0;
	if(n==1){if(s<10 && a[s]==1)return 1; else return 0;}
	else{
		k=(a[0]+a[1]*2+a[2]*4+a[3]*8+a[4]*16+a[5]*32+a[6]*64+a[7]*128+a[8]*256+a[9]*512)*10+(n-1);
		if(v[k][s]>=0)return v[k][s];
		for(i=0,m=n;m>0 && i<10;i++){if(a[i]==1){min+=m*i;m--;if(s<min)goto answer;}}
		for(i=9,m=n;m>0 && i>=0;i--){if(a[i]==1){max+=m*i;m--;if(s<=max)break;}}if(s>max)goto answer;
		for(i=0;i<10;i++){
			if(a[i]==1 && n*i<=s){
				a[i]=0;
				ans+=summing(n-1,s-n*i);
				a[i]=1;
			}
		}
		answer:
		v[k][s]=ans;
		return ans;
	}
}
int main(void){
	for(i=0;i<10;i++)a[i]=1;
	for(i=0;i<10240;i++){{for(j=0;j<333;j++)v[i][j]=-1;}}
	while(scanf("%d %d",&n,&s)!=EOF){printf("%d\n",summing(n,s));}
	return 0;
}

Measured memory_bytes: 13916
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]


def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m


def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a


def lcm(a,b):
    return a*b//gcd(a,b)


p = 10**9+7
N = int(input())
mul = 1
inv_sum = 0
for x in input().split():
    a = int(x)
    inv_sum += mod_inv(a, p)
    inv_sum %= p
    mul = lcm(mul, a)

print(mul * inv_sum % p)

Measured memory_bytes: 3828
# https://atcoder.jp/contests/abc123
# -*- coding: utf-8 -*-

import math

v1=[]
for i in range(5):
    v1.append(int(input()))

v2=[]
for i in range(5):
    v2.append( math.ceil(v1[i]/10)*10 )

result = 0
for i in range(5):
    if v2[i] - v1[i] > result:
        result = v2[i] - v1[i]

print(v2[0]+v2[1]+v2[2]+v2[3]+v2[4]-result)

Measured memory_bytes: 3064
import sys

# import bisect
from collections import Counter, deque, defaultdict

# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter

# import math

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())
    k = set()

    def divisors(n):
        # 素因数分解

        divisors = []

        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n // i)

        return divisors

    divisors1 = divisors(n)
    divisors1.sort()

    for d in divisors1[1:]:
        x = n
        while x % d == 0:
            x = x // d
        if x % d == 1:
            k.add(d)

    divisors2 = divisors(n-1)
    divisors2 = set(divisors2)
    k = k.union(divisors2)
    k.discard(1)
    print(len(k))

if __name__ == '__main__':
    main()


Measured memory_bytes: 39152
def main():
    l,s = map(int,input().split())
    cnt=0
    
    
    if(s<l):
        l=s
    
    for i in range(l+1):
        for j in range(l+1):
            if(s-i-j<=l and s-i-j>=0):
                cnt+=1
    print(cnt)
        
main()

Measured memory_bytes: 2940
s = input()
check = 0
if s[0] == "A":
  if s[2:len(s)-1].count("C") == 1:
    if s[1].lower() == s[1] and s[len(s)-1].lower() == s[len(s)-1]:
      t = s.replace("C","")
      if t[1:len(s)].lower() == t[1:len(s)]:
        check = 1
        
if check == 0:
  print("WA")
else:
  print("AC")
      
    
    
    

Measured memory_bytes: 3064
#include <stdio.h>
int main()
{
  int i,j,c,n,v,A[1000];
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  for(i=0;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(c=0;c<n;c++){
      printf("%d",A[c]);
      if(c<n-1)printf(" ");
    }
    printf("\n");
  }
  return 0;
}



Measured memory_bytes: 2144
use std::vec::Vec;
use std::cmp::*;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

const MOD: i64 = 1_000_000_000 + 7;

fn main() {
    let mut s: Vec<char> = read::<String>().chars().collect();
    let n: usize = s.len();
    s.reverse();
    let mut dp: Vec<Vec<i64>> = vec![vec![0; 13]; n+1];
    let mut tmp = 1;

    if s[0] == '?' {
      for j in 0..10 {
        dp[0][j] = 1;
      }
    } else {
      let num = (s[0].to_string()).parse::<usize>().unwrap();
      dp[0][num] = 1;
    }

    for i in 0..n-1 {
      tmp *= 10;
      tmp %= 13;
      if s[i+1] == '?' {
        for j in 0..13 {
          for k in 0..10 {
            let index = (j - k * tmp + 13 * 1000) % 13;
            dp[i+1][j] += dp[i][index];
            dp[i+1][j] %= MOD;
          }
        }
      } else {
        let num = (s[i+1].to_string()).parse::<usize>().unwrap();
        for j in 0..13 {
          let index = (j - num * tmp + 13 * 1000) % 13;
          //println!("j = {}, num * tmp = {}, index = {}", j, num * tmp, index);
          dp[i+1][j] += dp[i][index];
          dp[i+1][j] %= MOD;
        }
      }
    }




  println!("{}", dp[n-1][5])
}


Measured memory_bytes: 18684
#include <iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
using namespace std;
typedef long long int ll;
#define EPS 1e-9
#define pb push_back
#define FOR(i, a, b) for(ll i = a; i < b; i++)
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
void stones(ll n,ll k,vector<ll>&arr)
{
    vector<ll>dp(k+1,0);
    FOR(i,0,k+1)
    {
        FOR(j,0,n)
        {
            if(i-arr[j]>=0)
            dp[i]=dp[i]|!dp[i-arr[j]];
        }
    }
    /*FOR(i,0,n)
    {
        FOR(j,0,k+1)
        {
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }*/
    if(dp[k])
    {
        cout<<"First"<<endl;
    }
    else
    {
        cout<<"Second"<<endl;
    }
    return;

}
int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,k;
    cin>>n>>k;
    vector<ll>a(n,0);
    FOR(i,0,n)
    {
        cin>>a[i];
    }
    stones(n,k,a);
    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define cmin(a,b)(a=min(a,b))
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define EPS (1e-10)
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
typedef pair<int, int>P;

int a[100], e[100], r[100];
int dp[101][101];

int main() {
	int d, n;
	while (scanf("%d%d", &d, &n), d) {
		rep(i, n)scanf("%d%d%d", &a[i], &e[i], &r[i]);
		memset(dp, 0x3f, sizeof(dp));
		rep(i, 101) {
			dp[0][i] = 0;
		}
		for (int i = 0; i <= d; i++) {
			for (int j = 100; j >= 0; j--) {
				rep(k, n) {
					if (j >= r[k])cmin(dp[i][j], dp[max(0, i - a[k])][min(100, j + e[k])] + 1);
				}
			}
		}
		if (dp[d][0] == INF)puts("NA");
		else printf("%d\n", dp[d][0]);
	}
}

Measured memory_bytes: 3240
import numpy as np
A = np.array([[1, 1], [2, 4]])
Ai = np.linalg.inv(A)
B = [int(i) for i in input().split()]
B = np.array(B)
X = Ai.dot(B)
if X[0] >= 0 and X[1] >= 0 and X[0]-int(X[0]) == 0 and X[1]-int(X[1]) == 0:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 27620
#include <bits/stdc++.h>
using namespace std;
int main () {
  int N;
  cin >> N;
  vector <int> d(N);
  for (int i = 0; i < N; i++) cin >> d.at(i);
  int ans = 0;
  int count = 0;
  for (int i = 0; i < N-1; i++){
    for (int j = i+1; j < N; j++){
      ans += d.at(i) * d.at(j);
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
n=int(input())
c=0
flag = False
for i in range(n):
    d1, d2 = map(int,input().split())
    if d1 == d2:
        c +=1
        if c==3:
            flag = True
    else:
        c = 0
if flag == True:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 9176
#include <iostream>
#include <string>

int main()
{
	int input = 0;
	std::cin >> input;

	int hour = (input / 60) / 60;
	int min = (input / 60) % 60;
	int sec = input % 60;

	std::cout << hour << ":" << min << ":" << sec << std::endl;
	return 0;
}


Measured memory_bytes: 3092
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,a,b) for (int i = a; i < (b); ++i)
#define all(x) (x).begin(),(x).end()
#define YY puts("Yes")
#define NN puts("No")
const int INF = 1000000007;
typedef long long ll;
using namespace std;
using Graph = vector<vector<int>>;
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; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
ll fac(ll a) { return a > 1 ? fac(a - 1) * a : 1; }
int Rand() { return (rand() % 32768) * 32768 + (rand() % 32768); }
int solve(){
  int n;
  cin >> n;
  vector<ll>v(n);
  map<ll,ll>count;
  ll sum = 0,ans = 0;
  count[0]++;
  rep(i,n){
    cin >> v[i];
    sum += v[i];
    ans += count[sum];
    count[sum]++;
  }
  cout << ans << endl;
  return 0;
}
int main(){
  // ios::sync_with_stdio(false);cin.tie(nullptr);
  // cout << fixed;cout << setprecision(16) << endl; 
  solve();
  return 0;
}

Measured memory_bytes: 14336
#include"bits/stdc++.h"
using namespace std;
using ll=long long;
template<typename T=ll>inline T in(istream&is=cin){T ret;is>>ret;return ret;}
template<typename T>inline auto vec2(typename vector<T>::size_type h,typename vector<T>::size_type w,T v=T()){return vector<vector<T>>(h,vector<T>(w,v));}

int main()
{
    ll x=in();
    ll n=100;
    ll ans;
    for(ans=0;n<x;++ans)n+=n/100;
    cout<<ans<<endl;
}


Measured memory_bytes: 3620
//Name-Deepesh Bhatt
//Institute-IIT Dhanbad

#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
#define MOD 1E9+7
ll gcd(ll a,ll b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}
ll lcm(ll a ,ll b)
{
    return a/gcd(a,b)*b;
}
ll power(ll a, ll n)
{
    if (n == 0)
        return 1;
    ll p = power(a, n / 2);
    p = (p * p);
    if (n % 2)
        return (p * a);
    else
        return p;
}

int main()
{
    ios_base::sync_with_stdio(false);    //for fast I/O operation
    cin.tie(NULL);
    int n;
    cin>>n;
    map<int,int>m;
    for(int i=1;i<=n;i++){
        m[i]=0;
    }
    for(int i=1;i<n;i++){
        int t;
        cin>>t;
        m[t]++;
    }
    for(auto x:m){
        cout<<x.second<<endl;
    }
    return 0;
}

Measured memory_bytes: 13056
#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <algorithm>
#include <stack>
using namespace std;
#define mod 1000000007
#define PI acos(-1.0)
typedef long long ll;
const int INF=0x3f3f3f3f;
int d[8][2]={-1,0,0,-1,0,1,1,0,1,1,-1,-1,-1,1,1,-1};
ll n,x,y,k,a[200005],b[200005],num=INF;
int fun(ll mid)
{
    ll sum=0;
    for(int i=n-1;i>=0;i--)
    {
        k=a[i]-mid*y;
        if(k>0)
        {
            sum+=(k+x-y-1)/(x-y);
        }
        else break;
    }
    if(sum>mid) return 0;
    else return 1;
}
int main()
{
    scanf("%lld%lld%lld",&n,&x,&y);
    for(int i=0;i<n;i++)
        scanf("%lld",&a[i]);
    sort(a,a+n);
    ll s=1,e=(a[n-1]+y-1)/y;
    while(s<=e)
    {
        ll mid=(s+e)/2;
        if(fun(mid))
        {
            if(mid<num)num=mid;
            e=mid-1;
        }
        else s=mid+1;
    }
    printf("%lld\n",num);
    return 0;
}


Measured memory_bytes: 1024
if __name__ == '__main__':
   while 1:
    n,m,p = list(map(int,input().strip().split()))
    if n ==0 and m ==0 and p ==0:break
    player = []
    for _ in range(n):player.append(int(input()))
    bet = sum(player) *(100 - p)
    if player[m-1] == 0:print(0)
    else:
        ans = bet/player[m-1]
        print(int(ans))

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

int main() 
{
    ll n, m;
    cin >> n >> m;
    vector<ll> x(m);
    if (n>m)
    {
        cout << 0;
        return 0;
    }
    for(ll i=0; i<m; i++)
        cin >> x[i];
    sort(x.begin(), x.end());
    vector<ll> y(m-1);
    for (ll i=0; i<m-1; i++)
        y[i] = x[i+1]-x[i];
    sort(y.begin(), y.end());
    ll sum = 0;
    for (ll i=0; i<y.size()-n+1; i++)
        sum += y[i];
    cout << sum;
    return 0;
}

Measured memory_bytes: 1792
//  Created by conan1024hao in 2019.
//  Copyright © 2019 conan1024hao. All rights reserved.
//  専用ライブラリです、自由にコピーして構いません。
//  感谢看我的代码！Wechat:conan1024hao QQ:810396815
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define INF 10e16
#define MOD 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
//using Int=int_fast64_t;
typedef long long int ll;
typedef pair<ll,ll>Pll;
typedef pair<int,int>Pin;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
char dir[4]={'u','l','d','r'};
ll cmp1(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}

//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
int main(){//問題をちゃんと見ろ!!!!!!!!!!!!!!!!!      llか??????????        memset()!!!!!!!!!!!!
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    int a,b;cin>>a>>b;
    cout<<(a+b+1)/2<<endl;
    
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------


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

const int N=100;
const int INF=2000000000;
const int WHITE=0;
const int GRAY=1;
const int BLACK=2;

int n,M[N][N],d[N],color[N];

void dijkstra(){
    d[0]=0;
    color[0]=GRAY;
    while(true){
        int min_des=INF;
        int vertex=-1;
        for(int i=0;i<n;i++){
            if(min_des>d[i]&&color[i]==GRAY){
                min_des=d[i];
                vertex=i;
            }
        }
        if(vertex==-1) break;
        color[vertex]=BLACK;
        for(int i=0;i<n;i++){
            if(color[i]!=BLACK&&M[vertex][i]<INF){
                if(d[i]>d[vertex]+M[vertex][i]){
                    d[i]=d[vertex]+M[vertex][i];
                    color[i]=GRAY;
                }
            }
        }
    }
}        

int main(){
    int u,k,v,c;
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            M[i][j]=INF;
        }
        d[i]=INF;
        color[i]=WHITE;
    }
    for(int i=0;i<n;i++){
        cin>>u>>k;
        for(int j=0;j<k;j++){
            cin>>v>>c;
            M[u][v]=c;
        }
    }

    dijkstra();

    for(int u=0;u<n;u++){
        cout<<u<<' '<<d[u]<<endl;
    }
}



Measured memory_bytes: 3104
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

#define FOR(i, N) for (int i = 0; i < (int)N; i++)
#define FORIN(i, a, b) for (int i = a; i < (int)b; i++)
#define ALL(x) (x).begin(), (x).end()
#define MOD 1000000007
#define DEBUG(...) debug(__LINE__, ":" __VA_ARGS__)

using Pi = pair<int, int>;
using ll = long long;
const int INF = 1 << 28;

string to_string(string s) {
  return s;
}

template<class S,class T>
string to_string(pair<S,T> p){
	return "{"+to_string(p.first)+","+to_string(p.second)+"}";
}

template <class T>
string to_string(vector<T> v) {
  string ret = "{";
  for (int i = 0; i < v.size() - 1; ++i) {
    ret += to_string(v[i]) + ",";
  }
  if (v.size() > 0) {
    ret += to_string(v.back());
  }
  ret += "}";
  return ret;
}

void debug() {
  cerr << endl;
}

template <class Head, class... Tail>
void debug(Head head, Tail... tail) {
  cerr << to_string(head) << " ";
  debug(tail...);
}

void print() {
  cout << endl;
}

template <class Head, class... Tail>
void print(Head head, Tail... tail) {
  cout << to_string(head);
  print(tail...);
}

void get() {}

template <class Head, class... Tail>
void get(Head& head, Tail&... tail) {
  cin >> head;
  get(tail...);
}

template <class T>
void getv(vector<T>& vec) {
  for (int i = 0; i < vec.size(); ++i)
    cin >> vec[i];
}

int main() {
	int a;
	string s;
	cin>>a>>s;
	print(a<3200?"red":s);
  return 0;
}


Measured memory_bytes: 256