akhauriyash/Code-Regression huggingface dataset:
using System.Text;
using static System.Math;
using System.Collections.Generic;
using System;

public class hello
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine().Trim());
        var tab = new List<int>();
        var tp = new List<int>();
        for (int i = 0; i < n; i++)
        {
            string[] line = Console.ReadLine().Trim().Split(' ');
            var a = int.Parse(line[0]);
            var b = int.Parse(line[1]);
            var g = int.Parse(line[2]);
            for (int j = a; j <= b; j++)
            {
                tab.Add(j);
                tp.Add(g);
            }
        }
        tab.Add(0); tp.Add(0);
        var L = tab.ToArray();
        var good = tp.ToArray();
        var m = int.Parse(Console.ReadLine().Trim());
        var q = new int[m];
        var qmax = 0;
        for (int i = 0; i < m; i++)
        {
            var w = int.Parse(Console.ReadLine().Trim());
            q[i] = w;
            qmax = Max(qmax, w);
        }
        var LL = L.Length;

        var dp = new int[LL + 1, qmax + 1];
        for (int i = 0; i < LL; i++)
            for (int j = 0; j <= qmax; j++)
                if (j < L[i]) dp[i + 1, j] = dp[i, j];
                else dp[i + 1, j] = Max(dp[i, j], dp[i + 1, j - L[i]] + good[i]);
        var ans = new int[m];
        var sb = new StringBuilder();
        for (int i = 0; i < m; i++)
        {
            var tw = dp[LL, q[i]];
            if (tw == 0) { Console.WriteLine(-1); goto exit; }
            else sb.Append(string.Format("{0}\n", tw));
        }
        Console.Write(sb);
        exit:;
    }
    public static void readData(int[] good, int[] L)
    {
        for (int i = 0; i < good.Length - 1; i++)
        {
            string[] line2 = Console.ReadLine().Trim().Split(' ');
            good[i] = int.Parse(line2[0]);
            L[i] = int.Parse(line2[1]);
        }
    }
}


Measured memory_bytes: 259780
#include<iostream>

using namespace std;

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

int main() {
  int edge[6][2];
  edge[0][0] = 1;
  edge[0][1] = 2;
  edge[1][0] = -1;
  edge[1][1] = 3;
  edge[2][0] = 1;
  edge[2][1] = -1;
  edge[3][0] = 4;
  edge[3][1] = 5;
  edge[4][0] = 5;
  edge[4][1] = 2;
  edge[5][0] = 2;
  edge[5][1] = 1;
  string str;
  while (true) {
    cin >> str;
    if (str == "#") break;
    int pos = 0;
    try{
      rep (i, str.size()) {
	pos = edge[pos][str[i] - '0'];
	if (pos == -1) throw 1;
      }
      cout << (pos == 5 ? "Yes" : "No") << endl;
    } catch(int n) {
      cout << "No" << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1240
n,m = map(int,input().split())
a = [[0 for i in range(m)] for j in range(n)]
b = [0 for i in range(m)]
i = 1
while i <= n:
    row = list(map(int,input().split()))
    a[i-1] = row
    i +=1

i = 1
while i <= m:
    bi = int(input())
    b[i-1] = bi
    i+=1

for i in range(n):
    res = 0
    for j in range(m):
        res =  res + a[i][j]*b[j]
    print(res)
    


Measured memory_bytes: 5964
import java.util.*;
public class Main
{public static void main(String arg[]){Scanner in=new Scanner(System.in);for(;;){
            int N=in.nextInt();
            int M=in.nextInt();
            if((N|M)==0)
                return;
            int a[]=new int[101];
            for(int i=0;i<N;i++)
            {
                int m=in.nextInt();
                for(int j=0;j<m;j++)
                    a[in.nextInt()]++;
            }
            int t=0;
            for(int i=1;i<=100;i++)
                if(a[t]<a[i])
                    t=i;
            if(a[t]>=M)
                System.out.println(t);
            else
                System.out.println(0);
        }
    }
}

Measured memory_bytes: 12000
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		
		//long startTime = System.currentTimeMillis();
		
		Scanner sc=new Scanner(System.in);
		String moji=sc.next();
		char[] c=moji.toCharArray();
		int size=moji.length();
		
		int orikaeshi;
		if(size%2==0)orikaeshi=size/2-1;
		else orikaeshi=(size-1)/2-1;
		
		int count=0;
		
		for(int i=0;i<=orikaeshi;i++){
			if(c[i]!=c[size-1-i]){
				count++;
				//System.out.println(c[i]);
			}
		}
		
			System.out.println(count);
		
		
	}
}


Measured memory_bytes: 22868
#include<cstdio>
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        int x=0;
        for(int a=0;a<10;a++){
            for(int b=0;b<10;b++){
                for(int c=0;c<10;c++){
                    for(int d=0;d<10;d++){
                        if(a+b+c+d==n){
                            x++;
                        }
                    }
                }
            }
        }
        printf("%d\n",x);
    }

    return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>

int width,height;
char map[20][21];
int command_len;
char command[200];

