akhauriyash/Code-Regression huggingface dataset:
class MaxHeap():
    def __init__(self, a, h):
        self.a = a
        self.h = h
    def parent(self, i):
        return i//2
        
    def left(self, i):
        return 2 * i

    def right(self, i):
        return 2 * i + 1

    def maxHeapify(self, a, i):
        l = self.left(i)
        r = self.right(i)
        if l <= self.h and a[l] > a[i]:
            largest = l
        else:
            largest = i
        if r <= self.h and a[r] > a[largest]:
            largest = r
        if largest != i:
            a[i], a[largest] = a[largest], a[i]
            self.maxHeapify(a, largest)

    def buildMaxHeap(self, a):
        for i in range(self.h//2, 0, -1):
            self.maxHeapify(a, i)
        return a

if __name__ == '__main__':
    n = int(input().rstrip())
    a = [-1]
    a += [int(i) for i in input().rstrip().split(" ")]
    x = MaxHeap(a, n)
    for i in x.buildMaxHeap(x.a)[1:]:
        print("", i, end = "")
    print()
        

Measured memory_bytes: 65980
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;

int main()
{
	int w;
	while(cin >> w)
	{
		if(w == -1) break;
		int ans = 1150;

		REP(i,1,w+1)
		{
			if(i <= 10) continue;
			else if(i <= 20) ans += 125;
			else if(i <= 30) ans += 140;
			else ans += 160;
		}

		cout << 4280 - ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
n,q = list(map(int,input().split()))

from collections import deque
que = deque([])

for i in range(n):
    que.append((int(x) if x.isdigit() else x for x in input().split()))

totaltime = 0

while que:
    name,lefttime = que.popleft()
    if lefttime <= q:
        totaltime += lefttime
        print(name,totaltime)
    else:
        lefttime -= q
        totaltime += q
        
        que.append((name,lefttime))


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

#define INF 1e9
#define MAX_V 100005

struct edge {
    int to;
    int cost;
};

int V,E,r;
vector<edge> G[MAX_V];
int d[MAX_V];

void dijkstra(int s) {
    priority_queue<P, vector<P>, greater<P> > que;
    fill(d, d+V, INF);
    d[s] = 0;
    que.push(P(0, s));

    while (!que.empty()) {
        P p = que.top();
        que.pop();
        int v = p.second;
        if (d[v] < p.first) continue;

        for (int i=0; i<G[v].size(); ++i) {
            edge e = G[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }
}

signed main() {
    cin >> V >> E >> r;
    for(int i = 0; i < E; i++){
        int a,b,c;
        cin >> a >> b >> c;
        edge e = {b,c};
        G[a].push_back(e);
    }
    dijkstra(r);
    for(int i = 0; i < V; i++){
        if(d[i] == INF) cout << "INF" << endl;
        else cout << d[i] << endl;
    }
}


Measured memory_bytes: 19548
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int i,j,k;
int a[35],n;

int main(){
	for(i=1;i<=30;i++)a[i]=0;
	for(i=1;i<=28;i++)scanf("%d",&n),a[n]=1;
	for(i=1;i<=30;i++)if(a[i]==0)printf("%d\n",i);
	
	return 0;
}

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

int main()
{
  int n;
  cin >> n;
  vector<int> x(n);
  vector<int> y(n);
  for (int i = 0; i < n; i++)
  {
    cin >> x[i] >> y[i];
  }
  int cnt = 0;
  double ans = 0;
  vector<int> p(n);
  for (int i = 0; i < n; i++)
  {
    p[i] = i;
  }

  do
  {
    for (int i = 0; i < n - 1; i++)
    {
      double dx = x[p[i]] - x[p[i + 1]];
      double dy = y[p[i]] - y[p[i + 1]];
      ans += sqrt(dx * dx + dy * dy);
    }
    cnt++;
  } while (next_permutation(p.begin(), p.end()));

  cout << fixed << setprecision(10) << ans / cnt << endl;
}


Measured memory_bytes: 3852
#include<iostream>
#include<string>
using namespace std;
int main(){

  string S;
  long long K;
  cin>>S>>K;
  long long count=0;
  for(size_t i=0;i<=S.length()-1;i++){
  
    if(S[i]=='1'){
    
      count++;
      if(count==K){
      
        cout<<1;
        return 0;
      }
    }
    else{
    
      cout<<S[i];
      return 0;
    }
  }
  return 0;
}

Measured memory_bytes: 3592
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc=new Scanner(System.in);
        Word w=new Word(sc.next());
        int q=sc.nextInt();
        String com;
        for(int i=0;i<q;i++){
            com=sc.next();
            if(com.equals("replace")){
                w.replace(sc.nextInt(),sc.nextInt(),sc.next());
            }else if(com.equals("reverse")){
                w.reverse(sc.nextInt(),sc.nextInt());
            }else if(com.equals("print")){
                w.print(sc.nextInt(),sc.nextInt());
            }
        }
    }
}
class Word{
    private char[] c;
    Word(String s){
        this.c=s.toCharArray();
    }
    void replace(int a,int b,String r){
        for(int i=0;i<=b-a;i++)this.c[i+a]=r.charAt(i);
    }
    void reverse(int a,int b){
        char tmp;
        int i,j;
        for(i=a,j=b;i<j;i++,j--){
            tmp=this.c[i];
            this.c[i]=this.c[j];
            this.c[j]=tmp;
        }
    }
    void print(int a,int b){
        for(int i=a;i<=b;i++)System.out.printf("%c",this.c[i]);
        System.out.printf("\n");
    }
}


Measured memory_bytes: 40856
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int N=3003;
PII arr[N];
int dp[N];
int main(){
   // freopen("file.in", "r", stdin);
    int n,t;
    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;i++){
    	int a,b;
		scanf("%d%d",&a,&b);
		arr[i]=mp(a,b);	
    }
    sort(arr+1,arr+n+1);
    for(int i=1;i<=t;i++)
    	dp[i]=-INF;
    int ans=0;
    for(int i=1;i<=n;i++){
    	int a=arr[i].ff,b=arr[i].ss;
		for(int j=t-a;j>=0;j--)
			umax(dp[j+a],dp[j]+b);
		int mx=0;
		for(int j=i+1;j<=n;j++)
			umax(mx,arr[j].ss);
		for(int j=0;j<t;j++)
			umax(ans,dp[j]+mx);	
    }
    printf("%d\n",ans);
	return 0;
}


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

int main() {
    vector<vector<char>> a(3,vector<char>(3,0));
    for(int i=0;i<3;i++){
        for(int j=0; j<3; j++){
            cin >> a.at(i).at(j);
        }
    }
    cout << a.at(0).at(0) << a.at(1).at(1) << a.at(2).at(2) << endl;
}

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

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
#define RREP(i, n) RFOR(i, n, 0)
#define MFOR(i, m) for(auto i=(m).begin();i!=(m).end();i++)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((int)(x).size())

typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll << 50;

template<typename T>
void printv(vector<T> const& s) {
  REP(i, SZ(s)) {
    cout << s[i] << " ";
  }
  cout << endl;
}

int main () {
  cin.tie(0);
  cout << setprecision(10);

  int n; cin >> n;
  priority_queue<ll, vector<ll>, greater<ll>> a1;
  vll a2(n);
  priority_queue<ll> a3;
  ll su1 = 0, su2 = 0;

  REP(i, n) {
    int tmp; cin >> tmp;
    a1.push(tmp);
    su1 += tmp;
  }
  REP(i, n) cin >> a2[i];
  REP(i, n) {
    int tmp; cin >> tmp;
    a3.push(tmp);
    su2 += tmp;
  }

  vll sum1(n+1);
  sum1[0] = su1;
  REP(i, n) {
    if(a1.top() < a2[i]) {
      su1 += (a2[i] - a1.top());
      a1.pop();
      a1.push(a2[i]);
    }
    sum1[i+1] = su1;
  }

  vll sum2(n+1);
  sum2[n] = su2;
  REP(i, n) {
    if(a3.top() > a2[n-1-i]) {
      su2 += (a2[n-1-i] - a3.top());
      a3.pop();
      a3.push(a2[n-1-i]);
    }
    sum2[n-1-i] = su2;
  }

  ll ma = -LINF;
  REP(i, n+1) {
    ma = max(ma, sum1[i] - sum2[i]);
  }
  cout << ma << endl;
}


Measured memory_bytes: 4340
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
  
const int MAX = 2000001;
const int VMAX = 10000;
int A[MAX], B[MAX];   
int C[VMAX+1];
  
int main(){
    ios::sync_with_stdio(false);
         
    int n, i, j;
    cin >> n;
    
    for(i=0; i <= VMAX; i++) C[i] = 0;
  
    for(i=0; i<n; i++){
      cin >> A[i+1];
      C[A[i+1]]++;
    }
  
    for(i=1; i<=VMAX; i++){
      C[i] = C[i] + C[i-1];
    }
    for(j=1; j<=n; j++){
      B[C[A[j]]] = A[j];
      C[A[j]]--;
    }
    for(i=1;i<=n;i++){
      if(i>1) cout << " ";
      cout << B[i];
    }
    cout << "\n";
  
    return 0;
}

Measured memory_bytes: 16872
using System;

public class Hello{
    public static void Main(){

        string s = Console.ReadLine(); 
        int slen = s.Length;
        
        int A = -1;
        int Z = 0;
        for(int i = 0; i < slen; i++){
            if(s[i] == 'A' && A == -1){
                A = i;
            }else if(s[i] == 'Z'){
                Z = i;
            }else{
                //特に何もしない
            }
        }
        System.Console.WriteLine(Z-A+1);
    }
}


Measured memory_bytes: 11616
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
    
		// 整数の入力
		int x = sc.nextInt();
		int y = sc.nextInt();
        int ans = 0;
        if (x % y == 0) {
          ans = -1;
        } else {
          int i = 2;
          while(true) {
            if (i * x % y != 0) {
              ans = i * x;
              break;
            } else {
              i++;
            }
          }
        }

		// 出力
		System.out.println(ans);
	}
}

