akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>

using namespace std;

typedef pair<int,int> pii;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;cin>>n;

    int x=n/1000;
    char ans='C'+x;

    cout<<"AB"<<ans<<"\n";

    return 0;
}


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

template<typename T> T GCD(T x, T y){
    if(x < y)swap(x, y);
    if(y == 0)return x;
    return GCD(x % y, y);
}

int main()
{
  int n; cin >> n;
  ll ans = 0;
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
      for(int k = 1; k <= n; k++){
        int t = GCD(GCD(i, j), k);
        ans += t;
      }
    }
  }
  cout << ans << endl;
  system("pause");
}


Measured memory_bytes: 3696
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		int C = sc.nextInt();
		
		int[] map = new int[M];
		for (int i = 0; i < M; i++) {
			map[i] = sc.nextInt();
		}
		
		int ans = 0;
		for (int i = 0; i < N; i++) {
			int sum = 0;
			for (int j = 0; j < M; j++) {
				int a = sc.nextInt();
				sum += a*map[j];
			}
			
			if (sum + C > 0) {
				ans++;
			}
		}
		
		System.out.println(ans);
	}
}


Measured memory_bytes: 23892
#include <stdio.h>
#define MAX 44

/* Prototype Declaration */
int fibonacci(int);

/* Global Variable */
int F[MAX];

int main() {
  int i, n;

  scanf("%d", &n);

  //Initialize F
  for (i = 0; i <= n; i++ )
    F[i] = -1; 

  printf("%d\n", fibonacci(n));

  return 0;
}

/* Find The Fibonacci Sequence of The n th Term */
int fibonacci(int n) {
  if ( n == 0 || n == 1 ) return F[n] = 1;

  if ( F[n] != -1 ) return F[n];

  return F[n] = fibonacci(n-1) + fibonacci(n-2);
}

Measured memory_bytes: 596
<?php
# 標準出力
fscanf(STDIN, "%d",$S);
# 配列に変換
$tmp = str_split($S);
# 結果
$result = "Good";
# 一つずつ判定
for ($i = 0; $i <= 2; $i ++){
	
	if ($tmp[$i] == $tmp[$i + 1]){
		
		$result = "Bad";
		break;
	}
}
echo $result;
?>

Measured memory_bytes: 3576
#include <iostream>

int digit(int x){
  return 100 * x + 10 * x + x;
}

int main(){
  int n;
  std::cin>>n;

  int a = n / 100;
  int b = (n - 100 * a) / 10;
  int c = n - 100 * a - 10 * b;

  int x = digit(a);
  int y = digit(a + 1);
  std::cout<<(n<=x ?x:y)<<std::endl;
  return 0;
}

Measured memory_bytes: 764
from heapq import heappush, heappop
def solve():
    N = int(input())
    M = int(input())
    G = [[] for i in range(N)]
    for i in range(M):
        a, b, c, d = map(int, input().split(","))
        G[a-1].append((b-1, c))
        G[b-1].append((a-1, d))
    s, g, V, P = map(int, input().split(","))
    INF = 10**18
    def calc(s, g):
        dist = [INF]*N
        dist[s] = 0
        que = [(0, s)]
        while que:
            cost, v = heappop(que)
            if dist[v] < cost:
                continue
            for w, d in G[v]:
                if cost + d < dist[w]:
                    dist[w] = cost + d
                    heappush(que, (cost + d, w))
        return dist[g]
    s -= 1; g -= 1
    print(max(0, V - (calc(s, g) + calc(g, s)) - P))
solve()



Measured memory_bytes: 5664
#include <iostream>

using namespace std;

int main() 
{
    int x, h, m, s;
    cin >> x;

    h = x / 3600;
    m = (x % 3600) / 60;
    s = (x % 3600) % 60;

    cout << h << ':' << m << ':' << s << '\n'; 

    return 0; 

}


Measured memory_bytes: 3088
#include <bits/stdc++.h>
#include <algorithm>
#include <map>
#include <cstdlib>
#include <cmath>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
int main(){
    ll n,k;
    cin >> n >> k;
    ll ans=n;
    if(n>k){
        n=n%k;
        ans=n;
        while(n>=0){
            n=n-k;
            if(abs(n)<ans) ans=abs(n);
        }
    }else{
        if(k-n<ans) ans=k-n;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rap(i,first,last) for(int i=first;i<=last;++i)
using namespace std;
const int maxN=2005;
const int mod=1e9+7;
const int inv2=500000004;
long long fac[maxN*4+100],inv[maxN*4+100];
long long dp[maxN*2+100][maxN*2+100],N;
int A[1000005],B[1000005];
long long C(int n,int m)
{
	return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main()
{
	fac[0]=inv[0]=inv[1]=1;
	rap(i,1,maxN*4)fac[i]=1ll*fac[i-1]*i%mod;
	rap(i,2,maxN*4)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	rap(i,1,maxN*4)inv[i]=1ll*inv[i-1]*inv[i]%mod;
	scanf("%d",&N);
	rap(i,1,N)
	{
		scanf("%d%d",&A[i],&B[i]);
		dp[maxN-A[i]][maxN-B[i]]++;
	}
	rap(i,-maxN+1,maxN)
	rap(j,-maxN+1,maxN)
	{
		dp[maxN+i][maxN+j]+=dp[maxN+i-1][maxN+j]+dp[maxN+i][maxN+j-1];
		dp[maxN+i][maxN+j]%=mod;
	}
	long long answer=0;
	rap(i,1,N)
	{
		answer+=dp[maxN+A[i]][maxN+B[i]];
		answer%=mod;
		answer-=C(A[i]*2+B[i]*2,A[i]*2);
		answer=(answer+mod)%mod;
	}
	answer*=inv2;
	answer%=mod;
	printf("%lld\n",answer);
}

Measured memory_bytes: 136320
s=list(input())
t=list(input())
# print(s,t)

m=0
for i in range(len(s)-len(t)+1):
    c=0
    for j in range(len(t)):
        if s[i+j]==t[j]:
            c+=1
    m=max(m,c)

print(len(t)-m)

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

int main(){
  long long ans,n,array[200000],snuke,kuma=0;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>array[i];
    if(i){
      kuma+=array[i];
    }
  }
  snuke=array[0];
  ans=abs(snuke-kuma);
  for(int i=1;i<n-1;i++){
    snuke+=array[i];
    kuma-=array[i];
    ans=min(ans,abs(snuke-kuma));
  }
  cout<<ans<<endl;
}
    

Measured memory_bytes: 1792
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        int k = 0;
        char[] c = Integer.toString(n).toCharArray();
        for(char t : c) {
        	k += t - '0';
        }
        if(n % k > 0) {
        	System.out.println("No");
        }else {
        	System.out.println("Yes");
        }
    }
}

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