int main(void) {
	int d_num,c_data;
	int i,j;
	int x,y;
	scanf("%d",&d_num);
	for(c_data=0;c_data<d_num;c_data++) {
		scanf("%d%d",&height,&width);
		for(i=0;i<height;i++)scanf("%s",map[i]);
		scanf("%d",&command_len);
		scanf("%s",command);
		x=y=-1;
		for(i=0;i<height;i++) {
			for(j=0;j<width;j++) {
				if(map[i][j]=='^' || map[i][j]=='v' ||
						map[i][j]=='<' || map[i][j]=='>') {
					y=i;x=j;
					i=height;
					break;
				}
			}
		}
		if(x<0 || y<0)return 1;
		for(i=0;i<command_len;i++) {
			switch(command[i]) {
				case 'U':
					map[y][x]='^';
					if(y>0 && map[y-1][x]=='.') {
						map[y-1][x]='^';
						map[y][x]='.';
						y--;
					}
					break;
				case 'D':
					map[y][x]='v';
					if(y<height-1 && map[y+1][x]=='.') {
						map[y+1][x]='v';
						map[y][x]='.';
						y++;
					}
					break;
				case 'L':
					map[y][x]='<';
					if(x>0 && map[y][x-1]=='.') {
						map[y][x-1]='<';
						map[y][x]='.';
						x--;
					}
					break;
				case 'R':
					map[y][x]='>';
					if(x<width-1 && map[y][x+1]=='.') {
						map[y][x+1]='>';
						map[y][x]='.';
						x++;
					}
					break;
				case 'S':
					switch(map[y][x]) {
						case '^':
							for(j=0;y-j>=0;j++) {
								if(map[y-j][x]=='*') {
									map[y-j][x]='.';
									break;
								} else if(map[y-j][x]=='#')break;
							}
							break;
						case 'v':
							for(j=0;y+j<height;j++) {
								if(map[y+j][x]=='*') {
									map[y+j][x]='.';
									break;
								} else if(map[y+j][x]=='#')break;
							}
							break;
						case '<':
							for(j=0;x-j>=0;j++) {
								if(map[y][x-j]=='*') {
									map[y][x-j]='.';
									break;
								} else if(map[y][x-j]=='#')break;
							}
							break;
						case '>':
							for(j=0;x+j<width;j++) {
								if(map[y][x+j]=='*') {
									map[y][x+j]='.';
									break;
								} else if(map[y][x+j]=='#')break;
							}
							break;
					}
					break;
			}
		}
		for(i=0;i<height;i++)puts(map[i]);
		if(c_data<d_num-1)putchar('\n');
	}
	return 0;
}

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

template<class T> bool exist(string s, T key){
    return (s.find(key) != string::npos);
}

vector<string> v;
string n;
int ans = 0;

void gen(string s){
    //停止条件
    if(stol(s) <= stol(n)){
        if(exist(s, "7") && exist(s, "5") && exist(s, "3")){
            ans++;
        }
        gen(s + "3");
        gen(s + "5");
        gen(s + "7");
    }
    return;
}