Measured memory_bytes: 23764
#include<bits/stdc++.h>
using namespace std;
int n,a[100010],b[100010];
long long ans;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	sort(a+1,a+n+1);
	if (n&1)
	{
		ans-=a[(n+1)/2]+a[(n+1)/2-1];
		for (int i=1;i<=(n+1)/2-2;i++)
		{
			ans-=a[i]*2;
		}
		for (int i=(n+1)/2+1;i<=n;i++)
		{
			ans+=a[i]*2;
		}
	}
	else
	{
		ans-=a[n/2];
		for (int i=1;i<n/2;i++)
		{
			ans-=a[i]*2;
		}
		ans+=a[n/2+1];
		for (int i=n/2+2;i<=n;i++)
		{
			ans+=a[i]*2;
		}
	}
	long long mx=ans;
	ans=0;
	reverse(a+1,a+n+1);
	for (int i=1;i<=n;i++)
	{
		a[i]=-a[i];
	}
	if (n&1)
	{
		ans-=a[(n+1)/2]+a[(n+1)/2-1];
		for (int i=1;i<=(n+1)/2-2;i++)
		{
			ans-=a[i]*2;
		}
		for (int i=(n+1)/2+1;i<=n;i++)
		{
			ans+=a[i]*2;
		}
	}
	else
	{
		ans-=a[n/2];
		for (int i=1;i<n/2;i++)
		{
			ans-=a[i]*2;
		}
		ans+=a[n/2+1];
		for (int i=n/2+2;i<=n;i++)
		{
			ans+=a[i]*2;
		}
	}
	cout<<max(mx,ans)<<endl;
	/*
	int j,k;
	j=(n+1)>>1;
	k=j-2;
	for (int i=1;i<=(n+1)/2;i++)
	{
		if (j>0 && j<=n)
		{
			b[j]=a[i];
			j+=2;
		}
		if (k>0 && k<=n)
		{
			b[j]=a[k];
			k-=2;
		}
	}
	j=
	for (int i=n;i<=n;i++)
	*/
	return 0;
}