int grid[3][3];
int bingo[3][3] = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}};
int n, a;

int main()
{
    ios_base::sync_with_stdio(false);
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            cin >> a;
            grid[i][j] = a;
        }
    }
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a;
        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                if (a == grid[i][j])
                {
                    bingo[i][j] = 1;
                }
            }
        }
    }

    //check
    for (int i = 0; i < 3; i++)
    {
        if (bingo[i][0] == 1 && bingo[i][1] == 1 && bingo[i][2] == 1)
        {
            cout << "Yes";
            return 0;
        }
        if (bingo[0][i] == 1 && bingo[1][i] == 1 && bingo[2][i] == 1)
        {
            cout << "Yes";
            return 0;
        }
        if (bingo[0][i] == 1 && bingo[1][i] == 1 && bingo[2][i] == 1)
        {
            cout << "Yes";
            return 0;
        }
    }

    if (bingo[0][0] == 1 && bingo[1][1] == 1 && bingo[2][2] == 1)
    {
        cout << "Yes";
        return 0;
    }

    if (bingo[0][2] == 1 && bingo[1][1] == 1 && bingo[2][0] == 1)
    {
        cout << "Yes";
        return 0;
    }

    cout << "No";
    cin >> n;
    return 0;
}

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    // N : num of member
    // K : init point
    // Q : num of round
    li N, K, Q;
    cin >> N >> K >> Q;
    li *points = new li[N];

    int idx = 0;
    for (int i = 0; i < Q; i++) {
        cin >> idx;
        points[idx - 1]++;
    }

    for (int i = 0; i < N; i++) {
        if(points[i] + K - Q >= 1) {
            cout << "Yes" << endl;
        } else {
            cout << "No"  << endl;
        }
    }
}


Measured memory_bytes: 1408
# 累積和が見える
n = int(input())
a = list(map(int, input().split()))
ruiseki = [0 for _ in range(n)]
ruiseki[0] = a[0]
for i in range(1, n):
  ruiseki[i] = ruiseki[i-1] + a[i]

ans = 10 ** 16
for i in range(n-1):
  ans = min(ans, abs(ruiseki[-1] - ruiseki[i]*2))
  
print(ans)


Measured memory_bytes: 24800
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>

#define _GLIBCXX_DEBUG
using namespace std;
using vi = vector<int64_t>;
using vvi = vector<vi>;

int main(int argc, const char * argv[]) {
    // fasten cin
    cin.tie(0);
    ios::sync_with_stdio(false);
    // implement
    int64_t n,m,amount=0,cost=0,a,b;
    cin >> n >> m;
    vector<pair<int64_t, int64_t>> p(n);
    for(int i=0; i<n; i++){
        cin >> a >> b;
        p.at(i) = make_pair(a, b);
    }
    sort(p.begin(), p.end());
    for(int i=0; i<n; i++){
        if(m >= p.at(i).second + amount){
            amount += p.at(i).second;
            cost += p.at(i).first * p.at(i).second;
        }else{
            while(m>amount){
                cost += p.at(i).first;
                amount++;
            }
        }
    }
    cout << cost << endl;
}


Measured memory_bytes: 1792
N,Y = map(int, input().split())

ans = [-1,-1,-1]
for x in range(N+1):
    for y in range(N+1):
        k = N-x-y
        if k>=0 and 10000*x+5000*y+1000*k==Y:
                ans[0] = x
                ans[1] = y
                ans[2] = k

print(ans[0],ans[1],ans[2])

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

struct Node{
    int   key;
    Node* prev;
    Node* next;
};

