akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include<iomanip>
using namespace std;
typedef long long ll;
typedef long  l;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
const double PI=3.141592653589;
const int INF=1000000007;
const ll LMAX=1000000000000001;
int gcd(int a,int b){if(a<b)swap(a,b);int c=a%b;while(c!=0){a=b;b=c;c=a%b;}return b;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};

int main(){
  int n, m; cin >> n >> m;
  vector<int> x(m);
  rep(i, m) cin >> x[i];

  if(n >= m){
    cout << 0 << endl;
  }else{
    sort(ALL(x));
    vector<int> p(m-1);
    int sum = 0;
    rep(i, m-1){
      p[i] = x[i + 1] - x[i];
      sum += p[i];
    }
    sort(ALL(p), greater<int>());

    // cout << sum << endl;
    rep(i, n-1) sum -= p[i];
    cout << sum << endl;
  }

  return 0;
}


Measured memory_bytes: 1024
#define _USE_MATH_DEFINES  

#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#include <vector>

int main(){
    std::vector<std::vector<std::vector<int>>> rooms(4, std::vector<std::vector<int>>(3, std::vector<int>(10, 0)));

    int n;
    std::cin >> n;
    for(int i = 0; i < n; ++i){
        int b, f, r, v, buf;
        std::cin >> b >> f >> r >> v;
        buf = std::min(rooms.at(b - 1).at(f - 1).at(r - 1) + v, 9);
        rooms.at(b - 1).at(f - 1).at(r - 1) = buf;
    }

    for(int i = 0; i < 4; ++i){
        for(int j = 0; j < 3; ++j){
            for(int k = 0; k < 10; ++k){
                std::cout << " " << rooms.at(i).at(j).at(k);
            }
            std::cout << std::endl;
        }

        if(3 != i){
            std::cout << "####################" << std::endl;
        }
    }

    return 0;
}


Measured memory_bytes: 3160
import itertools

N = int(input())

nine_list = [9**i for i in range(0, 6)]
six_list = [6**i for i in range(1, 7)]

ans = float("inf")
for combi in itertools.product([i for i in range(6)], repeat=6):
    # print(combi)
    count = sum(combi)
    six_sum = sum([a*b for a, b in zip(six_list, combi)])
    if N < six_sum:
        continue
    rest = N - six_sum
    for nine in reversed(nine_list):
        if nine > rest:
            continue
        count += rest // nine
        rest = rest % nine
    ans = min(ans, count)

print(ans)

Measured memory_bytes: 45292
n=int(input())
t=tuple([0]+list(map(int,input().split()))+[0])
a=tuple([0]+list(map(int,input().split()))+[0])
c=1
m=10**9+7
for i in range(1,n+1):
    if t[i]>t[i-1]:
        if a[i]>a[i+1]and a[i]!=t[i]or a[i]==a[i+1]and a[i]<t[i]:
            print(0)
            exit()
    else:
        if a[i]>a[i+1]and a[i]>t[i]:
            print(0)
            exit()
        if a[i]==a[i+1]:
            c=min(t[i],a[i])*c%m
print(c)

Measured memory_bytes: 18480
#include <bits/stdc++.h>
using namespace std;
int main(){
  while (1){
    int N, M;
    cin >> N >> M;
    if (N == 0 && M == 0){
      break;
    }
    vector<int> mx(N, 0);
    vector<int> mn(N, 0);
    for (int i = 0; i < M; i++){
      int S, k;
      cin >> S >> k;
      for (int j = 0; j < k; j++){
        int c;
        cin >> c;
        c--;
        mx[c] += S;
        if (k == 1){
          mn[c] += S;
        }
      }
    }
    vector<pair<int, int>> mx2(N);
    for (int i = 0; i < N; i++){
      mx2[i] = make_pair(mx[i], i);
    }
    vector<pair<int, int>> mn2(N);
    for (int i = 0; i < N; i++){
      mn2[i] = make_pair(mn[i], i);
    }
    sort(mx2.rbegin(), mx2.rend());
    sort(mn2.begin(), mn2.end());
    if (mx2[0].second != mn2[0].second){
      cout << mx2[0].first - mn2[0].first + 1 << endl;
    } else {
      cout << max(mx2[0].first - mn2[1].first, mx2[1].first - mn2[0].first) + 1 << endl;
    }
  }
}


Measured memory_bytes: 3148
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <numeric>
#include <map>
#include <unordered_map>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mod 1000000007
using ll = long long;
using namespace std;

int main(){
  int N,K;
  cin >> N >> K;
  vector<int> X(N);
  rep(i,N) cin >> X[i];
  int ans = 0;
  rep(i,N){
    ans += 2*min(X[i],abs(K-X[i]));
  }
  cout << ans << endl;
  return 0;
}


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