Measured memory_bytes: 640
// Gaurav Nuti
 
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii > vii;
typedef vector<pll > vll;
#define pb push_back
#define mp make_pair 
#define ar array
#define mod 1000000007
#define F first
#define S second
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define For(i, a, b) for(__typeof (a) i=a; i<=b; i++)
#define inp_arr(a,n) for(__typeof (n) i=0; i<n; ++i) {cin>>a[i];}
#define debug_arr(a,n) {{for(__typeof (n) i=0; i<n; ++i) {cout<<a[i]<<" ";}cout<<"\n";}}
#define INF 1e9 

ll power(ll x, ll y) 
{ 
    ll res = 1;   
    while (y > 0) { 
        if (y & 1) 
            res = (res*x)%mod; 
        y = y>>1;
        x = (x*x)%mod; 
    } 
    return res%mod; 
}

ll power_without_mod(ll x, ll y) 
{ 
    ll res = 1;   
    while (y > 0) { 
        if (y & 1) 
            res = (res*x); 
        y = y>>1;
        x = (x*x); 
    } 
    return res; 
}

bool comparep(pair<ll, ll> i1, pair<ll, ll> i2){
	return (i1.S < i2.S);
} 

ll modInverse(ll a)
{
    return power(a , mod - 2);
}

vector< vector<ll>> graph;
vector<ll> num;
vector<bool> visited;
vector<ll> dist;

void bfs(int u){
    queue<ll> q;
    q.push(u);
    visited[u] = 1;
    while(!q.empty()){
        int u1 = q.front();
        q.pop();
        for(auto i = graph[u1].begin();i!=graph[u1].end();i++){
            num[*i]--;
            dist[*i] = max(dist[u1] + 1,dist[*i]);
            if(!visited[*i] && num[*i] == 0){
                visited[*i] = 1;
                q.push(*i);
            }
        }
    }
}

// int next_lunlun(ll n){
//     vector<int> digits;
//     while(n){
//         digits.pb(n%10);
//         n /= 10;
//     }
//     // reverse(digits.begin(),digits.end());
//     ll num_digits = digits.size(); 
//     int count_9 = 0;
//     for(int i: digits)
//         if(i == 9)
//             count_9++;
//     if(count_9 == num_digits)
//         return ;
//     for(int i=0;i<(num_digits-1);i++){
//         if(digits)
//     }
// }

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout); 
    #endif  
	
    ll t;
    // cin>>t;
    t = 1;
    for(ll z=0;z<t;z++){
        ll n,k;
        cin>>n>>k;
        ll a[n];
        inp_arr(a,n);
        ll dp[k+1];
        dp[0] = 0;
        for(ll i=1;i<=k;i++){
            int flag1 = 0;
            int flag2 = 0;
            for(ll j = 0;j<n;j++){
                if(i >= a[j]){
                    flag1 = 1;
                    if(dp[i - a[j]] == 0)
                        flag2 = 1;
                }
            }
            if(!flag1)
                dp[i] = 0;
            dp[i] = flag2;
            // cout<<i<<" "<<dp[i]<<"\n";
        }
        if(dp[k])
            cout<<"First";
        else
            cout<<"Second";
    }
}

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

using namespace std;
using namespace __gnu_pbds;

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

const int MAX_N = 2e5 + 5;
const int MAX_L = 20; // ~ Log N
const long long MOD = 1e9 + 7;
const long long INF = 1e9 + 7;
const double EPS = 1e-9;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;

#define LSOne(S) (S & (-S))
#define isBitSet(S, i) ((S >> i) & 1)



void solve() {
    int n, k; cin >> n >> k;
    int arr[n]; for (int i = 0; i < n; i++) cin >> arr[i];
    sort(arr, arr + n);
    int ans = 0;
    for (int i = 0; i < k; i++) ans += arr[i];
    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif // LOCAL

    int tc; tc = 1;
    for (int t = 1; t <= tc; t++) {
        //cout << "Case #" << t  << ": ";
        solve();
    }
}


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

int main() {
  int a,b;
  cin >> a >> b;
  if(a >= 13){
    cout << b << endl;
  }
  else if(a >= 6){
    cout << b/2 << endl;
  }
  else{
    cout << 0 << endl;
  }
}


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

int main() {
  string str;
  int begin,end;

  cin >> str;
  for(int i = 0;i < str.size();i++){
    if(str.at(i) == 'A'){
      begin = i;
      break;
    }
  }
  
  for(int i = str.size() - 1;i > 0;i--){
    if(str.at(i) == 'Z'){
      end = i;
      break;
    }
  }
  cout << end - begin + 1 << endl;
}


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

template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}

#define EPS (1e-7)
#define INF (1e9)
#define LLINF (1e18)
#define PI (acos(-1))
#define MOD (1000000007)
#define ALL(v) (v).begin(), (v).end()
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

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

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll s;
    cin >> s;
    ll x[3];
    ll y[3];
    x[2] = 0;
    y[2] = 0;
    x[1] = 1e9;
    y[1] = 1;
    x[0] = s % 1000000000;
    if (x[0] != 0)
    {
        x[0] = 1000000000 - x[0];
    }
    y[0] = (s + x[0]) / 1e9;
    for (int i = 0; i < 3; i++)
    {
        cout << x[i] << ' ' << y[i] << ' ';
    }
    cout << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(int argc, char const *argv[])
{
	long long n;
	cin >> n;
	if (n & 1)
		cout << 0 << '\n';
	else
	{
		n >>= 1;
		long long cnt = 0;
		for (long long i = 5; (n / i) >= 1; i*=5)
		{
			cnt += (n / i);
		}
		cout << cnt << '\n';
	}
	return 0;
}

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

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

    // cout << (a / b) << " " << (a % b) << " " << ((float)a / b) << endl; 
    printf("%d %d %.8lf\n", (a/b), (a%b), ((double)a/b));
}


Measured memory_bytes: 3152
#include <bits/stdc++.h>
#define int long long
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
  
signed main() {
    fast;
    int tot;
    cin>>tot;
    double x=tot/3.0;
    double vol=x*x*x;
    printf ("%lf\n",vol);
}


Measured memory_bytes: 256
#include <cstdio>

int main()
{
    int a,b,c;
    scanf("%d %d %d", &a, &b, &c);
    if (a == b)
    {
        printf("%d", c);
    }
    else if (b == c)
    {
        printf("%d", a);
    }
    else
    {
        printf("%d", b);
    }
    return 0;
}

