akhauriyash/Code-Regression huggingface dataset:
N = int(input())
S = input()
tmp = 0
for i in range(1, N):
    if S[i] == 'E':
        tmp += 1
c = [tmp] * N
for i in range(1, N):
    c[i] = c[i-1]
    if S[i-1] == "W":
        c[i] += 1
    if S[i] == "E":
        c[i] -= 1
print(min(c))


Measured memory_bytes: 15264
#include <stdio.h>
int main(){
int n, h[100],i;
int max=0;
int ans=0;
scanf("%d",&n);

for(i=0; i<n; i++){
scanf("%d",&h[i]);
if(max<=h[i]){
max=h[i];
ans++;}
}
printf("%d",ans);

return 0;
}


Measured memory_bytes: 128
#include <stdio.h>
typedef long long ll;

ll gcd(ll a, ll b){
  if(a == 0 || b == 0) return a + b;
  if(a >= b) return gcd(b, a % b);
  else return gcd(b, a);
}

int
main(int argc, char *argv[])
{
  long long a, b, c, d;
  scanf("%lld %lld %lld %lld", &a, &b, &c, &d);

  ll lcm = (c * d) / gcd(c, d);

  ll ans = (b / c) + (b / d) - (b / lcm) - (a / c) - (a / d) + (a / lcm);
  if(a % c == 0 || a % d == 0) ans += 1;
  ans = b - a + 1 - ans;

  printf("%lld\n", ans);

  return 0;
}

  


Measured memory_bytes: 128
module IO = struct

  (* @since 4.04.0 *)
  let split_on_char sep s =
    let open String in
    let r = ref [] in
    let j = ref (length s) in
    for i = length s - 1 downto 0 do
      if get s i = sep then begin
        r := sub s (i + 1) (!j - i - 1) :: !r;
        j := i
      end
    done;
    sub s 0 !j :: !r

  let read_ns () = read_line () |> split_on_char ' ' |> List.map int_of_string

end

let solve ans w v =
  let rec g ans j xs =
    if j = w then (ans, xs)
    else
      match xs with
      | [] -> g ans (j + 1) [(v.(j), j)]
      | (ch, _) :: _ ->
        if ch = v.(j) then g ans (j + 1) xs
        else if ch < v.(j) then g ans (j + 1) ((v.(j), j) :: xs)
        else
          let rec f ans k = function
            | [] -> g ans (j + 1) [(v.(j), k)]
            | (ch, cj) :: tl as ys ->
              if ch >= v.(j) then f (if ch * (j - cj) > ans then ch * (j - cj) else ans) cj tl
              else g ans (j + 1) ((v.(j), k) :: ys) in
          f ans j xs in
  let (ans, xs) = g ans 0 [] in
  List.fold_left (fun acc (ch, cj) -> if ch * (w - cj) > acc then ch * (w - cj) else acc) ans xs

let () =
  match IO.read_ns () with
  | [h; w] ->
    let s = Array.make w 0 in
    let t = Array.make w 0 in
    let rec doit i ans =
      if i = h then ans
      else begin
        IO.read_ns () |> List.iteri (fun j e -> t.(j) <- if e = 1 then 0 else s.(j) + 1);
        Array.iteri (fun i e -> s.(i) <- e) t;
        solve ans w t |> doit (i + 1)
      end in
    doit 0 0 |> Printf.printf "%d\n"
  | _ -> assert false

Measured memory_bytes: 5188
#include <stdio.h>

int main(){
	char ch;
	while((ch = getchar()) != EOF){
			if(ch >= 97 && ch <= 122)
				printf("%c",ch-32);
			else if(ch >= 65 && ch <= 90)
				printf("%c",ch+32);
			else
				printf("%c",ch);
	}
}



Measured memory_bytes: 2452
// 嘘貪欲っぽい
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    int n, m;
    string s;
    cin >> n >> m >> s;
    reverse(s.begin(),s.end());
    int acc = 0;
    for(int i = 1; i <= n; i++){
        if(s[i] == '1') acc++;
        else            acc = 0;
        if(acc >= m){
            cout << -1 << endl;
            return 0;
        }
    }
    vector<int> ret;
    vector<int> ok;
    for(int i = 0; i <= n; i++) if(s[i]=='0')   ok.push_back(i);
    int pos = 0;
    while(pos < n){
        int next = min(n, pos+m);
        next = *(--upper_bound(ok.begin(),ok.end(),next));
        ret.push_back(next-pos);
        pos = next;
    }
    reverse(ret.begin(), ret.end());
    for(int i = 0; i < ret.size(); i++) cout << ret[i] << " \n"[i+1==ret.size()];
    return 0;
}

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

using namespace std;

int main()
{
    int n, w;
    
    while (scanf("%d %d", &n, &w) && w){
        int hist[128] = {0};
        int hist2[128] = {0};
        for (int i = 0; i < n; i++){
            int x;
            scanf("%d", &x);
            hist[x]++;
        }
        for (int i = 0; i <= 100; i++){
            hist2[i / w] += hist[i];
        }
        int r = 0;
        int maxi = 0;
        for (int i = 0; i <= 100; i++){
            if (hist2[i]){
                r = i;
                maxi = max(maxi, hist2[i]);
            }
        }
        
        double ans = 0;
        for (int i = 0; i <= 100; i++){
            ans += ((r - i) * 1.0 / r) * hist2[i] * 1.0 / maxi;
        }
        
        printf("%.10f\n", ans + 0.01);
    }
    
    return (0);
}

Measured memory_bytes: 1224
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>

using namespace std;


int main(){
	cin.tie(0);
   	ios::sync_with_stdio(false);
    
    int a,b;
    cin >> a >> b;
    cout << (a-1)*(b-1)<< endl;
}

Measured memory_bytes: 256
;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (sb-int:defconstant-eqx OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0))
    #'equal)
  #+swank (ql:quickload '(:cl-debug-print :fiveam) :silent t)
  #-swank (set-dispatch-macro-character
           #\# #\> (lambda (s c p) (declare (ignore c p)) (read s nil (values) t))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)