class List{
    Node* nil;
    void delete_node(Node* n){
        n->prev->next = n->next;
        n->next->prev = n->prev;
        delete n;
    }
public:
    List(){
        nil = new Node;
        nil->prev = nil;
        nil->next = nil;
    }
    void insert_key(int key){
        Node* n = new Node;
        n->key = key;
        nil->next->prev = n;
        n->next = nil->next;
        nil->next = n;
        n->prev = nil;
    }
    void delete_key(int key){
        for (Node* n = nil->next; n != nil; n = n->next) {
            if (n->key == key) {
                delete_node(n);
                return;
            }
        }
    }
    void print_all(){
        for (Node* n = nil->next; n != nil; n = n->next) {
            if (n != nil->next) cout << " ";
            cout << n->key;
        }
        cout << endl;
    }
    void deleteFirst(){
        delete_node(nil->next);
    }
    void deleteLast(){
        delete_node(nil->prev);
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    List l;
    for (int i = 0; i < n; i++) {
        string command;
        cin >> command;
        if (command == "deleteFirst") {
            l.deleteFirst();
            continue;
        }
        if (command == "deleteLast") {
            l.deleteLast();
            continue;
        }
        int key;
        cin >> key;
        if (command == "insert") {
            l.insert_key(key);
            continue;
        }
        if (command == "delete") {
            l.delete_key(key);
            continue;
        }
    }
    l.print_all();
    return 0;
}

Measured memory_bytes: 34328
#include <stdio.h>
int main()
{
    int x, number;
    char num;
    while (1)
    {
        x = 0;
        scanf("%c", &num);
        if (num != '0')
        {
            while (1)
            {
                number = num - '0';
                x += number;
                scanf("%c", &num);
                if (num == '\n')
                    break;
            }
            printf("%d\n", x);
        }
        else
        {
            break;
        }
    }
    return 0;
}



Measured memory_bytes: 2044
from collections import deque


def bfs(sx, sy, gx, gy):
    q = deque([(sx, sy)])
    cost[sx][sy] = 1
    while q:
        x, y = q.popleft()
        for dx, dy in nb:
            nx = x + dx
            ny = y + dy
            if 0 <= nx and nx < h and 0 <= ny and ny < w and grid[nx][ny] == "." and cost[nx][ny] == float("inf"):
                q.append((nx, ny))
                cost[nx][ny] = cost[x][y] + 1
                if nx == gx and ny == gy:
                    return cost[nx][ny]
    return -1


h, w = map(int, input().split())
grid = [list(input()) for _ in range(h)]
cost = [[float("inf")] * w for _ in range(h)]
nb = [(-1, 0), (0, -1), (1, 0), (0, 1)]
black_cnt = 0
ans = 0


for i in range(h):
    black_cnt += str(grid[i]).count("#")

can_reach = bfs(0, 0, h - 1, w - 1)

if can_reach > 0:
    print(h * w - can_reach - black_cnt)
else:
    print(can_reach)

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

int main()
{
    int A, B, X;

    cin >> A >> B >> X;

    if(X > A+B)
        cout << "NO" << endl;
    
    else if(A > X)
        cout << "NO" << endl;

    else   
        cout << "YES" << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#define P pair<int, int>

using namespace std;

int main(){
  int n, m, q, c[100009];
  vector<int> G[100009];
  queue<int> Q;
  memset(c, -1, sizeof(c));
  cin >> n >> m;
  for(int i=0;i<m;i++){
    int s, e;
    cin >> s >> e;
    G[s].push_back(e);
    G[e].push_back(s);
  }
  for(int i=0;i<n;i++){
    if(c[i]!=-1)continue;
    c[i] = i;
    Q.push(i);
    while(!Q.empty()){
      int node = Q.front();Q.pop();
      for(int j=0;j<G[node].size();j++){
        if(c[G[node][j]]==-1){
          c[G[node][j]] = i;
          Q.push(G[node][j]);
        }
      }
    }
  }
  cin >> q;
  for(int i=0;i<q;i++){
    int s, e;cin >> s >> e;
    cout << (c[s] == c[e]? "yes": "no") << endl;
  }
}


Measured memory_bytes: 8992
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#include <iostream>

class TaskA {
public:
	void solve(std::istream& in, std::ostream& out) {
		int n, a; in>>n>>a;
		out<<(n*n)-a;
	}
};


int main() {
	TaskA solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 256
from math import floor

t1, t2 = map(int, input().split())
a1, a2 = map(int, input().split())
b1, b2 = map(int, input().split())

diff1 = (a1 - b1) * t1
diff2 = (a2 - b2) * t2
diff = diff1 + diff2

if diff1 * diff > 0:
    print("0")

elif diff == 0:
    print("infinity")

else:
    diff1 = abs(diff1)
    diff2 = abs(diff2)
    n = diff2 / (diff2 - diff1)

    if n == floor(n):
        n = floor(n)
        ans = 2 * n - 2
    else:
        n = floor(n)
        ans = 2 * n - 1

    print(ans)



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

using namespace std;

typedef long long  ll;

struct P {
    double x, y;
    P() { x = 0.0, y = 0.0; }
    P(double x, double y) : x(x), y(y) {}
};
P operator+(const P &p1, const P &p2) {
    return P(p1.x + p2.x, p1.y + p2.y);
}
P operator-(const P &p1, const P &p2) {
    return P(p1.x - p2.x, p1.y - p2.y);
}
P operator*(double k, const P &p) {
    return P(k * p.x, k * p.y);
}
P operator*(const P &p, double k) {
    return k * p;
}

//       p5
//       /\
// p1___/ \___p2
//    p3  p4
void KochCurve(P p1, P p2, int n)
{
    if (n == 0)
        return ;

    P p3 = 1.0 / 3.0 * (p2 - p1) + p1;
    P p4 = 2.0 / 3.0 * (p2 - p1) + p1;
    P tmp = p4 - p3;
    P p5;

    double theta = M_PI / 3.0;
    p5.x = cos(theta) * tmp.x - sin(theta) * tmp.y + p3.x;
    p5.y = sin(theta) * tmp.x + cos(theta) * tmp.y + p3.y;

    KochCurve(p1, p3, n - 1);
    printf("%.8f %.8f\n", p3.x, p3.y);
    KochCurve(p3, p5, n - 1);
    printf("%.8f %.8f\n", p5.x, p5.y);
    KochCurve(p5, p4, n - 1);
    printf("%.8f %.8f\n", p4.x, p4.y);
    KochCurve(p4, p2, n - 1);
}

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

    int n;
    cin >> n;

    printf("%.8f %.8f\n", 0.0, 0.0);
    KochCurve(P(0.0, 0.0), P(100.0, 0), n);
    printf("%.8f %.8f\n", 100.0, 0.0);

    return 0;
}

Measured memory_bytes: 1224
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner reader = new Scanner(System.in);
		int N = reader.nextInt();
		int Y = reader.nextInt();
		int max = Y / 10000;
		int[] ans = new int[3];

		for (int i = max; i >= 0; i--) {
			ans[0] = i;
			ans[2] = (5000 * (N - ans[0]) - (Y - ans[0] * 10000)) / 4000;
			ans[1] = N - ans[0] - ans[2];
			if (ans[0] * 10000 + ans[1] * 5000 + ans[2] * 1000 == Y && ans[0] >= 0 && ans[1] >= 0 && ans[2] >= 0) {
				System.out.print(ans[0] + " " + ans[1] + " " + ans[2]);
				return;
			}
		}

		System.out.print("-1 -1 -1");
		reader.close();
	}
}


Measured memory_bytes: 23252
N, M = gets.split.map(&:to_i)
a = (1..M).map { gets.to_i - 1} # 0-indexed

NOT_YET = -1
MOD = 1000000007

if N == 1 then
  puts 1
  exit
end

ways = Array.new(N, NOT_YET)
a.each { |hole| ways[hole] = 0 }

if ways[0] == NOT_YET then ways[0] = 1 end
if ways[1] == NOT_YET then ways[1] = 1 + ways[0] end

(2...N).each { |x| ways[x] = (ways[x - 1] + ways[x - 2]) % MOD if ways[x] == NOT_YET }

puts ways.last


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

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    sort(a.begin(), a.end());
    ll cnt = 1;
    rep(i, n - 1){
        if (a[i] != a[i + 1]) cnt ++;
    }
    
    if (cnt % 2 != 0) cout << cnt << endl;
    else cout << cnt - 1 << endl;
}

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