Measured memory_bytes: 128
package main
import "fmt"
func main() {
  var k,n,i,j int64
  var a []int64
  fmt.Scan(&k)
  n = k
  if n > 50 { n = 50 }
  if n < 2 { n = 2 }
  a = make([]int64,n)
  for i=0;i<n;i++ { a[i] = i+k/n }
  k %= n
  for i=0;i<k;i++ {
    a[i] += n+1
    for j=0;j<n;j++ {
      a[j]--
    }
  }
  fmt.Println(n)
  fmt.Print(a[0])
  for i=1;i<n;i++ {
    fmt.Print(" ")
    fmt.Print(a[i])
  }
  fmt.Println()
}

Measured memory_bytes: 512
def A(i,x):
 while i<n+2:t[i]+=x;i+=i&-i
(n,q),c,*z=[[*map(int,t.split())]for t in open(0)]
a=[0]*q
j,*b=t=[0]*9**6
for i,(l,r)in sorted(zip(range(q),z),key=lambda x:x[1][1]):
 while j<r:d=c[j];j+=1;A(b[d]+1,1);b[d]=j;A(j+1,-1)
 while l:a[i]+=t[l];l-=l&-l
print(*a)

Measured memory_bytes: 244100
#include <bits/stdc++.h>
#define rep(i,s,n) for (int i=s;i<n;++i)
#define drep(i,s,n) for (int i=n;i>=s;--i)
#define all(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define print(x) cout<<(x)<<endl
using namespace std;
typedef long long ll;
int gcd(int a,int b)
{if (a%b == 0) return(b);
 else          return(gcd(b,a%b));}
int lcm(int a,int b)
{return a*b/gcd(a,b);}
void printv(vector<auto> v) {cout<<'[';rep(i,0,v.size()){cout<<v[i]<<',';}cout<<']'<<endl;}
void printvv(vector<vector<auto>> vv)
{
  cout<<'['<<endl;
  rep(q,0,vv.size()){cout<<'[';rep(p,0,vv.at(q).size())cout<<vv.at(q).at(p)<<',';cout <<']'<<endl;}
  cout<<']'<<endl;
}
void solve(); int main(){cin.tie(0);ios::sync_with_stdio(0);solve();}
int step_x[] = {-1,0,0,1};
int step_y[] = {0,-1,1,0};
const long long INF = 1000000;
//------------------------------------------------------------
ll n,k;
void solve()
{
    cin >> n>>k;
    ll ans=0;

    for(ll i=k; i<n+2; i++)
    {
      ll min = i*(i-1)/2;
      ll max = i*(2*n-i+1)/2;
      ans += max-min+1;
      ans %= 1000000007;
    }

    print(ans);

    return;
}



Measured memory_bytes: 3644
N = int(input())
ans = 0
Bx = 0
BA = 0
xA = 0
for i in range(N):
    s = input()
    ans += s.count('AB')
    if s[0] == 'B' and s[-1] == 'A':
        BA += 1
    elif s[0] == 'B':
        Bx += 1
    elif s[-1] == 'A':
        xA += 1
if BA > 0:
    ans += (BA - 1)
    if Bx > 0:
        ans += 1
        Bx -= 1
    if xA > 0:
        ans += 1
        xA -= 1
ans += min(Bx, xA)
print(ans)


Measured memory_bytes: 3064
#include "bits/stdc++.h"
using namespace std;
const int MOD = 1e9 + 7;
typedef long long lint;
typedef pair<int, int> P;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define rep(i, n) for (lint i = 0; i < (n); i++)
#define INF LLONG_MAX
#define all(x) (x).begin(), (x).end()
#define pb push_back
int main()
{
    lint a;
    double b;
    cin >> a >> b;
    lint c = lint(b * 100 + 0.001);
    cout << a * c / 100 << endl;

    return 0;
}


Measured memory_bytes: 3732
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
int num[maxn];
int cmd(int a,int b) {
	return a>b;
}
int main() {
	int n;
	while(~scanf("%d",&n)) {
		for(int i=0; i<n; i++)
			scanf("%d",&num[i]);
		sort(num,num+n);
		int m=num[n-1];
		int posa=lower_bound(num,num+n,m/2)-num;
		int a=num[posa];
		sort(num,num+n,cmd);
		int posb=lower_bound(num,num+n,m/2,greater<int>())-num;
		int b=num[posb];
		int ans;
		if((m-a)>b)
			ans=a;
		else
			ans=b;
		printf("%d %d\n",m,ans);
	}
	return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <map>
#include <math.h>
#include <algorithm> // std::sort, std::min
#include <iomanip> // std::setprecision
#include <cmath> // std::ceil
#include <numeric>

int main() {
  long int K;
  std::cin >> K;

  long long int sum = 0;
  for (int i=1; i<=K; ++i) {
    for (int j=1; j<=K; ++j) {
      for (int k=1; k<=K; ++k) {
        sum += std::gcd(std::gcd(i, j), k);
      }
    }
  }
  std::cout << sum << std::endl;
  
  return 0;
}


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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  vector<int> A(N);
  vector<vector<int>> X(N), Y(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    for (int j = 0; j < A[i]; j++) {
      int x, y;
      cin >> x >> y;
      X[i].emplace_back(x - 1);
      Y[i].emplace_back(y);
    }
  }
  int res = 0;
  for (int bit = 0; bit < (1 << N); bit++) {
    int cnt = 0;
    for (int i = 0; i < N; i++) {
      if (!((bit >> i) & 1)) continue;
      for (int j = 0; j < A[i]; j++) {
        if (((bit >> X[i][j]) & 1) != Y[i][j]) cnt = -(1 << 28);
      }
      cnt++;
    }
    res = max(res, cnt);
  }
  cout << res << '\n';
  return 0;
}


Measured memory_bytes: 256
a = int(input())
s = 0
A=B=AB=0

d = {"A":0,"B":0}
for i in range(a):
    t = input()
    s+=t.count("AB")
    if t[0]=="B" and t[-1]=="A":AB+=1
    elif t[0]=="B":B+=1
    elif t[-1]=="A":A+=1
res = 0
if A==0 and B == 0 and AB >0:
    res = AB-1
elif A==0 and B == 0:
    res = 0 