int main() {
    int n;  cin >> n;
    for (int i = 1; true; i++) {
        if (i*n % 2 == 0) {
            cout << i*n << endl;
            break;
        }
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define ld long double
#define inf 0x7f7f7f7f7f7f7f7f 
#define maxn 1000010
#define ri register int
#define il inline
#define mk make_pair
#define pb push_back
#define fi first
#define se second
#define mod 998244353
#define db(x) cout << x << endl; 
#define eps 0.0001
using namespace std;
int a[maxn],b[maxn];
char s[maxn];
signed main()
{
	ios::sync_with_stdio(0);
	int a,b,c,k;
	cin >> a >> b >> c >> k;
	if(k<=a)
		cout << k;
	else
	{
		if(k-a<=b)
			cout <<a;
		else
			cout << a-(k-a-b);
	}
	return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
 
int main(){
    int x,y,a,b,c;
    cin >> x >> y >>a>>b>>c;
    vector<int> p(a);
    vector<int> q(b);
    vector<int> r(c);
    rep(i,a) cin >>p[i];
    rep(i,b) cin >>q[i];
    rep(i,c) cin >>r[i];
    sort(p.rbegin(),p.rend());
    sort(q.rbegin(),q.rend());
    vector<int> d;
    rep(i,x) d.push_back(p[i]);
    rep(i,y) d.push_back(q[i]);
    rep(i,c) d.push_back(r[i]);
    sort(d.rbegin(),d.rend());
    long ans=0;
    rep(i,x+y) ans+=d[i];
    cout << ans;
    return 0;
}

Measured memory_bytes: 3572
#include <iostream>
using namespace std;
int main(void){
  int n ,m;
  cin >> n >> m;
  if(n%2==0)
  {
  if(n>=2*m)
  {
      cout << "YES" << endl;
  }
  else
  {
      cout << "NO" << endl;
  }
}
else
{
    if(n+1>=2*m)
  {
      cout << "YES" << endl;
  }
  else
  {
      cout << "NO" << endl;
  }
}
    return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
N = int(input())

for n in range(1,3500+1):
    for h in range(1,3500+1):
        if (4*h*n-N*n-N*h)>0 and (N*h*n)%(4*h*n-N*n-N*h)==0:
            w = (N*h*n)//(4*h*n-N*n-N*h)
            print(h,n,w)
            exit()


Measured memory_bytes: 3060
class Board
  def initialize t
    @b = Array.new(144,0)
    (0..11).each do |x|
      (0..11).each do |y|
        if t[x][y] == "1" then
          @b[12*x+y] = 12*x+y+1
        end
      end
    end
  end

  def print
    (0..11).each do |x|
      (0..11).each do |y|
        if @b[12*x+y] != 0 then
          printf("%02x", @b[12*x+y])
        else
          printf( "  " )
        end
      end
      printf("\n")
    end
  end

  def neibor x, y
    n = []

    if @b[12*x+y] == 0 then
      return n
    else
      [ [x,y], [x-1,y], [x+1,y], [x,y-1], [x,y+1] ].each do |(xx,yy)|
        if 0 <= xx and xx < 12 and 0 <= yy and yy < 12 then
          v = @b[12*xx+yy]
          n.push v if v != 0
        end
      end
      n.uniq.sort
    end
  end

  def update tgt, val
    n = 0
    (12*12).times do |i|
      if tgt.include? @b[i] then
        @b[i] = val
        n += 1
      end
    end
    return n
  end

  def res
    @b.uniq.delete_if { |x| x == 0 }.size
  end
  
end

def solve t
  b = Board.new t
  while true
    c = 0
    12.times do |x|
      12.times do |y|
        n =  b.neibor(x,y)
        t =  n.shift
        c += b.update(n,t)
      end
    end
    break if c == 0
  end
#  b.print
  b.res
end

while not $stdin.eof? do
  t = []
  12.times do
    t.push $stdin.gets
  end
  $stdin.gets

  a = solve t

  printf("%d\n",a)
  
end



Measured memory_bytes: 6892
package main

import "fmt"

func main() {
	var n, c, min, max int
	fmt.Scan(&n)

	var colors = make([]bool, 8)

	for i := 0; i < n; i++ {
		fmt.Scan(&c)

		ccode := -1
		switch {
		case 1 <= c && c <= 399:
			ccode = 0
		case 400 <= c && c <= 799:
			ccode = 1
		case 800 <= c && c <= 1199:
			ccode = 2
		case 1200 <= c && c <= 1599:
			ccode = 3
		case 1600 <= c && c <= 1999:
			ccode = 4
		case 2000 <= c && c <= 2399:
			ccode = 5
		case 2400 <= c && c <= 2799:
			ccode = 6
		case 2800 <= c && c <= 3199:
			ccode = 7
		case 3200 <= c:
			max++
		}

		if ccode != -1 && !colors[ccode] {
			colors[ccode] = true
			min++
			max++
		}
	}
	if min == 0 {
		fmt.Printf("%d %d\n", 1, max)
	} else {
		fmt.Printf("%d %d\n", min, max)
	}
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep2(i, a, n) for(ll i = a; i < (ll)(n); i++)
#define memi cout << endl
#define kono(n) cout << fixed << setprecision(n)
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define hina cout << ' '
#define in(n) cin >> n
#define in2(n, m) cin >> n >> m
#define in3(n, m, l) cin >> n >> m >> l
#define out(n) cout << n
const ll mei = (ll)1e9 + 7;

int main(){
  ll n, a, b, c;
  in(n);
  bool h;
  vector<ll> p(100009, 0), q(100009, 0), r, s;
  rep2(i, 2, 1000){
    a = 2;
    if(q[i] == 0){
      while(i * a < 100009){
        q[i * a] = 1;
        a++;
      }
    }
  }
  rep2(i, 2, 100009){
    if(q[i] == 0)
      r.pb(i);
  }
  rep(i, r.size() - 1){
    a = (r[r.size() - i - 1] + 1) / 2;
    h = false;
    rep(j, r.size()){
      if(r[j] == a)
        h = true;
    }
    if(h)
      s.pb(r[r.size() - i - 1]);
  }
  b = 0;
  sort(all(s));
  a = 0;
  rep(i, 100009){
    if(i == s[a]){
      p[i] = b + 1;
      b++;
      a++;
    }
    else
      p[i] = b;
  }
  rep(i, n){
    in2(a, b);
    out(p[b] - p[a - 1]);
    memi;
  }
}


Measured memory_bytes: 2432
import random
import math
import collections
import itertools
import functools
import operator
import os
import sys

ri = lambda: map(int, raw_input().split())
def pi(a): print (' '.join(map(str, a)))

from fractions import Fraction
n = input()
a = ri()

print float(1/sum(Fraction(1, x) for x in a))


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

    ll cn[10][10];


int main(){
    ll N;cin>>N;
    rep(i,1,N+1){
        cn[i/(ll)pow(10,floor(log10(i)+1)-1)][i%10]++;
    }
    ll ans=0;
    rep(i,1,10){
        ans+=cn[i][i]*cn[i][i];
    }
    rep(i,1,9){
        rep(j,i+1,10){
            ans+=2*cn[i][j]*cn[j][i];
        }
    }
    cout<<ans<<endl;
}







Measured memory_bytes: 768
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using ll = long long;
using P = pair<int,int>;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}




int main()
{
    ll A,B,N;
    cin >> A >> B >> N;

    if((B - 1) <= N) N = B - 1;

    ll ans;

    ans = (A * N)/B - A * (N/B);

    cout << ans << endl;

    return 0;
}
//Ctrl+Shift+Bでコンパイルと実行を行ってデバッグすること

Measured memory_bytes: 3620
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Arrays;
import java.util.Collections;
import java.util.*;
class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();
    String s = scan.next();
    String[] split = s.split("");
    int count = 1;
    for (int i = 1;i < n; i++) {
      if (split[i].equals(split[i - 1])) {
        split[i - 1] = "0";
      }
      else{
        count += 1;
      }
    }
    System.out.println(count);
  }
}

Measured memory_bytes: 46544
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n, a, b;
  cin >> n >> a >> b;
  int cnt1 = 0, cnt2 = 0, cnt3 = 0;
  for(int i = 0; i < n; i++){
    int p; cin >> p;
    if(p <= a) cnt1++;
    else if(p <= b) cnt2++;
    else cnt3++;    
  }
  cout << min({cnt1, cnt2, cnt3}) << endl;
  return 0;
}

Measured memory_bytes: 3600
def d(a):
	return int(a)

N=int(input())
answer=""
for i in range(N):
	if answer!="":
		answer+="\n"
	a=input().split()
	
	a.sort(key=d)
	if int(a[0])**2+int(a[1])**2==int(a[2])**2:
		answer+="YES"
	else:
		answer+="NO"
print(answer)

Measured memory_bytes: 7616
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;

int main()
{
    int N; cin>>N;
    vector<long long> x(N), y(N);
    for (int i=0; i<N; i++)
        cin>>x[i]>>y[i];

    //  https://img.atcoder.jp/wtf19-open/editorial.pdf

    //  x[i], y[i] >= 0 とする
    long long base = 1LL<<58;
    for (int i=0; i<N; i++)
    {
        x[i] += base;
        y[i] += base;
    }

    //  直線 y = 0 上のランプのみが点灯するようにしたときに、
    //  x < n, x%3 == r を満たすxについて、 
    //  (x, 0) の点灯しているランプの個数が奇数となるか
    auto count = [&](long long n, long long r) -> bool
    {
        bool ret = false;
        for (int i=0; i<N; i++)
        {
            if (n <= x[i])
                continue;

            long long m = n - x[i] - 1;
            //  [k][r]: k桁以下を比較したときにm以下
            long long A[61][3] = {};
            //  [k][r]: 任意
            long long B[61][3] = {};

            //  0
            A[0][0] = 1LL;
            B[0][0] = 1LL;
            //  1
            if (y[i]&1)
            {
                if (m&1)
                    A[0][1] = 1LL;
                B[0][1] = 1LL;
            }

            for (int k=1; k<=60; k++)
                for (int pr=0; pr<3; pr++)
                {
                    //  0
                    A[k][pr] += m>>k&1 ? B[k-1][pr] : A[k-1][pr];
                    B[k][pr] += B[k-1][pr];
                    //  1
                    if (y[i]>>k&1)
                    {
                        long long cr = (pr + (1LL<<k)) % 3;
                        if (m>>k&1)
                            A[k][cr] += A[k-1][pr];
                        B[k][cr] += B[k-1][pr];
                    }
                }

            if (A[60][((r-x[i])%3+3)%3]%2 != 0)
                ret = !ret;
        }
        return ret;
    };

    //  y = 0 の直線上のランプのみが点灯するようにしたときに、
    //  (p, 0)が点灯しているか
    auto check = [&](long long p) -> bool
    {
        bool ret = false;
        for (int i=0; i<N; i++)
            if ((~y[i] & (p-x[i])) == 0)
                ret = !ret;
        return ret;
    };

    long long r3;
    for (r3=0LL; r3<3LL; r3++)
        if (count(1LL<<60, r3))
            break;
    assert(r3<3LL);

    long long l = 0;
    long long r = 1LL<<60;
    while (r-l > 1LL)
    {
        long long m = (l+r)/2;
        if (count(l, r3) == count(m, r3))
            l = m;
        else
            r = m;
    }

    long long t = l;
    for (int k=60; k>=0; k--)
        if (check(l-(1LL<<k)))
            l -= 1LL<<k;
    r = t;
    for (int k=60; k>=0; k--)
        if (check(r+(1LL<<k)))
            r += 1LL<<k;

    long long ansx = l-base;
    long long ansy = (r-l)-base;

    cout<<ansx<<" "<<ansy<<endl;
}


Measured memory_bytes: 512
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define repr(e,x) for(auto& e:x)
using namespace std;
typedef long long ll;
typedef long double ld;

int N,K;
int p[1000];

int main(){
    cin>>N>>K;
    rep(i,N) cin>>p[i];

    sort(p,p+N);

    int ans=0;
    rep(i,K){
        ans+=p[i];
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 3596
#01BFS

H,W = map(int,input().split())
CH,CW = map(int,input().split())
DH,DW = map(int,input().split())
S=[None]*H
for i in range(H):
    S[i] = input()

from collections import deque
def in_area(x,y):
    return 0<=x<=H-1 and 0<=y<=W-1
    
def cango_step(x,y):
    cand0 =[(x+1,y),(x-1,y),(x,y+1),(x,y-1)]
    cand=[c for c in cand0 if in_area(*c)]
    return cand

def cango_warponly(x,y):
    cand0 =[(x-2,y-2),(x-2,y-1),(x-2,y),(x-2,y+1),(x-2,y+2),
            (x+2,y-2),(x+2,y-1),(x+2,y),(x+2,y+1),(x+2,y+2),
            (x+1,y-2),(x,y-2),(x-1,y-2),
            (x+1,y+2),(x,y+2),(x-1,y+2),
            (x+1,y+1),(x+1,y-1),(x-1,y+1),(x-1,y-1)]
    cand=[c for c in cand0 if in_area(*c)]
    return cand

q = deque([(-1,-1,CH-1,CW-1,0)]) 
been = [[False]*W for _ in range(H)]
INF=10**20
shortest =[[INF]*W for _ in range(H)]
shortest[CH-1][CW-1] = 0
    
reach=False
while q:
    x_old,y_old,x_now,y_now,time = q.pop()
    #print(x_now,y_now,time)
    
#     if x_now==H-1 and y_now==W-1:
#         reach=True
#         break
        
    cand = cango_step(x_now,y_now)
    for x_new,y_new in cand:
        if S[x_new][y_new]=="." and shortest[x_new][y_new]>time:
            q.append((x_now,y_now,x_new,y_new,time))
            shortest[x_new][y_new]=time
            
    cand = cango_warponly(x_now,y_now)
    for x_new,y_new in cand:
        if S[x_new][y_new]=="." and shortest[x_new][y_new]>time+1:
            q.appendleft((x_now,y_now,x_new,y_new,time+1))
            shortest[x_new][y_new]=time+1
            
if shortest[DH-1][DW-1]==INF:
    print(-1)
else:
    print(shortest[DH-1][DW-1])       


Measured memory_bytes: 174568
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    ll a[n];
    for(int i=0;i<n;i++){
    	cin>>a[i];
    }
    if(n&1){
    	ll sum=0;
    	for(int i=0;i<n;i++){
    		if(i%2==0)sum+=a[i];
    	}
    	ll dp[n]; dp[0]=0;
    	for(int i=1;i<n;i++){
    		if(i%2==0)dp[i]=dp[i-1];
    	    else{
    	    	ll num=a[i]-a[i-1];
    	    	dp[i]=max(dp[i-1]+num,0LL);
    	    }
    	}
    	ll m=-1e18;
    	for(int i=0;i<n;i++){
    		if(i&1){
    			dp[i]-=a[i+1];
    			m=max(dp[i],m);
    		}
    	}
    	ll ans=sum-a[0];
    	ans=max(ans,sum+m);
    	cout << ans <<endl;
    }
    else{
    	ll b[n+1];
    	b[n]=0;
    	for(int i=n-1;i>=0;i--){
    		if(i&1)b[i]=b[i+1]+a[i];
    		else b[i]=b[i+1];
    	}
    	ll sum=0;
    	ll ans=-1e18;
    	for(int i=0;i<n-1;i++){
    		if(i%2==0)ans=max(ans,sum+b[i+1]),sum+=a[i];
    	}
        ans=max(ans,sum);
        cout << ans <<endl;
    }
    return 0;
}


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

ll max(ll a , ll b)
{
  return (a > b) ? a: b;
}
ll min(ll a , ll b)
{
  return (a < b) ? a : b;
}
void memset(int *arr , int n , int value)
{
    for(int i= 0; i<n ; i++)
    {
        arr[i] = value;
    }
}
/* int vacation(int **arr , int i , int n , int last , int **dp)
 {
     if(i == n)
     {
         return 0;
     }
     if(dp[i][last] != -1)
     {
         return dp[i][last] ;
     }

     int opsn1 = -1e9+7 ;
     int opsn2 = -1e9+7 ;
     int opsn3 = -1e9+7 ;

     if(last !=0)
     {
         opsn1 = arr[i][0] + vacation(arr , i+1 , n , 0 , dp);
     }
     if(last !=1)
     {
         opsn2 = arr[i][1] + vacation(arr , i+1  , n , 1 ,dp);
     }
     if(last !=2)
     {
         opsn3 = arr[i][2] + vacation(arr , i+1  , n , 2 ,dp);
     }
     return dp[i][last] = max(opsn1 , max(opsn2 , opsn3)) ;
}
*/
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    int **arr = new int*[n];
    for(int i= 0; i<n ; i++)
    {
        arr[i] = new int[3] ;
    }
    for(int i= 0; i<n ; i++)
    {
        for(int j= 0; j<3 ; j++)
        {
            cin>>arr[i][j];
        }
    }
    int **dp = new int*[n];
    for(int i=0 ; i<n ; i++)
    {
        dp[i]= new int[3];
    }
    for(int i= 0; i<n ; i++)
    {
        for(int j=0; j<3 ; j++)
        {
            dp[i][j] = -1 ;
        }
    }
    for(int i=0 ; i<3 ; i++)
    {
        dp[0][i] = arr[0][i] ;
    }
    for(int i=1 ; i<n ; i++)
    {
        for(int j = 0 ; j<3 ; j++)
        {
            for(int k= 0; k<3 ; k++)
            {
                if(j !=k)
                {
                    dp[i][j] = max(dp[i][j] , dp[i-1][k] + arr[i][j]);
                }
            }
        }
    }
    int ans = 0;
    for(int i= 0; i<3 ; i++)
    {
        ans = max(dp[n-1][i] , ans) ;
    }
    cout<<ans<<endl;

    //cout<<vacation(arr , 0 , n , 4 , dp);

    return 0;
}


Measured memory_bytes: 8064
#include <iostream>
using namespace std;
typedef long long ll;

ll max(ll a, ll b) {
    return a > b ? a : b; 
}

ll gcd(ll a, ll b) {
  if(b == 0) return a;
  return gcd(b, a % b);
}

int main(void){
    // Your code here!
    int N;
    ll K;
    cin >> N >> K;

    ll A[N];
    ll dp[N+1];


    ll maxv = 0;
    for(int i = 0; i < N; i++){
        cin >> A[i];
        maxv = max(maxv, A[i]);
        if(A[i] == K) {
            cout << "POSSIBLE" << endl;
            return 0;
        }
    }
    if(K > maxv){
        cout << "IMPOSSIBLE" << endl;
        return 0;
    }
    
    dp[0] = A[0];
    for(int i = 0; i < N; i++){
        dp[i+1] = gcd(dp[i], A[i]);
    }
    
    int start = 1;
    int gcdnum = 0;
   
    while(start <= N){
        gcdnum = dp[start];
        if(gcdnum == 1){
            cout << "POSSIBLE" << endl;
            return 0;
        }
        
        if(K % gcdnum == 0) {
            cout << "POSSIBLE" << endl;
            return 0;
        }
        start++;
    }
    
    cout << "IMPOSSIBLE" << endl;
    return 0;
    
}


Measured memory_bytes: 1792
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<string>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>

#define REP(i,n) for(int i=0;i<(n);i++)
#define EPS (1e-7)
#define INF (3e9)

using namespace std;
typedef long long int ll;

int A, B;
int main(void){
    cin >> A >> B;
    if(A<1 or A > 9 or B < 1 or B > 9) cout << -1 << endl;
    else cout << A * B << endl;
    return 0;
}



Measured memory_bytes: 256
chomp (my $n = <STDIN>);
chomp (my @d = split / /, <STDIN>);
chomp (my $m = <STDIN>);
chomp (my @t = split / /, <STDIN>);
my (%h, %g);
$h{$_}++ for @d;
$g{$_}++ for @t;
my $f = 1;
for my $k (keys %g) {
  if ($h{$k} < $g{$k}) {
    $f = 0;
    last;
  }
}
print ($f ? "YES" : "NO");

Measured memory_bytes: 84276
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = readInts()
ans = 0
for i in range(n):
    if A[i] % 2 == 0:
        while A[i] % 2 == 0:
            ans += 1
            A[i] //= 2
print(ans)


Measured memory_bytes: 6428
def solve():
	n=int(input())
	s=[c=="o"for c in input()]
	for a,b in ([0,0],[0,1],[1,0],[1,1]):
		r=[a,b]
		for i in range(n):a,b=b,s[-~i%n]==(a==b);r+=[b]
		if r[:2]==r[-2:]:print("".join("WS"[i]for i in r[:-2]),sep="");exit()
	print(-1)
	
if __name__=="__main__":
	solve()

Measured memory_bytes: 6920
x,n=map(int,input().split())
p=sorted(map(int,input().split()))
t={}
y=[(i>>1)*(1 if i&1 else -1)+x for i in range(1000)]
for i in range(-200,200):
    t[i]=True
for i in p:
    t[i]=False
for i in y:
    if t[i]:
        print(i)
        break

Measured memory_bytes: 62080
#include<iostream>
using namespace std;
#include<vector>
#include<functional>
template<typename T>
struct lazysegtree{
	using F=function<T(T,T)>;
	using G=function<T(T,T,int,int)>;
	const F calcfn,lazycalcfn;
	const G updatefn;
	int n;
	T defvalue,lazydefvalue;
	vector<T>dat,lazy;
	vector<bool>lazyflag;
	lazysegtree(int n_=0,T defvalue_=0,
		const F calcfn_=[](T a,T b){return a+b;},
		const F lazycalcfn_=[](T a,T b){return a+b;},
		const G updatefn_=[](T a,T b,int l,int r){return a+b*(r-l);},
		T lazydefvalue_=0
	):defvalue(defvalue_),lazydefvalue(lazydefvalue_),
		calcfn(calcfn_),lazycalcfn(lazycalcfn_),updatefn(updatefn_)
	{
		n=1;
		while(n<n_)n<<=1;
		dat.assign(2*n-1,defvalue);
		lazy.assign(2*n-1,lazydefvalue);
		lazyflag.assign(2*n-1,false);
	}
	void copy(const vector<T>&v)
	{
		for(int i=0;i<v.size();i++)dat[i+n-1]=v[i];
		for(int i=n-2;i>=0;i--)dat[i]=calcfn(dat[2*i+1],dat[2*i+2]);
	}
	void eval(int i,int l,int r)
	{
		if(lazyflag[i])
		{
			dat[i]=updatefn(dat[i],lazy[i],l,r);
			if(r-l>1)
			{
				lazy[2*i+1]=lazycalcfn(lazy[2*i+1],lazy[i]);
				lazy[2*i+2]=lazycalcfn(lazy[2*i+2],lazy[i]);
				lazyflag[2*i+1]=lazyflag[2*i+2]=true;
			}
			lazy[i]=lazydefvalue;
			lazyflag[i]=false;
		}
	}
	void update(int a,int b,T x,int k=0,int l=0,int r=-1)//[a,b)
	{
		if(r<0)r=n;
		eval(k,l,r);
		if(b<=l||r<=a)return;
		else if(a<=l&&r<=b)
		{
			lazy[k]=lazycalcfn(lazy[k],x);
			lazyflag[k]=true;
			eval(k,l,r);
		}
		else
		{
			update(a,b,x,2*k+1,l,(l+r)/2);
			update(a,b,x,2*k+2,(l+r)/2,r);
			dat[k]=calcfn(dat[2*k+1],dat[2*k+2]);
		}
	}
	T query(int a,int b,int k=0,int l=0,int r=-1)//[a,b)
	{
		if(r<0)r=n;
		eval(k,l,r);
		if(b<=l||r<=a)return defvalue;
		else if(a<=l&&r<=b)return dat[k];
		else return calcfn(
			query(a,b,2*k+1,l,(l+r)/2),
			query(a,b,2*k+2,(l+r)/2,r)
		);
	}
};
main()
{
	int N,Q;
	cin>>N>>Q;
	lazysegtree<pair<long,pair<int,int> > >P(
		N,
		make_pair(0,make_pair(0,0)),
		[](pair<long,pair<int,int> >A,pair<long,pair<int,int> >B)
		{
			return make_pair(A.first+B.first+(long)A.second.second*B.second.first,
				make_pair(
					A.second.first+B.second.first,
					A.second.second+B.second.second
				)
			);
		},
		[](pair<long,pair<int,int> >A,pair<long,pair<int,int> >B)
		{
			A.first^=B.first;
			return A;
		},
		[](pair<long,pair<int,int> >A,pair<long,pair<int,int> >B,int l,int r)
		{
			if(B.first==0)return A;
			else
			{
				return make_pair((long)(r-l)*(r-l-1)/2-A.first-(long)A.second.first*(A.second.first-1)/2-(long)A.second.second*(A.second.second-1)/2,
					make_pair(A.second.second,A.second.first)
				);
			}
		},
		make_pair(0,make_pair(0,0))
	);
	vector<pair<long,pair<int,int> > >init(N);
	for(int i=0;i<N;i++)
	{
		int t;cin>>t;
		if(t==0)init[i].second.first++;
		else init[i].second.second++;
	}
	P.copy(init);
	for(int i=0;i<Q;i++)
	{
		int t,l,r;cin>>t>>l>>r;
		l--;
		if(t==1)P.update(l,r,make_pair(1,make_pair(0,0)));
		else cout<<P.query(l,r).first<<endl;
	}
}


Measured memory_bytes: 22732
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

template<class T>
inline bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

bool used[200005];
bool usednumber[1000005];
bool ng[1000005];

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

    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i)  cin >> a[i];
    sort(a.begin(), a.end());
    a.emplace_back(a.back() + 1);
    int ans = 0;
    for(int i = 0; i < n; ++i){
        if(usednumber[a[i]])    continue;
        if(used[i]) continue;
        usednumber[a[i]] = true;
        if(!ng[a[i]]){
            if(*lower_bound(a.begin() + i + 1, a.end(), a[i]) != a[i])  ++ans;
        }
        for(int j = a[i] * 2; j < a[n]; j += a[i]){
            int p = lower_bound(a.begin() + i + 1, a.end(), j) - a.begin();
            if(a[p] == j){
                ng[j] = true;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 5924
#include <numeric>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <set>

using namespace std;

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

inline int getInt(){ int s; scanf("%d", &s); return s; }
inline double getDouble(){ double s; scanf("%lf", &s); return s; }

int main(){
  const int n = getInt();

  vector<double> p(n);

  REP(i,n) p[i] = getDouble();

  const double minimum = 0.01 / 100;

  double low  = -1e12;
  double high = 0;

  vector<double> pp(n);
  REP(i,128){
    const double med = (low + high) / 2.0;

    // 300 / pp * p = e
    // - 300 / (pp ^ 2) * p = de/dpp (= med)
    // - 300 / med * p = pp ^ 2
    // sqrt(-300 / med * p) = pp
    REP(i,n){
      const double tmp = sqrt(-300 / med * p[i]);
      if(tmp < minimum) pp[i] = minimum;
      else pp[i] = tmp;
    }

    const double sum = accumulate(pp.begin(), pp.end(), 0.0);
    if(sum > 0.03){
      high = med;
    }else{
      low = med;
    }
  }

  double ans = 0.0;
  REP(i,n){
    ans += 300 / pp[i] * p[i];
  }

  printf("%.8f\n", ans);

  return 0;
}

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

int gcd(int x,int y){
  if(y==0) return x;
  return gcd(y,x%y);
}

int main(){
  int n,k; cin>>n>>k;
  int a,maxnum; cin>>a;
  maxnum=a;
  for(int i=0;i<n-1;i++){
    int x; cin>>x;
    a=gcd(x,a);
    if(x>maxnum) maxnum=x;
  }
  if(k%a==0 && maxnum>=k){
    cout<<"POSSIBLE"<<endl;
  }else{
    cout<<"IMPOSSIBLE"<<endl;
  }
}

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

template<typename T>
using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

#define ll long long
#define __   ios_base::sync_with_stdio(0);cin.tie();cout.tie();
#define mod 1000000007

ll Set(ll N,ll pos){ return N=N | (1<<pos); }
ll reset(ll N,ll pos){ return N= N & ~(1<<pos); }
bool check(ll N,ll pos){ return (bool)(N & (1<<pos)); }


ll ar[]={0,0,1,-1};
ll br[]={1,-1,0,0};

string s;
ll n,m;
ll arr[500000];
ll brr[500000];

int main()
{__
        ll i,j,a,b;
        cin>>a>>b;
        cout<<a*b/(__gcd(a,b))<<endl;
}



Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<cstring>
#include<queue>
#include<stack>
using namespace std;
#define MOD 1000000007
#define INF (1<<29)
#define LINF (1LL<<60)
#define EPS (1e-10)
using ll = long long;
static const int MAX_N = 100000;

ll n;
vector<string> A;
int main(){
    cin >> n;
    for(ll i=0;i<n;i++){
        string s;
        cin >> s;
        sort(s.begin(),s.end());
        A.push_back(s);
    }
    sort(A.begin(),A.end());
    ll les=0;
    ll count=1;
    for(ll i=1;i<A.size();i++){
        if(A[i]!=A[i-1]){
            les+=count*(count-1ll)/2ll;
            count=1;
        }
        else count+=1;
    }
    les+=count*(count-1ll)/2ll;
    cout << les <<endl;
    return 0;
}

Measured memory_bytes: 5748
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main
{

	public static void main(String[] args) throws IOException
	{
		// TODO 自動生成されたメソッド・スタブ
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		int A = Integer.parseInt(str.substring(0, str.indexOf(" ")));
		int B = Integer.parseInt(str.substring(str.indexOf(" ") + 1,str.indexOf(" ", str.indexOf(" ") + 1)));
		int C = Integer.parseInt(str.substring(str.indexOf(" ", str.indexOf(" ") + 1) + 1,str.indexOf(" ", str.indexOf(" ", str.indexOf(" ") + 1) + 1)));
		int D = Integer.parseInt(str.substring(str.indexOf(" ", str.indexOf(" ", str.indexOf(" ") + 1) + 1) + 1));
		//System.out.println(A + " " + B + " " + C + " " + D);
		int E = 0;
		if(A < C) E = C;
		else E = A;
		int F = 0;
		if(B > D) F = D;
		else F = B;
		if(F - E < 0) System.out.println("0");
		else System.out.println(F - E);
	}

}


Measured memory_bytes: 21332
module Main where

import Control.Applicative
import Numeric

main :: IO ()
main = loop

loop :: IO ()
loop = do
  { [m, f, r] <- getInts
  ; if m == -1 && f == -1 && r == -1 then done
    else printGrade m f r 
  }

done :: IO ()
done = return  ()

printGrade :: Int -> Int -> Int -> IO ()
printGrade m f r = putStrLn (grade m f r) >> loop

grade :: Int -> Int -> Int -> String
grade m f r = if m == -1 || f == -1 then "F"
              else if mpf >= 80 then "A"
              else if mpf >= 65 then "B"
              else if mpf >= 50 then "C"
              else if mpf >= 30 then (if r >= 50 then "C" else "D")
              else "F"
   where
     mpf = m + f
--           

getInts :: IO [Int]
getInts = map read . words <$> getLine

putInts :: [Int] -> IO ()
putInts = putStrLn .  unwords . map show

getDoubles :: IO [Double]
getDoubles = map read . words <$> getLine

putDoubles :: [Double] -> IO ()
putDoubles = putStrLn . unwords . map showDouble

showDouble :: Double -> String
showDouble d = showFFloat Nothing d ""



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

int main(){
  int n;
  cin>>n;
  vector<int> a(n);
  bool flag = true;

  for(int i=0; i<n; i++){
    cin>>a[i];
    if(a[i] %  2 == 0){
      if(a[i] % 3 == 0 || a[i] % 5 == 0) continue;
      flag = false;
    }
  }

  if(flag) cout<<"APPROVED"<<endl;
  else cout<<"DENIED"<<endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+50;
typedef long long ll;
const ll INF = 1e18+50;
ll a[maxn];
ll b[maxn],c[maxn];
ll s1[maxn],s2[maxn];
int t1=0,t2=0;
int n,k;
ll minn=INF;
bool cmp(ll a,ll b)
{
    return a<b;
}
void solve()
{
    for(register int i=1;i<=n;i++)
    {
        int temp=i+k-1;
        ll mm;
        if(temp>n)
            break;
        if(a[i]*a[temp]<0)
        {
            mm=abs(a[i])+abs(a[temp]);
            ll tt=min(abs(a[i]),abs(a[temp]));
            mm+=tt;
        }
        else
        {
            mm=max(abs(a[temp]),abs(a[i]));
        }
        minn=min(minn,mm);
        //cout << minn << " " << mm << endl;
    }
    cout << minn << endl;
}
int main()
{
    scanf("%d %d",&n,&k);
    for(register int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        if(a[i]<=0)
        {
            b[++t1]=-a[i];
        }
        else
        {
            c[++t2]=a[i];
        }
    }
    sort(b+1,b+t1+1,cmp);
    sort(c+1,c+t2+1,cmp);
    sort(a+1,a+1+n,cmp);
    for(register int i=1;i<=t1;i++)
    {
        s1[i]=b[i];
    }
    for(register int j=1;j<=t2;j++)
    {
        s2[j]=c[j];
    }

    solve();
    for(register int i=0;i<=t1&&i<=k;i++)
    {
        ll mm;
        ll temp=k-i;
        if(i!=k&&temp<=t2)
        {
            ll t1=s1[i]*2+s2[temp];
            ll t2=s1[i]+s2[temp]*2;
            mm=min(t1,t2);
        }
        else if(i==k)
        {
            mm=s1[i];
        }
        //minn=min(minn,mm);
        //cout << minn << " " << mm <<endl;
    }
    //cout << minn << endl;

    //cout << minn << endl;
   // cout << "Hello world!" << endl;
    return 0;
}
/*
5 3
-30 -10 -5 20 50
*/


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

using namespace std;

int main(){
    int N,C,K,ans=0,t=1,i=1,c=1;
    cin >> N >> C >> K;
    vector<int> T(N);
    for(int i=0;i<N;i++){
        cin >> T[i];
    }

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

    t=T[0];
    ans++;

    while(i<N){
        if(K<T[i]-t || C==c){
            t=T[i];
            c=1;
            i++;
            ans++;
        }else{
            i++;
            c++;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define reprrev(i,a,b) for(int i=b-1;i>=a;i--) // [a, b)
#define reprev(i,n) reprrev(i,0,n)
typedef long long ll;
typedef unsigned long long ull;
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; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    cin.tie(0);
    ios::sync_with_stdio(false);<- これら、printfとかと併用しない方が良さそう

*/

const ll mod = 1e9+7;

void chmod(ll &M){
    if(M >= mod) M %= mod;
    else if(M < 0){
        M += (abs(M)/mod + 1)*mod;
        M %= mod;
    }
}

ll modpow(ll x, ll n){
    if(n==0) return 1;
    ll res=modpow(x, n/2);

    if(n%2==0) return res*res%mod;
    else return res*res%mod*x%mod;
}

int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };


// 線分 ab の偏角 返り値は[-π, π]
double argument(const pair<double, double> &a, const pair<double, double> &b){
    double ax=a.first, ay=a.second, bx=b.first, by=b.second;
    return atan2(by-ay, bx-ax);
}

/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */


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

    ll n, c; cin >> n >> c;
    vector<ll> x(n+2, 0), v(n+2, 0);
    repr(i, 1, n+1) cin >> x[i] >> v[i];
    x[n+1] = c;
    vector<ll> cumv(n+2, 0);
    repr(i, 1, n+2) cumv[i] = cumv[i-1] + v[i];

    vector<ll> fA(n+2, 0);
    repr(i, 1, n+1) fA[i] = max(fA[i-1], cumv[i]-x[i]);
    vector<ll> fA2(n+2, 0);
    repr(i, 1, n+1) fA2[i] = max(fA2[i-1], cumv[i]-2*x[i]);

    ll ans = 0;
    repr(b, 1, n+2) chmax(ans, cumv[n+1]-cumv[b-1] - 2*(x[n+1]-x[b]) + fA[b-1]);
    repr(b, 1, n+2) chmax(ans, cumv[n+1]-cumv[b-1] - (x[n+1]-x[b]) + fA2[b-1]);
    cout << ans << endl;

    return 0;
}

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

class BinaryIndexedTree
{
private:
    std::vector<int> vals;
    int n;
public:
    BinaryIndexedTree(int n_)
        : vals(n_, 0), n(n_) { }

    void add(int a, int w)
    {
        for (int x = a; x <= n; x += x & -x) {
            vals[x - 1] += w;
        }
    }

    int sum(int a) const
    {
        int ret = 0;
        for (int x = a; x > 0; x -= x & -x) {
            ret += vals[x - 1];
        }
        return ret;
    }
};

class SnLine
{
private:
    struct ProdRange
    {
        ProdRange() { l = r = 0; }
        ProdRange(int l_, int r_) { l = l_; r = r_; }
        int l, r;
    };

    static ProdRange makeProdRange(int l, int r)
    {
        return ProdRange { l, r };
    }

    std::vector<ProdRange> prList;

    int numProds;
    int numStops;

public:
    SnLine(int numStops_, int numProds_)
    {
        numStops = numStops_;
        numProds = numProds_;
        prList.reserve(numProds);
    }

    void addProdRange(int l, int r)
    {
        prList.emplace_back(l, r);
    }

    void solve()
    {
        std::sort(prList.begin(), prList.end(),
            [](const auto& a, const auto& b)
            { return ((a.r - a.l) < (b.r - b.l)); });

        BinaryIndexedTree bit(numStops);
        
        int numRemainingProds = numProds;

        auto pr = prList.begin();
        for (int d = 1; d <= numStops; ++d)
        {
            int r = numRemainingProds;

            if (1 < d)
            {
                for (int a = d; a <= numStops; a += d)
                {
                    r += bit.sum(a);
                }
            }

            printf("%d\n", r);
            //std::cout << r << std::endl;

            for(; pr != prList.end() && (d == pr->r - pr->l + 1); ++pr)
            {
                bit.add(pr->l, 1);
                bit.add(pr->r + 1, -1);
                --numRemainingProds;
            }
        }
    }
};

int main()
{
    int N, M;
    scanf("%d%d", &N, &M);
    //std::cin >> N >> M;

    SnLine sl(M, N);

    for (int i = 0; i < N; ++i)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        //std::cin >> l >> r;

        sl.addProdRange(l, r);
    }

    sl.solve();
    return 0;
}


Measured memory_bytes: 3712
#include <iostream>
using namespace std;
int main(void){
    int n, m, e, j;
    while(cin >> n && n){
        for(int i = 0; i < n; i++){
            cin >> m >> e >> j;
            if(m==100 || e==100 || j ==100){
                cout << "A" << endl;
            }else if(m +e >= 180 ){
                cout << "A" << endl;
            }else if(m + e + j >= 240){
                cout << "A" << endl;
            }else if(m + e + j >= 210){
                cout << "B" << endl;
            }else if(m + e + j >= 150 && (m >=80 || e >= 80)){
                cout << "B" << endl;
            }else{
                cout << "C" << endl;
            }
        }
    }
}


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
int main () {
  long N;
  cin >> N;
  long ans = 0;
  for(int i = 1; i <= N; i++){
    if(i % 3 != 0 && i % 5 != 0)ans += i;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,x) for(int i=0;i<x;i++)
#define put(ans)    cout << ans << endl;
#define reverse(s) reverse(s.begin(),s.end())

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

Measured memory_bytes: 3644
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    n, k = map(int, readline().split())

    COM_MAX = n

    fac, finv, inv = [0] * (COM_MAX + 1), [0] * (COM_MAX + 1), [0] * (COM_MAX + 1)
    fac[0] = fac[1] = finv[0] = finv[1] = inv[1] = 1

    for i in range(2, COM_MAX + 1):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    def com(n, r):
        if n < 0 or r < 0 or n < r:
            return 0
        return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD

    ans = 0
    for r in range(min(n, k + 1)):
        ans = (ans + com(n, r) * com(n - 1, r)) % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 32496
#include<bits/stdc++.h>
using namespace std;
map<string,int>a;
string s[200005],s1[200005];
int maxn,numb;
int n,k;
int main()
{
    
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        a[s[i]]++;
        if(a[s[i]]>=maxn)
        {
            if(a[s[i]]==maxn)
            {
                s1[++numb]=s[i];
            }
            else
            {
                s1[1]=s[i];
                numb=1;
                maxn=a[s[i]];
            }
        }
    }
    sort(s1+1,s1+numb+1);
    for(int i=1;i<=numb;i++)
    {
            k=s1[i].size();
            for(int w=0;w<k;w++)printf("%c",s1[i][w]);
            puts("");
    }
    return 0;
}


Measured memory_bytes: 37760
#include <bits/stdc++.h>
using namespace std;
#define rep(shoki,i,n) for(int i= shoki; i<n; i++)
#define _GLIBCXX_DEBUG
int n;
int a1,a2;
int main(){
    cin>>n>>a1>>a2;
    int a_min = min(a1,a2);
    int a_max = max(a1,a2);
    int atemp;
    rep(2,i,n){
        cin>>atemp;
        if(atemp>a_max) a_max = atemp;
        if(atemp<a_min) a_min = atemp;
    }
    cout << a_max - a_min << endl;
}

Measured memory_bytes: 256
#include <sstream>
#include <string>
#include<iostream>
using namespace std;
int main()
{
 char c;
  int i;
 //cout << "Enter a character: ";
 cin >> c;
 i=int(c)+1;
 char e = static_cast<char>(i);


  cout<<e;
 return 0;
}

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

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
#define all(v) (v).begin(), (v).end()
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

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

	int N, M;
	cin >> N >> M;
	pair<int, int> m[M];
	rep(i, 0, M) {
		int a, b;
		cin >> a >> b;
		m[i] = make_pair(b, a);
	}

	sort(m, m + M);

	int right = m[0].first;
	int rsl = 1;
	rep(i, 1, M) {
		if(m[i].second >= right) {
			rsl++;
			right = m[i].first;
		}
	}

	cout << rsl << endl;

}


Measured memory_bytes: 1024
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <string>
#define ll long long
using namespace std;
const int maxn=1e5+10;

int a[maxn], b[maxn], c[maxn];
string s;

int main() {
    //freopen("a.out", "w", stdout);
    ll n;
    while(cin >> n && n) {
        int sum=0;
        for(int i=1;i<=n;++i) cin>>a[i],sum+=a[i];
        sum/=n;
        int res=0;
        for(int i=1;i<=n;++i) if(a[i]<=sum) res++;
        cout<<res<<'\n';
    }
}


/*
100 1100101


*/


Measured memory_bytes: 3180
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static int maxWays(int[] cap, int K){
        int[] state = new int[K+1];
        state[0] = 1;
        for (int children = 0; children < cap.length; children++) {
            int[] prefix = new int[K+1];
            for (int candies = K; candies >= 0; candies--) {
            //for (int candies = 0; candies <= K; candies++) { // gives different calculation
                int up_to = Math.min(cap[children], K - candies);
                int L = candies+1;
                int R = candies + up_to;
                if (L <= R) {
                    prefix[L] = add_self(prefix[L], state[candies]);
                    if (R + 1 <= K) {
                        prefix[R + 1] = sub_self(prefix[R + 1], state[candies]);
                    }
                }
            }
            int prefix_sum = 0;
            for (int i = 0; i <= K; i++) {
                prefix_sum = add_self(prefix_sum,prefix[i]);
                state[i] = add_self(state[i], prefix_sum);
            }
        }

        return state[K];
    }

    private static int add_self(int a, int b){
        int sum = a+b;
        if (sum >= mod){
            sum -= mod;
        }
        return sum;
    }

    private static int sub_self(int a, int b){
        int sum = a-b;
        if (sum < 0){
            sum += mod;
        }
        return sum;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(reader.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[] a = new int[N];
        st = new StringTokenizer(reader.readLine());
        for (int i = 0; i < N; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        System.out.println(maxWays(a, K));
    }

    private static int mod = (int) (1e9+7);
}


Measured memory_bytes: 46548