int N, M;
vector<int>memo;
int dfs(bitset<20>&used,const vector<vector<int>>&sums,const vector<int>&nums,const int now) {
	if (memo[used.to_ulong()] != -1)return  memo[used.to_ulong()];
	if (used.count() == M)return memo[used.to_ulong()]=0;
	int ans = 0;
	for (int i = 0; i < M; ++i) {
		if (!used[i]) {
			used[i] = true;
			ans = max(ans,sums[i][now + nums[i]] - sums[i][now] + dfs(used, sums, nums, now + nums[i]));
			used[i] = false;
		}
	}
	return memo[used.to_ulong()] = ans;
}

int main() {
	cin >> N >> M;
	memo = vector<int>(1 << M,-1);
	vector<int>vs(N);
	vector<int>nums(M);
	vector<vector<int>>sums(M, vector<int>(N + 1));
	for (int i = 0; i < N; ++i) {
		cin >> vs[i]; vs[i]--;
		nums[vs[i]]++;
		for (int j = 0; j < M; ++j) {
			if (j == vs[i]) {
				sums[j][i + 1] = sums[j][i] + 1;
			}
			else {

				sums[j][i + 1] = sums[j][i];
			}
		}
	}
	bitset<20>bs;
	int ans = dfs(bs, sums, nums,0);
	cout << N - ans << endl;

	return 0;
}

Measured memory_bytes: 15364
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define PI 3.14159265359
#define INF 1000100100
#define all(x) (x).begin(),(x).end()
typedef long long ll;
#define P pair<int, int>
using namespace std;
ll dp[3005][6005];
 
int main(){
    int n,t; cin >> n >> t;
    rep(i,6005) dp[0][i]=0;
    vector<P> cui(n);
    rep(i,n) cin >> cui[i].first >> cui[i].second;
    sort(all(cui));

    rep(i,n){
        int a=cui[i].first;
        int b=cui[i].second;
        for(int j=6004; j>=0; j--){
            if(j<a) dp[i+1][j]=dp[i][j];
            else if(j-a>=t) dp[i+1][j]=dp[i][j];
            else dp[i+1][j]=max(dp[i][j],dp[i][j-a]+b);
        }
    }
    ll ans=0;
    rep(i,6005) ans=max(dp[n][i],ans);
    cout << ans << endl;
return 0;
}

Measured memory_bytes: 141056
import heapq
wl = []
rl = []
n = int(input())
c = input()
for i in range(n):
    if c[i] == "W":
        heapq.heappush(wl,i)
    else:
        heapq.heappush(rl,-i)
cnt = 0
# print(wl,rl)
if wl == [] or rl == []:
    print(0)
else:
    while wl[0] < -rl[0]:
        cnt += 1
        heapq.heappop(rl)
        heapq.heappop(wl)
        if wl == [] or rl == []:
            print(cnt)
            exit()
    print(cnt)

Measured memory_bytes: 17480
#include<stdio.h>

int main(void){
  int n,k,i,s=0,m;

  scanf("%d %d",&n,&k);

  for(i=0;i<n;i++){
    scanf("%d",&m);
    if(m<k-m) s+=2*m;
    else s+=2*(k-m);
  }

  printf("%d\n",s);

  return 0;
}

  


Measured memory_bytes: 128
#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    char s[5][5],ss[5][5];
    for (int i=1;i<=2;i++)
        for (int j=1;j<=3;j++)
            {cin>>s[i][j];ss[3-i][4-j]=s[i][j];}
    for (int i=1;i<=2;i++)
        for (int j=1;j<=3;j++)
            if (s[i][j]!=ss[i][j]) {printf("NO");return 0;}
    printf("YES");


    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <vector>
#include <cstdlib> 
#include <cmath>
#include <algorithm>
#include <sstream>
#include <string>
using namespace std;

int main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	
	int x = min({a, b});
	int y = min({c, d});
	cout << x + y << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

int WA[100001];
int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);


	int N = getint(), M = getint();

	rep(i, M) {
		int p = 0;
		char c;
		if (ci - cn + 16 > cm) {
			while ((ct = getcha()) >= '0') p = p * 10 + ct - '0';
			c = getcha();
			getcha();
			getcha();
		}
		else {
			while ((ct = *ci++) >= '0') p = p * 10 + ct - '0';
			c = *ci;
			ci += 3;
		}

		if (WA[p] >= 0) {
			if (c == 'A') WA[p] = -WA[p] - 1;
			else WA[p]++;
		}
	}

	int kotae1 = 0;
	int kotae2 = 0;
	rep1(i, N) {
		if (WA[i] < 0) {
			kotae1++;
			kotae2 -= WA[i];
		}
	}
	printf("%d %d\n", kotae1, kotae2 - kotae1);

	Would you please return 0;
}

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
typedef pair<int,int> pii;
typedef pair<long long, int> pli;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

ll mod = 1000000007;

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

ll inv(ll x){
  ll res = 1;
  ll k = mod - 2;
  ll y = x;
  while(k){
    if(k&1)res = (res*y)%mod;
    y = (y*y) % mod;
    k /= 2;
  }
  return res;
}


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

  string s,t;
  cin >> s >> t;
  int ret = 0;
  rep(i,s.length()){
    if(s[i] != t[i])ret++;
  }
  cout << ret << endl;
}

Measured memory_bytes: 3792
#include<iostream>
using namespace std;
int c[4] = { 10,50,100,500 };

int main() {
	bool flag = true;
	while (true) {
		int count, a[5], b[5], t = 0;
		cin >> count;
		if (!count)break;
		cin >> a[0] >>  a[1] >> a[2] >> a[3];
		for (int i = 0; i < 4; i++) {
			t += a[i] * c[i];
		}
		t -= count;
		for (int i = 3; i >= 0; i--) {
			b[i] = t / c[i];
			t -= b[i] * c[i];
		}
		if (flag)flag = false;
		else cout << endl;
		for (int i = 0; i < 4; i++) {
			
			if (a[i] > b[i]) cout << c[i] << " " << a[i]-b[i] << endl;
		}
	}
}