elif A==1 and B == 0:
    res = AB
elif A==0 and B ==1:
    res = AB
else:
    res = AB+1 + min(A-1,B-1)
print(res+s)

Measured memory_bytes: 44008
[n,a,b] = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]
ans = 0
for i in range(n-1):
    distance = x[i+1] - x[i]
    if distance*a < b:
        ans += distance * a
    else:
        ans += b
print(ans)


Measured memory_bytes: 62832
import sys
input = sys.stdin.readline
n=int(input())
c=[[] for i in range(n+1)]
d={}
for i in range(n-1):
    x,y,z=map(int,input().split())
    c[x].append(y)
    c[y].append(x)
    d[x,y]=z
d[1,1]=0
stack=[1]
parent=[None]*(n+1)
while stack:
    i=stack.pop()
    for j in c[i]:
        if j==parent[i]:
            continue
        parent[j]=i
        d[1,j]=d[1,i]+d[tuple(sorted([i,j]))]
        stack.append(j)
for i in range(1,n+1):
    print(d[1,i]%2)

Measured memory_bytes: 57692
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<long>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvb = vector<vector<bool>>;
using vvc = vector<vector<char>>;
using pii = pair<int, int>;
using pil = pair<int, long>;
using pll = pair<long, long>;
#define fix20 cout << fixed << setprecision(20)
#define YES cout << "Yes" << endl
#define NO cout << "No" << endl
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,s,t) for(int i=s; i<t; i++)
#define RNG(i,s,t,u) for(int i=s; i<t; i+=u)
#define MOD 1000000007
#define all(vec) vec.begin(), vec.end()

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

Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cmath>
#include <string>
#include <stdlib.h>
#include <fstream>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <iterator>
#include <iomanip>
using namespace std;

int main(){
    long long n;
    cin >> n;
    vector<long long> a(n + 1);
    for(int i = 1; i <= n; ++i) cin >> a[i];
    vector<long long> p(n + 1), d(n + 1);
    p[1] = a[1];
    for(int i = 2; i <= n; ++i) p[i] = p[i - 2] + a[i];

    for(int i = 2; i <= n; ++i){
        if(i % 2){
            d[i] = max(d[i - 1], d[i - 2] + a[i]);
        }
        else{
            d[i] = max(p[i - 1], d[i - 2] + a[i]);
        }
    }

    cout << d[n];
}


Measured memory_bytes: 8000
import java.util.*;
import java.io.*;
class Main
{
    public static void main(String args[])
    {
        Scanner sc= new Scanner(System.in);
        String  a=sc.next();
        String  b = sc.next();
        String s =a+b;
        int n =Integer.parseInt(s);
        if(Math.sqrt(n)-(int)(Math.sqrt(n))==0)
        System.out.println("Yes");
        else
        System.out.println("No");
    }
}

Measured memory_bytes: 21716
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		//ループ回数記録用変数
		int i = 1;
		
		//データの入力
		Scanner sc = new Scanner(System.in);
		while(true){
			
			int inputData = sc.nextInt();
			
			//終了条件の判定
			if(inputData == 0){
				break;
			}
			
			//結果を出力
			System.out.println("Case " + i + ": " + inputData);
			
			i++;
		}
	}
}


Measured memory_bytes: 41748
# Wrote in Mar 5, 2020 11:24 by reetok
require 'time'
require 'prime'
require 'bigdecimal'
def inp(type=:to_i,spst=" ")
  return eval("gets.chomp.split(#{spst}).map(&:#{type})")
end
def inpf() return self.inp(:to_f," ") end
def inps() return self.inp(:to_s," ") end
def r_up(a, b) (a/b).ceil end
def r_down(a, b) (a/b).floor end
def sum(a) a.inject(:+) end
def big(a,b) return (a>b)? a:b end
def small(a,b) return (a<b)? a:b end
def minp(n,datatype=:to_i)
  t = []
  n.times do
    t.push(eval("gets.chomp.#{datatype.to_s}"))
  end
end
def yes() puts "Yes" end
def no() puts "No" end
def ynju(bool,yes="Yes",no="No") puts (bool ? yes : no) end
class Integer
  def divisor_list
    devisors = [1]
    2.upto(self/2) do |i|
      devisors << i if self%i == 0
    end
    devisors << self
    return devisors.uniq.sort
  end
end
class Array
  def upper(a) #aより上
    self.sort.select{|n|n>=a}
  end
  def downer(a) #aより下
    self.sort.select{|n|n<=a}
  end
end

#---------------

while (h,w=inp)!=[0,0]
  h.times do
    puts "#" * w
  end
  puts "\n"
end



Measured memory_bytes: 7240
#include<stdio.h>

main(){

int n,m,i,j,a[100][100],b[100],c[100];

scanf("%d %d",&n,&m);

for(i=0;i<n;i++){
for(j=0;j<m;j++){
 scanf("%d",&a[i][j]);
}
}

for(j=0;j<m;j++){
 scanf("%d",&b[j]);
}

for(i=0;i<n;i++){
for(j=0;j<m;j++){
c[i] = c[i] + a[i][j]*b[j];
}
printf("%d\n",c[i]);

}

return 0;
}



Measured memory_bytes: 2140
hight = []
width = []
num = 0

while True:
    H,W = list(map(int,input().split()))
    if H==0 and W==0:
      break
    else:
      hight.append(H)
      width.append(W)
      num += 1

for i in range(num):
    for j in range(hight[i]):
      for k in range(width[i]):
       print("#",end="")
      print("")
    print("")



Measured memory_bytes: 7012
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		int min = 1;
		for(int i = 0;i < N;i ++) {
			min = min * 2;
		}
		for(int i = N - 1;i >= 0;i --) {
			int x = 1;
			for(int k = 0;k < i;k ++) {
				x = x * 2; 
			}
			for(int k = 0;k < N - i;k ++) {
				x += K;
			}
			if(x < min) min = x;
		}
		System.out.println(min);
	}
}

