akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

#define ll long long int
#define MOD ((int)(1e9) + 7)

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin >> n;
  unordered_map<int, int> hh;
  while(n--) {
    int tp;
    cin >> tp;
    auto fn = hh.find(tp);
    if(fn == hh.end())
      hh[tp] = 1;
    else
    {
      hh[tp]++;
    }
  }
  int cnt = 0;
  for(auto i: hh) {
    if(i.second > i.first) 
      cnt += i.second - i.first;
    else if (i.second < i.first)
      cnt += i.second;
  }
  cout << cnt << '\n';
  return 0;
}


Measured memory_bytes: 4260
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<map>
#include<set>
//#include <Eigen/Dense>
//#include <Eigen/Geometry>
//using namespace Eigen;

using namespace std;




int main() 
{
	int n;
	cin >> n;
	set<string> a;

	for (int i = 0; i < n; i++)
	{
		string temp;
		cin >> temp;
		a.insert(temp);
	}
	cout << a.size() << endl;
	return 0;
}


Measured memory_bytes: 19208
#include"stdio.h"
#include"math.h"

int cls(int);

int main()
{
  int n;
  int p;
  int i;
  int num=0;
  scanf("%d",&n);
  for(i=0;i<n;i++)
    {
      scanf("%d",&p);
      if(cls(p))num++;
    }
  printf("%d\n",num);
    return 0;
}

int cls(int n)
{
  int num=(int)sqrt(n);
  int i;
  for(i=2;i<=num;i++)
    {
      if(n%i==0)return 0;
    }
  return 1;
}


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

class Dice{
public:
    int *arr;
    Dice(int arr2[]){arr = arr2;}

    void roll(char direction){
        int temp;
        switch(direction){
            case 'N':
                temp = arr[0]; arr[0] = arr[1]; arr[1] = arr[5]; arr[5] = arr[4]; arr[4] = temp;
                break;
            case 'E':
                temp = arr[0]; arr[0] = arr[3]; arr[3] = arr[5]; arr[5] = arr[2]; arr[2] = temp;
                break;
            case 'W':
                temp = arr[0]; arr[0] = arr[2]; arr[2] = arr[5]; arr[5] = arr[3]; arr[3] = temp;
                break;
            case 'S':
                temp = arr[0]; arr[0] = arr[4]; arr[4] = arr[5]; arr[5] = arr[1]; arr[1] = temp;
        }
    }

    bool issame(int arr2[]){
        string line = "NNNNENNNNENNNNENNNNNENNNNEENNNN";
        for(int i = 0; i < 31; i++){
            bool same = true;
            for(int j = 0; j < 6; j++){
                if (arr[j] != arr2[j]){
                    same = false;
                    break;
                }
            }
            if(same) return true;
            else roll(line[i]);
        }
        return false;
    }
};

int main(){
    int arr[6], arr2[6], n;
    cin >> n;
    for(int i = 0; i < 6; i++) cin >> arr[i];
    Dice dice(arr);
    string result = "Yes";
    for(int j = 0; j < n - 1; j++){
        for(int i = 0; i < 6; i++) cin >> arr2[i];
        if(dice.issame(arr2)){
            result = "No";
            break;
        }
    }
    cout << result << endl;

    return 0;
}


