akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <cmath>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair
#define EPS 1e-8
#define equals(a,b) fabs((a) - (b)) < EPS

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

struct Point {
	double x, y;

	Point(double x=0, double y=0) : x(x), y(y) {}

	Point operator+(const Point &o) const { return Point(x+o.x, y+o.y); }

	Point operator-(const Point &o) const { return Point(x-o.x, y-o.y); }

	Point operator*(const double m) const { return Point(x*m, y*m); }

	Point operator/(const double d) const { return Point(x/d, y/d); }

	bool operator<(const Point &o) const { return x != o.x ? x < o.x : y < o.y; }

	bool operator==(const Point &o) const { return fabs(x-o.x) < EPS && fabs(y-o.y) < EPS; }

	double cross(const Point &o) const { return x * o.y - y * o.x; }

	double dot(const Point &o) const { return x * o.x + y * o.y; }

	double atan() const { return atan2(y, x); }

	double norm() const { return sqrt(dot(*this)); }

	double distance(const Point &o) const { return (o - (*this)).norm(); }

	double area(const Point &a,const Point &b) {
		Point p = a - (*this), p2 = b - (*this); 
		return p.cross(p2);
	}

	double area_abs(const Point &a,const Point &b) const {
		Point p = a - (*this), p2 = b - (*this);
		return fabs(p.cross(p2)) / 2.0;
	}	

	//線分abが自身に含まれているのかどうか判断する
	int between(const Point &a,const Point &b) {
		if(area(a,b) != 0) return 0;

		if(a.x != b.x)  return ((a.x <= x) && (x <= b.x)) || ((a.x >= x) && (x >= b.x));
		else return ((a.y <= y) && (y <= b.y)) || ((a.y >= y) && (y >= b.y));
	}      

	double distance_seg(const Point& a,const Point& b) {
		if((b-a).dot(*this-a) < EPS) {
			return (*this-a).norm();
		}
		if((a-b).dot(*this-b) < EPS) {
			return (*this-b).norm();
		}
		return abs((b-a).cross(*this-a)) / (b-a).norm();
	}

	bool hitPolygon(const Point& a,const Point& b,const Point& c) {
		double t = (b-a).cross(*this-b);
		double t2 = (c-b).cross(*this-c);
		double t3 = (a-c).cross(*this-a);	

		if((t > 0 && t2 > 0 && t3 > 0) || ( t < 0 && t2 < 0 && t3 < 0)) {
			return true;
		}

		return false;
	}
};

ostream& operator << (ostream& os, const Point& p) {
	os << "(" << p.x << ", " << p.y << ")";
	return os;
}