Measured memory_bytes: 21972
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <random>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
#define repl(i,n) for (long long i = 0; i < (n); ++i)
#define reppl(i,n,m) for (long long i = m; i < (n); ++i)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PL = pair<long long, long long>;
using Pxy = pair<double, double>;
using T = tuple<int, int, bool>;
const int INF = 1001001007;
const int mod = 1000000007;
const int MOD = 998244353;
const ll inf = 1e18;
template <typename AT>
void printvec(vector<AT> &ar){
    rep(i,ar.size()-1) cout << ar[i] << " ";
    cout << ar[ar.size()-1] << endl;
}
template <typename Q>
void printvvec(vector<vector<Q>> &ar){
    rep(i,ar.size()){
        rep(j,ar[0].size()-1) cout << ar[i][j] << " ";
        cout << ar[i][ar[0].size()-1] << endl;
    }
}
template <typename S>
bool range(S a, S b, S x){
    return (a <= x && x < b);
}

void yn(int o){
    if (o == 0) cout << "No" << endl;
    else cout << "Yes" << endl;
}

int main() {
    int n, k; cin >> n >> k;
    int ans = 1;
    rep(i,n){
        ans += min(ans,k);
    }
    cout << ans << endl;
}

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

using namespace std;
typedef long long ll;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mp make_pair
#define pb push_back
#define lp(i,s,f) for(ll i = s; i < ll(f); i++)
#define inF freopen("input.in", "r", stdin);
#define outF freopen("output.in", "w", stdout);
#define endl '\n'
#define MOD 1000000007
#define mm(arr) memset(arr, 0, sizeof(arr))

int main(){
    FAST
    string s, t; cin >> s >> t;
    int n = t.size();
    int ans = 1e9;
    for(int i = 0; i + n - 1 < s.size(); i++){
        int cnt = 0;
        int r = 0;
        for(int j = i; j < i + n; j++){
            if(s[j] != t[r]){
                cnt++;
            }
            r++;
        }
        ans = min(ans, cnt);
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3652
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()
if S.count('R') > S.count('B'):
    print('Yes')
else:
    print('No')


Measured memory_bytes: 13668
import sys

for line in sys.stdin:
    n = [int(i) for i in line.replace("\n", "").split(" ")]
    n.sort()
    low = n[0]
    hi = n[1]
    while hi % low:
        hi, low = low, hi % low
    print("%d %d" % (low, n[0] / low * n[1]))

Measured memory_bytes: 7608
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
        ifstream in("input.txt");
        //ofstream out("output.txt");
        #define cin in
        //#define cout out
#endif
int const MAXN=210000;
long long int n, h[MAXN], b[MAXN], tree[MAXN];
long long int query(int index){
	long long int res=0LL;
	while(index>0){
		res=max(res,tree[index]);
		index-=index&(-index);
	}
	return res;
}
void update(int index, long long int val){
	while(index<=n+10){
		tree[index]=max(tree[index],val);
		index+=index&(-index);
	}
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>h[i];
	for(int i=0;i<n;i++)
		cin>>b[i];
	for(int i=0;i<n;i++){
		long long int best=query(h[i]);
		update(h[i],best+b[i]);
	}
	cout<<query(n+5);
}

Measured memory_bytes: 5120
# ENV[Z = 'RUBY_THREAD_VM_STACK_SIZE'] || exec( { Z => '50000000' },'ruby',$0)
# readlines.map(&:chomp!).map { |e| e.split.map(&:to_i) }
# gets.split.map(&:to_i)
#
#
n = gets.to_i
card = gets.split.map(&:to_i)

s = 0
card.sort.reverse.each_with_index do |c,i|
  if i%2 == 0
    s += c
  else
    s -= c
  end
end

puts s


Measured memory_bytes: 3836
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <set>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,j) FOR(i,0,j)
#define mp std::make_pair

const int INF = 1 << 24;
const int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1}, dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};

typedef unsigned long long ull;
typedef std::pair<int,int> P;

int main(){
    int table[246913];
    std::fill(table, table+246913, 1);

    table[0] = 0;
    table[1] = 0;

    for(int i=4;i<=246913;i+=2){
        table[i] = 0;
    }

    for(int i=3;i<=246913;i+=2){
        if(table[i]){
            for(int j=i*2;j<=246913;j+=i){
                table[j] = 0;
            }
        }
    }

    for(int i=1;i<=246913;i++){
        table[i] += table[i-1];
    }

    int N;
    while(std::cin >> N, N){
        std::cout << table[2*N] - table[N] << std::endl;
    }
}

Measured memory_bytes: 2124
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<sstream>
#include<string>
#include<numeric>
using namespace std;
typedef long long ll;
ll mod = 1e9+7;
//ll mod = 998244353;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main(){
    string s;
    cin >> s;
    ll ret = 0;
    int cnt = 0;
    int n = s.length();
    rep(i, n) {
        if ( s[i] == 'A' ) ++cnt;
        else if ( s[i] == 'B' ) {
            if ( i + 1 < n && s[i+1] == 'C' ) {
                ret += cnt;
                ++i;
            }
            else cnt = 0;
        }
        else cnt = 0;

    }
    cout << ret << endl;
    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=5e18;
 
int main() {
  string s;
  ll d;
  cin >> s >> d;
  ll k=s.size();
  mat dp0(k+1,vec(d));
  mat dp1(k+1,vec(d));
  dp0[0][0]=1;
  for(ll i=0;i<k;i++) {
    for(ll j=0;j<d;j++) {
      ll nj0=(j+(s[i]-'0'))%d;
      (dp0[i+1][nj0]+=dp0[i][j])%=mod;
      for(ll n=0;n<=9;n++) {
        ll nj=(j+n)%d;
        if(n<(s[i]-'0')) {
          (dp1[i+1][nj]+=dp0[i][j])%=mod;
        }
        (dp1[i+1][nj]+=dp1[i][j])%=mod;
      }
    }
  }
  cout << (dp0[k][0]+dp1[k][0]-1+mod)%mod << endl;
}

Measured memory_bytes: 16640
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void _main()
{
    int N, T, A;
    cin >> N >> T >> A;
    int H;
    int ans = -1;
    double minAbs = 1000000.0;
    rep(i, 0, N)
    {
        cin >> H;
        const double t = T - H * 0.006;
        if (chmin(minAbs, abs(t - A)))
        {
            ans = i;
        }
    }
    cout << ans + 1 << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){

	long N;
	
	long A[100001];
	
	long i,j,t;
	
	int ret;
	
	ret = scanf("%ld",&N);
	
	for (i=1; i<=N; i++){
		
		scanf("%ld",&t);
		
		A[t]=i;
		
		//printf("A[%ld]=%ld\n",i,A[i]);
		
	}
	
	for (i=1; i<=(N); i++){
		
		printf("%ld ",A[i]);
		
	}
	

}


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