#-swank (disable-debugger) ; for CS Academy

;; BEGIN_INSERTED_CONTENTS
(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
  (declare #.OPT)
  (macrolet ((%read-byte ()
               `(the (unsigned-byte 8)
                     #+swank (char-code (read-char in nil #\Nul))
                     #-swank (sb-impl::ansi-stream-read-byte in nil #.(char-code #\Nul) nil))))
    (let* ((minus nil)
           (result (loop (let ((byte (%read-byte)))
                           (cond ((<= 48 byte 57)
                                  (return (- byte 48)))
                                 ((zerop byte) ; #\Nul
                                  (error "Read EOF or #\Nul."))
                                 ((= byte #.(char-code #\-))
                                  (setf minus t)))))))
      (declare ((integer 0 #.most-positive-fixnum) result))
      (loop
        (let* ((byte (%read-byte)))
          (if (<= 48 byte 57)
              (setq result (+ (- byte 48) (* 10 (the (integer 0 #.(floor most-positive-fixnum 10)) result))))
              (return (if minus (- result) result))))))))

(defmacro dbg (&rest forms)
  #+swank
  (if (= (length forms) 1)
      `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
      `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

(defconstant +mod+ 1000000007)

;;;
;;; Body
;;;

(defun main ()
  (let* ((n (read))
         (as (make-array n :element-type 'uint32))
         (res 0)
         (current-max 0))
    (declare (uint32 n current-max)
             (uint62 res))
    (dotimes (i n) (setf (aref as i) (read-fixnum)))
    (dotimes (i n)
      (let* ((p (+ 1 current-max))
             (a (aref as i))
             (quot (floor (- a 1) p)))
        (incf res quot)
        (unless (zerop quot)
          (setf (aref as i) 1))
        (setq current-max (max current-max (aref as i)))))
    (println res)))

#-swank (main)


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

#define MAX 30
#define NIL -1

struct Node { int parent, right, left; };
Node T[MAX];
int H[MAX];
int D[MAX];

int getSibling(int u) {
    if (T[u].parent == NIL) return NIL;
    if (T[T[u].parent].left != NIL && T[T[u].parent].left != u) return T[T[u].parent].left;
    if (T[T[u].parent].right != NIL && T[T[u].parent].right != u) return T[T[u].parent].right;
    return NIL;
}

int getDegree(int u) {
    int deg = 0;
    if (T[u].left != NIL) { deg++; }
    if (T[u].right != NIL) { deg++; }
    return deg;
}

void rec(int u, int d) {
    D[u] = d;
    if (T[u].right != NIL) { rec(T[u].right, d + 1); }
    if (T[u].left != NIL) { rec(T[u].left, d + 1); }
}

int getHeight(int u, int h) {
    int hr = 0, hl = 0;
    if (T[u].right != NIL) { hr = getHeight(T[u].right, h + 1) + 1; }
    if (T[u].left != NIL) { hl = getHeight(T[u].left, h + 1) + 1; }
    return H[u] = max(hr, hl);
}

void print(int u) {
    cout << "node " << u << ": ";
    cout << "parent = " << T[u].parent << ", ";
    cout << "sibling = " << getSibling(u) << ", ";
    cout << "degree = " << getDegree(u) << ", ";
    cout << "depth = " << D[u] << ", ";
    cout << "height = " << H[u] << ", ";
    if (T[u].parent == NIL) {
        cout << "root" << endl;
    }
    else if (T[u].left != NIL || T[u].right != NIL) {
        cout << "internal node" << endl;
    }
    else {
        cout << "leaf" << endl;
    }
}

int main()
{
    int n; cin >> n;
    for (int i = 0; i < n; ++i) {
        T[i].parent = T[i].left = T[i].right = H[i] = D[i] = NIL;
    }
    for (int i = 0; i < n; ++i) {
        int id, right, left; cin >> id >> left >> right;
        T[id].right = right;
        T[id].left = left;
        if (left != NIL) {
            T[left].parent = id;
        }
        if (right != NIL) {
            T[right].parent = id;
        }
    }
    int u = 0;
    for (int i = 0; i < n; ++i) {
        if (T[i].parent == NIL) { 
            u = i;
        }
    }
    rec(u, 0);
    getHeight(u, 0);
    for (int i = 0; i < n; ++i){
        print(i);
    }
}


Measured memory_bytes: 3080
import java.util.Scanner;

// ???Input?????????
// (1) 1???????????°??????????????????(scan.nextInt())
// (2) ??????n????¨????m???????¬??????????(n ?? m)?????????A??¨????????¨?????????
// (3) ????´???°???m???????¬????????????????????????????b??¨????????¨?????????
// (4) n???????????\?????????????????°?????????
	// (4.1) m???????????\?????????????????°?????????
		// (4.1.1) ??°??????????????????
		// (4.1.2) ?????????????????°????????????A???[n - 1][m - 1]???????´???????
// (5) m???????????\?????????????????°?????????
	// (5.1) ??°??????????????????
	// (5.2) ?????????????????°?????????????????????b???[m - 1]???????´???????

// ???Output?????????
// (6) n?????°???????????\?????????????????°?????????
	// (6.1) ?¶????????????????0??§???????????????
	// (6.2) m?????°???????????\?????????????????°?????????
		// (6.2.1) ??????A???[n - 1][m - 1]???????´????????????¨??????????????????b???[m - 1]???????´??????????????????????
		// (6.2.2) ???????????????????¶????????????????
	// (6.3) ?¶??????????????????¨?????????
// (7) scan?????????????????????

public class Main {

	public static void main(String[] args) {

		int m = 0;
		int n = 0;

		Scanner scan = new Scanner(System.in);

		n = scan.nextInt();
		m = scan.nextInt();

		int[][] matrixA = new int[n][m];
		int[] vectorB = new int[m];

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				int matNum = scan.nextInt();
				matrixA[i][j] = matNum;

			}
		}
		for (int j = 0; j < m; j++) {
			int vecNum = scan.nextInt();
			vectorB[j] = vecNum;
		}

		for (int i = 0; i < n; i++) {
			int sumResult = 0;
			for (int j = 0; j < m; j++) {
				int sum = (matrixA[i][j]) * (vectorB[j]);
				sumResult += sum;
			}
			System.out.println(sumResult);
		}
		scan.close();
	}
}

Measured memory_bytes: 40220
X,Y,Z,K = list(map(int,input().split()))
A = sorted(list(map(int,input().split())),reverse=True)
B = sorted(list(map(int,input().split())),reverse=True)
C = sorted(list(map(int,input().split())),reverse=True)

ma,mb,mc = A[0],B[0],C[0]
sA = [a-ma for a in A] + [-10**15]
sB = [b-mb for b in B] + [-10**15]
sC = [c-mc for c in C] + [-10**15]

ia,ib,ic = 0,0,0
while min(10**6,(X)*(Y)*(Z)) > (ia+1)*(ib+1)*(ic+1):
    m = max(sA[ia+1],sB[ib+1],sC[ic+1])
    if ia < (X-1) and sA[ia+1] == m:
        ia = min(ia+1,X-1)
    if ib < (Y-1) and sB[ib+1] == m:
        ib = min(ib+1,Y-1)
    if ic < (Z-1) and sC[ic+1] == m:
        ic = min(ic+1,Z-1)
ans = []
for a in A[:ia+1]:
    for b in B[:ib+1]:
        for c in C[:ic+1]:
            ans.append(a+b+c)
ans.sort(reverse=True)
for out in ans[:K]:
    print(out)


Measured memory_bytes: 55976
#include<stdio.h>
#include<math.h>
int main(){
	int n,a,b,c,i,j,k,tmp;
	scanf("%d",&n);
	if(n==2){
		scanf("%d%d",&a,&b);
		if(a>b){tmp=a;a=b;b=tmp;}
		j=a/2;
		for(i=1;i<=j;i++){
			if(a%i==0){
				if(b%i==0){
					printf("%d\n",i);
				}
			}
		}
		if(b%a==0)printf("%d\n",i);
	}
	if(n==3){
		scanf("%d%d%d",&a,&b,&c);
		if(b>c){tmp=b;b=c;c=tmp;}
		if(a>b){tmp=a;a=b;b=tmp;}
		j=a/2;
		for(i=1;i<=j;i++){
			if(a%i==0){
				if(b%i==0){
					if(c%i==0){
						printf("%d\n",i);
					}
				}
			}
		}
		if(b%a==0){
			if(c%a==0){
				printf("%d\n",i);
			}
		}
	}
	return 0;
}



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

typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> pll;
#define endl "\n";
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

ll const inf = 1e18;
ll const maxn = 1e6+5;
ll const mod = 1e9+7;

// code begins here

int main(){
    fast;
    
    ll n;
    cin>>n;
    
    vector<ll> arr(n);
    for(auto &u: arr)
        cin>>u;
    
    vector<ll> cnt(maxn,0), cnt1(maxn, 0);
    
    set<ll> s;
    
    for(ll i=0;i<n;i++){
        cnt1[arr[i]]++;
        if(s.count(arr[i]))
            continue;
        for(ll j=arr[i];j<maxn;j+=arr[i]){
            cnt[j]++;
        }
        s.insert(arr[i]);
    }
    
    ll ans = 0;
    for(ll i=0;i<n;i++){
        if(cnt[arr[i]]==1 && cnt1[arr[i]]==1)
            ans++;
    }
    
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 29760
from collections import defaultdict
n = int(input())
dic = defaultdict(int)
for i in range(n):
    dic[input()[0]] += 1
L = []
for s in "MARCH":
    if s in dic:
        L.append(dic[s])

ans = 0
for i in range(len(L)):
    for j in range(i+1,len(L)):
        for k in range(j+1,len(L)):
            ans += L[i]*L[j]*L[k]
print(ans)

Measured memory_bytes: 3444
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
const int INF = (1<<30)-1;
const long long LINF = (1LL<<62)-1;
const long double PI = acos(-1.0L);
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

vector<bool> prime_table(int n) {
  vector<bool> res(n + 1, true);
  if (n >= 0) res[0] = false;
  if (n >= 1) res[1] = false;
  for (int i = 2; i * i <= n; i++) {
    if (!res[i]) continue;
    for (int j = i + i; j <= n; j += i) {
      res[j] = false;
    }
  }
  return res;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  auto prime = prime_table(1e8);
  int ans = 0;
  rep(i, n) {
    int a;
    cin >> a;
    if (prime[a])
      ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 14872
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;

LL a[100010],b[100010];
int main(void)
{
    int n,i,j;
    while(scanf("%d",&n)==1)
    {
        for(i=1;i<=n;i++)
            scanf("%lld%lld",&a[i],&b[i]);
        LL cnt = 0;
        for(i=n;i>=1;i--)
        {
            if((a[i]+cnt) % b[i] == 0)
                continue;
            a[i] = (a[i]+cnt)%b[i];
            cnt += (b[i]-a[i]);
        }
        cout << cnt << endl;
    }

    return 0;
}


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

using namespace std;

#define il inline
#define re register int
#define Rep(i, s, e) for (re i = s; i <= e; ++i)
#define Dep(i, s, e) for (re i - s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout);

il int read() {
	int x = 0; bool f = true; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = false; c = getchar();}
	while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
	return f ? x : -x;
}

int n1, n2;
string s1, s2, out;

int main() {
	cin >> s1 >> s2;
	n1 = read(), n2 = read();
	cin >> out;
	if (out == s1) --n1;
	else --n2;
	return printf("%d %d\n", n1, n2) & 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
typedef long long ll;
int a[100000+5];
int qm(int x,int y)
{
    int ans=1;
    while(y)
    {
        if(y%2==1)
        {
            ans=ans*x;
        }
        y/=2;
        x=x*x;
    }
    return ans;
}
int main()
{
    //freopen("out.txt","w",stdout);
    int n;
    scanf("%d",&n);
    //printf("%d\n",a[n]);
    a[0]=0;
    for(int i=1;i<=n;i++)
        a[i]=i;
    for(int i=1;qm(6,i)<=n;i++)
    {
        int x=qm(6,i);

        for(int k=x;k<=n;k++)
        {
            a[k]=min(a[k],a[k-x]+1);
        }


    }
    for(int i=1;qm(9,i)<=n;i++)
    {
        int x=qm(9,i);

        for(int k=x;k<=n;k++)
        {
            a[k]=min(a[k],a[k-x]+1);
        }


    }
    printf("%d\n",a[n]);
    /*printf("{");
    for(int i=n/2;i<=n;i++)
    {
        printf("%d,",a[i]);
    }
    printf("}");*/

    return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
string s[15];
main(){
    int H,W;
    cin >> H >>W;
    for (int i= 0 ;i < H; i++)
        cin >>s[i];
    for(int b= 0; b < (1<<H); b++){
        vector<int> v,w;
        if(__builtin_popcount(b) != (H+1)/2 || !(b&1)) continue;
        for(int i = 0; i < H; i++){
            if((1<<i)&b) w.push_back(i);
            else v.push_back(i);
        }
        int flf=0;
        vector<int> p;
        for(int i =0 ;i < w.size(); i++)
            p.push_back(i);
        do{
            vector<vector<short int> > a,b;
            vector<short int> c;
            for(int i =0 ;i < W; i++){
                a.push_back(c);
                b.push_back(c);
            }
            int fl = 0;

            for(int i= 0;i < v.size(); i++)
                for(int j = 0; j < W; j++)
                 a[j].push_back(s[v[i]][j]*200+s[w[p[i]]][j]),
                 b[j].push_back(s[w[p[i]]][j]*200+s[v[i]][j]);
            if(w.size()>v.size())
                for(int j = 0; j < W; j++)
                 a[j].push_back(s[w[p[w.size()-1]]][j]),
                 b[j].push_back(s[w[p[w.size()-1]]][j]);
                int ans=0;
             for(int j = 0; j < W; j++)
                if(a[j] ==b[j]) ans++;
            sort(a.begin(),a.end());
            sort(b.begin(),b.end());

            if(a!=b) continue;
            for(int i= 1;i < a.size(); i++){
               if(a[i]==a[i-1]) ans-=2,i++;
            }
            if(ans <= 1) {//cout<<ans<<" "<<a.size()<<" "<<v.size()<<" "<<w.size()<<endl;
       //     for(int i = 0; i<a.size(); i++)
         //       cout<<(char)a[i][0]<<endl;
                cout<<"YES"<<endl;
                return 0;
            }
        }while(next_permutation(p.begin(),p.end()));
    }
    cout<<"NO"<<endl;

}
/*
ddx
acb
cab

(a,c),d
(c,a),d
(b,b),x

*/


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;
template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}
int main() {
  cin.tie(0);
  cout << fixed << setprecision(10);
  int n, q; cin >> n >> q;
  string s; cin >> s;
  vector<int> su(n);
  su[0] = 0;
  for(int i=1;i<n;++i) {
    if(s[i-1] == 'A' && s[i] == 'C') {
      su[i] = su[i-1] + 1;
    } else {
      su[i] = su[i-1];
    }
  }
  for(int i=0;i<q;++i) {
    int l, r; cin >> l >> r;
    l--; r--;
    cout << su[r] - su[l] << endl;
  }
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i <= (n); i++)
#define zep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,m,n) for(ll i = (m); i <= n; i++){cout << (x[i]) << " ";} cout<<endl;

const int MAX = 510000;
//const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	
	ll n, k;
	cin >> n >> k;
	ll a[n];
	zep(i, 0, n){
		cin >> a[i];
	}
	sort(a, a+n);
	ll cnt[n], rcnt[n];
	zep(i, 0, n){
		cnt[i] = i+1;
		rcnt[i] = n-i;
	}
	/*rrep(i, n-2, 0){
		if(a[i] == a[i+1]){
			cnt[i] = cnt[i+1];
		}
	}
	rep(i, 1, n-1){
		if(a[i] == a[i-1]){
			rcnt[i] = rcnt[i-1];
		}
	}*/

	//printa(rcnt, 0, 3)
	COMinit();
	
	ll ans = 0;
	zep(i, 0, n){
		if(cnt[i]-1 >= k-1){
			//cout << cnt[i] << k << " " << COM(1, 1) << endl;;
			ll res = COM(cnt[i]-1, k-1);
			//print(res)
			res *= a[i];
			res %= MOD;
			ans += res;
			ans %= MOD;
		}
		if(rcnt[i]-1 >= k-1){
			ll res = MOD-COM(rcnt[i]-1, k-1);
			res *= a[i];
			res %= MOD;
			ans += res;
			ans %= MOD;
		}
		//cout << ans << " " << ans + MOD << endl;
	}
	print(ans)
	return 0;
}

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

#define min(a,b) (((a)<(b))?(a):(b))
#define max(a,b) (((a)>(b))?(a):(b))
#define abs(a) (((a)>0)?(a):(-a))

int main()
{
	int a, b;
	
	scanf("%d%d", &a, &b);
	printf("%d", max(a+b,max(a-b,a*b)));
	return 0;
}

Measured memory_bytes: 256
n, y = map(int, input().split())

for i in range(n + 1):
    for j in range(n - i + 1):
        if i * 10000 + j * 5000 + (n - i - j) * 1000 == y:
            print(i, j, n - i - j)
            exit()
print("-1 -1 -1")
    


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

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

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define what_is(x) cerr << #x << " is " << x << endl;
#define MT make_tuple
#define eb emplace_back
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))

#define REP(i,a,b) for (int i = a; i <= b; i++)
#define FOR(i,n) for (int i=0;i < n ; i++)
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}

int main(){
	string e,o;
	cin >> o >> e;
	int a=0,b=0;
	int i=o.length();
	int j=e.length();
	int count=1;
	while(a<i || b < j){
		if(count%2) {cout << o[a]; a++;}
		if(count%2==0) {cout << e[b];b++;}
		count++;
	}

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
typedef long long int ll;
ll s[51];
ll p[51];
ll pt(ll a,ll b);
int main(){
  ll n,x;
  cin >> n>>x;
  s[0]=1;//層の数
  p[0]=1;//全体のパティの数
  for(int i=1;i<50;i++){
    s[i]=s[i-1]*2+3;
    p[i]=p[i-1]*2+1;
  }
  cout <<pt(n,x)<<endl;
}
ll pt(ll a,ll b){//levelaのb層目までもパティの数
  if(a==0) {
  if(b<=0) return 0;
  else return 1;
}
  else if(1+s[a-1]>=b) return pt(a-1,b-1);
  else return p[a-1]+1+pt(a-1,b-2-s[a-1]);
}


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

int main() {
  long N, D, A;
  cin >> N >> D >> A;
  vector<pair<long, long>> V(N);
  for (long i = 0, x, h; cin >> x >> h; i++) V.at(i) = {x, h};
  sort(V.begin(), V.end());
  queue<pair<long, long>> Q;
  long ans = 0;
  for (long i = 0, cor = 0; i < N; i++) {
    auto [pos, hp] = V.at(i);
    while (Q.size()) {
      auto [range, dmg] = Q.front();
      if (pos > range) {
        cor -= dmg;
        Q.pop();
      } else {
        break;
      }
    }
    hp -= cor;
    if (hp <= 0) continue;
    long cnt = (hp + A - 1) / A;
    ans += cnt;
    Q.push({pos + D + D, A * cnt});
    cor += A * cnt;
  }
  cout << ans << "\n";
}

Measured memory_bytes: 7816
#include<iostream>
#include<algorithm>
#include<unordered_map>
//#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define chmax(a,b) a=max(a,b);
#define N (1<<18)
#define M 19
ll n,v;
class Alpha{
 public:
 ll f[N];
 P g[N][M];
 void setg(ll a[]){
     for(int k=0;k<M;k++){
         for(int i=0;i<n;i++)g[i][k]=make_pair(i,i);
         ll bef=1e18,pnt=0; a[n]=1e18;
         for(int i=0;i<=n;i++){
          if(abs(a[i]-bef)>(v>>k)){
           for(int j=pnt;j<i;j++)g[j][k]=make_pair(pnt,i-1);
           pnt=i;   
          }
          bef=a[i];
         }
         if((v>>k)==0)break;
     }
 }
 void main(ll a[]){
  setg(a);   
  for(int i=0;i<N;i++)f[i]=-1;
  for(int i=0;i<N;i++){
      for(int j=0;j<M-1;j++){
          if(i&(1<<j))continue;
          chmax(f[i+(1<<j)],g[f[i]+1][j+1].second);
      }
  }
 }
};Alpha L,R;

class Solve{
  public:
  unordered_map<ll,bool> mas;
  bool main(ll l,ll r){
      if(mas.size()>M)return 0;
      if(mas.find(l)!=mas.end()){
       return mas[l];   
      }
      bool res=0;
      int who=1; for(int x=v;x;x>>=1)who*=2;
      for(int i=0;i<who;i++){
       int ls=i,rs=who-1-i;
       if(l-1<=L.f[ls]&&n-1-R.f[rs]<=r+1)res=1;
      }
      mas[l]=res;
      return res;
  }
};Solve sv;

ll a[N];
int main(){
    cin>>n>>v;
    for(int i=0;i<n;i++)cin>>a[i];
    L.main(a);
    for(int i=0;i<n/2;i++)swap(a[i],a[n-i-1]);
    R.main(a);
    for(int i=0;i<n;i++){
     bool ans=sv.main(L.g[i][0].first,L.g[i][0].second);   
     cout<<(ans?"Possible":"Impossible")<<endl;
    }
 return 0;   
}


Measured memory_bytes: 163712
#include "bits/stdc++.h"
using namespace std;

int main() {
	string S[7] = { "SUN", "MON","TUE","WED","THU","FRI","SAT"};
	string T;
	cin >> T;
	for (int i = 0; i < 7; i++) {
		if (S[i] == T) {
			cout << 7 - i << endl;
			return 0;
		}
	}
}

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

#define EACH(i, a) for (auto &&i : a)
#define FOR(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define RFOR(i, a, b) for (int i = (int)b - 1; i >= (int)a; --i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) FOR(i, 1, int(n) + 1)
#define RREP(i, n) RFOR(i, 0, n)
#define RREPS(i, n) RFOR(i, 1, int(n) + 1)
#define ALL(x) (x).begin(), (x).end()
#define MEMSET(v, h) memset((v), h, sizeof(v))
#define debug(x) cout << #x << ": " << x << endl

#define pb push_back
#define mp make_pair
#define F first
#define S second

#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev
#define INF (1L << 30)
#define MOD (1000000007)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

template <class T>
void pv(T a, T b)
{
  for (T i = a; i != b; ++i)
    cout << *i << " ";
  cout << endl;
}
template <class T>
void pvp(T a, T b)
{
  for (T i = a; i != b; ++i)
    cout << "(" << i->first << ", " << i->second << ") ";
  cout << endl;
}
template <class T>
bool chmax(T &a, const T &b)
{
  if (a < b)
  {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
  if (b < a)
  {
    a = b;
    return 1;
  }
  return 0;
}
int in()
{
  int x;
  scanf("%d", &x);
  return x;
}

using ll = long long;
#define int ll

//**********

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

  int n, m;
  cin >> n >> m;

  // A[i]: member i が j 番目に好きなスポーツ
  vector<int> A[301];

  REP(i, n)
  {
    REP(j, m)
    {
      int sp;
      cin >> sp;
      A[i].pb(sp - 1);
    }
  }

  int best_members = 999;

  if (m == 1)
  {
    best_members = n;
  }

  REP(ii, m - 1)
  {
    int popular[301];
    MEMSET(popular, 0);
    REP(i, n)
    { // popular[m]はm番目のスポーツの参加人数
      popular[A[i][0]] += 1;
    }
    int max_sp = 0;
    int max_members = 0;
    REP(sp, m)
    {
      if (max_members < popular[sp])
      {
        max_sp = sp;
        max_members = popular[sp];
      }
    }

    // debug(max_sp + 1);
    // debug(max_members);

    REP(i, n)
    { // 最大人気スポーツを除外
      A[i].erase(remove(ALL(A[i]), max_sp), A[i].end());
    }

    if (best_members > max_members)
    { // もし最大人数が、これまでで最小だったら更新
      best_members = max_members;
    }
  }

  cout << best_members << endl;

  return 0;
};


Measured memory_bytes: 1536
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<complex>
#include<string>
#include<cstring>
using namespace std;
#define rep2(x,from,to) for(int x=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
#define INF 100000000
#define debug(x) cout<<#x<<": "<<x<<endl

#define all(x) x.begin(),x.end()
typedef pair<int,int> P;
typedef pair<int,P> PP;
string s[10];
int flag;
int zu[12][12];
int main()
{
	int w,h;
	cin>>w>>h;
	rep(i,w)
	{
		cin>>s[i];
		rep(j,h)
		{
			if(s[i][j]=='#')zu[i+1][j+1]=1;
		}
	}
	flag=1;
	rep2(i,1,w+1)rep2(j,1,h+1)
	{
		if(!((i==1&&j==1)||(i==w&&j==h)))
		{
			if(zu[i][j]==1)
			{
				if(!(zu[i-1][j]+zu[i][j-1]==1&&zu[i+1][j]+zu[i][j+1]==1))
				{
					flag=0;
				}
			}
		}
		else if(i==1&&j==1)
		{
			if(!(zu[i+1][j]+zu[i][j+1]==1))flag=0;
		}
		else
		{
			if(!(zu[i-1][j]+zu[i][j-1]==1))flag=0;
		}
	}
	if(flag)
	{
		cout<<"Possible"<<endl;
	}
	else cout<<"Impossible"<<endl;
	return 0;
}

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

int main(){
	int n;cin>>n;
	int cnt=0;
	rep(i,n){
		int a;cin>>a;
		if(a%2==0)cnt++;
	}
	cout<<cnt<<endl;
}


Measured memory_bytes: 3104
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int main()
{
  int N, K;
  cin >> N >> K;
  string S;
  cin >> S;
  REP(i, N)
  {
    if (i == K - 1)
      cout << (char)(S[i] - 'A' + 'a');
    else
      cout << S[i];
  }
  cout << "\n";
  return 0;
}

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

int main() {
  int N;
  cin >> N;
  if (N%10==3)
    cout << "bon" << endl;
  else if (N%10==0 || N%10==1 || N%10==6 || N%10==8)
    cout << "pon" << endl;
  else
    cout << "hon" << endl;

}

Measured memory_bytes: 3580
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <tuple>
#include <stack>
#include <bitset>

#define MAX_N 1000000
#define MAX_M 1000000
#define INF   1000000000

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
struct edge {ll to; ll cost;};
vector<edge> G[MAX_N];
ll d[MAX_N];
ll sign[MAX_N];

void dijkstra(const ll start, const vector<edge> (&G)[MAX_N], ll (&d)[MAX_N]) {

  priority_queue<P, vector<P>, greater<P> > pque;
  fill(d, d + MAX_N, INF);
  fill(sign, sign + MAX_N, INF);
  
  d[start] = 0;
  pque.push( P(0, start) );
  
  while (!pque.empty()) {
    P p = pque.top();
    pque.pop();
    
    ll v = p.second;
    if (d[v] < p.first) continue;
    
    for(ll i = 0; i < G[v].size(); i++) {
      edge e = G[v][i];
      
      if (d[e.to] > d[v] + e.cost) {
        d[e.to] = d[v] + e.cost;
        pque.push( P(d[e.to], e.to) );
	sign[e.to] = v;
      }
    }
  }
}

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

    ll N, M;
    cin >> N >> M;

    for (ll i = 0; i < M; i++) {
      ll f, t;
      cin >> f >> t;
      f--; t--;

      edge e1, e2;
      e1.to   = t;
      e1.cost = 1;
      e2.to   = f;
      e2.cost = 1;

      G[f].push_back(e1);
      G[t].push_back(e2); 
    }

    ll s = 0;
    dijkstra(s, G, d);

    for(int i = 1; i < N; i++) {
      if(sign[i] == INF) {
	cout << "No" << endl;
	return 0;
      }
    }
      
    cout << "Yes" << endl;
    for(int i = 1; i < N; i++) {
      cout << ++sign[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 54412
input_num=[input() for i in range(2)]

n=input_num[0].split()
n=list(map(int,n))
a=input_num[1].split()
a=list(map(int,a))
     
if len(a)<=n[1]:
  print(0)
else:
  a.sort(reverse=True)
  b=a[n[1]:]
  print(sum(b))

Measured memory_bytes: 28916
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int main(){
	
	int N,Q,M,Date[101],i,l,k;
	
	while(0<=scanf("%d%d",&N,&Q)){
		for(i=0;i<101;i++){
			Date[i]=0;
		}
		
		if((N==0) && (Q==0)){
			break;
		}
		
		for(k=0;k<N;k++){
			scanf("%d",&M);
			if(M==0){
				continue;
			}else{
				for(i=0;i<M;i++){
					scanf("%d",&l);
					++Date[l];
				}
			}
		}
		l=0;
		i=0;
		for(k=0;k<100;k++){
			if(i<Date[k] && Date[k]>=Q){
				i=Date[k];
				l=k;
			}
		}
		
		printf("%d\n",l);
	}
	
	return 0;
}

Measured memory_bytes: 764
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    cout << (n-1)*(m-1) << endl;

    return 0;
}

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

using namespace std;

using ll = long long;
using ld = long double;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(8) << setiosflags(ios::fixed);

    const ll MOD = 1e9 + 7, P = 13;
    array<ll, 6> d = {1, 10, 9, 12, 3, 4};

    string s;
    cin >> s;

    const int len = s.size();
    vector<vector<ll>> dp(len + 1, vector<ll>(P));
    dp[0][0] = 1;

    for (int i = 0; i < len; ++i) {
        for (int j = 0; j < P; ++j) {
            if (dp[i][j] == 0) continue;

            if (s[i] == '?') {
                for (int k = 0; k < 10; ++k) {
                    int add = len - i - 1;
                    if (add != 0) add = d[add % 6];
                    else add = 1;

                    add = (add * k) % P;
                    (dp[i + 1][(add + j) % P] += dp[i][j]) %= MOD;
                }
            }
            else {
                int add = len - i - 1;
                if (add != 0) add = d[add % 6];
                else add = 1;

                add = (add * (int)(s[i] - '0')) % P;
                (dp[i + 1][(add + j) % P] += dp[i][j]) %= MOD;
            }
        }
    }

    cout << dp[len][5] << endl;

    return 0;
}


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

int main(){
  ll N; cin >> N;
  
  ll cnt2 = 0; ll cnt5 = 0;
  
  if( N % 2 == 0 ){ 
    ll k = N/2;
    
    ll res = k;
    
    while( res > 0 ){ 
      res /= 2;
      cnt2 += res;
    }
    
    cnt2 += k;
    
    res = k;
    
    while( res > 0 ){
      res /= 5;
      cnt5 += res;
    }
    
     cout << min(cnt2,cnt5) << endl;
    
  }
  else{
    
    ll k = (N+1)/2;
    
    ll res = N+1;
    
    while( res > 0 ){
      res /= 2;
      cnt2 += res;
     
    }
    
    res = N+1;
    
    while( res > 0){ 
      res /= 5;
      cnt5 += res;
      
    }
    
    res = k;
    
    while( res > 0 ){ 
      res /= 2;
      cnt2 -= res;
      
    }
    
    cnt2 -= k;
    
    
    res = k;
    
    while( res > 0 ){
      
      res /= 5;
      
      cnt5 -= res;
      
    }
    
    cout << min(cnt2,cnt5) << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <queue>
#include <map>
#include <set>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
const int INF = 1<<29;
typedef pair<int,int> pii;
#define F first
#define S second
int main() {
  int n, m, p, q, r;
  while(cin >> n, n) {
    cin >> m >> p >> q >> r;
    vector<pii> v;
    v.push_back(pii(1, n));
    REP(i, m) {
      int x, y;
      cin >> x >> y;
      int num = 0;
      int xpos=-1, ypos;
      int xrem, yrem;
      REP(i, v.size()) {
        int tmp = v[i].S - v[i].F + 1;
        if (num < x && x <= num+tmp) {
          xpos = i;
          xrem = x-num;
        }
        if (num < y && y <= num+tmp) {
          ypos = i;
          yrem = y-num;
          break;
        }
        num += tmp;
      }
//      printf("xpos=%d,xrem=%d, ypos=%d,yrem=%d\n",xpos,xrem,ypos,yrem);
      vector<pii> next;
      if (xpos==ypos) {
        if (v[xpos].F+yrem <= v[xpos].S)
          next.push_back(pii(v[xpos].F+yrem, v[xpos].S));
        next.insert(next.end(), v.begin()+xpos+1, v.end());
        if (v[xpos].F+xrem <= v[xpos].F+yrem-1)
          next.push_back(pii(v[xpos].F+xrem, v[xpos].F+yrem-1));
        next.insert(next.end(), v.begin(), v.begin() + xpos);
        if (v[xpos].F <= v[xpos].F+xrem-1)
          next.push_back(pii(v[xpos].F, v[xpos].F+xrem-1));
      } else {
        if (v[ypos].F+yrem <= v[ypos].S)
          next.push_back(pii(v[ypos].F+yrem, v[ypos].S));
        next.insert(next.end(), v.begin()+ypos+1, v.end());
        if (v[xpos].F+xrem <= v[xpos].S)
          next.push_back(pii(v[xpos].F+xrem, v[xpos].S));
        next.insert(next.end(), v.begin()+xpos+1, v.begin()+ypos);
        if (v[ypos].F <= v[ypos].F+yrem-1)
          next.push_back(pii(v[ypos].F, v[ypos].F+yrem-1));
        next.insert(next.end(), v.begin(), v.begin() + xpos);
        if (v[xpos].F <= v[xpos].F+xrem-1)
          next.push_back(pii(v[xpos].F, v[xpos].F+xrem-1));
      }
      v = next;
      // FOR(it, v) {
      //   printf("(%d,%d)",it->F,it->S);
      // }
      // cout << endl;
    }
    int res = 0;
    int num = 0;
    bool f = 0;
    REP(i, v.size()) {
      int tmp = v[i].S - v[i].F + 1;
      if (f) {
        if (num < q && q <= num+tmp) {
          if (v[i].F <= r) res += min(min(r, v[i].S), v[i].F+q-num-1) - v[i].F + 1;
          break;
        }
        if (v[i].F <= r) res += min(r, v[i].S)-v[i].F+1;
      } else if (num < p && p <= num+tmp) {
        if (v[i].F + p-num-1 <= r) res += min(r, v[i].S) - (v[i].F+p-num-1) + 1;
        f = 1;
      }
      num += tmp;
    }
    cout << res << endl;
  }
}

Measured memory_bytes: 1160
def solve():
    N, W = map(int, input().split())
    w = []
    v = []
    for i in range(N):
        tmpw, tmpv = map(int, input().split())
        w.append(tmpw)
        v.append(tmpv)
    
    dp = [[0] * (W+1) for i in range(N+1)]
    for i in range(N):
        for sum_w in range(W+1):
            if sum_w - w[i] >= 0:
                dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w-w[i]]+ v[i])
            
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
    
    print(dp[-1][-1])


if __name__ == '__main__':
    solve()


Measured memory_bytes: 120048
#include <stdio.h>

int main(void)
{
	int n, x;
	int i, j, k;
	int cnt;

	while (1) {
		scanf("%d %d", &n, &x);
		if (n + x == 0)	break;

		cnt = 0;

		for (i = 1; i < n - 1; i++)
			for (j = i + 1; j < n; j++) 
				for (k = j + 1; k < n + 1; k++) 
					if (i + k + j == x)	cnt++;
		
		printf("%d\n", cnt);
	}

	return 0;
}

Measured memory_bytes: 600
import java.util.*;

/**
 * Created by Seiya on 2016/10/16.
 */

public class Main {

    static final long MOD = 1000000007;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();

        long ans = 1;
        for (int i = 1; i <= N  ; i++) {
            ans = ans * i;
            ans = ans % MOD;
        }

        System.out.println(ans);


    } // mainMethod



} // MainClass


Measured memory_bytes: 21844
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional> // for less 
#define pb push_back
#define For(i,s,e) for (ll i=(s); i<(e); i++)
#define Debug_array(a,n) for (ll i=(0); i<(n); i++) cout<<a[i]<<" "
#define Foe(i,s,e) for (ll i=(s); i<=(e); i++)
#define Fod(i,s,e) for (ll i=(s)-1; i>=(e); i--)
#define pii pair<ll,ll>
#define fi first
#define se second
#define endl "\n"
#define mp make_pair
#define big_prime 15486277
#define bigger_prime 179424697
#define biggest_prime 32416188691
//#define random_shuffle(indices.begin(), indices.end());
//std::random_device rd;
//std::mt19937 g(rd());
//std::shuffle(v.begin(), v.end(), g);
using namespace __gnu_pbds; 
using namespace std;
template <class T> ostream& operator << (ostream &os, const vector<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T> ostream& operator << (ostream &os, const set<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T, class S> ostream& operator << (ostream &os, const pair<T, S> &v) { os << v.first << ' ' << v.second; return os; }
// template <class T, class S> ostream& operator << (ostream &os, const unordered_map<T, S> &v) { for (auto i : v) os << '(' << i.first << "=>" << i.second << ')' << ' '; return os; }
 
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <class Arg1> void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << endl; }
    template <class Arg1, class... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args) {
        const char* sep = strchr(names + 1, ',');
        cerr.write(names, sep - names) << " : " << arg1 << "  ";
        __f(sep + 1, args...);
    }
#else
#define trace(...) 0
#define _CRT_SECURE_NO_WARNINGS
#endif // ifndef ONLINE_JUDGE


typedef long long ll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; 

#define Mod 1000000007
#define MAX 5002

map<vector<ll> , ll> M;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	ll n;cin>>n;
	ll ans = 0;
	For(i,0,n){
		string s;cin>>s;
		vector<ll> f(26,0);

		For(i,0,s.size()) f[s[i]-'a']++;

		if(M.find(f)==M.end()){
			M.insert({f,1});
		}else{
			ans += M[f];
			M[f]++;
		}

	}

	cout<<ans<<endl;




























	
}

Measured memory_bytes: 29952
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String {
            bytes
                .by_ref()
                .map(|r| r.unwrap() as char)
                .skip_while(|c| c.is_whitespace())
                .take_while(|c| !c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        v: [usize; 5]
    }
    let r: Vec<usize> = v.iter().map(|x| ((x + 9) / 10) * 10).collect();
    let max = v.iter().zip(r.iter()).map(|(x, y)| y - x).max().unwrap();
    println!("{}", r.iter().sum::<usize>() - max);
}


Measured memory_bytes: 4352
# abc122_b.py
s = input()
ans = 0
cnt = 0
for i in s:
    if i == "A" or i=="T" or i=="G" or i=="C" :
        cnt+=1
    else:
        if ans<cnt:
            ans=cnt
            cnt=0
if ans<cnt:
    ans=cnt

print(ans)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,k;
	cin>>a>>b>>k;
	int j=0;
	for(int i=min(a,b);i>=1;i--)
	{
		if(a%i==0&&b%i==0)
		{
			j++;
			if(j==k)
			{
				cout<<i<<"\n";
				return 0;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 256
// きさま！ 見ているなッ！

#include<iostream>
#include<queue>
#include<memory>
#include<map>
#include<set>
#include<unordered_map>
#include<array>
#include<vector>
#include<algorithm>
#include<list>
#include<limits>
#include<stdio.h>
#include<math.h>
#include<string>
#include<thread>

using namespace std;
using ll = long long;
using vec = vector<int>;
using mat = vector<vec>;
using lst = list<ll>;

const ll MOD = 1000000007;


int main()
{
	int N;
	cin >> N;
	set<string> st;

	for (int i = 0; i < N; ++i)
	{
		string S; cin >> S;
		st.insert(S);
	}

	cout << st.size() << endl;

	return 0;
}



Measured memory_bytes: 19096
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
using namespace std;

typedef long long lld;

lld gcd(lld a, lld b) {return b==0 ? a : gcd(b, a%b);}
lld lcm(lld a, lld b) {return a * b / gcd(a, b);}

int main() {
    lld A, B, C, D;
    
    scanf("%lld%lld%lld%lld", &A, &B, &C, &D);

    printf("%lld", B-A+1 - (B/C-(A-1)/C) - (B/D-(A-1)/D) + (B/lcm(C,D)-(A-1)/lcm(C,D)));
  
    return 0;
}

Measured memory_bytes: 256