Measured memory_bytes: 1160
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <utility>
#include <iostream>
#include <algorithm>
#include <functional>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define ll long long
#define ull unsigned long long
#define INF (1 << 30)
#define LLINF (1LL << 62)
#define MOD7 1000000007
#define MOD9 1000000009
#define eps 1e-9
#define P pair<int, int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pul pair<ull, ull>
#define all(a) (a).begin(), (a).end()
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);--i)
#define REP(i,n) for (int i=0;i<(n);++i)
#define RREP(i,n) for (int i=(n)-1;i>=0;--i)

void YES() { cout << "YES\n"; }
void NO() { cout << "NO\n"; }
void Yes() { cout << "Yes\n"; }
void No() { cout << "No\n"; }
void yes() { cout << "yes" << endl; }
void no() { cout << "no" << endl; }

int n, k, ans = INF;
bool num[10];

void dfs(int sum) {
	if (sum >= n) {
		ans = min(ans, sum);
		return;
	}

	for (int i = 0; i < 10; ++i) {
		if (num[i] || (sum == 0 && i == 0))
			continue;
		dfs(sum * 10 + i);
	}
}

int main() {
	cin >> n >> k;
	int t;
	for (int i = 0; i < k; ++i) {
		cin >> t;
		num[t] = true;
	}

	dfs(0);

	cout << ans << endl;

	return 0;
}

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

using namespace std;

#define fst first
#define scd second
#define PB push_back
#define MP make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define omajinai ios::sync_with_stdio(false);cin.tie(0)
#define rep(i,x) for(int i=0;i<(int)(x);++i)
#define rep1(i,x) for(int i=1;i<=(int)(x);++i)

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

template<typename T>T& max(T&a,T&b){if(a>=b)return a;return b;}
template<typename T>T& min(T&a,T&b){if(a<b)return a;return b;}
template<typename T>bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<typename T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<typename T>T get(){T a;cin>>a;return a;}
template<typename T>T rev(T a){reverse(all(a));return a;}
template<typename T>vector<T>&sort(vector<T>&a){sort(all(a));return a;}

const int inf = 1e9;
const ll linf = 3e18;
const double eps = 1e-9;

int nails[5005][5005];

signed main()
{
    int N, M; cin >> N >> M;

    rep(i, M) {
        int A, B, X; cin >> A >> B >> X;

        nails[A - 1][B - 1]++;
        nails[A - 1][B]--;
        nails[A + X][B - 1]--;
        nails[A + X][B + X + 1]++;
        nails[A + X + 1][B]++;
        nails[A + X + 1][B + X + 1]--;
    }

    rep(i, N + 2) {
        rep(j, N + 2) {
            nails[i][j + 1] += nails[i][j];
        }
    }

    rep(i, N + 2) {
        rep(j, N + 2) {
            nails[j + 1][i] += nails[j][i];
        }
    }

    rep(i, N + 2) {
        int y = i + 1;
        int x = 1;

        while (y <= N && x <= N) {
            nails[y][x] += nails[y - 1][x - 1];
            y++;
            x++;
        }
    }

    int ans = 0;

    rep(i, N + 2) {
        rep(j, N + 2) {
            ans += nails[i][j] > 0;
        }
    }

    cout << ans << endl;
}

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