using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define ll long long int
#define INF 1000000007
#define llINF 1000000000000000007
#define v(i) vector<i>
#define vv(i) vector<vector<i>>
// cin.eof() 入力個数の問題
// int num = atoi(string.c_str()); 文字列の整数変換
int keta(ll n){int ans=0;while(n>0){n /= 10; ans++;}return ans;}
ll _pow(ll a,ll b){ll ans = 1;rep(i,b){ ans *= a;}return ans;}

int main() {
   int a,b; cin>>a>>b;
   int ans=0;
   for(int i = a; i <= b;i++){
       if(i/10000 == i%10 && (i-(i/10000)*10000)/1000 == (i%100)/10 ) ans++;
           
       }
   
   cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3568
# D - Line++

N, X, Y = map(int, input().split())
X -= 1
Y -= 1
cnt = [0] * N

for i in range(N):
    for j in range(i+1,N):
         tmp = min(j-i, abs(i-X)+abs(j-Y)+1)
         cnt[tmp] += 1

for k in range(1, N):
    print(cnt[k])

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

using namespace std;

int main()
{
	string str;
	cin >> str;
	do {
		
		int n;
		cin >> n;
		int total = 0;
		int temp = 0;

		while (n--) {
			cin >> temp;
			total += temp;
		}
		temp = total % str.size();
		cout << str.substr(temp) << str.substr(0, temp) << endl;
	} while (cin >> str, str != "-");

	return 0;
}

Measured memory_bytes: 3124
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include <functional>
#include<time.h>
#include <stack>
#include<iomanip>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define ll long long
#define llint long long int
#define reverse(v)  reverse(v.begin(), v.end());
#define Yes(ans) if(ans)cout<<"Yes"<<endl; else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define hei(a) vector<a>
#define whei(a) vector<vector<a>>
#define UF  UnionFind 
#define Pint pair<int,int>
#define keta(a)  fixed << setprecision(a)
constexpr auto INF = 100000000000;
constexpr auto mod = 1000000007;
//辞書順はnext_permutation( begin( v ), end( v ) );やで！
struct edge { int to, cost; };

//sは初めの点、vは頂点size、dは最短距離を求める(初期化はINF),Gは有向グラフ
void dijkdtra(int s,int v,vector<int>&d,whei(edge)&G) {
	priority_queue<Pint, vector<Pint>, greater<Pint>> que;//firstが距離、secondが頂点
	d[s] = 0;//スタートの距離はもちろんzero
	que.push(Pint(0, s));
	while (!que.empty()) {
		Pint p = que.top();
		que.pop();
		int V = p.second;
		if (d[V] < p.first)continue;
		for (int i = 0; i < G[V].size();i++) {
			edge e = G[V][i];
			if (d[e.to] > d[V] + e.cost) {
				d[e.to] = d[V] + e.cost;
				que.push(Pint(d[e.to], e.to));
			}
		}
	}
}

int main() {
	int n;
	cin >> n;
	hei(llint) s(n + 1,0);
	rep(i, 0, n) {
		llint a;
		cin >> a;
		s[i + 1] = s[i] + a;
	}
	sort(s.begin(), s.end());
	llint ans = 0;
	llint x = 1;
	s.push_back(INF);
	rep(i, 0, n+1) {
		if (s[i] == s[i + 1])x++;
		else {
			ans += (x * (x - 1)) / 2;
			x = 1;
		}
	}

	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4736
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define int long long
#define INF 1000000000000000000
using namespace std;

#define ANS(f) if(f) cout << "YES" << endl; else cout << "NO" << endl;

typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int, int> Pii;

template<typename T>
void readv(vector<T> &a){ REP(i, a.size()) cin >> a[i]; }
void readi(vector<int> &a){ REP(i, a.size()){cin >> a[i]; a[i]--;} }
void debug(mat m){REP(i, m.size()){ REP(j, m[i].size()){ cout << m[i][j] << ","; } cout << endl; }}



signed main(){

    int N, W; cin >> N >> W;
    vec w(N), v(N);
    REP(i, N) cin >> w[i] >> v[i];
    mat dp(N + 1, vec(W + 1, -INF));
    REP(j, W + 1) dp[0][j] = 0;
    REP(i, N){
        REP(j, W + 1){
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
            if(j + w[i] <= W) dp[i + 1][j + w[i]] = max(dp[i + 1][j + w[i]], dp[i][j] + v[i]);
        }
    }
    cout << dp[N][W];
    
    return 0;
}

Measured memory_bytes: 80256
s = str(input())
N = len(s)
kai = 0
for i in range(int((N+1)/2)-1):
    if s[i] == s[int(i+(N+1)/2)] and kai == 0:
        kai = 0
    else:
        kai = 1

if kai == 0:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << endl;
#define CFYN(n) cout << ( (n) ? "YES":"NO") << endl;
using ll = long long;
using ull = unsigned long long;

int main(void)
{
    IOS
    int n, k;
    cin >> n >> k;
    vector<vector<int>> v(n,vector<int>());
    deque<int> su;      // 種類別1個目
    deque<int> deq;     // 2個目以降
    REP(i,n) {
        int t, d; cin >> t >> d;
        t--;
        v[t].emplace_back(d);
    }
    REP(i,n) sort(RALL(v[i]));
    
    ll ans = 0;
    REP(i,n) {
        if (!v[i].empty()) {
            ans += v[i].front();
            su.emplace_back(v[i].front());
            FOR(j,1,v[i].size()) deq.emplace_back(v[i][j]);
        }
    }

    sort(ALL(deq));
    sort(RALL(su));

    ll d2 = 0;
    ll kind = su.size();
    if ( kind > k ) {
        while (kind > k) {
            ans -= su.back();
            kind--;
            su.pop_back();
        }
    } else if (kind < k) {
        FOR(i,kind,k) {
            d2 += deq.back();
            deq.pop_back();
        }
    }

    while(!deq.empty()) {
        ll a1 = kind * kind + ans + d2;
        ll a2 = (kind-1) * (kind-1) + ans + d2 - su.back() + deq.back();
        if (a1 < a2) {
            kind--;
            ans -= su.back();
            su.pop_back();
            d2 += deq.back();
            deq.pop_back();
        } else break;
    }
    //cerr << kind << " " << ans << " " << d2 << endl;
    cout << kind * kind + ans + d2 << endl;

    return 0;
}

Measured memory_bytes: 6144
#include<stdio.h>

int main(void)
{
    int A=0;
    int B=0;
    int T=0;
    int count=0;

    scanf("%d%d%d",&A,&B,&T);
    if(((A<1||A>20)||(B<1||B>20))||(T<1||T>20)){
        goto end;
    }

    int i=A;
    while(i<=T+0.5){
        i+=A;
        count+=1*B;
        //printf("%d,%d\n",A,count);
    }

    printf("%d\n",count);
    end:
    return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
int main()
{
int N,K,S,i,h[100000];
S=0;
scanf("%d%d", &N,&K);
for(i=0;i<=N;i++){
	scanf("%d",&h[i]);
	if(h[i]>=K)
		S++;
}
printf("%d",S);
}

Measured memory_bytes: 512
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int a, b;
	char op;
	cin >> a >> op >> b;
	if (op == '+') cout << a + b << endl;
	else cout << a - b << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    long[] a = new long[n];
    for(int i = 0; i < n; i++) {
      a[i] = sc.nextLong();
    }
    long[] rui = new long[n];
    rui[0] = a[0];
    for(int i = 1; i < n; i++) {
      rui[i] = (rui[i - 1] + a[i]);
    }
    int[] l = new int[n];
    int[] r = new int[n];
    int p = 0;
    for(int i = 1; i < n - 2; i++) {
      int t = p;
      int m = 0;
      for(int j = p; j < i; j++) {
        long s1 = rui[j];
        long s2 = rui[i] - rui[j];
        if(s1 >= s2) {
          t = j;
          if(j == p) m = 1;
          break;
        }
      }
      if(t == p) {
        if(m == 0) {
          l[i] = (i - 1);
          p = (i - 1);
        }
        if(m == 1) {
          l[i] = p;
        }
      } else {
        if(Math.abs(rui[i] - rui[t] - rui[t]) >= Math.abs(rui[i] - rui[t - 1] - rui[t - 1])) {
          l[i] = (t - 1);
          p = (t - 1);
        } else {
          l[i] = t;
          p = t;
        }
      }
    }
    p = 2;
    for(int i = 1; i < n - 2; i++) {
      int t = p;
      int m = 0;
      for(int j = p; j <= n - 2; j++) {
        long s1 = rui[j] - rui[i];
        long s2 = rui[n - 1] - rui[j];
        if(s1 >= s2) {
          t = j;
          if(j == p) m = 1;
          break;
        }
      }
      if(t == p) {
        if(m == 0) {
          r[i] = n - 2;
          p = (n - 2);
        }
        if(m == 1) {
          r[i] = p;
        }
      } else {
        if(Math.abs(rui[n - 1] - rui[t] - rui[t] + rui[i]) >= Math.abs(rui[n - 1] - rui[t - 1] - rui[t - 1] + rui[i])) {
          r[i] = (t - 1);
          p = (t - 1);
        } else {
          r[i] = t;
          p = t;
        }
      }
    }
    long ans = Long.MAX_VALUE;
    for(int i = 1; i < n - 2; i++) {
      long s1 = rui[l[i]];
      long s2 = rui[i] - rui[l[i]];
      long s3 = rui[r[i]] - rui[i];
      long s4 = rui[n - 1] - rui[r[i]];
      long ma = Math.max(s1, s2);
      ma = Math.max(ma, s3);
      ma = Math.max(ma, s4);
      long mi = Math.min(s1, s2);
      mi = Math.min(mi, s3);
      mi = Math.min(mi, s4);
      ans = Math.min(ans, ma - mi);
    }
    System.out.println(ans);
  }
}


Measured memory_bytes: 94468
#include <bits/stdc++.h>
#ifdef TOPOLOGY
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...)
#endif
using namespace std;