Measured memory_bytes: 3220
#include<bits/stdc++.h>
#define mod %
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main(){
    int a, b; cin >> a >> b;
    int cnt = 0;

    for(b -= 1; b > 0; b -= (a - 1)){ cnt++;}

    cout << cnt << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main (){
   int N;
 int A;
   cin >> N;
 cin >> A;
  int x=N/500;
  N = N-500*x;
  if (A>=N){
  cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,i,k=4,f;string s,o;
int main(){
    cin>>n>>o;
    for(s=o;k--&&!f;){
        s[0]="WS"[k>>1];
        s[1]="WS"[k&1];
        for(i=2;i<n;i++)s[i]=s[i-1]^o[i-1]&4^s[i-2]&4^4;
        for(f=i=n;i--&&f;)f=s[i]^o[i]&4^s[(n+i-1)%n]^s[(i+1)%n]&4;
        f&&cout<<s;
    }
    f||cout<<-1;
    return 0;
}

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

int main() {
  int n;
  cin >> n;
  int fourth_count = 0;
  int second_count = 0;
  int limit = n / 2;
  rep(i,n){
    ll a;
    cin >> a;
    if(a % 4 == 0) fourth_count++;
    else if(a % 2 == 0)second_count++;
  }
  if(fourth_count + second_count / 2 >= limit){
    cout << "Yes" << endl;
  }else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
import java.util.*;

class Main{
	public static void main(String args[]){
    	Scanner sc = new Scanner(System.in);
      	int n = sc.nextInt();
      	if((n%1000) == 0){
          System.out.println(0);
        }else{
          System.out.println((1000-(n%1000)));        	
        }
    }
}

Measured memory_bytes: 35684
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define REP(i, n) for(int i = 0;i < (n);++i)
#define RREP(i, n) for(int i = (n)-1; i >= 0; --i)

#define endl '\n'
#define pb push_back
#define eb emplace_back
#define pque priority_queue
#define umap unordered_map
#define BIG 2000000000
#define VERYBIG 1000000000000000ll
#define PI 3.1415926
#define coutdb cout<<fixed<<setprecision(15)

const int dx[]={1,0,-1,0,1,1,-1,-1}, dy[]={0,-1,0,1,1,-1,1,-1};
const long long MOD = 1e9+7;

// typedef int_fast64_t ll;
#define int int_fast64_t

template<typename T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template<typename T> inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template<typename T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template<typename T> inline T nHr(T a,T b){return nCr(a+b-1,b);}

typedef pair<int, int> INTP;
typedef vector<int> INTV;
struct edge2 {int to, cost;};
struct edge3 {int from, to, cost;};

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

  int N, M, L, Q; cin >> N >> M >> L;

  vector<INTV> dist1(N, INTV(N, VERYBIG)), dist2(N, INTV(N, VERYBIG));
  REP(i, N) dist1[i][i] = 0;

  REP(i, M){
    int A, B, C; cin >> A >> B >> C;
    A--; B--;
    if(C <= L) {
      dist1[A][B] = C;
      dist1[B][A] = C;
    }
  }

  REP(k, N) REP(i, N) REP(j, N){
    dist1[i][j] = min(dist1[i][j], dist1[i][k]+dist1[k][j]);
  }

  REP(i, N) REP(j, N){
    if(dist1[i][j] <= L) dist2[i][j] = 1;
  }

  REP(k, N) REP(i, N) REP(j, N){
    dist2[i][j] = min(dist2[i][j], dist2[i][k]+dist2[k][j]);
  }

  cin >> Q;
  REP(q, Q){
    int s, t; cin >> s >> t; s--; t--;
    if(dist2[s][t] == VERYBIG){
      cout << -1 << endl; continue;
    }
    cout << dist2[s][t]-1 << endl;
  }
}


Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
 
const int MAX = 2e5 + 5;

int32_t main()
{
   IOS;
   int n, m,k,books=0;
   cin >> n >> m >> k;

   int pa[MAX], pb[MAX];

   int a[MAX], b[MAX];

   for(int i=0; i<n; i++)
   {
   		cin >> a[i];
   		pa[i+1]=pa[i]+a[i];
   }

   for(int i=0; i<m; i++)
   {
   		cin >> b[i];
   		pb[i+1]=pb[i]+b[i];
   }

   int j=m;

   for(int i=0; i<=n; i++)
   {
   		if(pa[i]>k)
   			break;
   		while(pb[j]>k-pa[i])
   		{
   			j--;
   		}
   		books=max(books,i+j);
   }

   cout << books << endl;
   	
   return 0;
}

Measured memory_bytes: 9912
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < static_cast<int>(n); ++i)
#define REPR(i, n) for (int i = static_cast<int>(n) - 1; i >= 0; --i)
#define FOR(i, a, b) \
  for (int i = static_cast<int>(a); i < static_cast<int>(b); ++i)
#define FORR(i, a, b) \
  for (int i = static_cast<int>(b) - 1; i >= static_cast<int>(a); --i)
#define ALL(f, x, ...) \
  ([&](auto &y) { return (f)(begin(y), end(y), ##__VA_ARGS__); })(x)
#define INDEX(x, xs) &x - &xs[0]

void async_io() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}
const auto inf = INT_MAX / 3;
const auto pi = 2 * std::acos(0.0);
const auto eps = 1e-14;
using ll = long long int;
using ull = unsigned long long;

signed main() {
  async_io();
  int n;
  while (true) {
    cin >> n;
    if (n == 0) return 0;
    auto sum = 0;
    for (int i = 2;; i++) {
      auto base = i * (i + 1) / 2;
      if (base > n) break;
      if ((base - n) % i == 0) sum++;
    }
    cout << sum << "\n";
  }
}

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

int main()
{
    char ch[4], s[4];
    int i, sum = 0;

    cin >> ch >> s;

    for(i = 0; i < 3; i++){
        if(ch[i] == s[i]){
            sum++;
        }
    }

    cout << sum << endl;

    return 0;
}


Measured memory_bytes: 256
from math import gcd
a,b,c,d,e,f=map(int,input().split())
g=gcd(a,b)
a=a//g
b=b//g
G=gcd(c,d)
c=c//G
d=d//G
axby=[0]*1000
czdw=[0]*1000
for x in range(100):
    for y in range(100):
        if a*x+b*y<(a-1)*(b-1):
            axby[a*x+b*y]=1
for z in range(100):
    for w in range(100):
        if c*z+d*w<(c-1)*(d-1):
            czdw[c*z+d*w]=1
A=[]
C=[]
for i in range(1000):
    if axby[i]==1:
        A.append(i)
for i in range(1000):
    if czdw[i]==1:
        C.append(i)
i=(a-1)*(b-1)
while i<=(f//(100*g))+5:
    A.append(i)
    i+=1
j=(c-1)*(d-1)
while j<=(f//G)+5:
    C.append(j)
    j+=1
n=len(A)
m=len(C)
dis=0
ans=[0,0]
for i in range(n):
    for j in range(m):
        if 100*g*A[i]+G*C[j]<=f and G*C[j]<=e*g*A[i] and not(A[i]==C[j]==0):
            if dis<=(100*G*C[j])/(100*g*A[i]+G*C[j]):
                dis=(100*G*C[j])/(100*g*A[i]+G*C[j])
                ans[0],ans[1]=A[i],C[j]
print(100*g*ans[0]+G*ans[1],G*ans[1])




Measured memory_bytes: 73672
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
int main(){
	#ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
#endif
       ios_base::sync_with_stdio(false);
       cin.tie(0);
   int n , cnt = 0; 
   cin>>n;
   int a[n];
   for(int i =0; i<n; i++){
   	cin>>a[i];
   } 
   for(int i = 0;i <n ;i++){
      for(int j = i+1 ;j <n ;j++){
     cnt +=(a[i]*a[j]);
 }
}
   cout<<cnt<<endl;
   return 0;
}

Measured memory_bytes: 3700
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int gcd(int a, int b) {  
  return b != 0 ? gcd(b, a % b) : a;
}//MAX
int lcm(int a, int b) { 
   return a * b / gcd(a, b);
   }
//MIN
 main() {
int n,k;
cin >> n >> k;
double ans = 0.00;
double che;
for(int i=1;i<=n;i++){
  ll point = i;
   che = 1.00/n;
  while(point<k){
    che*=1.00/2.00;
    point*=2;
  }
  ans+=che;
}
cout << fixed<<setprecision(15);
cout << ans << endl;
 }
 


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
const int maxN = 2e5 + 55;

int n, k;
ll sum[maxN];

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

    cin >> n >> k;

    for(int i = 1; i <= n + 1; i++) {
        sum[i] = i - 1;
        sum[i] += sum[i - 1];
    }

    ll ans = 0;

    for(int i = k; i <= n + 1; i++) {
        ll lf = sum[i];
        ll rt = sum[n + 1] - sum[(n + 1) - i + 1 - 1];
        ans = (ans + (rt - lf + 1) % MOD) % MOD;
    }

    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 5200
#include<iostream>
using namespace std;
int main()
{
    long int n,m,a[101],b[101],sum=0,i,j,c,p=0,t;
    cin>>n>>m>>c;
    for(i=0;i<m;i++)
    {
        cin>>b[i];
    }
    while(n--)
    {
        sum=0;
        for(i=0;i<m;i++)
        {
            cin>>a[i];
        }
        for(i=0;i<m;i++)
        {
            t=a[i]*b[i];
            sum+=t;
        }
        sum+=c;
        if(sum>0)
        {
            p++;
        }
    }
    cout<<p<<endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef long long ll;
int main(void)
{
  int n,m;
  scanf("%d %d",&n,&m);
  ll a[100],b[100],c[100],d[100];
  for(int i=0;i<n;i++){
    scanf("%lld %lld",&a[i],&b[i]);
  }
  for(int i=0;i<m;i++){
    scanf("%lld %lld",&c[i],&d[i]);
  }

  for(int i=0;i<n;i++){
    int min=abs(a[i]-c[0])+abs(b[i]-d[0]);
    int min_tmp=1;
    for(int j=1;j<m;j++){
      // printf("%d\n",abs((a[i]-c[j])+(b[i]-d[j])));
      if(abs(a[i]-c[j])+abs(b[i]-d[j])<min){
        min=abs(a[i]-c[j])+abs(b[i]-d[j]);
        min_tmp=j+1;
      }
    }
    printf("%d\n",min_tmp);
  }



  return 0;
}


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

int main() {
    int N, A[100];

    cin >> N;
    for (int i=0; i<N; i++) cin >> A[i];

    // 降順にソート
    sort(A, A+N, greater<int>());

    int alice_score = 0, bob_score = 0;
    for (int i=0; i<N; i++) {
        if (i % 2 == 0) alice_score += A[i];
        else bob_score += A[i];
    }
    cout << alice_score - bob_score << endl;
}

Measured memory_bytes: 256
from fractions import gcd
import sys
sys.setrecursionlimit(4100000)

def os(): return input()
def oi(): return int(input())
def oli(): return map(int, input().split())
def olai(): return list(map(int, input().split()))
def olas(): return list(input().split())
def mlai(L): return [int(input()) for _ in range(L)]
def mlas(L): return [input() for _ in range(L)]
def ar(a, b, c=-1, d=-1, INIT=0):
    if(c==-1): return [[INIT]*b for _ in range(a)]
    if(d==-1): return [[[INIT]*c for _ in range(b)] for __ in range(a)]
    return [[[[INIT]*d for _ in range(c)] for __ in range(b)] for ___ in range(a)]

def lcm(a, b): return (a*b)//gcd(a, b)
#MOD
P = 10**9 + 7
N = 200001 #使う最大値+1以上にする、値に注意3*10^5とかにしとくと安心
inv = [0] + [1] # 1/x
finv = [1] + [1] # 1/x!
fac = [1] + [1] # x!
for i in range(2, N):
  inv += [inv[P % i] * (P - int(P / i)) % P]
  fac += [(fac[i-1] * i) % P]
  finv += [(finv[i-1] * inv[i]) % P]

def comb(a, b):
    if a<b or b < 0: return 0 # error
    return (fac[a] * ((finv[b] * finv[a-b]) % P)) %P

#全方位木dp
#-------------------------------------------------------------------
#扱うクラス
class T:
    num = 1
    child = 0

    def __init__(self, a, b):
        self.num = a
        self.child = b

#零元
zero = T(1, 0)
#一個上に遷移した時の変化
def step(x):
    return T(x.num, x.child+1)
#マージ
def merge(x, y):
    return T((x.num*y.num*comb(x.child+y.child, x.child))%P, x.child+y.child)

G = [[] for _ in range(200001)]
down_data = [zero for _ in range(200001)]
dat = [zero for _ in range(200001)]

def dfs(now, parent):
    cnt = 0
    for to in G[now]:
        if(to==parent): continue
        cnt += 1
        dfs(to, now)
        down_data[now] = merge(down_data[now], step(down_data[to]))

def dfs_rev(now, parent, rev):
    #累積
    left = []
    right = []
    cnt = 0
    for to in G[now]:
        if(to==parent): continue
        if(len(left)==0): left.append(step(down_data[to]))
        else: left.append(merge(left[cnt-1], step(down_data[to])))
        cnt += 1
    cnt = 0
    for to in reversed(G[now]):
        if(to==parent): continue
        if(len(right)==0): right.append(step(down_data[to]))
        else: right.append(merge(right[cnt-1], step(down_data[to])))
        cnt += 1
    cnt = 0
    dat[now] = merge(rev, down_data[now])

    for to in G[now]:
        if(to==parent): continue
        x = zero if cnt==0 else left[cnt-1]
        y = zero if cnt==len(right)-1 else right[len(right)-2-cnt]
        dfs_rev(to, now, step(merge(rev, merge(x, y))))
        cnt += 1
#-------------------------------------------------------------------
def main():
    n = oi()
    for i in range(n-1):
        a, b = oli()
        G[a].append(b)
        G[b].append(a)
    root = -1
    for i in range(1, n+1):
        if(len(G[i]) == 1):
            root = i
            break
    dfs(root, -1)
    dfs_rev(root, -1, zero)
    for i in range(1, n+1):
        print(dat[i].num)

if __name__ == "__main__": main()


Measured memory_bytes: 146856
from collections import Counter
def prm(a):
  if a == 1 or a == 4:
    return False
  for i in range(2,int((a)**0.5+1)):
    if a%i == 0:
      return False
  else:
    return True
prime = []
for i in range(1,10**6+1):
  if prm(i):
    prime.append(i)
def sepa(a):
  ans = []
  while a>1:
    for x in prime:
      if a%x == 0:
        ans.append(x)
        a = a//x
        break
    else:
      ans.append(a)
      a = 1
  return Counter(ans)
n,p = map(int,input().split())
c = sepa(p)
ans = 1
for k,v in c.items():
  if n<=v:
    ans *= k**(v//n)
print(ans)

Measured memory_bytes: 47196
import java.io.*;

class Main {

    public static void main( String[] args ) {
        try {
	      	BufferedReader kb = new BufferedReader( new InputStreamReader( System.in ) );
			String[] str = kb.readLine( ).split( " " );
        	int n = Integer.parseInt( str[0] );
        	int k = Integer.parseInt( str[1] );
        	int[] w = new int[n];
        	int i;
        	int maxW = 0, sumW = 0;
        	for( i=0; i<n; i++ ) {
        		w[i] = Integer.parseInt( kb.readLine( ) );
        		sumW += w[i];
        		maxW = Math.max( maxW, w[i] );
        	}
        	
        	int left, right, middle;
        	int loadings, P;
        	int truckCnt;
        	
        	P = 0;
        	if( n == k ) {
        		P = maxW;
        	} else if( 1 == k ) {
        		P = sumW;
        	} else {
        		left = Math.max( maxW, sumW/k );
	        	right = 10000*100000;
	        	loadings = 0;
	    		while( left <= right ) {
		        	middle = ( left+right )/2;
					truckCnt = 0;
					loadings = 0;
					for( i=0; i<n; i++ ) {
						loadings += w[i];
						sumW += loadings;
						if( middle < loadings ) {
							truckCnt++;
							if( k < truckCnt+1 ) { break; }
							i--;
							loadings = 0;
						}
					}
					if( truckCnt+1<= k ) { 
						P = middle;
					}
					if( k < truckCnt+1 ) {
						left = middle + 1;
					} else {
						right = middle - 1;
					}
	    		}
    		}
    		
			System.out.println( P );
        } catch( IOException e ) {
            System.err.println( e );
        }
    }
}

Measured memory_bytes: 29336
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        long[] a = new long[n];
        Map<Long, Long> map = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            long temp = Long.parseLong(sc.next());
            a[i] = temp;
            if (map.containsKey(temp)) {
                map.put(temp, map.get(temp) + 1);
            } else {
                map.put(temp, 1L);
            }
        }
        long ans = 0;
        for (Map.Entry<Long, Long> e : map.entrySet()) {
            ans += e.getValue() * (e.getValue() - 1) / 2;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(ans - (map.get(a[i]) - 1));
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }
}

Measured memory_bytes: 76716
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb(x) push_back(x)
#define f(i,st,n) for(i=st;i<n;i++)
#define qu queue
#define ps(x) push(x)
#define vec vector
#define ft() front()
#define mst(a,b) memset(a,b,sizeof(a))
#define mod 1000000007
#define sfl(x) scanf("%lld",&x)
#define pfl(x) printf("%lld\n",x)
#define pf(x) printf("%lld",x)
#define mpr make_pair
#define fs first
#define se second
#define inf LLONG_MAX
 
 
 
ll gcd(ll a,ll b){
    if(a==0){
        return b;
    }                     
    return gcd(b%a,a);
}
ll power(ll x,ll y){            
    ll res=1;
    while(y>0){
        if(y%2==1){
            res=(res*x);
        }
        x=(x*x);
        y=y/2;
    }
    return res;
}
 

double a[3000],dp[3000][3000];
ll n;


double fn(ll i,ll k){
if(k>(n/2))return 0.00;
if(i==n)return 1.00;

if(dp[i][k]!=-1)return dp[i][k];

ll p=1;

dp[i][k]= (a[i]*fn(i+1,k))+((1-a[i])*fn(i+1,k+1));

return dp[i][k];




}
int main(){
 
/* #ifndef ONLINE_JUDGE
    
   freopen("input.txt", "r", stdin);
   
   freopen("output.txt", "w", stdout);
   #endif*/

ll i,j;
sfl(n);
f(i,0,3000){
  f(j,0,3000)dp[i][j]=-1;
}

f(i,0,n){
scanf("%lf",&a[i]);
}

printf("%.10lf",fn(0,0));



   return 0;
 }

Measured memory_bytes: 70784
#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
using vpii = vector<pair<int, int>>;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define rep1(i, n) for (int i = 1; i < (int)n; i++)
const ll mod = 1e9+7;
const ll inf = 1e10;
const double pi = 3.141592;

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int q;
  cin >> q;
  vector<int> p(100002, 0);
  vector<int> like(100002, 0);
  for(int i = 2; i < 100001; ++i){
    if(!p[i]) for(int j = i+i; j < 100001; j += i) ++p[j];
  }
  for(int i = 3; i < 100001; i += 2){
    if(!p[i] && !p[(i+1)/2]) ++like[i];
  }
  for(int i = 3; i < 100001; ++i) like[i] += like[i-1];
  rep(i, q){
    int l, r;
    cin >> l >> r;
    cout << like[r]-like[l-1] << "\n";
  }
  return 0;
}   

Measured memory_bytes: 1408
#include<bits/stdc++.h>
#include<stdio.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define pb                  push_back
#define arr                 vector<ll>
#define mem(x,val)          memset(x,val,sizeof(x))
#define vp                 vector<pair<ll,ll>>
#define matrix              vector<vector<ll> >
#define digit(x)            floor(log10(x))+1
#define debug(x)            cerr << #x << " is " << x << endl;
#define all(a)              a.begin(),a.end()
#define fixed               setprecision(15)
// ll dx[]={-1,1,0,0},dy[]={0,0,-1,1}; 4 Sides
//ll dx[]={-1,1,-1,1,0,0,-1,1} , dy[]={-1,1,0,0,-1,1,1,-1};    8 Sides
using namespace std;
ll maxx = INT_MIN;  
ll minx = INT_MAX;
ll MOD = (ll)1e9+7;
arr read(ll n){
    arr a;
    for (ll i=0;i<n;i++){
        ll x;
        cin>>x;
        a.pb(x);
    }
    return a;
}
  int main(){
        ll n;
        cin>>n;
        arr a  = read(n);
        arr pre;
        pre.pb(a[0]);
        for (ll i=1;i<a.size();i++){
            pre.pb(a[i]+pre.back());
        }
        ll ans = 0;
        ll cmp = pre.back();
        for (ll i=0;i<a.size()-1;i++){
            ll c = cmp - pre[i];
            c = c%MOD;
            ll d = a[i]%MOD;
            ll e = (c*d)%MOD;
            ans += e%MOD;
        }
        cout<<ans%MOD<<endl;
        return 0;
}


Measured memory_bytes: 7884
#include <iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
int main()
{
	int a, b, k, gcd[100] = {}, all = 0, cnt = 0, tmp = 0;
	cin >> a >> b >> k;

	for (int i = 1; i <= 100; i++) {
		if (a%i == 0 && b%i == 0)gcd[i] = i,all++;
	}

	for (int i = 1; i <= 100; i++) {
		if (gcd[i] > 0)cnt++;
		if (k == all - cnt + 1) {tmp = gcd[i]; break;}
	}
	cout << gcd[tmp] << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ALL(A) (A).begin(),(A).end()
#define ll long long
const ll mod = 1e9+7;
const ll INF = 2*1e18;
const int inf = 1e9+7;


ll gcd(ll a,ll b){
	ll c;
	while(a%b){
		c = b;
		b = a%b;
		a = c; 
	}
	return b;
}
bool IsPrime(ll num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (ll i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}
int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll A,B;
	cin >> A >> B;
	set<ll> st;
	vector<ll> v;
	for(ll i=1;i*i<=A;i++){
		if(A%i==0){
			st.insert(i);
			if(i*i!=A)st.insert(A/i);
		}
	}
	for(ll i=1;i*i<=B;i++){
		if(B%i==0){
			if(st.find(i)!= st.end()){
				v.push_back(i);
			}
			if(st.find(B/i)!=st.end()){
				v.push_back(B/i);
			}
		}
	}
	ll cnt = 1;
	for(auto x:v){
		//cout << x << endl;
		if(IsPrime(x)){
			cnt++;
		//	cout << x << endl;
		}
	}
	cout << cnt << endl;
}

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

int main(){
  int i,j,cnt=0;
  ll n,a,b;
  cin>>n>>a>>b;
  if(a>b)cout<<0;
  else if(a==b)cout<<1;
  else if(n==1)cout<<0;
  else cout<<(n-2)*(b-a)+1;
}

Measured memory_bytes: 256
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from operator import xor
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    n = int(input())
    a = [int(ai) for ai in input().split()]

    x = reduce(xor, a)

    sol = [x ^ i for i in a]
    print(*sol)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()


Measured memory_bytes: 101484
import sys
sys.setrecursionlimit(int(1e6))

n=int(input())
l=[[0,0,0]]
for _ in range(n):
    l.append(list(map(int,input().split())))

memo=[[-1,-1,-1] for _ in range(n+1)]
memo[0][0]=0
memo[0][1]=0
memo[0][2]=0
def dp(i,j):
    if memo[i][j]!=-1:
        return memo[i][j]
    else:
        memo[i][j]=max(dp(i-1,(j+1)%3)+l[i][j],dp(i-1,(j+2)%3)+l[i][j])
        return memo[i][j]
print(max(dp(n,0),dp(n,1),dp(n,2)))

Measured memory_bytes: 143628
from sys import stdin
import math

a=int(stdin.readline())
PP=0
K=0

if a==1:
    print(0)
    K=1
L=list()


for b in range(2,int(math.floor(math.sqrt(a)))+1):
    count=0
    if a%b==0:
        while a%b==0:
            count+=1
            a=a/b
    if count>0:
       L.append(count)


if len(L)==0 and K==0:
    print(1)
    PP=1

if a!=1:
    L.append(1)

sum=0

for k in range(0,len(L)):
    p=L[k]
    sum+=int(math.floor((-1+math.sqrt(1+8*p))/2))


if PP==0 and K==0:
   print(sum)

Measured memory_bytes: 9312
// tyrionlannister238

#include<bits/stdc++.h>
using namespace std;
 
string to_string(string s) {
    return '"' + s + '"';
}

string to_string(char ch) {
    string s(1, ch);
    return '\'' + s + '\'';
}

string to_string(const char *s) {
    return to_string((string)s);
}

string to_string(bool b) {
    return (b ? "true" : "false");
}

template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for (const auto &x : v) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}

#ifndef ONLINE_JUDGE
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define ll long long
#define pb push_back
#define speed ios_base::sync_with_stdio(0);	cin.tie(0);	cout.tie(0);

int main() {
	ll a, b, c, d; cin >> a >> b >> c >> d;
	cout << ( ( (a/d + (a % d != 0)) < (c/b + (c % b != 0)) ) ? "No\n" : "Yes\n") ;
}


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

typedef long long ll;

#define v(T) vector<T>
#define ttt(T) tuple<T, T, T>
#define pb push_back
#define mp make_pair
#define rep(i, s, n) for(int i=s;i<n;i++)
#define repeq(i,s,n) for(int i=s;i<=n;i++)
#define poiu(n) for(int i=0; i < n; i++)
#define MOD 1000000007
#define endl '\n'

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

using namespace std;

int n;
int k;
int temp;
int cnt;


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

    cin >> n;
    cin >> k;
    while(n--) {
        cin >> temp;

        if(temp >= k)
            cnt++;
    }
    cout << cnt << endl;

    


    return 0;

}



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

int main() {
  int K;
  cin >> K;
  string S;
  cin >> S;
  string A;
  int size = S.size();
    if ( size <= K ){
    cout << S <<endl;
  }
  else {
    for (int i =0; i<K ; i++ ){
      A += S.at(i);
    }
    cout << A << "..." << endl;
    }
}

Measured memory_bytes: 3624
//12
#include<iostream>
#include<vector>

using namespace std;

int main(){
  for(int n;cin>>n,n;){
    vector<int> up;
    while(n--){
      int p;
      cin>>p;
      up.push_back(p);
    }
    for(int i=0;i<up.size()-1;i++){
      if(i==0||up[i]-up[i-1]!=1){
	cout<<up[i]<<((up[i+1]-up[i]==1)?'-':' ');
      }else if(up[i+1]-up[i]!=1){
	cout<<up[i]<<' ';
      }
    }
    cout<<up.end()[-1]<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include <iostream>
 
using namespace std;
 
bool BSearch(int A[] ,unsigned int sp ,unsigned int ep ,int n){ //あり、なしのみboolで返す
  int mid = (ep+sp) / 2;
  int l = sp;
  int r = ep;
  while(l <= r){
    mid = (l + r) / 2;
    if(A[mid] == n){
      return 1;
    }
    else if(A[mid] < n){
      l = mid + 1;
    }
    else{
      r = mid - 1;
    }
  }
  return 0;
}
 
int main(void){
  int n,q;
  int counter = 0;
  int S[100000];
  int T[50000];
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> S[i];
  }
  cin >> q;
  for(int i=0;i<q;i++){
    cin >> T[i];
  }
 
 
  for(int i=0;i<q;i++){
    if(BSearch(S,0,n,T[i]))
      counter++;
  }
  cout << counter << endl;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define rrep2(ri,x,n) for(int ri = (int)(n-1); ri >= (int)(x); ri--)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using namespace std;

int main(){
  string s;
  cin >> s;
  int n = s.size();
  bool f = (s.back() == '1' || s.front() == '0');
  s.pop_back();
  string sr = s;
  reverse(sr.begin(), sr.end());
  if(f == true || sr != s){
    cout << -1 << endl;
    return 0;
  }
  vector<int> from;
  rep(i, n-1){
    if(i == n-2){
      cout << i+1 << " " << i+2 << endl;
    }
    if(s.at(i) == '1'){
      for(int j : from){
        cout << j+1 << " " << i+1 << endl;
      }
      from.clear();
    }
    from.push_back(i);
  }
  return 0;
}

Measured memory_bytes: 4128
import Control.Monad
import qualified Data.ByteString.Char8 as BS
import Data.List
import Data.Maybe
import Data.Ord
import Data.Time
import qualified Data.Vector as VC
import qualified Data.Vector.Mutable as VM

readIntegers :: IO [Integer]
readIntegers = map (fst . fromJust . BS.readInteger) . BS.words <$> BS.getLine

readIntegerLists :: Int -> IO [[Integer]]
readIntegerLists n = replicateM n (map (fst . fromJust . BS.readInteger) . BS.words <$> BS.getLine)

readInts :: IO [Int]
readInts = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine

readIntLists :: Int -> IO [[Int]]
readIntLists n = replicateM n (map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine)

readStrings :: IO [String]
readStrings = map BS.unpack . BS.words <$> BS.getLine

readStringLists :: Int -> IO [[String]]
readStringLists n = replicateM n (map BS.unpack . BS.words <$> BS.getLine)

main :: IO ()
main = do
  [n, k] <- readInts
  h <- readInts
  print $ solve k h

solve k h
  | null dropped = 0
  | otherwise = foldl1' (+) dropped
  where
    dropped = drop k $ sortOn Down h

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

using namespace std;

const int MAX_N = 1e5 + 5;
const int MAX_L = 20;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;

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

int N;
ll A[MAX_N], B[MAX_N];
ll ans = 0;

void solve() {
    cin >> N;
    for (int i = 1; i <= N + 1; i++) cin >> A[i];
    for (int i = 1; i <= N; i++) cin >> B[i];
    for (int i = 1; i <= N; i++) {
        ll fi = min(B[i], A[i]);
        ans += fi; B[i] -= fi;
        ll se = min(B[i], A[i + 1]);
        ans += se; A[i + 1] -= se;
    }
    cout << ans;
}

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

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


Measured memory_bytes: 1792
N = int(input())

anslist = [0]
i = 1
while i < (N+1):
    if i % 15 == 0:
        a=1
    elif i % 3 == 0:
        a=1
    elif i % 5 == 0:
        a=1        
    else:
        anslist.append(i)
    i += 1
    
b = sum(anslist)

print(b)

Measured memory_bytes: 29988
n,k = map(int,input().split())
if(k >= n+1):
    print(1)
else:
    t = 0
    for i in range(k,n+2):
        d = n - i
        s1 = i * (i - 1) // 2
        s2 = n * (n + 1) // 2 - d * (d + 1) // 2
        t += s2 - s1 + 1
        t %= 10**9+7
    print(t)

Measured memory_bytes: 9220
N = int(input())
buble_A = list(map(str,input().split()))
selection_A=list(buble_A)
number=str(''.join(buble_A))
number=list(number[1::2])
number=[int(x) for x in number]
num_B=list(number)
num_S=list(number)

#バブルソート
flg=1
while flg:
    flg=0
    for i in range(N-1,0,-1):
        if num_B[i]<num_B[i-1]:
            num_B[i],num_B[i-1]=num_B[i-1],num_B[i]
            buble_A[i],buble_A[i-1]=buble_A[i-1],buble_A[i]
            flg=1

#選択ソート
for i in range(N-1):
    minj=i
    for j in range(i,N):
        if num_S[j]<num_S[minj]:
            minj=j
    if minj != i:
        num_S[i],num_S[minj]=num_S[minj],num_S[i]
        selection_A[i],selection_A[minj]=selection_A[minj],selection_A[i]

[print(buble_A[x],end=' ') for x in range(N-1)];print(buble_A[N-1]);print('Stable')

[print(selection_A[x],end=' ') for x in range(N-1)];print(selection_A[N-1]); print('Stable') if buble_A == selection_A else print('Not stable')



Measured memory_bytes: 5616
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using namespace std;
int main(){
  int a,b;
  cin>>a>>b;
  
  if(a>b){
    cout<<a-1<<endl;
  }
  else{
    cout<<a<<endl;
  }
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const long long maxn=1e9+10;
int main()
{
    int x;cin>>x;
    int ansA,ansB;
    for(int i=1;(long long)pow(i,5)<=maxn*maxn;i++)
    {
    	if(x>=pow(i,5))
    	{
    		long long num=x-pow(i,5);
    		int zhishu=(int)pow(num,1.0/5.0);
    		if((long long)pow(zhishu,5)==num)
    		{
    			ansA=i;ansB=-zhishu;break;
			}
		}
		else if(x<pow(i,5))
		{
			long long  num=pow(i,5)-x;
			int zhishu=(int)pow(num,1.0/5.0);
			if((long long)pow(zhishu,5)==num)
			{
				ansA=i;ansB=zhishu;break;
			}
		}
	}
	cout<<ansA<<" "<<ansB<<endl;
	return 0;
}

Measured memory_bytes: 4096
n = int(input())
A = [int(i) for i in input().split()]

p = 10 ** 9 + 7

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def get_inv(n, p=10**9 + 7):
    inv = [0, 1]
    for i in range(2, n+1):
        inv.append(-(p//i * inv[p%i]) % p)
    return inv

f = fact(n)
inv = get_inv(n)

csum = [0]

for i in range(1, n+1):
    csum.append((csum[-1] + inv[i]) % p)

ans = 0
for i, a in enumerate(A):
    ans += (csum[i+1] + csum[n-i] - csum[1] + p) % p * a
    ans %= p

print(ans * f[n] % p)

Measured memory_bytes: 19216
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <string>
#pragma warning(disable : 4996)

#define MAX_N 50
#define MAX_K 100

std::vector<int> D;
int Max = 0;

void refunc(int l, int r, int k, int prev, int sum) {
	//printf("l:%d r:%d sum:%d k:%d\n", l, r, sum, k);
	if (k == 0) {
		//printf("total: %d\n", sum);
		if (sum > Max) {
			Max = sum;
		}
		return;
	}
	if (r-l  >= 0) {
		refunc(l + 1, r, k - 1, D[l], sum + D[l]);
		refunc(l, r - 1, k - 1, D[r], sum + D[r]);
	}
	if (prev < 0) {
		refunc(l, r, k - 1, 0, sum - prev);
	}
	if ((r - l < 0) && (prev >= 0)) {
		//printf("total: %d\n", sum);
		if (sum > Max) {
			Max = sum;
		}
		return;
	}
	
}
bool compare(int l, int r) {
	return l < r;
}

int main(void) {
	int n, k;
	scanf("%d %d", &n, &k);
	for (int i = 0; i < n; ++i) {
		int a;
		scanf("%d", &a);
		D.push_back(a);
	}
	//refunc(0, D.size() - 1, k, 0, 0);
	//printf("%d", Max);
	int sumA = 0;
	std::vector<int> minusA;
	for (int l = 0; l <= n; ++l) {
		int il = l - 1;
		if (il >= 0) {
			int v = D[il];
			sumA += v;
			if (v < 0) minusA.push_back(v);
		}
		int sumB = 0;
		std::vector<int> minusB;
		for (int r = 0; r <= n; ++r) {
			if (l + r > n) continue;
			if (l + r > k) continue;
			int ir = r - 1;
			if (ir >= 0) {
				int v = D[D.size()-1-ir];
				sumB += v;
				if (v < 0) minusB.push_back(v);
			}
			int sum = sumA+sumB;
			std::vector<int> minus = minusA;
			std::copy(minusB.begin(), minusB.end(), std::back_inserter(minus));
			int op = k - l - r;
			std::sort(minus.begin(), minus.end());
			if (op > minus.size()) op = minus.size();
			for (int i = 0; i < op ; ++i) {
				sum = sum + (-1 * minus[i]);
			}
			if (sum > Max) {
				Max = sum;
			}
		}
	}

	printf("%d", Max);



	return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)?"YES":"NO")
ll n,m;
//ld ;
//string s;
// char c;

int main() {
  cin >> n >> m;
  cout << ((n*(n-1))/2)+((m*(m-1))/2) << endl;
  return 0;
}

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

int main(){
	string s; cin>>s;
	bool ok = true;
	if(s[0] != 'A') ok = false;
	if(isupper(s[1])) ok = false;
	if(isupper(s.back())) ok = false;
	int c = 0;
	for(int i=2; i<(int)s.size()-1; ++i)
		if(s[i] == 'C') c++;
	cout<< (ok && c==1? "AC":"WA") <<endl;
}


Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse4")
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
#define int ll
#define sz(x) (int)(x).size();
#define all(x) x.begin(), x.end()
#define trav(i,a) for(auto &i:a) 
inline int in(){int x;scanf("%lld",&x);return x;}
int32_t main()
{
	int n=in();
	vector<int>a(n),b(n);
	trav(i,a){i=in();}
	iota(b.begin(),b.end(),1);
	int i=0,j=0;
	while(i<n and j<n)
	{
		if(a[i]==b[j]){i++;j++;}
		else i++;
	}
	if(j==0){cout<<-1;}
	else
	cout<<n-j;
	
}

Measured memory_bytes: 6404
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<numeric>
#include<utility>

using namespace std;

typedef long long int ll;
const int INF = 1<<30;
const long long LINF = 1LL<<60;

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    cout << min(b / a, c) << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long counter[100005];

int main(){
  long long n,k;
  cin>>n>>k;
  while(n--){
    int a,b;
    cin>>a>>b;
    counter[a]+=b;
  }
  long long sum = 0;
  for(int i=1; i<=100000; i++){
    sum+=counter[i];
    if(sum>=k){
      cout<<i;
      return 0;
    }
  }
}

Measured memory_bytes: 4336
#include <iostream>

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

   for(int i=0; i<S.size(); ++i){
      int index = S[i] - 'A' + N;
      if(index>=26) index -= 26;
      S[i] = 'A' + index;
   }
   std::cout << S << std::endl;
   return 0;
}


Measured memory_bytes: 256
def prime_t(t):
    i=2
    while i**2<=t:
        if t%i==0:
            return 0
        i+=1
    return 1
l=[]
for i in range(2,50022):
    if prime_t(i):
        l.append(i)
#print l
while 1:
    try:
        o=y=50000
        n=int(raw_input())
        for i in l:
            if y<n and n<i:
                print y,i
                break
            elif y==n and o<n and n<i:
                print o,i
                break
            o=y
            y=i
        
    except:
        break

Measured memory_bytes: 7756
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
 
        if(a+b+c>=22){
            // 出力
	        System.out.println("bust");
        }else{
            // 出力
	        System.out.println("win");
        }
	}
}

Measured memory_bytes: 35508
import java.util.*;

public class Main{
  static int p = 1000000007;
  static long[] fac, inv, finv;
  public static void main(String[]args){
    Scanner sc = new Scanner(System.in);
    int X = sc.nextInt();
    int Y = sc.nextInt();
    int Z = X+Y;
    if(Z%3 != 0){
      System.out.println(0);
      return;
    }
    
    
    int d = Z/3;
    int e = (d-Math.abs(X-Y))/2;
    
    fac = new long[Z];
    finv = new long[Z];
    inv = new long[Z];
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < Z; i++){
        fac[i] = fac[i - 1] * i % p;
        inv[i] = p - inv[p%i] * (p/i)%p;
        finv[i] = finv[i-1] * inv[i] % p;
    }
    long ans = cmb(d, e);
    System.out.println(ans);
  }
  
  public static long cmb(int n, int k){
    if(n < k){
      return 0;
    }
    if(n<0 || k<0){
      return 0;
    }
    return fac[n] * (finv[k] * finv[n - k] % p) % p;
}
    
}

Measured memory_bytes: 70612
#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i=a; i<n; i++)
#define RREP(i, a, n) for(ll i=n-1; i>=a; i--)
typedef long long ll;
const ll mod =1e9+7;
const ll inf =1e18;
using namespace std;

ll a, b;
int main() {
    cin>>a>>b;
    cout<<max(0LL, a-2*b)<<endl;
    return 0;
}

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

using namespace std;
int main(){
	int k;
	int a,b;
	string ans="NG";
	cin>>k>>a>>b;
   while(a<=b){
   	if(a%k==0){
   		ans="OK";
   		break;
   	}
   	a++;
   }
   cout<<ans<<endl;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define bug1( x ) {cerr << (#x) <<"="<< x << endl;}
#define bug2( x , y ) {cerr << (#x) <<"="<< (x) << "    " << (#y) << "="<< (y) << endl;}
#define bug3( x , y , z ) {cerr << (#x) <<"="<<(x) << "    " << (#y) <<"="<< (y) << "    " << (#z) <<"="<< (z) << endl;}
#define bug4( x , y , z , w) {cerr << (#x) <<"="<<(x) << "    " << (#y) <<"="<< (y) << "    " << (#z) <<"="<< (z) << "    " << (#w) <<"="<< w << endl;}
#define bug5( x , y , z , w ,p) {cerr << (#x) <<"="<<(x) << "    " << (#y) <<"="<< (y) << "    " << (#z) <<"="<< (z) << "    " << (#w) <<"="<< w << "    " << (#p) <<"="<< p << endl;}
#define bug6( x , y , z , w ,p , q) {cerr << (#x) <<"="<<(x) << "    " << (#y) <<"="<< (y) << "    " << (#z) <<"="<< (z) << "    " << (#w) <<"="<< w << "    " << (#p) <<"="<< p << "    " << (#q) <<"="<< q << endl;}
#define bugn( x , n ) {cerr << (#x) <<":";for(int i=0;i<n;i++)cerr << x[i] <<"  "; cerr << endl;}
#define bugnm( x , n , m ) {cerr << (#x)<<endl;for(int i=0;i<n;i++){cerr << "Row #" << i<< ":";for(int j=0;j<m;j++)cerr << x[i][j] << "   ";cerr << endl;}}
typedef long long ll;
typedef long double ld;
using namespace std;


struct box{
	int w,pos,n_related=0;
	bool operator <(const box other){
		return w < other.w;
	}
};
int32_t main(){
	IOS
	int n,m;cin>>n>>m;
	vector<box>a;
	for(int i=0;i<n;i++){
		box cur; cin >> cur.w; cur.pos = i; cur.n_related = 1;
		a.push_back(cur);
	}
	for(int i=0;i<m;i++){
		box cur; cin >> cur.w; cur.pos = i; cur.n_related = 0;
		a.push_back(cur);
	}
	sort(a.begin(),a.end());
	int ans = 0 , n_cnt = 0 , m_cnt = 0;
	for(size_t i=0;i<a.size();i++){
		if( a[i].n_related ){
			ans+= a[i].w * ( m+1 - m_cnt );
			n_cnt++;
		}else{
			ans+= a[i].w * ( n+1 - n_cnt );
			m_cnt++;
		}
	}
	cout << ans << endl;
		
		
	
}
/*
 * long long or int?
 * index out of bound?
 * Tested on own test case?corner?
 * Make more general solution.
 * Read Read Read Read ....
 */


Measured memory_bytes: 9516
class UnionFind:
    def __init__(self,N):
        self.par=[i for i in range(N)]
        self.siz=[1 for _ in range(N)]
        self.rank=[0 for _ in range(N)]
    def find(self,x):
        if self.par[x]==x:
            return x
        else:
            self.par[x]=self.find(self.par[x])
            return self.par[x]
    def union(self,a,b):
        a=self.find(a)
        b=self.find(b)
        if a==b:
            return 0
        else:
            if self.rank[a]>self.rank[b]:
                self.par[b]=a
                self.siz[a]+=self.siz[b]
            else:
                self.par[a]=b
                self.siz[b]+=self.siz[a]
                if self.rank[a]==self.rank[b]:
                    self.rank[b]+=1
    def size(self,a):
        return self.siz[self.find(a)]
    def same(self,a,b):
        return self.find(a)==self.find(b)

N,M=map(int,input().split())
UF=UnionFind(N)
for i in range(M):
    A,B=map(lambda x:int(x)-1,input().split())
    UF.union(A,B)
ans=1
for i in range(N):
    ans=max(ans,UF.size(i))
print(ans)

Measured memory_bytes: 94340
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
using namespace std;

#define INF (1ll<<60)


long long M = 1000000007;


int main(int argc, char const *argv[]) {
    long long n,a,b,c,d;cin>>n>>a>>b>>c>>d;
    long long k = b-a;
    if(k<0)k = -k;
    long long tmp = - (n-1)*c,argmin;
    argmin = tmp;
    for(int i=0;i<=n-1;++i){
        // i*[c,d] - (n-1-i)*[c,d]
        if(k >= i*c-(n-1-i)*d && k <= i*d - (n-1-i)*c){
            cout<<"YES"<<endl;
            return 0;
        }
    }
    cout<<"NO"<<endl;
    return 0;
}

Measured memory_bytes: 256