int main () {
  int A, B;
  cin >> A >> B;
  long long ans = 0;
  
  for (long long i = 1; i <= B+1; i++){
    if ((A*i)%B == 0) {
      ans = A*i;
      break;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
H = gets.to_i
k = (0...50).find{ |i| (H >> i) == 1 }
hs = Array.new(k+1, 0)
hs[-1] = 1
t = 0
(0...hs.size).reverse_each{ |i|
  t += hs[i]
  if i > 0
    hs[i-1] += hs[i] * 2
  end
  hs[i] = 0
  #p [t, hs]
}
p t


Measured memory_bytes: 1788
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

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

    int ans = 0;

    // 分割位置をずらして、順番に調べていく
    for(int i = 1; i < n; i++)
    {
        int cnt = 0;

        // アルファベットが分割された両方に存在するか確認する
        for(char c = 'a'; c <= 'z'; c++)
        {
            bool left = false,right = false;

            // 分割された左側
            for(int j = 0; j < i; j++)
            {
                if( s[j] == c )
                {
                    left = true;
                }
            }

            // 分割された右側
            for(int j = i; j < n; j++)
            {
                if( s[j] == c )
                {
                    right = true;
                }
            }

            if( left && right )
            {
                cnt++;
            }
        }

        if( ans < cnt )
        {
            // 含まれる文字列の最大値を求める
            ans = cnt;
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int S, a, b;
  cin >> S;
  a = S/100;
  b = S%100;
  bool am = true;
  bool bm = true;
  if(a > 12 || a == 0){
    am = false;
  }
  if(b > 12 || b == 0){
    bm = false;
  }
  
  if(am && bm){
    cout << "AMBIGUOUS" << endl;
  }
  else if (am == true && bm == false){
    cout << "MMYY" << endl;
  }
  else if (bm == true && am == false){
    cout << "YYMM" << endl;
  }
  else {
    cout << "NA" << endl;
  }
  return 0;
}
    


Measured memory_bytes: 256
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
lint extgcd(lint a, lint b, lint &x, lint &y) {
  lint g = a; x = 1; y = 0;
  if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
  return g;
}
lint invMod(lint a, lint m) {
  lint x, y;
  if (extgcd(a, m, x, y) == 1) return (x + m) % m;return 0;
}
vector<lint> zyo,rz;
lint mo=1000000007;
lint co(int a,int b){
	if(a<0 || b<0 || a<b) return 0;
	return ((zyo[a]*rz[b]%mo)*rz[a-b])%mo;
}
vector<int> so;
bool used[100100];
int main()
{
	int n,m;cin>>n>>m;lint out=1;
	zyo.pb(1);
	rep(i,100100){
		zyo.pb((zyo[i]*(i+1))%mo);
	}
	rep(i,100100) rz.pb(invMod(zyo[i],mo));
	REP(i,2,100100){
		if(!used[i]) so.pb(i);
		for(int j=i+i;j<100100;j+=i) used[j]=true;
	}
	rep(i,so.size()){
		int t=0;
		while(m%so[i]==0){
			t++;m/=so[i];
		}
		if(t>0){
			out*=co(n+t-1,t);out%=mo;
		}
	}
	if(m>1){
		out*=co(n,1);out%=mo;
	}
	cout<<out<<endl;
}


Measured memory_bytes: 2548
// AOJ 1163: Cards
// 2017.9.15 bal4u@uu
// 2018.3.12

#include <stdio.h>
#include <string.h>

#define MAX 1004
short hi[MAX], to[MAX][MAX];
char  seen[MAX];
short match[MAX];

int bipartiteMatching(int m, int n)
{
	int u, max;
	int bpm(int u);

	memset(match, -1, (m+n) << 1);
	max = 0;
	for (u = 0; u < m; u++) {
		memset(seen, 0, m+n);
		if (bpm(u)) max++;
	}
	return max;
}

int bpm(int u)
{
	int i, v;

	for (i = 0; i < hi[u]; i++) {
		v = to[u][i];
		if (seen[v]) continue;
		seen[v] = 1;
		if (match[v] < 0 || bpm(match[v])) {
			match[u] = v, match[v] = u;
			return 1;
		}
	}
	return 0;
}
//#define getchar_unlocked()  getchar()
int in()
{
	int n = 0, c = getchar_unlocked();
	do n = 10*n + (c & 0xf), c = getchar_unlocked(); while (c >= '0');
	return n;
}

int gcd(int a, int b)
{
	int r;
if (!((a | b) & 1)) return 2;
	while (b != 0) r = a % b, a = b, b = r;
	return a;
}

int b[501], r[502];

int main()
{
	int i, j, m, n;

	while (m = in()) {
		n = in();
		for (i = 0; i < m; i++) b[i] = in();
		for (j = 0; j < n; j++) r[j] = in();

		memset(hi, 0, (m+n) << 2);
	    for (i = 0; i < m; i++) for (j = 0; j < n; j++) {
			if (gcd(b[i], r[j]) > 1) to[i][hi[i]++] = m + j;
		}			

		printf("%d\n", bipartiteMatching(m, n));
	}
	return 0;
}



Measured memory_bytes: 2672
//#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include <cmath>
#include <limits>
#include <unordered_map>  
using namespace std;

int main(void)
{
  int a,b;

  cin>>a>>b;

  if(a % 2 == 0 || b % 2 == 0)
  {
    cout<<"Even"<<endl;
    return 0;
  }
  else
  {
    cout<<"Odd"<<endl;
    return 0;
  }
  
}

Measured memory_bytes: 3612
#include <iostream>
#include <cstdint>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <algorithm>

int main(void)
{
    int64_t a, b;
    std::cin >> a >> b;

    b += (b%a == 0) ? a : -a;

    std::cout << b << std::endl;

    return 0;
}

Measured memory_bytes: 256
import math


class UnionFind:

    def __init__(self, N: int):
        # d[i] = <parent id> if i is a child,
        #       - <size of the group> if i is a root
        self.d = [-1 for _ in range(N)]

    def root(self, x: int) -> int:
        if self.d[x] < 0:
            return x
        self.d[x] = self.root(self.d[x])
        return self.d[x]

    def unite(self, x: int, y: int) -> bool:
        x, y = self.root(x), self.root(y)
        if x == y:
            return False
        if self.d[x] > self.d[y]:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(self, x: int, y: int) -> bool:
        return self.root(x) == self.root(y)

    def size(self, x: int):
        return -self.d[self.root(x)]

    def show(self):
        m = {}
        for n in range(len(self.d)):
            r = self.root(n)

            if r not in m:
                m[r] = [n]
            else:
                m[r].append(n)

        print("root -> childs")
        print("---------------------")
        for key in m:
            print("{} -> {}".format(key, m[key]))


class Solution:

    def solve(self, N: int, M: int, bridges):

        # solve
        uf = UnionFind(N+1)

        ans = N * (N-1) // 2
        answer = []

        for a, b in reversed(bridges):
            answer.append(ans)

            if not uf.same(a, b):
                ans -= uf.size(a) * uf.size(b)
                uf.unite(a, b)

        answer.reverse()

        return answer


if __name__ == '__main__':

    # standard input
    N, M = map(int, input().split())
    bridges = []
    for i in range(M):
        bridges.append(tuple(map(int, input().split())))

    # solve
    solution = Solution()
    sol = solution.solve(N, M, bridges)
    for s in sol:
        print(s)


Measured memory_bytes: 21744
/*input
4 3
-1 -2 -3 -4
*/

#include <bits/stdc++.h>
#include <unistd.h>

#define rep(i,j,n) for(i=j;i<n;i++)
#define repi(i,j,n) for(i=j;i>n;i--)
#define inf 1e18
#define M 1000000007
#define pie 3.141592653589793238
#define ll long long
#define ld long double
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define pb push_back
#define F first
#define S second
#define UQ(x) (x).resize(distance((x).begin(),unique(x.begin(),x.end())))

using namespace std;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rnd64(chrono::high_resolution_clock::now().time_since_epoch().count());

ll power(ll a,ll m,ll mod){
	ll ans=1;
	while(m){
		if(m%2){
			ans*=a;
			ans%=(mod);
		}
		a=(a*a)%(mod);
		m>>=1;
	}
	return ans;
}


void init(ll* a,ll n,ll val){
	for(ll i=0;i<n;i++)
		a[i]=val;
}

void solve(){
	ll i,j,_;
	ll k,m;
	cin>>m>>k;
	vll a;
	ll cz=0;
	rep(i,0,m){cin>>j;if(j)a.pb(j);else cz=1;}
	sort(a.rbegin(),a.rend(),[](ll &b,ll &c){
		return abs(c)>abs(b);
	});
	if((ll)a.size()<k){
		cout<<0<<endl;
		return;
	}
	vll n,p;
	rep(i,0,k){
		if(a[i]<0)n.pb(a[i]);
		else p.pb(a[i]);
	}
	if((((ll)n.size())%2)==0){
		ll ans=1;
		for(auto i : p)ans*=i,ans%=M;
		for(auto i : n)ans*=(-i),ans%=M;
		cout<<ans<<endl;
		return;
	}
	ll ap=0,an=0;
	rep(i,k,(ll)a.size()){
		if(a[i]>0){
			ap=a[i];
			break;
		}
	}
	rep(i,k,(ll)a.size()){
		if(a[i]<0){
			an=a[i];
			break;
		}
	}
	if((!ap&&!an) || (!ap&&(ll)p.size()==0)){
		if(cz){
			cout<<0<<endl;
			return;
		}
		ll ans=1;
		reverse(a.begin(),a.end());
		rep(i,0,k){ans*=a[i],ans%=M;}
		if(ans<0)ans+=M;
		cout<<ans<<endl;
		return;
	}
	if(p.size()==0 || abs(an)*abs(n[(ll)n.size()-1]) < ap*p[(ll)p.size()-1]){
		ll ans=1;
		rep(i,0,(ll)n.size()-1)ans*=n[i],ans%=M;
		for(auto i : p)ans*=i,ans%=M;
		ans*=ap;
		ans%=M;
		if(ans<0)ans+=M;
		cout<<ans<<endl;
	}else{
		ll ans=1;
		rep(i,0,(ll)p.size()-1)ans*=p[i],ans%=M;
		for(auto i : n)ans*=i,ans%=M;
		ans*=an;
		if(ans<0)ans+=M;
		ans%=M;
		cout<<ans<<endl;
	}
	

}

int main()
{
	ios::sync_with_stdio(0);
 	cin.tie(0);
	ll T=1;
	//cin>>T;
	while(T--){
		solve();
	}
	return 0;
}




Measured memory_bytes: 8160
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string.h>
#include <cstdio>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std; using ll = long long; using ld = long double;  using pll = pair<ll, ll>;
using vl = vector<ll>; using vll = vector<vl>; using vlll = vector<vll>; using vpll = vector<pll>;
using vs = vector<string>; using tll = tuple<ll, ll, ll>; using vtll = vector<tll>;
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; }
const ld PI = 3.1415926535897932;
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define co(i) cout << i << endl;
#define co2(i,j) cout << i << " " << j << endl;
#define co3(i) cout << i << " ";
#define po(i) cout << i.first << " " << i.second << endl;
void in() {}
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail>
void debug_out(Head h, Tail... t) {
	cerr << " " << h;
	if (sizeof...(t) > 0) cerr << " :";
	debug_out(t...);
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> vec) {
	for (size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
	return os;
}
ll ctoi(char c) {
	switch (c) {
	case '0': return 0; case '1': return 1; case '2': return 2;
	case '3': return 3; case '4': return 4; case '5': return 5;
	case '6': return 6; case '7': return 7; case '8': return 8;
	case '9': return 9;  default: return 0;
	}
}
bool pairCompare(const pll firstElof, pll secondElof)
{
	return firstElof.second < secondElof.second;
}
//AtCoder以外ではコメントアウトを忘れずに！
//#include <atcoder/all>
//using namespace atcoder;
//**Snippetリスト**//
//rep, vin, all, iteLoop, bitSearch, bitList, nod, LIS, digitDP, treeDP, Rerooting//
//gcdlcm, isPrime, eratos, primeFactorize, Npow, combination, divisor, modinv, doubling//
//dfs, bfs, dijkstra, WarshallFloyd, BellmanFord, UnionFind, Kruskal, RMQ, LCA, FordFulkerson//
ll i, j, k, l; ll N, M, K, H, W, X, Y, Z, R, Q, T;
ll MOD = 1000000007, INF = 1LL << 60, ans = 0, z = 0, o = 1;
vl flag, D; vll path; vs S;
//main内でCOMinit(N+1)を忘れずに！
vl fac, finv, inv;
void COMinit(ll N) {
	fac.resize(N);
	finv.resize(N);
	inv.resize(N);
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (ll i = 2; i < N; 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;
	}
}
ll COM(ll n, ll 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() {
	ll S;
	cin >> S;
	//項の数
	COMinit(100000);
	for (i = 1; i < 700; i++) {
		ll N = S - i * 3;
		if (N < 0) break;
		(ans += COM(N + i - 1, N)) %= MOD;
	}
	co(ans);
}


Measured memory_bytes: 5568
#include <iostream>
#include<algorithm>
#include<string>
#include <cmath>
#include <vector>
#include <map>
#include <cstdio>
#include <iomanip>
#include<set>
#include <numeric>
#pragma region Macros
#define int long long
#define double long double
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define REP(i,n) for(int i=1;i<=n;i++)
#define LAST(x) x[x.size()-1]
#define ALL(x) (x).begin(),(x).end()
#define swap(a,b) (a += b,b = a - b,a -= b)
#define DIVCEIL(a,b) ((a+b-1)/b)
//int CHMAX

int intpow(int a, int n) {
	// a^nのint ver
	rep(i, n - 1)
		a *= a;
	return a;
}
int MODPOW(int a, int n, int mod) {
	// a^n mod
	int ans = 1;
	while (n > 0) {
		if (n & 1)
			ans = ans * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return ans;
}
int FACT(int a) {
	if (a == 0)
		return 1;
	else
		return a * FACT(a - 1);
}
int MODFACT(int a, int mod) {
	if (a == 0)
		return 1;
	else
		return (a * FACT(a - 1)) % mod;
}
int nPr(int n, int r) {
	int s = n - r + 1;
	int sum = 1;
	for (int i = s; i <= n; i++)
		sum *= i;
	return sum;
}
int MODnPr(int n, int r, int mod) {
	int s = n - r + 1;
	int sum = 1;
	for (int i = s; i <= n; i++) {
		sum *= i;
		sum = sum % MOD;
	}
	return sum;
}
//int nCr(int n, int r)
int nCr2(int n, int r) {
	return FACT(n) / (FACT(r) * FACT(n - r));
}
int GCD(int a, int b)
{
	if (a < b)
		swap(a, b);
	if (b == 0)
		return a;
	if (a % b == 0)
		return b;
	return GCD(b, a % b);
}
int LCM(int a, int b)
{
	return  a * b / GCD(a, b);
}
int NUMOFDIV(int n) {
	//約数の数（だっけ？）
	int ans = 0;
	REP(i, n) {
		if (n % i == 0)
			ans++;
	}
	return ans;
}
int CEIL1(int n) {
	//1桁目切り上げ
	return (n + 9) / 10 * 10;
}
int DIGIT(int n, int k) {
	//nのk桁目
	rep(i, k - 1)
		n /= 10;
	return n % 10;
}
int DIGITSUM(int n) {
	int sum = 0, dig;
	while (n) {
		dig = n % 10;
		sum += dig;
		n /= 10;
	}
	return sum;
}
int DIVTIME(int n, int k) {
	//nをkで何回割れるか的な
	int div = 0;
	while (n % k == 0) {
		div++;
		n /= k;
	}
	return div;
}
int binary(int n) {
	//10進数→2進数
	int ans = 0;
	for (int i = 0; n > 0; i++) {
		ans += n % 2 * intpow(10, i);
		n /= 2;
	}
	return ans;
}
double LOG(int a, int b) {
	return log(b) / log(a);
}
inline bool BETWEEN(int x, int min, int max) {
	if (min <= x && x <= max)
		return true;
	else
		return false;
}
inline bool between(int x, int min, int max) {
	if (min < x && x < max)
		return true;
	else
		return false;
}
inline bool PRIMEOR(int x) {
	if (x == 1)
		return false;
	if (x == 2)
		return true;
	if (x % 2 == 0)
		return false;
	double sqrtx = sqrt(x);
	for (int i = 3; i <= sqrtx; i += 2) {
		if (x % i == 0)
			return false;
	}
	return true;
}
bool SQRTOR(int n) {
	if (sqrt(n) == (int)sqrt(n))
		return true;
	else
		return false;
}
// 順位付け
using namespace std;
#pragma endregion

signed main() {
	int M, D, ans = 0, d1, d2;
	cin >> M >> D;
	REP(i, M) {
		REP(j, D) {
			d1 = DIGIT(j, 1);
			d2 = DIGIT(j, 2);
			if (d1 > 1 && d2 > 1 && d1 * d2 == i)
				ans++;
		}
	}
	cout << ans << endl;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define CON 100010
//#define MOD 1e9+7
const long long mod=1e9+7;
using namespace std;
int main() 
{
	int N,M;
	cin>>N>>M;
	vector<int> stairs(N+2,true);
	for(int i=0;i<M;i++)
	{
		int a;
		cin>>a;
		stairs[a]=false;
	}
	vector<ll> dp(N+2);
	dp[0]=1;
	for(int now=0;now<N;now++)
	{
		for(int next=now+1;next<=min(N,now+2);next++)
		{
			if(stairs[next])
			{
				dp[next]+=dp[now];
				dp[next]%=mod;
			}
		}
	}
	cout<<dp[N]<<endl;
	return 0;
}

Measured memory_bytes: 1408
import java.util.Scanner;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int R = sc.nextInt();
        
        if (N >= 10) {
            System.out.println(R);
        } else {
            System.out.println(R + 100*(10 - N));
        }
        
    }
}

Measured memory_bytes: 23252
A, B = map(int,input().split())
S = input()
result = "Yes"
if(A<=0 or B<=0 or A>5 or B>5 or S.count("-") != 1):
	result = "No"
else:
	T = S.split("-")
	if(not T[0].isdigit() or not T[1].isdigit()
	or len(T[0]) != A or len(T[1]) != B):
		result ="No"
print(result)

Measured memory_bytes: 3064
N = int(input())
A = list(map(int,input().split()))

A.sort(reverse=True)

from collections import deque
d = deque()
ans = 0

d.append(A[0])
for i in range(1,N):
    d.append(A[i])
    d.append(A[i])
    ans += d.popleft()

print(ans)

Measured memory_bytes: 94168
import sys
import math
import fractions
import bisect
import queue
import heapq
from collections import deque
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint
N, K = map(int, input().split())

1行のstring
S, T = input().split()

1行の整数配列
P = list(map(int,input().split()))

改行あり整数
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

N行M列の初期化
dp = [[INF] * M for i in range(N)]

'''


N = int(input())

# 最大の753数は777777753
ans = []

for keta in range(3,10):
    for bit in range(3**keta): # 0:3 1:5 2:7

        temp = 0
        check = [False, False, False]
        for k in range(keta):
            where = bit%(3**(k+1))//(3**k)
            temp += (where*2+3)*(10**k)
            check[where] = True
        
        if all(check):
            ans.append(temp)

ans.sort()
idx = bisect.bisect_right(ans, N)
print(idx)





Measured memory_bytes: 6076
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

int main(void){
  int N, M;
  cin >> N >> M;
  map<long long, int> A;
  for(int cnt = 0; cnt < N; ++cnt){
    long long a;
    cin >> a;    
    ++A[a];
  }

  for(int cnt = 0; cnt < M; ++cnt){
    int B, C;
    cin >> B >> C;
    A[C] += B;
  }

  long long offset = pow(10, 9);
  map<long long, int> Ans;
  for(auto itr = A.begin(); itr != A.end(); ++itr){
    Ans[offset - itr->first] = itr->second;
  }

  long long ans = 0;
  for(auto itr = Ans.begin(); itr != Ans.end(); ++itr){
    if(N > itr->second){
      ans += (offset - itr->first) * itr->second;
      N -= itr->second;
    }else{
      ans += (offset - itr->first) * N;
      break;
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 25216
// 6/14 リアルタイム参加
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using Graph = vector<vector<int>>;

int main() {
    int X, Y;
    cin >> X >> Y;

    if (Y >= 2 * X && Y <= 4 * X && Y % 2 == 0) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 3592
def resolve():
    n = int(input())
    ans = 0
    for _ in range(n):
        d1, d2 = map(int, input().split())
        if d1 == d2:
            ans += 1
        else:
            ans = 0
        if ans == 3:
            print("Yes")
            return

    print("No")

resolve()

Measured memory_bytes: 9168
import scala.io.StdIn._

object Main extends App {

  val n = readInt()
  val A = readLine().split(" ").map(_.toInt)

  def solve() = {
    rec(A, A.min)
  }

  def rec(list: Array[Int], divider: Int): Int = {
    if(list.isEmpty) divider
    else {
      val filtered = list.collect {
        case num if num % divider != 0 => num % divider
      }
      if(filtered.nonEmpty && divider > filtered.min) {
        rec(divider +: filtered, filtered.min)
      } else rec(filtered, divider)
    }
  }

  println(solve())

}



Measured memory_bytes: 62876