int a[4], n, no[4];

int main() {
	cin >> a[0] >> a[1] >> a[2] >> a[3] >> n;
	for (int i = 0; i < 4; i++) {
		int tmp = a[i];
		for (int j = i + 1; j < 4; j++) {
			tmp <<= 1;
			if (tmp < a[j]) no[j] = 1;
		}
	}
	long long ans = 0;
	long long m = 4LL * n;
	for (int i = 3; i >= 0; i--) {
		if (no[i]) continue;
		ans += (m >> i) * a[i];
		m %= (1 << i);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
   int a,b,c,d,m,n;

   scanf("%d",&a);
   scanf("%d",&b);
   scanf("%d",&c);
   scanf("%d",&d);

   if(a>=b) m=b;
      else m=a;
   if(c>=d) n=d;
      else n=c;

   printf("%d",m+n);

   return 0;
}



Measured memory_bytes: 128
def gcd(a, b):
    while b:
        a, b = b, a % b
    return(a)

T = int(input())
for i in range(T):
    A,B,C,D = map(int,input().split())
    if B > D:
        print('No')
    elif A < B:
        print('No')
    elif C + 1 >= B:
        print('Yes')
    else:
        q = gcd(B,D)
        r = (A-C)%q
        if r == 0:
            r = q
        if C + r >= B:
            print('Yes')
        else:
            print('No')

Measured memory_bytes: 3064
def gcd(x,y):
    if x < y:
        x,y = y,x
        
    if y == 0:
        return x
    else:
        return gcd(y,x%y)

def lcm(x,y):
    return (x*y)//gcd(x,y)

a,b,c,d = map(int,input().split())

al = b-a+1

cnt_c = b//c - (a-1)//c 

cnt_d = b//d - (a-1)//d 

cnt_t = b//lcm(c,d) - (a-1)//lcm(c,d) 

print(al - cnt_c - cnt_d + cnt_t)

Measured memory_bytes: 9152