int main() {
	int n;
	while(cin >> n && n) {
		vector<Point> v(n);
		set<Point> st;
		rep(i, n) {
			cin >> v[i].x >> v[i].y;
			st.insert(v[i]);
		}

		int ans = 0;
		rep(i, n) {
			REP(j, i+1, n) {
				Point p = v[j] - v[i];
				Point a = v[i] + Point(p.y, -p.x);
				Point b = v[i] + Point(p.x + p.y, p.y - p.x);

				if(st.find(a) != st.end() && st.find(b) != st.end()) {
					ans = max(ans, (int) p.dot(p));
				}

				Point c = v[i] + Point(-p.y, p.x);
				Point d = v[i] + Point(p.x - p.y, p.y + p.x);

				if(st.find(c) != st.end() && st.find(d) != st.end()) {
					ans = max(ans, (int) p.dot(p));
				}
			}
		}

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

Measured memory_bytes: 1464
#include <algorithm>
#include <cmath>
#include <complex>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

using namespace std;

using ll = long long;
using P = pair<int, int>;

const long long MOD = 1e9+7;

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

ll solve(ll h) {
    if (h == 1) return 1;
    return solve(h / 2) * 2 + 1;
}

int main() {
    ll h;
    cin >> h;
    ll ans = solve(h);
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
/// Macros ---------------------
#define ll long long
#define int long long
#define pb push_back
#define vi vector<int>
#define f first
#define s second
#define ii pair<int,int>
#define lb lower_bound
#define up upper_bound
#define rep(i,x,y) for(int i=(x);i<=(y);i++)
#define ld long double
/// Constracts -------------------
const int maxn=1e5;
const int INF=(1ll)<<(30ll);
const int inf=1000000000000000000;
const int eps=1e-9;
/// Quick Pow ---------------------
int qpow(int b,int e)
{
    if( !e ) return 1;
    if( e & 1 ) return qpow(b, e - 1) * b;
    int pwur = qpow(b, e >> 1);
    return pwur * pwur;
}

/// My Code ---------------------

int32_t main()
{
    set<char>st;
    string s;
    cin>>s;
    int n=s.size();
    for(int i=0;i<n;i++){
        st.insert(s[i]);
    }
    if(st.size()==s.size())puts("yes");
    else puts("no");
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
 
const int N = 3e5 + 7;

long long n, k, f[N], M = 998244353;

long long power(long long a, long long b) {
	if (b == 0)
		return 1;
	long long t = power(a, b / 2);
	t = (t * t) % M;
	if (b % 2)
		t = (t * a) % M;
	return t;
}

long long chs(long long a, long long b) {
	if (a > b)
		return 0;
	long long t = f[b];
	t = (t * power(f[a], M - 2)) % M;
	t = (t * power(f[b - a], M - 2)) % M;
	return t;
}


long long a, b;

int main() {
	f[0] = 1;
	for (long long i = 1; i < N; i++)
		f[i] = (f[i - 1] * i) % M;
	cin >> n >> a >> b >> k;
	long long res = 0;
	for (long long x = 0; x <= n; x++) {
		long long tmp = k - a * x;
		if (tmp % b || tmp < 0)
			continue;
		long long y = tmp / b;
		if (x > n || y > n)
			continue;
		res = (res + chs(x, n) * chs(y, n)) % M;
	}
	cout << res;


	return 0;
}


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

int main() {
    ios::sync_with_stdio(false);
    //n/b+n%b=s (n/b)*b+n%b=n (n/b)*(b-1)=n-s
    ll n, s;
    cin >> n >> s;
    for (ll i = 2; i <= 890328; i++) {
        ll b = n, c = 0;
        while (b) c += b % i, b /= i;
        if (c == s) {
            cout << i;
            return 0;
        }
    }
    if (n == s) {cout << n + 1; return 0;}
    if (n < s) {cout << -1; return 0;}
    for (int i = 890328; i; i--) if ((n - s) % i == 0) {
        ll j = (n - s) / i + 1, b = n, c = 0;
        while (b) c += b % j, b /= j;
        if (c == s) {
            cout << j;
            return 0;
        }
    }
    if (s == 1) cout << n;
    else cout << -1;
}


Measured memory_bytes: 256
import std.conv;
import std.stdio;
import std.array;
import std.range;
import std.string;
import std.algorithm;

void main()
{
	while(true)
	{
		auto n = readln.chomp.to!int;
		if(n == 0) break;
		
		auto hs = readln.split.map!(a => a.to!int()).array;

		foreach(i; 0..(n+1)) {
			if(isCommonDiff(hs[0..i] ~ hs[(i+1)..(n+1)])) {
				writeln(hs[i]);
				break;
			}			
		}
	}
}

bool isCommonDiff(int[] ary)
{
	auto n = ary[1] - ary[0];
	
	foreach(i; 2..ary.length) {
		if(ary[i] - ary[i-1] != n) {
			return false;
		}
	}

	return true;
}

Measured memory_bytes: 2044
n = int(input())
lineb = input().split(" ")
total_a = int(lineb[0])

for i in range(n - 2):
    if int(lineb[i]) <= int(lineb[i+1]):
        total_a += int(lineb[i])
    else:
        total_a += int(lineb[i+1])
        
total_a += int(lineb[n-2])
        
print(total_a)

Measured memory_bytes: 3060
import java.util.*;

public class Main {

    static Scanner sc = new Scanner(System.in);

    static int MOD = (int)1e9+7;
    static int n = sc.nextInt();
    static int a = sc.nextInt();
    static int b = sc.nextInt();
//    static long[] facts = new long[n];

    public static void main(String[] args) {
//        facts = new long[n+1];
//        facts[0] = 1;

//        long[] comb = new long[n+2];
//        comb[0] = 1;

//        long comb = 1;

//        long comA = 0;
//        long comB = 0;


//        for (int i=1; i<=b; i++){
//            comb = ((comb*(n-i+1))/i)%MOD;
////            if (i==a) comA = comb;
//            if (i==a) comA = comb;
////            if (i==b) comB = comb;
//            if (i==b) comB = comb;
////            ans += comb%MOD;
////            ans %= MOD;
//
//        }

//        long comA = comb[a];
//        System.out.println(comA%MOD);

//        long comB = comb[b];
//        System.out.println(comB%MOD);
//        for (int i=1; i<n+1; i++){
//            facts[i] = facts[i-1]*i%MOD;
//        }
//        long comA = nck(n, a);
//        long comB = nck(n, b);

//        System.out.println(comA);
//        System.out.println(comB);

        long sum = modpow(2, n);
//        System.out.println(sum);

        long comA = nck(n, a);
        long comB = nck(n, b);

        long ans = sum-comA-comB-1+MOD*2;

        System.out.println(ans%MOD);

//        System.out.print(((ans)+MOD*2)%MOD);


    }

    public static long modpow(long a, long b){  // 計算量はlog(MOD);
        if (b==0) return 1;
        else if (b==1) return a;
        long x = modpow(a, b/2);
        return b%2==0 ? x*x%MOD : x*(x*a%MOD)%MOD;
    }
    public static long inv(long n){ // 逆元。x^(-1)≡x^(p-2) (MOD p)
        return modpow(n, MOD-2);
    }
    public static long nck(int n, int k){
        long res = 1;
        for (int i=0; i<k; i++){
            res = (res*(n-i))%MOD;
            res = (res*inv(i+1))%MOD;
        }
        return res;
    }

}


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

using namespace std;

long long calc_val(string S, int c) {
    if(c==0) return stoll(S);
    
    long long sum = 0;
    int left = 0;

    for(int i = 0; i < S.size(); i++) {
        if((c & 1<<i) == 0 && i != S.size() - 1) continue;
        else {
            {
                sum += stoll(S.substr(left, (i+1)-left));
                left = i + 1;
            }
        }
    }

    return sum;

}

int main() {
    string S;
    long long sum = 0;

    cin >> S;

    for(int i = 0; i < 1 << S.size()-1; i++) {
        sum += calc_val(S, i);
    }

    cout << sum << endl;

}

Measured memory_bytes: 256
h,w=map(int,input().split())
maze=[input() for i in range(h)]
class UnionFind:
    #def   -> foo=UnionFind(n,1)  <- 1-based index, default is 0
    #method -> foo.hoge(huga)
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [[0,0,1] for i in range(size + first_index)]
        for i in range(size):
            self._parents[i][int(maze[i//w][i%w]==".")]=1
    def find(self, x: int) -> int:
        try:
            if type(self._parents[x]) is list:
                return x
        except IndexError:print(x);exit()
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]
    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(y)

        if x == y:
            return False
        if self._parents[x][2] < self._parents[y][2]:
            x, y = y, x
        self._parents[x] = [self._parents[x][i]+self._parents[y][i] for i in range(3)]
        self._parents[y] = x
        return True
ans=0
m=[(0,1),(0,-1),(1,0),(-1,0)]
uf=UnionFind(h*w)
for i in range(h):
    for j in range(w):
        for dx,dy in m:
            if 0<=dx+i<h and 0<=dy+j<w and maze[i][j]!=maze[i+dx][j+dy]:
                uf.unite(i*w+j,(i+dx)*w+j+dy)
for i in uf._parents:
    if type(i)is list:ans+=i[0]*i[1]
print(ans)

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

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

    int dishes[5];
    int min_one = 10;
    int last_idx = 0;
    rep(i, 5) {
        int dish;
        cin >> dish;
        if(dish%10 && dish%10 < min_one) {
            min_one = dish%10;
            last_idx = i;
        }

        dishes[i] = dish;
    }

    int res = 0;
    rep(i, 5){
        if(i != last_idx) res += 10*(dishes[i]/10 + 1*(dishes[i]%10!=0));
    }
    res += dishes[last_idx];
    
    cout << res << endl;
}

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

const long inf = 1000000000000;

struct Edge
{
    int to;
    long cost;
    Edge(int to, long cost) : to(to), cost(cost) {}
};

vector<vector<Edge>> input_graph()
{
    int n, m;
    cin >> n >> m;
    vector<vector<Edge>> graph(n);
    for (auto i = 0; i < m; i++)
    {
        int a, b;
        long c;
        cin >> a >> b >> c;
        a -= 1;
        b -= 1;
        Edge e(b, c);
        graph[a].push_back(e);
    }

    return graph;
}

vector<long> bellman_ford(vector<vector<Edge>> graph)
{
    int size = graph.size();
    vector<long> dist(size, -inf);
    dist[0] = 0;

    for (auto k = 0; k < size; k++)
    {
        for (auto i = 0; i < size; i++)
        {
            for (auto j = 0; j < graph[i].size(); j++)
            {
                if (dist[i] != -inf && (dist[i] + graph[i][j].cost > dist[graph[i][j].to]))
                {
                    dist[graph[i][j].to] = dist[i] + graph[i][j].cost;
                    if (k == size - 1 && graph[i][j].to == size - 1)
                    {
                        dist[size - 1] = inf;
                    }
                }
            }
        }
    }

    return dist;
}

int main()
{
    vector<vector<Edge>> graph = input_graph();
    vector<long> d = bellman_ford(graph);
    if (d[graph.size() - 1] == inf)
    {
        cout << "inf" << endl;

    }
    else
    {
        cout << d[graph.size() - 1] << endl;

    }
}

Measured memory_bytes: 384
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

S = input()
if S == 'AAA' or S == 'BBB':
    print("No")
else:
    print("Yes")



Measured memory_bytes: 8232
#include <iostream>//cout<<right で右揃え
#include <iomanip>//cout<<setw(数字) で空白による桁揃え
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <cstdlib>//abs()で整数絶対値
#include <cmath>//abs()かfabs()で少数絶対値
#include <functional>//sort第三引数greater<型名>()で降順
#include <map>

using namespace std;
using ll = long long int;

int main(){
    int H,W;cin>>H>>W;
    int Ch,Cw;cin>>Ch>>Cw;Ch--;Cw--;
    int Dh,Dw;cin>>Dh>>Dw;Dh--;Dw--;
    vector<vector<bool>> S(H,vector<bool>(W)),seen(H,vector<bool>(W));
    vector<vector<int>> dist(H,vector<int>(W));
    for(int i=0;i<H;i++) for(int j=0;j<W;j++) dist[i][j] = 1e9;
    dist[Ch][Cw] = 0;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            char c;cin>>c;
            if(c=='.') S[i][j] = true;
        }
    }
    const int di[] = {0,0,-1,1};
    const int dj[] = {-1,1,0,0};
    deque<pair<int,int>> que;
    que.push_back({Ch,Cw});
    while(que.size()){
        auto p = que.front();que.pop_front();
        int i = p.first, j = p.second;
        if(seen[i][j]) continue;
        for(int k=0;k<4;k++){
            int i2 = i + di[k],j2 = j + dj[k];
            if(i2<0||i2>=H||j2<0||j2>=W) continue;
            if(!S[i2][j2]) continue;
            if(dist[i2][j2]>dist[i][j]){
                dist[i2][j2] = dist[i][j];
                que.push_front({i2,j2});
            }
        }
        for(int k=-2;k<3;k++){
            for(int l=-2;l<3;l++){
                int i2 = i + k,j2 = j + l;
                if(i2<0||i2>=H||j2<0||j2>=W) continue;
                if(!S[i2][j2]) continue;
                int d2 = dist[i][j] + 1;
                if(dist[i2][j2]>d2){
                    dist[i2][j2] = d2;
                    que.push_back({i2,j2});
                }
            }
        }
        seen[i][j] = true;
    }
    if(dist[Dh][Dw]!=1e9) cout << dist[Dh][Dw] << endl;
    else cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 7952
#include<iostream>
    #include<stdio.h>
    //#include <bits/stdc++.h>
    #include<vector>
    #include<float.h>
    #include<iomanip>
    #include<algorithm>
    #include<string>
    #include<cstring>
    #include<math.h>
    #include<sstream>
    #include<set>
    #include<map>
    #include<queue>

    #define INF 1e9
    #define rep(i,n)for(int i=0;(i)<(int)(n);i++)
    #define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
    #define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
    #define vec(type,n) vector<type>(n)
    #define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))

    using namespace std;
    using ll = long long;

    int main(){
      int n;
      cin>>n;
      auto t = vec(int,n+1);
      auto sum = vec(int,n+1);
      t[0] = 0,sum[0] = 0;
      REP(i,1,n){
          int x,y;
          cin>>t[i]>>x>>y;
          sum[i] = x+y;
      }
      bool f = true;
      REP(i,1,n){
          if(t[i]%2 != sum[i]%2 || sum[i]-sum[i-1]>t[i]-t[i-1]){
              f = false;
              break;
          }
      }
      cout<<(f ? "Yes":"No")<<endl;
    }


Measured memory_bytes: 1024
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
#mod = 10 ** 9 + 7 
mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
D = LIST()

d = Counter(D)

if d[0] == 1 and D[0] == 0:
	pass
else:
	print(0)
	exit()

ans = 1
tmp = 1
for i in range(max(d.keys())+1):
	ans = ans * pow(tmp, d[i], mod) % mod
	tmp = d[i]

print(ans)

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

int main() {

	int n; ll x; cin >> n >> x;
	vector<ll> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	ll ans = 0;
	for (int i = 1; i < n; i++) {
		if(a[i - 1] + a[i] < x){}
		else if (x <= a[i - 1]) {
			ans += a[i];
			ans += a[i - 1] - x;
			a[i] = 0;
			a[i - 1] = x;
		}
		else {
			ll tmp = x - a[i - 1];
			ans += a[i] - tmp;
			a[i] = tmp;
		}
	}
	cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4056
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vc = vector<char>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

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

  rep(i, 19){
    if((i == 5) || (i == 13)) cout << ' ';
    else cout << s[i];
  }

  cout << endl;
  
  return 0;
}

Measured memory_bytes: 256
n=int(input())
List=list(map(int, input().split()))
for i in range(n):
    if(List[i]%2==0):
        if(List[i]%3==0):
            continue;
        elif(List[i]%5==0):
            continue;
        print("DENIED")
        exit(0)
print("APPROVED")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <vector> 
# include <cstdint>
#define FOR(i,l,r) for(int i=(l);i<(r);++i)
#define RFOR(i,l,r) for(int i=(l);i>=(int)(r);i--)
#define rep(i,n)  FOR(i,0,n)
#define rrep(i,n)  RFOR(i,n-1,0)

#define int long long
using namespace std;
const int MX = 1e6;
const int inf = 1e9;

vector<int> ra(MX,0);
vector<int> par(MX,0);
using P = pair<int, int>;
using ll = long long;
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

int find(int x) {
    if(par[x] == x) {
        return x;
    } else {
        return par[x] = find(par[x]);
    }
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x==y) return;
    if(ra[x]<ra[y]) {
        par[x] = y;
    }else {
        par[y] = x;
        if(ra[x]==ra[y]) {
            ra[x]++;
            
        }
    }
}

bool same(int x, int y) {
    return find(x) == find(y);
}

int a[MX];
signed main(){
    int n;
    cin >> n;

    int k[n];
    rep(i,n) {
        int x;
        cin >> x;
        a[x]++;
        k[i] = x;
    }

    ll ans = 0;
    rep(i,n+1) {
        if(a[i]<=1) continue;
        ans += (a[i]*(a[i]-1))/2;    
    }

    rep(i,n) {
        ll tmp = ans;
        int num = a[k[i]];
        tmp -= (num*(num-1))/2;
        num--;
        tmp += (num*(num-1))/2;
        cout << tmp << endl;
    }
    

}



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

#define     bip(a)         __builtin_popcount(a)
#define     ull            unsigned long long
#define     ll             long long
#define     u              unsigned
#define     pb             push_back
#define     pf             push_front ///for list
#define     mp             make_pair
#define     is             insert
#define     ff             first
#define     ss             second
#define     vi             vector<int>
#define     vl             vector<ll>
#define     si             set<int>
#define     sl             set<ll>
#define     li             list<int>
#define     pii            pair<int,int>
#define     pll            pair<ll,ll>
#define     mii            map<int,int>
#define     mll            map<ll,ll>
#define     ma             INT_MAX
#define     mi             INT_MIN
#define     mod            1000000007
#define     pi             3.14159265359
#define     e              2.71828182846
#define     inf            1000000000000000LL
#define     all(x)         x.begin(), x.end()
#define     lb(a,b,c)      lower_bound(a,a+b,c)-a
#define     ub(a,b,c)      upper_bound(a,a+b,c)-a
#define     lbv(a,c)       lower_bound(all(a),c)-a.begin()
#define     ubv(a,c)       upper_bound(all(a),c)-a.begin()
#define     srt1(a,b)      sort(a,a+b)
#define     srt2(a,b)      sort(a,a+b,greater<int>())
#define     gcd(a,b)       __gcd(a,b)
#define     lcm(a,b)       (a*(b/gcd(a,b)))
#define     harmonic(n)    0.57721566490153286l+log(n)
#define     mem(a, b)      memset(a, b, sizeof(a))

///s.lower_bound(a),s.upper_bound(a), for set
///nCr(x, y) = nCr(x-1, y-1) + nCr(x-1, y)
///factorial digit   ((n * log10(n / e) +log10(2 * pi * n) /2.0));


int main()
{
    string s;
    cin>>s;
    int dp[200000+5];
    mem(dp,0);
    int p=1;
    int cnt[2019];
    mem(cnt,0);
    cnt[0]=1;
    ll ans=0;
    for(int i = s.length()-1 ;i>=0 ;i--){
        dp[i]=(dp[i+1]+(s[i]-'0')*p)%2019;
        p*=10;
        p%=2019;

        int c=dp[i];
        ans+=cnt[c];
        cnt[c]++;
    }
    cout<<ans<<endl;
}



Measured memory_bytes: 4520
#include <stdio.h>
#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <set>
#include <algorithm>
#include <math.h>
using namespace std;
using i64 = int64_t;
#define rep(i, n) for(int i=0;i<n;++i)
#define rep2(i, x, n) for(int i=x;i<n;++i)

int main()
{   
    string s;
    int x,y;
    cin >> s >> x >> y;

    vector<int> dx;
    vector<int> dy;

    int t_cnt = 0;
    int f_cnt = 0;
    int n = s.size();
    rep(i,n)
    {
        string si = s.substr(i,1);
        if(si == "F")
        {
            f_cnt++;
            if(i==n-1)
            {
                if(t_cnt%2==0) dx.push_back(f_cnt);
                else dy.push_back(f_cnt);
            }
        } 
        else
        {
            if(f_cnt>0)
            {
                if(t_cnt%2==0) dx.push_back(f_cnt);
                else dy.push_back(f_cnt);
            }
            f_cnt = 0;
            t_cnt++;
        }
    }

    unordered_set<int> rx;
    rx.insert(0);
    rep(i,(int)dx.size())
    {
        unordered_set<int> tmp_rx;
        if(i==0 && s.substr(0,1)=="F")
            tmp_rx.insert(dx[i]);
        else
        {
            for(auto& rxi:rx)
            {
                tmp_rx.insert(rxi-dx[i]);
                tmp_rx.insert(rxi+dx[i]);
            }
        }

        rx.clear();
        for(auto& rxi:tmp_rx)
            rx.insert(rxi);
    }

    unordered_set<int> ry;
    ry.insert(0);
    rep(i,(int)dy.size())
    {
        unordered_set<int> tmp_ry;
        for(auto& ryi:ry)
        {
            tmp_ry.insert(ryi-dy[i]);
            tmp_ry.insert(ryi+dy[i]);
        }

        ry.clear();
        for(auto& ryi:tmp_ry)
            ry.insert(ryi);
    }

    cout << ((rx.count(x)>0 && ry.count(y)>0) ? "Yes" : "No") << endl;
    return 0;
}

Measured memory_bytes: 896
coin500 = gets.chomp.to_i # 500
coin100 = gets.chomp.to_i # 100
coin50 = gets.chomp.to_i # 50
price = gets.chomp.to_i
count = 0

c500 = 0
c100 = 0
c50 = 0
while c500 <= coin500
  c100 = 0
  while c100 <= coin100
    c50 = 0
    while c50 <= coin50
      if (c500 * 500) + (c100 * 100) + (c50 * 50) == price
        #p "500:#{c500} 100:#{c100} 50:#{c50}"
        count += 1
      end
      c50 += 1
    end
    c100 += 1
  end
  c500 += 1
end

puts count


Measured memory_bytes: 1788
#include<iostream>
#include<string>
#include<vector>
#include <math.h>

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

using namespace std;

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

	vector<int> X(N);
	rep(i,N)
		cin >> X[i];

	int ave = 0;
	rep(i,N)
		ave += X[i];
	ave = round((float)ave / N);

	int ans = 0;
	rep(i,N){
		ans += (X[i] - ave) * (X[i] - ave);
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define all(a)  (a).begin(),(a).end()
typedef long long ll;
ll mod=1000000007;

int main() {
  int n,l;cin >> n >> l;
  vector<int> v(n);
  for(int i=1;i< n+1 ;++i){
    v[i-1] = l+i-1;
  }
  sort(all(v), [](int a, int b){return abs(a) < abs(b);});
  cout << accumulate(all(v), 0) - v[0] << endl;
  return 0;
}


Measured memory_bytes: 256
/*
  Motto - try hard to become an expert
*/
#include <bits/stdc++.h>
#include <map>
#include <algorithm>
#include <vector>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <chrono>
#include <thread>
#include <iomanip>
 
//define
#define rep(i,n)    for(int i=0;i<n;i++)
#define repu(i,k,n) for(int i=k;i<=n;i++)
#define repd(i,k,n) for(int i=k;i>=n;i--)
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define INF (int)INT_MAX
#define all(v)  v.begin(), v.end()
#define endl "\n"
 
//typedef
typedef long long int ll;
typedef long double ld;
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
typedef std::vector< pii > vii;
typedef std::vector< ll > vll;
typedef std::vector< std::pair < pii, int > > vpp;
 
const int N = 3*1e5 +5 ;
const long long MOD = 1e9 + 7;
const long long inf = 1e18;
 
using namespace std;
 

ll modpow(ll x,ll n){
    ll res=1;
    while(n>0){
        if(n&1) res=res*x%MOD;
        x=x*x%MOD;
        n>>=1;
    }
    return res;
}
 
ll modFact(ll n, ll p) 
{ 
    if (n >= p) 
        return 0; 
  
    ll result = 1; 
    for (ll i = 1; i <= n; i++) 
        result = (result * i) % p; 
  
    return result;  
} 
 
bool isPrime(int x)
{
    if(x%2==0)
        return 0;
    for(int i=3;i<=sqrt(x);i+=2)
    {
        if(x%i==0)
            return 0;
    }
    return 1;
}
 
ll binomialCoeff(ll n, ll k) 
{ 
	ll C[n + 1][k + 1]; 
	ll i, j; 


	for (i = 0; i <= n; i++) 
	{ 
		for (j = 0; j <= min(i, k); j++) 
		{ 
			
			if (j == 0 || j == i) 
				C[i][j] = 1; 

			else
				C[i][j] = (C[i - 1][j - 1] + 
										C[i - 1][j])%MOD; 
		} 
	} 

	return C[n][k]; 
}
bool compare(const string &a , const string&b){
	
}
 
void solve()
{
	int n , l ;
	cin>>n>>l ;
	string s[n] ;
	rep(i ,n){
		cin>>s[i];
	}
	sort(s , s+n) ;
	rep(i , n){
		cout<<s[i];
	}
}
 
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(0);
    cin.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--)
    {
        solve();
    } 
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Measured memory_bytes: 3840
#include <bits/stdc++.h>
#define lli long long int
#define inf 2147483647
#define infll LLONG_MAX
#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define Yes() cout << "Yes" << endl
#define No() cout << "No" << endl
#define YES() cout << "YES" << endl
#define NO() cout << "NO" << endl
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);
    vector<vector<int>> a(3, vector<int>(3, 0));

    rep(i, 3){
        rep(j, 3) cin >> a[i][j];
    }
    int n, in;
    cin >> n;

    rep(k, n){
        cin >> in;
        rep(i, 3){
            rep(j, 3){
                if(a[i][j] == in) a[i][j] = -1;
            }
        }
    }

    rep(i, 3){
        if(a[i][0] == -1 && a[i][1] == -1 && a[i][2] == -1){
            Yes();
            return 0;
        }
        if(a[0][i] == -1 && a[1][i] == -1 && a[2][i] == -1){
            Yes();
            return 0;
        }
    }

    if((a[0][0] == -1 && a[1][1] == -1 && a[2][2] == -1)
    || (a[0][2] == -1 && a[1][1] == -1 && a[2][0] == -1)){
        Yes();
        return 0;
    }
    No();
}

Measured memory_bytes: 256
"""
    こんにちは。これはクシャルです
    
    Author : thekushalghosh (クシャル)
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time
start_time = time.time()
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################
    
def solve():
    n = inp()
    q = 0
    w = 1000000000000000000000000000
    qq = 0
    ww = 1000000000000000000000000000
    qqqq = 0
    wwww = 1000000000000000000000000000
    a = []
    for i in range(n):
        x,y = invr()
        a.append((x,y))
        q = max(q,x + y)
        w = min(w,x + y)
        qq = max(qq,x - y)
        ww = min(ww,x - y)
        qqqq = max(qqqq,y - x)
        wwww = min(wwww,y - x)
    if len(set(a)) == 1:
        print(0)
    else:
        print(max(q - w,qq - ww,qqqq - wwww))
    
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
 
def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
        sys.stdout.close()
    
#---------------------- USER DEFINED INPUT FUNCTIONS ----------------------#
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
 
#------------------ USER DEFINED PROGRAMMING FUNCTIONS ------------------#
def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1] + 1
    return(q)

def counter_elements(a):
    q = dict()
    for i in range(len(a)):
        if a[i] not in q:
            q[a[i]] = 0
        q[a[i]] = q[a[i]] + 1
    return(q)

def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97],1
    return(q)
 
def factors(n):
    q = []
    for i in range(1,int(n ** 0.5) + 1):
        if n % i == 0: q.append(i); q.append(n // i)
    return(list(sorted(list(set(q)))))
 
def prime_factors(n):
    q = []
    while n % 2 == 0: q.append(2); n = n // 2
    for i in range(3,int(n ** 0.5) + 1,2):
        while n % i == 0: q.append(i); n = n // i
    if n > 2: q.append(n)
    return(list(sorted(q)))

def transpose(a):
    n,m = len(a),len(a[0])
    b = [[0] * n for i in range(m)]
    for i in range(m): 
        for j in range(n): 
            b[i][j] = a[j][i]
    return(b)

#-----------------------------------------------------------------------#
        
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
main()

Measured memory_bytes: 118412
#include<bits/stdc++.h>
using namespace std;
#define pt pair<double,double>
#define x first
#define y second
const int M=1e5+10;
double cross2(pt o,pt a,pt b)
{return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);}
pt p[M];//polygon
int n;
vector<pt>hull; 
void convexhull()
{ 
  hull.push_back(p[0]);
  for(int i=1;i<n;i++)
    { 
      while(hull.size()>1 && cross2(hull[hull.size()-2],hull.back(),p[i])>0) 
	hull.pop_back(); 
      hull.push_back(p[i]); 
    }
  int hs=hull.size();
  for(int i=n-2;i>=0;i--)
    {
      while(hull.size()>hs && cross2(hull[hull.size()-2],hull.back(),p[i])>0) 
	hull.pop_back();
      hull.push_back(p[i]);
    }
}
int main()
{ 
  cin>>n;
  for(int i=0;i<n;i++)
    cin>>p[i].x>>p[i].y;
  sort(p,p+n);
  convexhull();
  //the first point is repeated at last!
  hull.pop_back();
  cout<<hull.size()<<endl;
  int my=100000,mx=1000000,ind;
  for(int i=0;i<hull.size();i++)
    if(hull[i].y<my)
      my=hull[i].y,mx=hull[i].x,ind=i;
    else if(hull[i].y==my && mx>hull[i].x)
      mx=hull[i].x,ind=i;
  for(int i=ind,cnt=hull.size();cnt;cnt--,i=(i-1+hull.size())%hull.size())
    cout<<hull[i].x<<" "<<hull[i].y<<endl;
}

Measured memory_bytes: 6572
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
using namespace __gnu_pbds;
using namespace std;

typedef long long int lli;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<lli> vli;
typedef vector<pii> vii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> OrderedSet;

const int MOD	= 1e9 + 7;
const double PI = acos(-1.0);

#define fastio			ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(auto &i : c)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define fill(a)  memset(a, 0, sizeof (a))
#define error(x) cerr << #x << " = " << (x) << endl
#define errorp(p) cerr << #p << " = " << (p.first) << ", " << (p.second) << endl

template<typename T> T gcd(T a, T b){return(b?__gcd(a,b):a);}
template <typename T> T lcm(T a, T b){return (a*b)/gcd(a,b); }
int mul(int a, int b, int c){lli res=(lli)a*b;return (int)(res>=c?res%c:res);}
template<typename T>T power(T e, T n, T m){T x=1,p=e;while(n){if(n&1)x=mul(x,p,m);p=mul(p,p,m);n>>=1;}return x;}
int mod_neg(int a, int b, int c){int res;if(abs(a-b)<c)res=a-b;else res=(a-b)%c;return(res<0?res+c:res);}
template<typename T>T extended_euclid(T a, T b, T &x, T &y){T xx=0,yy=1;y=0;x=1;while(b){T q=a/b,t=b;b=a%b;a=t;\
t=xx;xx=x-q*xx;x=t;t=yy;yy=y-q*yy;y=t;}return a;}
template<typename T>T mod_inverse(T a, T n){T x,y,z=0;T d=extended_euclid(a,n,x,y);return(d>1?-1:mod_neg(x,z,n));}
template <class T>  inline void smax(T &x,T y){ x = max((x), (y));}
template <class T>  inline void smin(T &x,T y){ x = min((x), (y));}

int calculate(int a, int b){
    return a * a * a * a  + a * a * a * b + a * a * b * b + a * b * b * b + b * b * b * b;
}

//handle special case;

void get_divisors(int X, vi &v){
    int temp = int(ceil( sqrt(X)));
    for(int i = 2; i < temp; i++){
        if(X % i == 0){
            

            v.pb(i);
            v.pb(X/i);
        }
    }
    if(temp * temp == X){
        v.pb(temp);
    }
    
}

int main(){
    #ifdef DEBUG
		freopen("test", "r", stdin);
	#endif
    fastio;
    
    int X;
    cin >> X;
    vi divs;
    divs.pb(1);
    divs.pb(X);
    get_divisors(X, divs);
    set<int> s(all(divs));

    tr(s, i){
        bool found = false;
        rep(A, MOD){
            int B = A - i;
            int val = calculate(A, B);
            if(val == X / i){
                cout << A << " " << B << endl;
                found = true;
                break;
            }
            if(B > 0 && val > X / i){
                break;
            }
        }
        if(found){
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 3680
#include <cstdio>
typedef long long lld;
const int MAXN = 2e5+5;
const int LOGK = 60; 
int A[LOGK][MAXN];
int N;
lld K;

int main() {
  scanf(" %d%lld", &N, &K);
  for (int i = 1; i <= N; ++i) {
    scanf("%d", &A[0][i]);
  }
  for (int j = 1; (1LL << j) <= K; ++j) {
    for (int i = 1; i <= N; ++i) {
      A[j][i] = A[j-1][A[j-1][i]];
    }
  }
  int ret = 1;
  for (int j = 0; K; ++j) {
    if (K & 1) {
      ret = A[j][ret];
    }
    K >>= 1;
  }
  printf("%d\n", ret);
  return 0;
}

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

using namespace std;

const int mod = 1e9 + 7;

int main(){
    int N;
    cin >> N;
    if(N == 1){
        cout << 3 << endl;
        return 0;
    }
    string s1, s2;
    cin >> s1 >> s2;

    s1.push_back('0');
    s2.push_back('0');

    long long ans;
    int pre_state;
    if(s1[0] == s1[1] && s2[0] == s2[1]){
        pre_state = 1;
        ans = 6;
    }else if(s1[0] == s2[0]){
        pre_state = 0;
        ans = 3;
    }

    for(int i=(pre_state ? 2 : 1) ;i<N;){
        if(s1[i] == s1[i+1] && s2[i] == s2[i+1]){
            if(pre_state){
                (ans *= 3) %= mod;
            }else{
                (ans *= 2) %= mod;
            }
            i += 2;
            pre_state = 1;
        }else if(s1[i] == s2[i]){
            if(pre_state){
                ans %= mod;
            }else{
                (ans *= 2) %= mod;
            }
            pre_state = 0;
            i++;
        }
    }

    cout << ans << endl;
    return 0;

}

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

int main(){
	int ans=0;
	string s;
	cin>>s;
	if(s[1]==s[2] && (s[0]==s[1] || s[1]==s[3])) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <stack>
using namespace std;
using P = pair<int , int>;
int main()
{
    int n;
    cin >> n;
    vector<P> a(n);
    for (int i = 0; i < n; ++i)
    {
        int value;
        cin >> value;
        a[i].first = i;
        a[i].second = value;
    }
    sort(a.begin(), a.end(), [](const P& x, const P& y){ return x.second < y.second; });
    for (int i = 0; i < n; ++i)
    {
        cout << a[i].first + 1;
        if (i != n - 1) cout << ' ';
        else cout << endl;
    }
    return 0;
}


Measured memory_bytes: 1664
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<iostream>
#include<map>
#include<string>
#include<bitset>

#define MOD 1000000007

using namespace std;

typedef long long ll;

inline void add(int &x,int y) {
  ((x+=y)>=MOD)?x-=MOD:0;
} 

ll C[105][105];

void pre(int n) {
  for(int i=0;i<=n;i++) C[i][0]=1;
  for(int i=1;i<=n;i++)
    for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
}

int f[85][85][85],up[85];
int sum[85];

void dp(int n,int m,int c) {
  memset(f,0,sizeof(f));
  int t=m+2*c-1;
  f[0][0][0]=1;
  for(int i=0;i<m;i++)
    for(int j=0;j<=up[i]&&2*j-m+t<=n;j++) {
      int s=f[i][j][0];
      for(int k=1;k<=up[m]&&j+(m-i)*k<=up[m];k++) {
      	for(int l=1;i+l<=m&&j+l*k<=up[i+l];l++)
      	  add(f[i+l][j+l*k][k],s*C[i+l][l]%MOD);
      	add(s,f[i][j][k]);
	  }
    }
  for(int i=0;i<=up[m]&&2*i-m+t<=n;i++) {
  	int s=0;
  	for(int j=0;j<=i;j++) add(s,f[m][i][j]);
  	if (!s) continue;
  	int v=2*i-m+t;
  	for(int j=0;j<=2*m+2&&v+j<=n;j++)
  	  add(sum[v+j],s*C[m+c][c]%MOD*C[2*m+2][j]%MOD);
  }
}

char str[85];

int q[85],lpos[85];
bool vis[85];

int main() {
  int n,k;
  scanf("%d%d%s",&n,&k,str+1);
  pre(100);
  for(int i=0;2*i<=k;i++) {
  	memset(vis,0,sizeof(vis));
  	int cnt=0;
  	int lx=1,rx=0;
  	for(int j=1;j<=k&&cnt<i;j++)
  	  if (str[j]=='r') q[++rx]=j;
  	  else if (lx<=rx) {
  	  	  vis[q[lx++]]=vis[j]=1;
  	  	  lpos[++cnt]=j;
		}
	if (cnt<i) continue;
	int s=0;
	for(int j=1;j<=k;j++)
	  if (!vis[j]&&str[j]=='r') s++;
	int r=1;
	lpos[i+1]=k+1;up[i+1]=0;
	for(int j=0;j<=s;j++) {
		if (j) {
			while (vis[r]||str[r]!='r') r++;
			vis[r]=1;
		}
		for(int t1=i;t1>0;t1--) {
			up[t1]=up[t1+1];
			for(int t2=lpos[t1+1]-1;t2>lpos[t1];t2--)
			  if (!vis[t2]) up[t1]++;
			up[t1]++;
		}
		reverse(up+1,up+i+1);
		dp(n,i,j);
	}
  }
  int ans=0;
  for(int i=1;i<=n;i++) add(ans,sum[i]*C[n-1][i-1]%MOD);
  printf("%d\n",ans);
  return 0;
}

Measured memory_bytes: 6184
//Author: AnandRaj doubleux
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll; 

#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define test() int t;cin>>t;while(t--)
#define all(v) v.begin(),v.end()
#define prinp(p) cout<<p.first<<" "<<p.second<<endl
#define prinv(V) for(auto v:V) cout<<v<<" ";cout<<endl
#define take(V,f,n) for(int in=f;in<f+n;in++) cin>>V[in]
#define what(x) cerr<<#x<<" = "<<x<<endl
#define KStest() int t,t1;cin>>t;t1=t;while(t--)
#define KScout cout<<"Case #"<<t1-t<<": "
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9+7,MAX = 1e6+5;
const ll INF = 1e18+5;

vector<bool> is_prime(MAX, true);
vi MinDiv(MAX);
void Sieve()
{
	is_prime[0] = is_prime[1] = false;
	int i,j;
	for (i = 2; i*i <= MAX; i++) 
	{
    	if (is_prime[i]) 
    	{
    		MinDiv[i]=i;
        	for (j = i * i; j <= MAX; j += i)
            {
				is_prime[j] = false;
				MinDiv[j]=i;
    		}
    	}
	}
	for(int i=2;i<=MAX;i++) if(is_prime[i]) MinDiv[i]=i;
}

int main()
{
	int n;
	cin>>n;
	vi A(n);
	take(A,0,n);
	set<int> D;
	Sieve();
	int last = A[n-1];
	
	while(last>1)
	{
		int x = MinDiv[last];
		D.insert(x);
		while(last%x==0)
		{
			last/=x;
		}
	}
	bool can=true;
	for(int i=n-2;i>=0;i--)
	{
		vi P;
		int num = A[i];
		while(num>1)
		{
			int x = MinDiv[num];
			P.push_back(x);
			while(num%x==0)
			{
				num/=x;
			}
		}
		for(auto p:P)
		{
			if(D.count(p)) can=false;

			D.insert(p);
		}
		if(!can) break;
	}
	if(can) cout<<"pairwise coprime"<<endl;
	else
	{
		int g = A[0];
		for(int i=1;i<n;i++) g = __gcd(g,A[i]);

		if(g==1) cout<<"setwise coprime"<<endl;
		else cout<<"not coprime"<<endl;
	}

}	

Measured memory_bytes: 11172
#include <bits/stdc++.h>
using namespace std;
int main(void){

    int n, m;
    
    cin >> n >> m;
    vector<pair<long long,long long>> ab(n);
    vector<pair<long long,long long>> info(n);

    for(int i=0; i<n; i++) {
        cin >> ab[i].first >> ab[i].second;
    }

    sort(ab.begin(), ab.end());

    for(int i=0; i<n; i++) {
        if(i!=0) {
            info[i].first += ab[i].second*ab[i].first + info[i-1].first;
            info[i].second += ab[i].second + info[i-1].second;
        }
        else {
            info[i].first = ab[i].second*ab[i].first;
            info[i].second = ab[i].second;
        }
    }

    long long result = 0;
    int index = 0;
//    cout << info[index].first << " " << info[index+1].first << endl;
    while(m > info[index].second) {
        index++;
    }
    
    if(index == 0) {
        for(int i=0; i<m; i++) {
            result += ab[index].first;
        }
    }
    else {
        result += info[index-1].first;
        int remaind = m - info[index-1].second;
        for(int i=0; i<remaind; i++) {
            result += ab[index].first;
        }
    }

    cout << result << endl;

    return 0;
}


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

#define FORE(i, a) for (auto i = a.begin(); i != a.end(); ++i)
#define REPU(i, a, b) for (int i = (a); i < (b); ++i)
#define REPD(i, a, b) for (int i = (a); i > (b); --i)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())

typedef long long ll;
const int MOD = 1000000007;
template<class T, class U> inline void amax(T &a, U b) { if (b > a) a = b; }
template<class T, class U> inline void amin(T &a, U b) { if (b < a) a = b; }
template<class T> T gcd(T a, T b) { while (b != 0) { T c = a; a = b; b = c % b; } return a; }

int main(int argc, char *argv[]) {
	ios_base::sync_with_stdio(false);

	string s; cin >> s;
	REPU(i, 0, s.size()) if (s[i] == ',') {
		s[i] = ' ';
	}
	cout << s << endl;

	return 0;
}


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

int main() {
  int n;
  cin >> n;
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    string s = to_string(i);
    int l = s.size();
    if (l & 1) ans++;
  }

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


Measured memory_bytes: 3744
N, K = map(int,input().split())
S = input()

A = 0
B = 0

for i in range(N-1):
    if S[i] == "R" and S[i+1] == "L":
        A += 1

if S[0] == "R" and S[N-1] == "L":
    A -= 1
    B += 1
elif S[0] == "L" and S[N-1] == "R":
    B += 1

ans = A * 2 + B + 1

while(K > 0):
    if A > 0:
        ans -= 2
        A -= 1
    elif B > 0:
        ans -= 1
        B -= 1
    else:
        break
    K -= 1

print(N - ans)

Measured memory_bytes: 3316