int main(){
    cin >> n;
    gen("0");
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef  long long int ll;
typedef long double db;
#define pb push_back
#define mp make_pair
#define ub(v,val) upper_bound(v.begin(),v.end(),val)
#define np(str) next_permutation(str.begin(),str.end())
#define lb(v,val) lower_bound(v.begin(),v.end(),val)
#define sortv(vec) sort(vec.begin(),vec.end())
#define rev(p) reverse(p.begin(),p.end());
#define v vector
#define PI 3.1415926535
#define len length()
#define repc(i,s,e) for(ll i=s;i<e;i++)
#define fi first
#define se second
#define mset(a,val) memset(a,val,sizeof(a));
#define mt make_tuple
#define repr(i,n) for( i=n-1;i>=0;i--)
#define rep(i,n) for( i=0;i<n;i++)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const ll M = 1e9 + 7;
ll INF = 1e16;

ll n, m;

int main() {
	// your code goes here
	IOS;

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ll i, j, t, k, x, y, z,   N;
	cin >> n;
	ll odd = 0;
	rep(i, n) {
		cin >> x;
		if (x % 2 != 0)
			odd++;
	}
	if (odd > 0) {
		cout << "first";
	}
	else
		cout << "second";
	return 0;
}

Measured memory_bytes: 3624
import sys
import os


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

    N = int(sys.stdin.buffer.readline().rstrip())
    V = list(map(int, sys.stdin.buffer.readline().split()))
    V.sort()

    for n in range(N-1):
        V[n+1] = (V[n] + V[n+1])/2

    print(V[N-1])


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <stdio.h>
//#include <stdlib.h>
//#include <string.h>
//#include <stdbool.h>
//#include <limits.h>
//#include <math.h>

int main() {
  int n;
  scanf("%d", &n);
  char s[n+1], t[n+1];
  scanf("%s", s);
  scanf("%s", t);
  for (int i=0; i<n; i++) {
    printf("%c", s[i]);
    printf("%c", t[i]);
  }
  printf("\n");
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    vll a(n); for (int i = 0; i < n; i++) cin >> a[i];
    ll sum = 0, ans1 = 0, ans2 = 0;
    for (int i = 0; i < n; i++) {
        sum += a[i];
        if (i % 2 == 0 && sum <= 0) {
            ans1 += abs(sum) + 1;
            sum = 1;
        } else if (i % 2 == 1 && sum >= 0) {
            ans1 += abs(sum) + 1;
            sum = -1;
        }
    }
    sum = 0;
    for (int i = 0; i < n; i++) {
        sum += a[i];
        if (i % 2 == 0 && sum >= 0) {
            ans2 += abs(sum) + 1;
            sum = -1;
        } else if (i % 2 == 1 && sum <= 0) {
            ans2 += abs(sum) + 1;
            sum = 1;
        }
    }
    cout << min(ans1, ans2) << endl;
    return 0;
}

Measured memory_bytes: 1024
/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
string s,t;
int sum,j,x,k,n,m; 
vector<int>mapp[30] ;
signed main ()
{
    cin>>s>>t;
	n=s.length(),m=t.length();
    for(int i=0;i<s.size();i++)
        mapp[s[i]-'a'].push_back(i+1);
    if(mapp[t[0]-'a'].size()==0)
	{
        puts("-1") ;
        return 0 ;
    }
    k=mapp[t[0]-'a'][0];
    sum+=k;
    for(int i=1;i<m;i++)
	{
        x=t[i]-'a' ;
        if(!mapp[x].size())
		{
            puts("-1") ;
            return 0 ;
        }
        j=upper_bound(mapp[x].begin(),mapp[x].end(),k)-mapp[x].begin() ;
        if(j==mapp[x].end()-mapp[x].begin())//没找到,再来一个 
            sum+=mapp[x][0]+n-k,k=mapp[x][0];
		else //找到了 
            sum+=mapp[x][j]-k,k=mapp[x][j];
    }
    cout<<sum<<endl; 
}

Measured memory_bytes: 1724
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<cmath>
using namespace std;
#define REP(i, limit) for(int i=0; i< limit; ++i)
#define FOR(i, j, limit) for(int i=j; i< limit; ++i)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ECHO(x) cout<<x<<endl;
#define LL long long
int INF = 2147483647;
LL LINF = 9223372036854775807;
LL MOD = 1000000007;
typedef pair<int, int>P;
typedef pair<LL, LL>PL;
typedef vector<int> vi;
typedef vector<LL> vl;

int n, A, B, C, ans=INF;
int l[8];

void dfs(int a, int b, int c, int i, int joint){
  if(i==n){
    if(a*b*c==0) return;
    ans=min(ans, abs(a-A)+abs(b-B)+abs(c-C) + 10*(joint-3));
    //cout<<a<<" "<<b<<" "<<c<<" "<<ans<<endl;
  }
  else{
    dfs(a+l[i], b, c, i+1, joint+1);
    dfs(a, b+l[i], c, i+1, joint+1);
    dfs(a, b, c+l[i], i+1, joint+1);
    dfs(a, b, c, i+1, joint);
  }
}


int main(){
  cin>>n>>A>>B>>C;
  REP(i, n) cin>>l[i];

  dfs(0, 0, 0, 0, 0);
  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 256
import sys
import numpy as np
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())


def main():
    n, x = mi()
    a = li()
    cnt = 0
    for i in range(1,n):
        if a[i-1]+a[i]>x:
            cnt += a[i-1]+a[i]-x
            a[i] = max(0, x-a[i-1])
    print(cnt)
        
if __name__ == '__main__':
    main()

Measured memory_bytes: 38112
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import math
import bisect
import random
def LI(): return list(map(int, input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return list(input())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
mod = 1000000007

#A
"""
s = input().split("/")
if int(s[0]) > 2019:
    print("TBD")
elif int(s[0]) == 2019:
    if int(s[1]) > 4:
        print("TBD")
    elif int(s[1]) == 4:
        if int(s[2]) > 30:
            print("TBD")
        else:
            print("Heisei")
    else:
        print("Heisei")
else:
    print("Heisei")
"""

#B
n = I()
ans = 0
for i in range(n):
    x,u = input().split()
    x = float(x)
    if u == "JPY":
        ans += x
    else:
        ans += x*380000.0
print(ans)
#C
"""
n,a,b,c = LI()
l = IR(n)
f = [True for i in range(3)]
ans = 0
for i in range(n):
    for d in range(3):
        if abs(l[i]-[a,b,c][d]) <= 10 and f[d]:
            ans += abs(l[i]-[a,b,c][d])
            f[d] = False
            l[i] = -float("inf")
k = False
for i in f:
    if i:
        k = True
        break
if not k:
    print(ans)
    quit()
"""
#D
"""
a,b,q = LI()
s = IR(a)
t = IR(b)
for i in range(q):
    x = I()
    c = bisect.bisect_left(s,x)
    ans = float("inf")
    k = abs(x-s[c-1])
    y = s[c-1]
    d = bisect.bisect_left(t,y)
    ans = min(ans,k+abs(y-t[d-1]))
    if d < b:
        ans = min(ans,k+abs(y-t[d-1]),min(abs(x-s[c-1]),abs(t[d]-x))+abs(t[d]-s[c-1]))
    ans = min(k,ans)
    if c < a:
        k = abs(x-s[c])
        y = s[c]
        d = bisect.bisect_left(t,y)
        if d == b:
            if t[-1] < x:
                k = min(s[c]-x,x-t[d-1])+s[c]-t[d-1]
        else:
            if abs(y-t[d-1]) < abs(y-t[d]):
                if t[d-1] < x:
                    k = min(s[c]-x,x-t[d-1])+s[c]-t[d-1]
            else:
                k += abs(y-t[d])
        ans = min(k,ans)
    print(ans)
"""
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T


Measured memory_bytes: 39024
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <sstream>

using namespace std;

long evaluateDN(long N) {
	long ret = 0;

	while (N > 0) {
		ret += N % 10;
		N /= 10;
	}

	return ret;
}

int main() {
	long argN;
	cin >> argN;

	long ret = INFINITY;
	for (long i = 1; i < argN; ++i) {
		long A = i;
		long B = argN - A;

		long sum = evaluateDN(A);
		sum += evaluateDN(B);

		ret = min(ret, sum);
	}

	cout << ret << endl;
}

Measured memory_bytes: 256
#pragma region Macros

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define int ll
using vi = vector<int>;
using vvi = vector<vi>;

#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(x) (x).begin(), (x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

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;
}

// debug methods
// usage: debug(x,y);
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x
#define debug_1(x1) cout << #x1 << ": " << x1 << endl
#define debug_2(x1, x2) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << endl
#define debug_3(x1, x2, x3) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << endl
#define debug_4(x1, x2, x3, x4) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << ", " #x4 << ": " << x4 << endl
#define debug_5(x1, x2, x3, x4, x5) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << ", " #x4 << ": " << x4 << ", " #x5 << ": " << x5 << endl
#ifdef _DEBUG
#define debug(...)                                                        \
    CHOOSE((__VA_ARGS__, debug_5, debug_4, debug_3, debug_2, debug_1, ~)) \
    (__VA_ARGS__)
#else
#define debug(...)
#endif

#pragma endregion

void Main() {
    int N;
    cin >> N;
    set<int> d;
    int buff;
    REP(i, N) {
        cin >> buff;
        d.insert(buff);
    }

    cout << SIZE(d);
}

#pragma region main
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Main();
    cout << flush;
}
#pragma endregion


Measured memory_bytes: 3576
use std::io::*;

fn calc(mut n: i32) -> i32 {
    let mut s: i32 = 0;
    while n != 0 {
        s += n % 10;
        n /= 10;
    }
    s
}

fn main() {
    let scan = stdin();
    let mut line = String::new();
    let _ = scan.read_line(&mut line);
    let vec: Vec<&str> = line.split_whitespace().collect();
    let N: i32 = vec[0].parse().unwrap();
    let A: i32 = vec[1].parse().unwrap();
    let B: i32 = vec[2].parse().unwrap();
    let mut ans: i32 = 0;
    for x in 0..N + 1 {
        let s = calc(x);
        if A <= s && s <= B {
            ans += x;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long int
using namespace std;
 
int main() {
    fast();
   /* ll t;
    cin>>t;
    while(t--)
    {
       
    }*/
    double n;
    cin>>n;
    double ans=n/3.0*n/3.0*n/3.0;
  cout << fixed <<ans<<endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<map>
using  namespace std;
int main()
{
	int x,a;
	scanf("%d%d",&x,&a);
	if(x<a)printf("0\n");
	else printf("10\n");
}

Measured memory_bytes: 256
INF = (1 << 31) - 1

n = gets.to_i
ms = n.times.map {gets.split.map(&:to_i)}

dp = Array.new(n + 1) {Array.new(n + 1, 0)}
dim = [ms[0][0]] + ms.map(&:last)

2.upto(n) do |l|
  1.upto(n - l + 1) do |i|
    j = i + l - 1
    dp[i][j] = INF
    i.upto(j - 1) do |k|
      tmp = dp[i][k] + dp[j][k] + dp[k + 1][j] + dim[i - 1] * dim[k] * dim[j]
      dp[i][j] = [dp[i][j], tmp].min
    end
  end
end

puts dp[1][n]


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

int n;
int a[455];

long long dp[455][455];

long long rec(int l, int r) {
	if (l == r) return 0;
	if (dp[l][r] >= 0) return dp[l][r];
	
	long long res = 0;
	
	for (int i = l; i <= r; i++) res += a[i];
	
	long long best = LLONG_MAX;
	
	for (int i = l; i < r; i++) {
		best = min(best, rec(l, i) + rec(i + 1, r));
	}
	
	res += best;
	
	return dp[l][r] = res;
}
int main() {
	cin >> n;
	
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	
	memset(dp, -1, sizeof(dp));
	
	cout << rec(0, n - 1);
}


Measured memory_bytes: 1920
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using ll = long long int;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = 998244353ll;

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

ll rwpw(ll a, ll p = MOD-2){
	ll ret = 1ll;
	while(p){
		if(p%2){
			mul_mod(ret,a);
		}
		mul_mod(a,a);
		p /= 2;
	}
	return ret;
}

ll fc[225816]={1ll},nv[225816]={1ll};

ll c(int n, int k){
	ll ret = fc[n];
	if(n<k){
		return 0ll;
	}
	mul_mod(ret,nv[k]);
	mul_mod(ret,nv[n-k]);
	return ret;
}

int main(void){
	int n,k,i;
	ll m,tmp,ans=0ll;
	std::cin >> n >> m >> k;
	for(i=1; i<=n; ++i){
		fc[i] = fc[i-1]*i%MOD;
		nv[i] = rwpw(fc[i]);
	}
	for(i=0; i<=k; ++i){
		tmp = m;
		mul_mod(tmp,rwpw(m-1,n-i-1));
		mul_mod(tmp,c(n-1,i));
		add_mod(ans,tmp);
	}
	std::cout << ans << std::endl;
	return 0;
}


Measured memory_bytes: 6804
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
int main() {
  string s1,s2,s3;
  cin >> s1 >> s2 >> s3 ;
  cout << s1.at(0) << s2.at(0) << s3.at(0) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using pint = pair<int,int>;

const long long INFLL = 1LL << 60;
const int INFI = 1000000000;


int main(){
    long long X, Y; cin >> X >> Y;
    long long  count = 1;
    long long A = X;
    while(true){
        A*=2;
        if(A<=Y) count++;
        else break;
    }
    cout << count << endl;
}




Measured memory_bytes: 256
using namespace std;
#include <bits/stdc++.h>
#define frr(i, r, l) for(int i = r; i >= l; --i)
#define fr(i, l, r) for(int i = l; i < r; ++i)
#define forit(it, type, var) for(type::iterator it = var.begin(); it != var.end(); it++)
#define ii pair<int, int>
#define iii pair<int, ii>
#define MEMS(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define m_p make_pair
#define pb push_back
#define ll long long
#define ld long double
typedef pair<ll, ll> iPair; 
priority_queue< ll, vector <ll> , greater<ll>>pq1,pq2;
#define maxN 1000000000000000000
ll power(ll a,ll b){ll res=1;while(b>0){res*=a;b--;}return res;}
int main()
{
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,ar[200005];
    map<ll,ll>mp;
    vector<ll>v;
    set<ll>s;
    cin>>n;
    fr(i,0,n)
    {
        cin>>ar[i];
        mp[ar[i]]++;
        s.insert(ar[i]);
    }
    for(auto it=s.begin();it!=s.end();it++)
    {
        v.pb(*it);
    }
    ll ans=0;
    fr(i,0,v.size())
    {
        ll st=mp[v[i]];
        fr(k,i+1,v.size()){
        ll st1=mp[v[k]];
        ll st2=v[i]+v[k];
        fr(j,k+1,v.size())
        {
            if(v[j]<st2)
            {
                ans=ans+st*st1*mp[v[j]];
            }
        }
        }
    }
    cout<<ans<<endl;
    return 0;
}

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

int main()
{
	int n;
	cin>>n;
	ll cnt=n-1;
	for(int i=2;i<n;i++)
	{
		if(n%i!=0)
		{
			cnt+=n/i;
		}
		else
		{
			cnt+=n/i-1;
		}
	}
	cout<<cnt<<endl;
	return 0;
}


Measured memory_bytes: 3640
import numpy as np
import functools
import math
import collections
import scipy
import fractions
import itertools

def solve():
    n = int(input())
    w = []
    bit = 0
    for i in range(n):
        w.append(input())
    if len(set(w)) != n:
        print("No")
    else:
        for i in range(n-1):
            if w[i][-1] != w[i+1][0]:
                print("No")
                bit = 1
                break
        if bit == 0:
            print("Yes")
    return 0

if __name__ == "__main__":
    solve()


Measured memory_bytes: 21904
object Main extends App {
  val inputnkq = scala.io.StdIn.readLine()
  val nkqArray = inputnkq.split(" ").map(_.toInt).toVector

  val n = nkqArray(0)
  val k = nkqArray(1)
  val q = nkqArray(2)

  var answerMap = scala.collection.mutable.Map.empty[Int, Int]
  (1 to q).foreach { _ =>
    val a = scala.io.StdIn.readInt()
    answerMap.get(a).fold(answerMap.put(a, 1))(v => answerMap.put(a, v + 1))
  }

  (1 to n).foreach { i =>
    answerMap.get(i).fold {
      if ( (k - q) > 0 ) {
        println("Yes")
      } else {
        println("No")
      }
    } { a =>
      if ( (k - q + a) > 0 ) {
        println("Yes")
      } else {
        println("No")
      }
    }
  }

}

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

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

    int n;
    cin >> n;
    vector<map<char, int>> v(n);
    rep(i,n){
        string s;
        cin >> s;
        
        rep(j, s.size()){
            v[i][s[j]]++;
        }
    }
    
    string ans = "";
    
    rep(i,26){
        bool flag = true;
        int mm = 51;
        rep(j,n){
            if(v[j].count( (char)('a' + i) ) == 0){
                flag = false;
            }
            else{
                // cout << (char)('a' + i) << endl;
                mm = min(mm, v[j][(char)('a' + i)]);
            }
        }
        
        if(flag){
            // cout << (char)('a' + i) << endl;
            rep(j,mm) ans += (char)('a' + i);
        }
    }
    
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 384
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix
from sys import stdin


def makeConnected(n, connections):
    l = list(zip(*connections))
    d = [1] * len(connections)
    a = csr_matrix((d, (l[0], l[1])), (n, n))
    return connected_components(a, return_labels=0)


def main():
    input = lambda: stdin.readline()[:-1]
    N, M = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in [0] * M]

    ab = [[a - 1, b - 1] for a, b in AB]
    ans = makeConnected(N, ab) - 1
    print(ans)


main()


Measured memory_bytes: 74212
#include <bits/stdc++.h>
#pragma GCC diagnostic ignored "-Wunused-result"
#define int long long
using namespace std;

#define fin(i,n) for (int i = 0; i < n; i++)
#define fin2(i,a,b) for (int i = a; i < b; i++)
#define ford(i,n) for (int i = n-1; i >= 0; i--)
#define ford2(i,a,b) for (int i = a-1; i >= b; i--)
 
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define mod 1000000007
#define PI 3.1415926535897932384626
#define EXP1 2.718281828459045
#define BIG 1000000000000000000

#define sl(n) scanf("%lld", &n)
#define sll(n,m) scanf("%lld %lld", &n, &m)
#define slll(n,m,k) scanf("%lld %lld %lld", &n, &m, &k)
#define sllll(n,m,k,o) scanf("%lld %lld %lld %lld", &n, &m, &k, &o)
#define sd(n) scanf("%lf", &n)
#define sdd(n,m) scanf("%lf %lf", &n, &m)
#define sddd(n,m,k) scanf("%lf %lf %lf", &n, &m, &k)
#define sc(c) scanf(" %c", &c)
#define ss(s) scanf("%s", s)
#define sal(t,n) fin(iz,n) { scanf("%lld", &t[iz]); }
#define sad(t,n) fin(iz,n) { scanf("%lf", &t[iz]); }
#define gl(t) scanf(" %[^\n]", t);

#define pc(n) printf("%c\n", n)
#define ps(s) printf("%s\n", s)
#define pss(s) printf("%s\n", s.c_str())
#define pl(n) printf("%lld\n", n)
#define pll(n,m) printf("%lld %lld\n", n, m)
#define plll(n,m,k) printf("%lld %lld %lld\n", n, m, k)
#define pd(n) printf("%lf\n", n)
#define pdd(n,m) printf("%lf %lf\n", n, m)
#define pal(t,n) fin(rz,n) { printf("%lld ", t[rz]); } printf("\n")
#define pad(t,n) fin(rz,n) { printf("%lf ", t[rz]); } printf("\n")

#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
 
#define OK ps("OK")
#define OK1 ps("OK1")
#define OK2 ps("OK2")

#define ll int
#define vl vector<ll>
#define vvl vector<vl>
#define vvvl vector<vvl>

#define dll pair<ll, ll>
#define vdll vector<dll>
#define vvdll vector<vdll>

#define vb vector<bool>
#define vvb vector<vb>
#define vd vector<double>
#define vvd vector<vd>
#define vc vector<char>
#define vvc vector<vc>

#define all(v) v.begin(), v.end()
#define vlen(v) (int)(v.size())
#define pb push_back
#define fi first
#define se second

string s,t;
int a,b;
const int mm = 3005;
int dp[mm][mm];
int choix[mm][mm];
int gdp(int x, int y)
{
    if (x >= a || y >= b) return 0;
    if (dp[x][y] == -1) {
        int c1 = gdp(x+1, y);
        int c2 = gdp(x, y+1);
        int c3 = (s[x] == t[y] ? 1:0) + gdp(x+1, y+1);
        int r = max(max(c1, c2), c3);
        dp[x][y] = r;
        if (c1 == r) choix[x][y] = 1;
        else if (c2 == r) choix[x][y] = 2;
        else choix[x][y] = 3;
    }

    return dp[x][y];
}

string lcs;

void build(int x, int y)
{
    if (x >= a || y >= b) return;
    int c = choix[x][y];
    if (c == 1) build(x+1,y);
    else if (c == 2) build(x, y+1);
    else {
        if (s[x] == t[y]) lcs.push_back(s[x]);
        build(x+1,y+1);
    }
}

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

    cin >> s >> t;
    a = s.length();
    b = t.length();

    fill_n(&dp[0][0], mm*mm, -1);
    gdp(0, 0);
    build(0, 0);
    cout << lcs << '\n';
}

Measured memory_bytes: 141824
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(obj) (obj).begin(),(obj).end()
#define debug(x) cerr << #x << ": " << endl
#define rep(i,n) for(int i=0; (i)<(n); ++(i))
#define rrep(i,n) for(int i=(n); (i)>=0; --(i))
#define reps(i,s,n) for(int i=(s); (i)<(n); ++(i))
#define maxi(v) distance(v.begin(), max_element(v.begin(), v.end()))
#define mini(v) distance(v.begin(), min_element(v.begin(), v.end()))
#define maxemt(v) *max_element(v.begin(), v.end())
#define minemt(v) *min_element(v.begin(), v.end())
#define lb(v,x) v[lower_bound(v.begin(), v.end(), x) - v.begin()]
#define ub(v,x) v[upper_bound(v.begin(), v.end(), x) - v.begin()]
template<class T> inline bool print(T& x){ cout << x << endl; return true; }
template<class T> inline bool print_(T& x){ cout << x << " "; return true; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
ll gcd(ll x, ll y){
  if(y==0) return x;
  else return gcd(y, x%y);
  }
ll lcm(ll x, ll y){
  return x / gcd(x,y) * y;
}
const int INF = 1e9;
const ll llINF = 1LL<<60;
const int MOD = 1e9+7;
const double EPS = 1e-9;

int sc, sr, gc, gr;
int maze[20][20], d[20][20];
int column, row;

int Maze_minsolve_bfs(){
  queue<pair<int,int>> que;
  rep(i,column) rep(j,row) d[i][j]=INF;
  que.push(pair<int,int>(sc,sr));
  d[sc][sr]=0;
  while(que.size()){
    pair<int,int> p=que.front(); que.pop();
    if(p.first==gc && p.second==gr) break;
    rep(i,4){
      int nx=p.first+dx[i],ny=p.second+dy[i];
      if(0<=nx && nx<column && 0<=ny && ny<row && maze[nx][ny]!=1 && d[nx][ny]==INF){
        que.push(pair<int,int>(nx,ny));
        d[nx][ny]=d[p.first][p.second]+1;
      }
    }
  }
  return d[gc][gr];
}

int main(){
  int h, w; cin >> h >> w;
  column=h, row=w;
  vector<vector<char>> s(h, vector<char>(w));
  rep(i,h) rep(j,w){
    cin >> s[i][j];
    if(s[i][j]=='.') maze[i][j]=0;
    else if(s[i][j]=='#') maze[i][j]=1;
  }
  int ans=0;
  rep(i,h){
    rep(j,w){
      rep(k,h){
        rep(l,w){
          if(s[i][j]=='#' || s[k][l]=='#') continue;
          sc=i, sr=j, gc=k, gr=l;
          chmax(ans, Maze_minsolve_bfs());
        }
      }
    }
  }
  cout << ans;

  
return 0;
}


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

int main() {
    std::cout<<std::fixed<<std::setprecision(10);
    
    ll N; cin >> N;
    ll ans = 0;
    if (N == 1) {
        cout << 0 << endl;
        return 0;
    } else if (N == 2) {
        cout << 1 << endl;
        return 0;
    } else {
        ans += (N-1) * (N/2);
    }
    if (N%2 == 1){
        ans += (N/2);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cmath>
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll inf = 1000000007;
vector<ll>heya[100005];
int main(void) {
    ll n, m;
    cin >> n >> m;
   
    int a, b;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        a--; b--;
        heya[a].push_back(b);
        heya[b].push_back(a);
    }
    queue<ll>que;
    vector<ll>dist(n, inf);
    vector<ll>pre(n, -1);
    dist[0] = 0;
    que.push(0);
    while (!que.empty()) {
        int x = que.front();
        que.pop();
        for (auto id : heya[x]) {
            if (dist[id] != inf) {
                continue;
            }
            dist[id] = dist[x] + 1;
            pre[id] = x + 1;
            que.push(id);
        }
    }
    cout << "Yes" << endl;
    for (int i = 1; i < n; i++) {
        cout << pre[i] << endl;
    }
    return 0;
}


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

int main(void) {
    char buffer[10];
    int N = atoi(fgets(buffer, 10, stdin));
    int count = 0;
    while (N >= 3) {
        N -= 3;
        count++;
    }
    printf("%d", count);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PLL = pair<ll, ll>;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repn(i,n) for(int i = 0; i <= (int)(n); i++)
#define srep(i,l,n) for(int i = l; i < (int)(n); i++)
#define srepn(i,l,n) for(int i = l; i <= (int)(n); i++)
#define drep(i,n) for(int i = (int)(n-1); i >= 0; i--)
#define drepn(i,n) for(int i = (int)(n); i >= 0; i--)
#define debug(var)  do{std::cout << #var << " : ";view(var);}while(0)
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }
template<typename T> inline istream& operator>>(istream &i, vector<T> &v) {rep(j, size(v)) i >> v[j]; return i;}
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; }
template<class T> T gcd(T a, T b) {if(b==0)return a; else return gcd(b,a%b);}
template<class T> T lcm(T a, T b) {return a/gcd(a,b)*b;}
template<class T = int> using V = vector<T>;
template<class T = int> using VV = vector<V<T>>;
bool isIn(int i, int j, int h, int w) {return i >= 0 && i < h && j >= 0 && j < w;}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void err() {cout << -1 << endl;}
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define ep emplace_back

const int MOD = 1000000007;
const int INF = 1e9;

#define PI acos(-1);
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int ddx[8] = {1,1,1,-1,-1,-1,0,0};
int ddy[8] = {0,1,-1,0,1,-1,1,-1};

template <class T>
struct CumlativeSum2 {
    vector<vector<T>> sum;
    CumlativeSum2(int h, int w):sum(h+1, vector<T>(w+1, 0)){};

    void add(int x, int y, T z) {
        sum[x][y] += z;
    }

    void build() {
        for(int i = 1; i < sum.size(); i++) {
            for(int j = 1; j < sum[i].size(); j++) {
                sum[i][j] += sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
            }
        }
    }

    T q(int sx, int sy, int gx, int gy) {
        return sum[gx][gy]-sum[sx][gy]-sum[gx][sy]+sum[sx][sy];
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    CumlativeSum2<ll> sum(n, n);
    rep(i, m) {
        int l, r;
        cin >> l >> r;
        sum.add(l, r, 1);
    }
    sum.build();

    while(q--) {
        int u, v;
        cin >> u >> v;
        cout << sum.q(u-1, u-1, v, v) << endl;
    }
}

Measured memory_bytes: 5268
n=int(input())
spade=set(range(1,14,1))
heart=set(range(1,14,1))
club=set(range(1,14,1))
diamond=set(range(1,14,1))
for a in range(n):
    e,b=input().split()
    if e=="S":
        spade.remove(int(b))
    if e=="H":
        heart.remove(int(b))
    if e=="C":
        club.remove(int(b))
    if e=="D":
        diamond.remove(int(b))
for i in spade:
    print("S",i)
for i in heart:
    print("H",i)
for i in club:
    print("C", i)
for i in diamond:
    print("D",i)



Measured memory_bytes: 5608
use std::io::{stdin, Read};

#[allow(unused_macros)]
macro_rules! parse {
    ($it: ident ) => {};
    ($it: ident, ) => {};
    ($it: ident, $var:ident : $t:tt $($r:tt)*) => {
        let $var = parse_val!($it, $t);
        parse!($it $($r)*);
    };
    ($it: ident, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = parse_val!($it, $t);
        parse!($it $($r)*);
    };
}

#[allow(unused_macros)]
macro_rules! parse_val {
    ($it: ident, [$t:tt; $len:expr]) => {
        (0..$len).map(|_| parse_val!($it, $t)).collect::<Vec<_>>();
    };
    ($it: ident, ($($t: ty),*)) => {
        ($(parse_val!($it, $t)),*)
    };
    ($it: ident, $t: ty) => {
        $it.next().unwrap().parse::<$t>().unwrap()
    };
}

fn primes(mut n: usize) -> Vec<(usize, usize)> {
    let mut cur = 2;
    let mut count = 0;
    let mut ret = vec![];
    while n >= cur && cur <= (n as f64).sqrt() as usize + 1 {
        if n % cur == 0 {
            count += 1;
            n /= cur;
        } else {
            if count > 0 {
                ret.push((cur, count));
                count = 0;
            }
            cur += 1;
        }
    }
    if count > 0 {
        if cur == n {
            ret.push((cur, count + 1));
            n = 1;
        } else {
            ret.push((cur, count));
        }
    }
    if n > 1 {
        ret.push((n, 1));
    }
    ret
}

fn solve(s: &str) {
    let mut it = s.split_whitespace();
    parse!(it, n: usize);
    let ps = primes(n);
    let mut ret = 0;
    for (p, m) in ps {
        let mut k = 1;
        while m >= (k + 1) * (k + 2) / 2 {
            k += 1;
        }
        ret += k;
    }
    println!("{}", ret);
}

fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    solve(&s);
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_input() {
        let s = "
        ";
        solve(s);
    }
}


Measured memory_bytes: 2120
import java.math.*;
import java.util.*;

public class Main {

    Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        new Main().run();
    }

    void run() {

        long money = 1000;

        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i=0; i<n; i++) arr[i] = sc.nextInt();

        List<Pair> list = new ArrayList<>();

        int l = 0;
        int r = 0;
        for (int i=1; i<n; i++) {
            if (arr[i-1]<=arr[i]) {
                r++;
                if (i==n-1) {
                    Pair pair = new Pair(l, r);
                    list.add(pair);
                }
            } else {
                Pair pair = new Pair(l, r);
                list.add(pair);
                r++;
                l = r;
            }
        }

        for (int i=0; i<list.size(); i++) {
//            System.out.print(list.get(i).l + " ");
//            System.out.println(list.get(i).r);
        }

        for (int i=0; i<list.size(); i++) {
            int left = list.get(i).l;
            int right = list.get(i).r;
            long lCnt = money / (long)arr[left];
            money -= arr[left] * lCnt;
            money += arr[right] * lCnt;
//            System.out.println(money);
        }

        System.out.print(money);


    }

    class Pair {
        int l;
        int r;
        public Pair(int l, int r) {
            this.l = l;
            this.r = r;
        }
    }

}



Measured memory_bytes: 35608
def warshal_floyd(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        d[i][j] = min(d[i][j], d[i][k]+d[k][j])
  return d

n, m = map(int, input().split())
INF = 10**18
d = [[INF for i in range(n)] for j in range(n)]
e = [[0, 0, 0] for _ in range(m)]
for i in range(m):
    a, b, c = map(int, input().split())
    a, b = a-1, b-1
    d[a][b] = c
    d[b][a] = c

    e[i][0] = a
    e[i][1] = b
    e[i][2] = c

for i in range(n):
    d[i][i] = 0

d = warshal_floyd(d)
ans = 0
for i in range(m):
    a = e[i][0]
    b = e[i][1]
    c = e[i][2]
    for k in range(n):
        if d[a][k] == c + d[b][k]:
            break
    else:
        ans += 1
print(ans)

Measured memory_bytes: 3444
from collections import Counter
n = int(input())
a = [int(i) for i in input().split()]
cum = [0] * (n + 1)
for i in range(n):
    cum[i + 1] = cum[i] + a[i]
cum = sorted(cum)
count = Counter(cum)
ans = 0
for v in count.values():
    ans += v * (v - 1) // 2
print(ans)

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

int main()
{
ll int b,ans,n,a[100],i,j,p=0,s;
cin>>n;
s=0;
for(i=1;i<=9;i++)
{
    for(j=1;j<=9;j++)
    {
        ans=i*j;
        //a[p]=ans;
       // p++;
        if(ans==n)
        {
            p=-1;
        }
    }
    if(p==-1)
    {
        break;
    }
}
if(p==-1)
{
    cout<<"Yes"<<endl;
}
else
{
    cout<<"No"<<endl;
}
return 0;
}

Measured memory_bytes: 256
// AtCoder template
// sabaより胡蝶しのぶさんの方が可愛いのではないか？
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < n; ++i)

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

    string s; cin >> s;
    int n = s.size();
    
    bool flag = true;
    rep(i,n) if(s[i] != s[n-i-1]) flag = false;
    rep(i,(n-1)/2) if(s[i] != s[(n-1)/2-i-1]) flag = false;
    for(int i = (n+3)/2-1; i < n; ++i) if(s[i] != s[n-i-1]) flag = false;

    if(flag) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <set>
#include <utility>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <cstdio>
#include <map>
#include <list>

using namespace std;

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

#define rep(i,x) for(Int i = 0; i < (Int)(x); i++)
#define rrep(i,x) for(Int i = ((Int)(x) - 1); i >= 0; i--)
#define _upgrade ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define pb push_back


template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

//ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
//ll lcm(ll x, ll y) {return x / gcd(x, y) * y;}

Int dx[4] = {1,0,-1,0};
Int dy[4] = {0,1,0,-1};
const Int INF = 1001002003004005006ll;
const Int mod = 1e9 + 7;
const double PI = 3.14159265358979323846;


// ****************************************CODE***************************************//








int main(){
        string x;
        cin >> x;

        Int scount = 0;
        Int tcount = 0;
        Int ans = 0;
        for(int i = 0; i < x.size(); i++){
                if(x[i] == 'S') scount++;
                if(x[i] == 'T'){
                        if(scount > 0){
                                scount--;
                                ans++;
                        }
                }
        }

        ans = x.size() - 2*ans;

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



















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

void setmax(uint8_t& a, int b) {
	if (b > a) {
		a = b;
	}
}

const int MAXX = 190;
const int MAXY = 190;
const int MAXN = 20;
int X, Y;
char A[MAXX][MAXY];
uint8_t dp[MAXX][MAXX][MAXY], ndp[MAXX][MAXX][MAXY];

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> X >> Y;
	for (int x = 0; x < X; x++) {
		cin >> A[x];
	}

	for (int xlo = X-1; xlo >= 0; xlo--) {
		for (int xhi = xlo; xhi < X; xhi++) {
			for (int ylo = Y-1; ylo >= 0; ylo--) {
				if (xlo == xhi || (A[xhi][ylo] == A[xhi-1][ylo] && dp[xlo][xhi-1][ylo] > ylo)) {
					if (ylo < Y-1 && A[xhi][ylo] == A[xhi][ylo+1]) {
						dp[xlo][xhi][ylo] = dp[xlo][xhi][ylo+1];
					} else {
						dp[xlo][xhi][ylo] = ylo+1;
					}
				} else {
					dp[xlo][xhi][ylo] = ylo;
				}
			}
		}
	}

	int ans = 0;
	while (dp[0][X-1][0] < Y) {
		for (int xlo = 0; xlo < X; xlo++) {
			for (int xhi = xlo; xhi < X; xhi++) {
				for (int ylo = 0; ylo < Y; ylo++) {
					// append right
					if (dp[xlo][xhi][ylo] == Y) {
						ndp[xlo][xhi][ylo] = Y;
					} else {
						ndp[xlo][xhi][ylo] = dp[xlo][xhi][dp[xlo][xhi][ylo]];
					}

					// append down
					// find last position such that dp(mid) <= dp(mid+1)
					int mi = xlo, ma = xhi - 1;
					while (mi <= ma) {
						int md = (mi + ma) / 2;
						setmax(ndp[xlo][xhi][ylo], min(dp[xlo][md][ylo], dp[md+1][xhi][ylo]));
						if (dp[xlo][md][ylo] <= dp[md+1][xhi][ylo]) {
							ma = md - 1;
						} else {
							mi = md + 1;
						}
					}
				}
			}
		}
		memcpy(dp, ndp, sizeof(dp));
		ans++;
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 13568
#include <iostream>
#include <vector>
#include<string>


#define ll         long long
#define rep(i,n)   for(int i = 0; i < n; i++)

#define vi         vector<int>
#define vs         vector<string>

#define vpii       vector<pair<int,int>>
#define vpis       vector<pair<int,string>>
#define vpss       vector<pair<string,string>>
#define mkp        make_pair

#define vvi        vector<vector<int>>

using namespace std;

int main()
{
  int s, w;

  cin >> s >> w;

  if (w >= s) {
    cout << "unsafe";
  } else {
    cout << "safe";
  }






  return 0;
}


Measured memory_bytes: 3640
import java.util.Scanner;

public class Main {
	public static void main(String[]args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int i = 0;
		for(i = 1; i <= n; i = i * 2) {
		}
		i = i / 2;
		System.out.println(i);
	}
}


Measured memory_bytes: 21844
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define FAST_IO  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mod 100000
#define endl "\n"
#define PI 3.14159265358979323846264338327950288
 
using namespace std ;
using bigint = long long int ;
using vi = vector<int> ;
using vll = vector<long long int> ;


int main(){
    FAST_IO ;
    int N ; cin >> N ;
    int arr[N+1] ;
    for( int i = 0 ; i < N ; i++ ){
        cin >> arr[i] ;
    }
    bigint ans = 0 ;
    
    for( int i = 1 ; i < N ; i++ ){
        if( arr[i] < arr[i-1] ){
            ans = ans + max( 0 , arr[i-1] - arr[i]) ;
            arr[i] = arr[i-1] ;
        }
    }
    cout << ans << endl ;
    return 0 ;
}
 

Measured memory_bytes: 4436
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e6 + 3, Mod = 1e9 + 7;

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
	int n;
	cin>>n;
	if(n==1){
		cout<<0<<endl;
		return 0;
	}
	ll ret1=1;
	ll ret2=1;
	ll ret3=1;
	for(int i=0;i<n;i++){
		ret1*=10;
		ret2*=9;
		ret3*=8;
		ret1=ret1%Mod;
		ret2=ret2%Mod;
		ret3=ret3%Mod;
	}
	ret1=ret1-2*ret2+ret3;
	while(ret1<0)ret1+=Mod;
	cout<<ret1<<endl;
}


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

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef long long ll ;
typedef long double ld ;

const ll MOD = 1e9 + 7 ;
const double PI = 2 * acos(0.0) ;
const long double EPS = 1.0E-14 ;

int main()
{
    ll a, b, c ;
    cin >> a >> b >> c ;
    swap(a, b) ;
    swap(a, c) ;
    cout << a << " " << b << " " << c ;

    return 0 ;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

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

		int n = sc.nextInt();
		sc.next();

		String[] s = new String[n];

		for (int i = 0; i < s.length; i++) {
			s[i] = sc.next();
		}

		Arrays.sort(s);

		for (String string : s) {
			System.out.print(string);
		}
		System.out.println();

		sc.close();
	}
}



Measured memory_bytes: 22996
import java.util.*;
public class Main{
  public static void main(String[] args){
   Scanner sc = new Scanner(System.in);
   String S = sc.next();
    int N = S.length();
   int count =0;
     for(int i =0;i<N/2;i++)
     {
        if(S.substring(i,i+1).equals(S.substring(N-i-1,N-i)));
		else count++;    
     }
        	System.out.println(count);
 }
}

Measured memory_bytes: 23764