akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
    int N;
    cin >> N;
    string S;
    cin >> S;
    // 累積和での実装
    vector<int> blacks(1, 0), whites(1, 0);
    for (int i = 0; i < N; i++)
    {
        if (S[i] == '#')
        {
            blacks.push_back(blacks[i] + 1);
        }
        else
        {
            blacks.push_back(blacks[i]);
        }
        if (S[N - 1 - i] == '.')
        {
            whites.push_back(whites[i] + 1);
        }
        else
        {
            whites.push_back(whites[i]);
        }
    }
    // 番兵を前後にくっつける
    blacks.push_back(blacks[N]);
    whites.push_back(whites[N]);
    reverse(whites.begin(), whites.end());
    vector<int> costs;
    for (int i = 0; i < N + 2; i++)
    {
        costs.push_back(blacks[i] + whites[i + 1]);
    }
    int ans = *min_element(costs.begin(), costs.end());
    //for (int i = 0; i < costs.size(); i++)
    //{
    //    cout << "blacks:" << blacks[i] << endl;
    //    cout << "whites:" << whites[i] << endl;
    //}
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3568
A,B,C,X,Y=map(int,input().split())
total=0
if A+B<=C*2:
    print(A*X+B*Y)
    exit(0)
else:
    total+=min(X,Y)*2*C

if X<Y:
    if B<2*C:
        total+=(Y-X)*B
    else:
        total+=(Y-X)*C*2

if X>Y:
    if A<2*C:
        total+=(X-Y)*A
    else:
        total+=(X-Y)*C*2

print(total)


Measured memory_bytes: 3064
import java.util.Scanner;

class Main {
    private static void solve() {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int result = 0;
            for (int a = 0; a < 10; a++) {
                for (int b = 0; b < 10; b++) {
                    for (int c = 0; c < 10; c++) {
                        for (int d = 0; d < 10; d++) {
                            if (a + b + c + d == n) {
                                result++;
                            }
                        }
                    }
                }
            }
            System.out.println(result);
        }
    }

    public static void main(String... args) {
        solve();
    }
}

Measured memory_bytes: 0
/**
 *    author:  nasimnoob
**/

#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<math.h>
using namespace std;
int main()
{
    //string ;
    double a,b,c;
    cin>>a;
    b = 2*3.1416*a;
    cout<<b<<endl;
    return 0;
}




Measured memory_bytes: 3788
h, w = map(int, input().split())
field = [input() for _ in range(h)]
# 左、右、上、下
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
impossible = False

for y in range(h):
    if impossible:
        break

    for x in range(w):
        if field[y][x] == '.':
            continue

        check = False

        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]

            if nx < 0 or nx >= w or ny < 0 or ny >= h:
                continue

            if field[ny][nx] == '#':
                check = True
        if not check:
            impossible = True
            break

if impossible:
    print('No')
else:
    print('Yes')


Measured memory_bytes: 3064
#include <stdio.h>

void clear(int a[],int num){
  int i;

  for(i=0;i<num;i++){
    a[i]=0;
  }

}

void array_in(int a[],int num){
  int i;

  for(i=0;num!=0;i++){
    a[i]=num%10;
    num /= 10;
  }
}

void func(int ans[],int num[]){
  int i,j,a,b,n,p[200];

  clear(p,200);

  for(i=0;i<7;i++){
    for(j=0;j<20;j++){
      p[i+j] += ans[j]*num[i];
      if(p[i+j] >= 10){
	       p[i+j+1] += p[i+j]/10;
         p[i+j]=p[i+j]%10;
      }
    }
  }

  for(i=0;i<20;i++){
    ans[i]=p[i];
  }
}

void divide(int a[],int num){
  int i;

  while(a[0] == 0){
    for(i=0;i<num-1;i++){
      a[i]=a[i+1];
    }
  }

}

int main(void){
  int a,n,i,j,cnt;
  int ans[100];
  int num[7];

  clear(ans,100);
  ans[0]=1;
  scanf("%d",&a);
  for(i=a;i>=1;i--){
    n=i;
    clear(num,7);
    array_in(num,n);
//    divide(num,7);
    func(ans,num);
//    divide(ans,20);
  }
  for(i=99;i>=0;i--){
    if(ans[i] != 0){
      printf("%d",ans[i]);
      break;
    }
  }
  i--;

  for(;i>=0;i--){
    printf("%d",ans[i]);
  }


  printf("\n");

  return 0;
}

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

    void solve() {
	    ll n;
	    cin >> n;
	    ll cnt = 1, val = 1;
	    while(val <= n) val = 2*val;
	    val/=2;
	    cout << (2*val - 1) << endl;
    }

    int main() {
      cin.sync_with_stdio(0); cin.tie(0);
      cin.exceptions(cin.failbit);
      //ll ti;   cin >> ti;  while(ti--)
      solve();
      return 0;
    }


Measured memory_bytes: 256
def main():
    N, Wei = map(int, input().split())
    W = [0] * N
    V = [0] * N
    for i in range(N):
        W[i], V[i] = map(int, input().split())
    dp = [[0] * (Wei + 5) for _ in range(N + 5)]
    dp[0][Wei] = 0
    for i in range(N):
        for w in range(Wei+1):
            if w >= W[i]:
                dp[i+1][w] = max(dp[i][w-W[i]] + V[i], dp[i][w])
            else:
                dp[i+1][w] = dp[i][w]

    print(dp[N][Wei])


if __name__ == "__main__":
    main()

Measured memory_bytes: 149460
def main():
    h, w = map(int, input().split())

    minv = 100000000000
    for i in range(1, h):
        s = []
        s.append(i*w)
        j = w//2
        s.append((h-i)*j)
        s.append((h-i)*(w-j))
        if max(s) - min(s) < minv:
            minv = max(s) - min(s)

        s = []
        s.append(i*w)
        j = (h-i)//2
        s.append(j*w)
        s.append((h-i-j)*w)
        if max(s) - min(s) < minv:
            minv = max(s) - min(s)

    h, w = w, h
    for i in range(1, h):
        s = []
        s.append(i*w)
        j = w//2
        s.append((h-i)*j)
        s.append((h-i)*(w-j))
        if max(s) - min(s) < minv:
            minv = max(s) - min(s)

        s = []
        s.append(i*w)
        j = (h-i)//2
        s.append(j*w)
        s.append((h-i-j)*w)
        if max(s) - min(s) < minv:
            minv = max(s) - min(s)
    print(minv)


if __name__ == "__main__":
    main()

Measured memory_bytes: 3188
IDENTIFICATION DIVISION.
       PROGRAM-ID. HELLO.

       ENVIRONMENT DIVISION.
       INPUT-OUTPUT SECTION.
       FILE-CONTROL.

           SELECT STDIN ASSIGN TO KEYBOARD ORGANIZATION LINE SEQUENTIAL.


       DATA DIVISION.


       FILE SECTION.

           FD STDIN.
           01 LN PIC X(65535) USAGE DISPLAY.
             88 EOF VALUE HIGH-VALUES.

       WORKING-STORAGE SECTION.
       
           01 OUT PIC X(65535) USAGE DISPLAY.

       PROCEDURE DIVISION.

           INITIALIZE LN, OUT.

           MAIN-PROCEDURE.
               
             OPEN INPUT STDIN
             READ STDIN
               AT END SET EOF TO TRUE
             END-READ
             CLOSE STDIN
             
             MOVE LN TO OUT
             INSPECT OUT REPLACING
               FIRST "2017" BY "2018"

             DISPLAY OUT
             
             STOP RUN.

       END PROGRAM HELLO.


Measured memory_bytes: 1404
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<stack>
#include<queue>
#include<string>
#include<set>
#include<map>
using namespace std;
#define rep(i,n) for(int i=0;(i)<(n);(i)++)
#define FOR(i,m,n) for(int i=(m);(i)<(n);(i)++)
typedef long long ll;

int main(){
    int a,b,c;
    cin >> a >> b >> c;
    if(a==b&&b==c)cout << "Yes" << endl;
    else cout << "No" << endl;    
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
  long int a,b,k,i;
  scanf("%ld%ld%ld",&a,&b,&k);
  if(a>=k)
    a -= k;
  else if(a+b>=k){
    k -= a;
    a = 0;
    b -= k;
  }
  else
    a = b = 0;
  printf("%ld %ld\n",a,b);
  return 0;
}

Measured memory_bytes: 1732
#include "bits/stdc++.h"

using namespace std;

int maxFrom(vector<int> A, int m, int M, int N
        , const vector<int>& a, const vector<int>& b, const vector<int>& c, const vector<int>& d) {
    if (A.size() == N) {
        int point = 0;
        for (int q = 0; q < a.size(); ++q) {
            if (A[b[q]] - A[a[q]] == c[q]) {
                point += d[q];
            }
        }
        return point;
    }

    vector<int> takeThis(A.begin(), A.end());
    takeThis.push_back(m);
    int ret = maxFrom(takeThis, m, M, N, a, b, c, d);

    if (m < M) {
        int skipThisValue = maxFrom(A, m + 1, M, N, a, b, c, d);
        ret = max(ret, skipThisValue);
    }

    return ret;
}

void Main() {
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<int> a(Q, 0), b(Q, 0), c(Q, 0), d(Q, 0);
    for (int i = 0; i < Q; ++i) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }

    for (int i = 0; i < Q; ++i) {
        a[i] -= 1;
        b[i] -= 1;
    }

    vector<int> A;
    int ans = maxFrom(A, 1, M, N, a, b, c, d);
    cout << ans << endl;
}

int main() {
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 3636
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

var sc *bufio.Scanner

const BufferSize = 1024

func nextInt() int {
	if !sc.Scan() {
		panic(nil)
	}
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

var production bool

func debugf(format string, v ...interface{}) {
	if !production {
		fmt.Printf(format, v...)
	}
}

func pow(x, y int) int {
	//_, _ = fmt.Printf("pow: %v, %v\n", x,y)
	z := x
	if y == 0 {
		return 1
	}
	for i := 1; i < y; i++ {
		z = z * x
	}
	return z
}

type combi struct {
	fac  []int
	finv []int
	inv  []int
	mod  int
}

func (c *combi) init(n int, m int) {
	c.fac = make([]int, n)
	c.finv = make([]int, n)
	c.inv = make([]int, n)
	c.mod = m

	c.fac[0] = 1
	c.fac[1] = 1
	c.finv[0] = 1
	c.finv[1] = 1
	c.inv[1] = 1
	for i := 2; i < n; i++ {
		c.fac[i] = c.fac[i-1] * i % c.mod
		c.inv[i] = c.mod - c.inv[c.mod%i]*(c.mod/i)%c.mod
		c.finv[i] = c.finv[i-1] * c.inv[i] % c.mod
	}
}

func (c *combi) combi(n, k int) int {
	if n < k {
		return 0
	}
	if n < 0 || k < 0 {
		return 0
	}
	return c.fac[n] * (c.finv[k] * c.finv[n-k] % c.mod) % c.mod
}

func answer(reader io.Reader, writer io.Writer) {
	sc = bufio.NewScanner(reader)
	buf := make([]byte, BufferSize)
	sc.Buffer(buf, 1e+6)
	sc.Split(bufio.ScanWords)
	r1 := nextInt()
	c1 := nextInt()
	r2 := nextInt()
	c2 := nextInt()

	var c combi
	m := pow(10, 9) + 7
	c.init(r2+c2+4, m)
	ans := 0
	/*
		for i := r1; i < r2+1; i++ {
			for j := c1; j < c2+1; j++ {
				ans += c.combi(i+j, i)
				ans %= m
			}
		}
	*/

	ans += c.combi(r2+c2+2, r2+1)
	ans %= m
	ans -= c.combi(r2+c1+1, r2+1)
	if ans < 0 {
		ans += m
	}
	ans %= m
	ans -= c.combi(r1+c2+1, r1)
	if ans < 0 {
		ans += m
	}
	ans %= m
	ans += c.combi(r1+c1, r1)
	ans %= m

	_, _ = fmt.Fprintf(writer, "%d", ans)
}

func main() {
	production = true
	answer(os.Stdin, os.Stdout)
}


Measured memory_bytes: 49024
n,k=map(int,input().split())
a=list(map(int,input().split()))
c=2
t=0
path=[]
s=set()
cycle=[]
while(c<=k):
    if a[t] in s:
        #print(path.index(a[t]),a[t])
        cycle=path[path.index(a[t]):]
        k-=c-1
        break
    path.append(a[t])
    s.add(a[t])
    t=a[t]-1
    c+=1
if cycle==[]:
    print(a[t])
else:
    print(cycle[k%len(cycle)])
 

Measured memory_bytes: 113888
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
mod=10**9+7

N,H=MI()
a=[0]*N
b=[0]*N

for i in range(N):
    a[i],b[i]=MI()

    
AM=max(a)
BL=[]

for i in range(N):
    if b[i]>AM:
        BL.append(b[i])
        
BL.sort(reverse=True)

ans=0
for i in range(len(BL)):
    ans+=1
    H-=BL[i]
    if H<=0:
        break
        
if H>0:
    ans+=(H+AM-1)//AM
    
print(ans)





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

int main() {
    int n;
    cin >> n;
    int h[n];
    rep(i, n) cin >> h[i];

    int pre = -999;
    rep(i, n) {
        if (pre <= h[i]-1) pre = h[i]-1;
        else if (pre <= h[i]) pre = h[i];
        else {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    return 0;
}


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

#define INFLL 2000000000000000000
#define INF 2000000000
#define MOD 1000000007
#define BASE 77747
#define PI acos(-1.0)
#define MAXLEN 29

typedef std::pair <int, int> pii;
typedef long long ll;
typedef std::vector <ll> vll;

using namespace std;

int d, g;
int p[10], c[10];
int dp[10][1001];

int main() {
	cin >> d >> g;
	for (int i = 0; i < d; i++) cin >> p[i] >> c[i];
	for (int i = 1; i < p[0]; i++) {
		dp[0][i] = i * 100;
	}
	dp[0][p[0]] = p[0] * 100 + c[0];
	for (int i = 1; i < d; i++) {
		for (int j = 0; j <= p[i]; j++) {
			int toAdd = 0;
			if (j == p[i]) toAdd = c[i];
			for (int k = 0; k + j <= 1000; k++) dp[i][k + j] = max(dp[i - 1][k + j], dp[i - 1][k] + j * (i + 1) * 100 + toAdd);
		}
	}
	int ans = INF;
	for (int i = 0; i < d; i++) for (int j = 0; j <= 1000; j++) if (dp[i][j] >= g) ans = min(ans, j);
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#define N 2000001
int B[N];
main(){
  int i, j, n, m=0, A[N], C[10001];
  
  scanf("%d", &n);
  for(i=1; i<n+1; i++){
    scanf("%d", &A[i]);
    
    if(A[i]>m){
      m=A[i];
    }
  }
  
  for(i=0; i<m+1; i++){
    C[i]=0;
  }
  for(j=1; j<n+1; j++){
    C[A[j]]++;
  }
  for(i=1; i<m+1; i++){
    C[i]=C[i]+C[i-1];
  }
  for(j=n; j>0; j--){
    B[C[A[j]]]=A[j];
    C[A[j]]--;
  }
  for(i=1; i<n; i++){
    printf("%d ", B[i]);
  }
  printf("%d\n", B[n]);
  
  return 0;
}

Measured memory_bytes: 16260
#include <bits/stdc++.h>
#define lli long long int
#define all(c) c.begin(), c.end()
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define deb(x) cout << #x << " " << x << endl;
#define rep(i, n) for (i = 0; i < n; i++)
#define Rep(i, k, n) for (i = k; i < n; i++)
#define write(x) cout << x << " ";
#define writeLine(x) cout << x << endl;
#define fast std::ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define ppi pair<int, int>
using namespace std;

int main()
{
    fast;

#ifndef ONLINE_JUDGE
    freopen("/home/kalit/Desktop/Data Structures-Algo-Competitive/src/codeforces/input.txt", "r", stdin);
    freopen("/home/kalit/Desktop/Data Structures-Algo-Competitive/src/codeforces/output.txt", "w", stdout);
#endif
    int n;
    cin >> n;
    vector<lli> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    vector<lli> left(n);
    vector<lli> right(n);

    left[0] = a[0];
    right[n - 1] = a[n - 1];

    for (int i = 1; i < n; i++)
    {
        left[i] = __gcd(left[i - 1], a[i]);
    }
    for (int i = n - 2; i >= 0; i--)
    {
        right[i] = __gcd(right[i + 1], a[i]);
    }

    lli ans = left[n - 1];
    for (int i = 1; i < n - 1; i++)
    {
        ans = max(ans, __gcd(left[i - 1], right[i + 1]));
    }
    ans = max(ans, left[n - 2]);
    ans = max(ans, right[1]);
    cout << ans << endl;
}


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

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

map<int, int> mp;
bool correct[100010];

int main() {
  int N, M;
  cin >> N >> M;
  int p;
  string s;
  for (int i = 0; i < M; i++) {
    cin >> p >> s;
    if (correct[p]) continue;

    if (s == "WA") {
      mp[p]++;
    } else {
      correct[p] = true;
    }
  }

  int ans_correct = 0;
  int ans_pena = 0;
  for (int i = 1; i <= N; i++) {
    if (correct[i]) {
      ans_pena += mp[i];
      ans_correct++;
    }
  }

  cout << ans_correct << " " << ans_pena << endl;
  return 0;
}


Measured memory_bytes: 4992
var n,i : longint;
    ans,a: int64;
    zero : boolean;
begin
    read(n);
    ans := 1;
    zero := false;
    for i := 1 to n do begin
        read(a);
        if (ans <> -1) and (a <= 1000000000000000000 div ans) then
            ans := ans * a
        else
            ans := -1;
        if a = 0 then
            zero := true;
    end;
    if not zero then writeln(ans) else writeln(0);
end.


Measured memory_bytes: 1392
#include <iostream>
#include <sstream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <cassert>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;

int n, m;
int hint[10000][10];
bool appear[10000][10];
int hit[10000], blow[10000];
int tmp[10];
int ans[10];
int ansnum;

typedef pair<bool, int> pbi;

void dfs(int now, int used) {
   REP(i, m) {
    if (hit[i] > n-now || blow[i] > n-now) return;
  }
  // REP(i, now)
  //   cout << tmp[i];
  // cout << endl;
  if (now == n) {
    ansnum++;
    memcpy(ans, tmp, sizeof(tmp));
    return;
  }
 
  REP(i, 10) {
    if (used >> i & 1) continue;
    vector<pbi> record;
    REP(j, m) {
      if (hint[j][now] == i) {
        if (hit[j] > 0) {
          hit[j]--;
          record.push_back(pbi(0, j));
        } else {
          goto br;
        }
      } else if (appear[j][i]) {
        if (blow[j] > 0) {
          blow[j]--;
          record.push_back(pbi(1, j));
        }
        else {
          goto br;
        }
      }
    }
    tmp[now] = i;
    dfs(now+1, used|1<<i);
  br:;
    FOR(it, record) {
      if (it->first) {
        blow[it->second]++;
      } else {
        hit[it->second]++;
      }
    }
  }
}

int main() {
  while(cin >>n>>m, n||m) {
    memset(appear, 0, sizeof(appear));
    REP(i, m) {
      REP(j,n) {
        char c;
        cin >> c;
        hint[i][j] = c-'0';
        appear[i][c-'0'] = 1;
      }
      cin >> hit[i];
      cin >> blow[i];
    }
    ansnum = 0;
    dfs(0, 0);
    if (ansnum == 1) {
      REP(i, n)
        cout << ans[i];
      cout << endl;
    }
    else cout << "NO" << endl;
  }
}

Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <cassert>
#include <random>

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

using namespace std;
typedef long long int ll;
const int INF = 1000000000;
const double PI = acos(-1);
const ll mod = 1000000007;

int main()
{
    ll x, k, d;
    cin >> x >> k >> d;

    x = abs(x);
    if (k <= x / d) {
        cout << x - k * d << endl;
        return 0;
    }
    k -= x / d;
    x = x % d;
    if (k % 2 == 0) cout << x << endl;
    else cout << d - x << endl;
    return 0;
}


Measured memory_bytes: 3532
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <set>
#include <map>
#include <unordered_set>
using namespace std;

long long n, A, B, C, D;

bool can(long long curr, long long l, long long r, long long maxAtt, bool jumped) {
	if (maxAtt < 0) return 0;
	if (curr >= l && curr <= r) {
		if (maxAtt % 2 == 0) return 1;
		else if (curr + C <= r || curr - C >= l) return 1;
		else return 0;
	} else if (!jumped) {
		if (curr < l) {
			long long jumps = (l - curr + C - 1) / C;
			return can(curr + jumps * C, l, r, maxAtt - jumps, 1);
		} else {
			long long jumps = (curr - r + C - 1) / C;
			return can(curr - jumps * C, l, r, maxAtt - jumps, 1);
		}
	} else {
		return 0;
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	//freopen("game.in", "r", stdin);
	//freopen("game.out", "w", stdout);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin >> n >> A >> B >> C >> D;
	long long LL = -D;
	long long LR = -C;
	long long RL = C;
	long long RR = D;
	
	for (int i = -(n - 2); i <= n - 2; i++) {
		long long currA = A + D * i;
		long long currDelta = B - currA;
		int attemptsLeft = n - 2 - abs(i);
		if (can(currDelta, LL, LR, attemptsLeft, 0) || can(currDelta, RL, RR, attemptsLeft, 0)) {
			cout << "YES";
			return 0;
		}
	}
	cout << "NO";
	
	return 0;
}

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

using namespace std;
mt19937_64 rng(58);

// find b s.t. a * b = 1 (mod m)
template <typename T>
T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a; swap(a, m);
    u -= t * v; swap(u, v);
  }
  assert(m == 1);
  return u;
}

template <typename T>
T pow(T x, long long p) {

}

template<long long mod = 1000000007>
struct modint{
	long long a;
	modint() : a(0){}
	modint(long long t) { a = t % mod; if(a < 0) a += mod; }
	operator long long() const{ return a; }
	bool operator==(const modint &x) const{ return a == x.a; }
	bool operator!=(const modint &x) const{ return a != x.a; }
	modint operator-() const{ return modint(a ? (mod - a) : 0); }
	modint operator~() const{ return inverse(a, mod); }

	modint operator+(const modint &x) const{ return modint(*this) += x; }
	modint operator-(const modint &x) const{ return modint(*this) -= x; }
	modint operator*(const modint &x) const{ return modint(*this) *= x; }
	modint operator/(const modint &x) const{ return modint(*this) /= x; }

	modint &operator+=(const modint &x){
		a += x.a;
		if(a >= mod) a -= mod;
		return *this;
	}
	modint &operator-=(const modint &x){
		a -= x.a;
		if(a < 0) a += mod;
		return *this;
	}
	modint &operator*=(const modint &x){
		a = a * x.a % mod;
		return *this;
	}
	modint &operator/=(const modint &x){
		a = a * (~x).a % mod;
		return *this;
	}

	friend ostream &operator<<(ostream &os,const modint &x){
		return os << x.a;
	}
	friend istream &operator>>(istream &is,modint &x){
		long long t;
		is >> t;
		x = modint(t);
		return is;
	}

	modint pow(long long x) const{
		modint ret = 1,tmp = a;
		for(;x;tmp *= tmp,x >>= 1){
			if(x & 1) ret *= tmp;
		}
		return ret;
	}
};

typedef long long ll;
ll f(int k, int n) { // count of sequence s.t. gcd(A_1, A_2, ..., A_k) = 1
    ll ans = 0;

    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll n, k;
    cin >> n >> k;
    modint<> mem[100001];
    modint<> ans = 0;
    for (int g = k; g > 0; g--) {
        // ans += g * count of sequence s.t gcd(s) == g
        modint<> count = modint<>(k / g).pow(n);
        for (int x = 2; g * x <= k; x++) {
            count -= mem[g * x];
        }
        mem[g] = count;
        ans += g * count;
    }
    cout << ans << "\n";
}

Measured memory_bytes: 4428
N = int(input())
a = [[0]*3 for ac in range(N)]

for i in range(N):
    a[i][0], a[i][1], a[i][2] = map(int, input().split())

dp = [[0]*3 for _ in range(N)]

dp[0][0] = a[0][0]
dp[0][1] = a[0][1]
dp[0][2] = a[0][2]

for i in range(1, N):
    for activity in range(3):
        for yesterday_activity in range(3):
            if yesterday_activity != activity:
                dp[i][activity] = max (
                    dp[i][activity], dp[i-1][yesterday_activity] + a[i][activity]
                )
print(max(dp[N-1][0], dp[N-1][1], dp[N-1][2]))

Measured memory_bytes: 100620
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long LL;
const int N = 1e5+10 , mod = 1e9+7;
inline int read()
{
	register int x = 0 , f = 0; register char c = getchar();
	while(c < '0' || c > '9') f |= c == '-' , c = getchar();
	while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0' , c = getchar();
	return f ? -x : x;
}
int n;
int f[N] , lst[N] , a[N];
char s[N];
int main()
{
	scanf("%s" , s);
	for( ; s[n] ; ++n) a[n+1] = (a[n] + s[n] - 'a' + 1) % 3;
	int flag = 0;
	for(int i = 1 ; i < n ; ++i) if(s[i] == s[i - 1]) { flag = 1; break; }
	if(!flag) return puts("1") , 0;
//	for(int i = 0 ; i < n ; ++i) a[i+1] = (a[i] + s[i] - 'a' + 1) % mod;
	for(int i = 0 ; i <= 2 ; ++i) lst[i] = i == a[n] ? n : n + 1;
	f[n] = 1;
	for(int i = n - 1 ; i ; --i)
	{
		f[i] = a[i] == a[n];
		for(int j = 1 ; j <= 2 ; ++j) (f[i] += f[lst[(a[i] + j) % 3]]) %= mod;
		lst[a[i]] = i;
	}
	cout << (f[lst[1]] + f[lst[2]]) % mod << '\n';
	return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ;
#endif

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;

template< typename T >
struct edge {
  int src, to;
  T cost;
  edge(int to, T cost) : src(-1), to(to), cost(cost) {}
  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}
  edge &operator=(const int &x) {
    to = x;
    return *this;
  }
  operator int() const { return to; }
};
template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< Edges< T > >;
using UnWeightedGraph = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;
int negative[2510] = {};

template< typename T >
vector< T > bellman_ford(Edges< T > &edges, int V, int s) {
  const auto INF = numeric_limits< T >::max();
  vector< T > dist(V, INF);
  dist[s] = 0;
  for(int i = 0; i < V - 1; i++) {
    for(auto &e : edges) {
      if(dist[e.src] == INF) continue;
      dist[e.to] = min(dist[e.to], dist[e.src] + e.cost);
    }
  }
  bool flag = 0;
  for(int i = 0; i < V+1; i++){
    for(auto &e : edges) {
        if(dist[e.src] == INF) continue;
        if(dist[e.src] + e.cost < dist[e.to])
        {
            dist[e.to] = dist[e.src] + e.cost;
            negative[e.to] = 1;
        }
    }
  }
  return dist;
}

void propagate(Edges<LL> &edges){
    for(auto &e : edges){
        if(negative[e.src] == 1) negative[e.to] = 1;
    }
}

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    LL N,M,P; cin >>N>>M>>P;
    Edges<LL> es;
    REP(i,2510) negative[i] = 0;
    REP(i,M)
    {
        LL a,b,c; cin>>a>>b>>c;
        a--; b--;
        //c *= -1;
        c -= P;
        c *= -1;
        es.emplace_back(a,b,c);
    }
    auto dists = bellman_ford(es,N,0);
    propagate(es);

    if(negative[N-1] == 1)
    {
        cout << -1 << endl;
        return 0;
    }
    else
    {
        cout << max(dists[N-1] * -1,0LL) << endl;
    }

}


Measured memory_bytes: 512
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int a,b,m,A[100000],B[100000],c,p=1e9,q=1e9,ans,L;
int main(void){
    cin>>a>>b>>m;
    for(int i=0;i<a;i++){
        cin>>A[i];
        p=min(p,A[i]);
    }
    for(int i=0;i<b;i++){
        cin>>B[i];
        q=min(q,B[i]);
    }
    ans=p+q;
    for(int i=0;i<m;i++){
        cin>>a>>b>>c;
        a--;
        b--;
        L=A[a]+B[b]-c;
        ans=min(ans,L);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 1024
import collections
import sys
sys.setrecursionlimit(10**6)

def getls():
    return [ipt for ipt in input().split()]
def getlsi():
    return [int(ipt) for ipt in input().split()]
#Topological sort Gは辞書として渡す
def tsort(N,G,dic):
    res = 0
    #Topological Sort
    if dic[N] != -1:
        return dic[N]
    for node in G[N]:
        res = max(res,tsort(node,G,dic)+1)
    dic[N] = res
    return dic[N]

[n,m] = getlsi()
dic_next = collections.defaultdict(list)
dp = [-1] * n
for i in range(m):
    [x,y] = getlsi()
    dic_next[x-1].append(y-1)
ans = 0
for i in range(n):
    ans = max(ans,tsort(i,dic_next,dp))
print(ans)


Measured memory_bytes: 67784
def prim():
    INFTY = float('inf')
    color = ['WHITE' for _ in range(n)]
    d = [INFTY for _ in range(n)]
    p = [None for _ in range(n)]
    d[0] = 0
    p[0] = -1

    while True:
        mincost = INFTY
        for i in range(n):
            if color[i] != 'BLACK' and d[i] < mincost:
                mincost = d[i]
                u = i
        
        if mincost == INFTY:
            break

        color[u] = 'BLACK'

        for v in range(n):
            if color[v] != 'BLACK' and A[u][v] != -1:
                if A[u][v] < d[v]:
                    d[v] = A[u][v]
                    p[v] = u
                    color[v] = 'GRAY'
    return sum(d)

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

print(prim())



Measured memory_bytes: 5908
#include <bits/stdc++.h>
using namespace std;
#define modulo 998244353
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 10000000000000000



int main(){
	
	int N,A;
	cin>>N>>A;
	
	if(N%500<=A){
		cout<<"Yes"<<endl;
	}
	else{
		cout<<"No"<<endl;
	}
	
		
    return 0;
}


Measured memory_bytes: 256
L = int(input())
N = len(bin(L)[2:])
R = 1 << N - 1
UVW = sum([[(i, i+1, 0), (i, i+1, 1<<i-1)] for i in range(1, N)], [])
for i, s in enumerate(bin(L)[:2:-1], 1):
    if s == "1":
        UVW.append((i, N, R))
        R += 1 << i - 1

print(N, len(UVW))
for t in UVW:
    print(*t)

Measured memory_bytes: 3064
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <cassert>
#include <exception>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<string,ll> P;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<P> vp;
#define rep(i,a,n) for(ll i = (a);i < (n);i++)
#define per(i,a,n) for(ll i = (a);i > (n);i--)
#define lep(i,a,n) for(ll i = (a);i <= (n);i++)
#define pel(i,a,n) for(ll i = (a);i >= (n);i--)
#define clr(a,b) memset((a),(b),sizeof(a))
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define sz size()
#define print(X) cout << (X) << endl
const ll INF = 1e+9+7;
double n,m,l;
string s,t;
ll d[100000],dp[100][100];

int main(){
  cin >> n >> m;
  ll ans = 1;
  rep(i,0,n-1){
    ans *= m-1;
  }
  ans *= m;
  print(ans);
  return 0;
}

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

#define int long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define FOR(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define SORT(c) sort((c).begin(),(c).end())

typedef long long ll;
const ll INF = 1LL<<60;
const ll mod = 1e9 + 7;
const int MAX_N = 5e5 + 5;
int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 };
vector<ll> prime;

ll inv[MAX_N], fac[MAX_N];

template <class T = ll> T in() { T x; cin >> x; return (x); }
inline ll GCD(ll a, ll b) { ll c; while (b != 0) { c = a % b; a = b; b = c; }return a; }
inline ll LCM(ll a, ll b) { return a * b / GCD(a, b); }
inline ll POW(ll a, ll b) { ll c = 1; while (b > 0) { if (b & 1) { c = a * c%mod; }a = a * a%mod; b >>= 1LL; }return c; }
inline void _nCr() { fac[0] = 1; for (int i = 1LL; i < MAX_N; i++) { fac[i] = fac[i - 1] * i%mod; }for (int i = 0; i < MAX_N; i++) { inv[i] = POW(fac[i], mod - 2); } }
inline ll nCr(ll n, ll r) { return (fac[n] * inv[r] % mod)*inv[n - r] % mod; }
inline void PRI(ll n) { bool a[n + 1]; for (int i = 0; i < n + 1; i++) { a[i] = 1; }for (int i = 2; i < n + 1; i++) { if (a[i]) { prime.pb(i); ll b = i; while (b <= n) { a[b] = 0; b += i; } } } }

vector<vector<pair<int,int>>> Edge;
vector<int> node;

bool bellman_ford(int n,int s) {
	node = vector<int>(n,INF);
	node[s] = 0;
	REP (i,n) {
		REP (j,Edge.size()) {
			REP (k,Edge[j].size()) {
				int from = j,to = Edge[j][k].F;
				int cost = Edge[j][k].S;
				if (node[from] != INF && node[to] > node[from] + cost) {
					node[to] = node[from] + cost;
					if (i == n - 1 && to == n - 1) return true;
				}
			}
		}
	}
	return false;
}

signed main() {
	int n,m;
	cin >> n >> m;
	node = vector<int>(n);
	Edge = vector<vector<pair<int,int>>>(n);
	REP (i,m) {
		int x,y,z;
		cin >> x >> y >> z;
		Edge[x-1].push_back({y-1,-z});
	}
	if (bellman_ford(n,0)) {
		cout << "inf" << endl;
	} else {
		cout << -node[n-1] << endl;
	}
}

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

int main(void){
  int n, count = 0; cin >> n;
  string s; cin >> s;
  for (int i=2; i<=n; ++i) {
    if (s[i-2] == 'A') {
      if (s[i-1] == 'B') {
        if (s[i] == 'C') {
          count++;
        }
      }
    }
  }
  cout << count << endl;
  return 0;
}


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

#define watch(x) cerr << (#x) << ": " << (x) << endl
#define int long long



int32_t main() {
    
    int n; cin >> n;

    int edges;
    if(n%2) {
        edges = (n-1)*(n-2) + (n-1);
    } else {
        edges = n*(n-2);
    }
    edges /= 2;

    cout << edges << endl;
    for(int i = 1; i <= n; ++i) {
        int complement = (n%2 ? n-i : (n+1)-i);
        for(int j = i+1; j <= n; ++j) {
            if(j != complement) {
                cout << i << " " << j << endl;
            }
        }
    }
    
    return 0;
}


Measured memory_bytes: 256
H, W, A, B = [int(x) for x in input().split()]

def formatMatrix(matrix):
  return "\n".join(["".join(x) for x in matrix])

def bitShift(matrix, n):
  for i in range(len(matrix)):
    matrix[i] = shift(matrix[i], n)
  return matrix

def shift(row, n):
  new = [0]*len(row)
  i = 0
  carry = False
  for x in row:
    ## If carry and last index not placed make 1
    if (i+n) > n:
      carry = True
    new[(i+n)%len(row)] = x
    i +=1 
  ### Alternative to this block of code would be in invert an entries in the matrix, ie turn 1's to 0's and vice versa
  if carry:
    for i in range((i+n)%len(row), len(row)):
      new[i] = '1'
  return new

def usualMatrix(n):
  i = 0
  x = []
  for a in range(n):
    x.append([])
    j = 0
    for y in range(n):
      if i == j:
        x[i].append('1')
      else:
        x[i].append('0')
      j += 1
    i += 1
  return x

def transpose(m):
  new = [[] for x in range(len(m[0])) ]
  for row in m:
    i = 0
    for entry in row:
      new[i].append(entry)
      i += 1
  return new

def thing(H,W,A,B):
  if H == W and A == 1 and B == 1:
    return usualMatrix(H)
  if H == 0 or W == 0:
    return -5
  if (B > H//2 or B < 0) or (A > W//2 or A < 0):
    return -1
  if B > A:
    a = thing1(W,H,B,A)
    if type(a) == int:
      return -1
    return transpose(a)  
  else:
    return thing1(H,W,A,B)
    
def thing1(H,W,A,B):
  matrix = [['1']*A+['0']*(W-A) for x in range(H)]
  part1 = bitShift(matrix[:B], A)
  part2 = matrix[B:]
  new_matrix = part1 + part2
  return new_matrix

matrix = thing(H,W,A,B)
if type(matrix) == int:
  print(-1)
else:
  print(formatMatrix(matrix))

Measured memory_bytes: 20852
#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<set>
#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<iomanip>
#define MAX 100001
#define ll long long int
#define eps 1e-7
using namespace std;

vector<string>s;
int main(){
  s.resize(1);
  cin>>s[0];
  s[0].insert(4," ");
  cout<<s[0]<<endl;
  return 0;
}


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

#define for_(i,a,b) for(int i=(a);i<(b);++i)

int main() {
	int n, d;
	while (cin >> n >> d, n != 0) {
		vector< stack< int > > que(n, stack< int >());
		vector< int > sum(n, 0);
		for_(i,0,n) {
			int m; cin >> m;
			for_(j,0,m) {
				int c; cin >> c;
				que[i].push(c);
				sum[i] += c;
			}
		}
		
		bool end = false;
		while (!end) {
			end = true;
			for_(i,0,n) {
				if (que[i].empty()) continue;
				sum[i] -= que[i].top();
				if (*max_element(sum.begin(), sum.end()) - *min_element(sum.begin(), sum.end()) <= d) { que[i].pop(); end = false; }
				else sum[i] += que[i].top();
			}
		}
		
		cout << (*max_element(sum.begin(), sum.end()) == 0 ? "Yes" : "No") << endl;
	}
}

Measured memory_bytes: 3052
#include <iostream>
using namespace std;
#define MAX 1000

int main(){
    int n,m;
    int ms[MAX+1];
    
    while(true){
        cin >> n >> m;
        if(!n&&!m) break;
        
        for(int i = 0 ; i < n ; i++) cin >> ms[i];
    
        int go,t=0,cnt = 0;
        bool flg = false;
        
        for(int i = 0 ; i < m ; i++){
            cin >> go;
            if(!flg){
                t += go;
                t += ms[t];
                cnt++;
                if(t >= n-1) flg = true;
            }
        }
        cout << cnt << endl;
    }
    
    return 0;
}

Measured memory_bytes: 1164
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c;
	cin >> a >> b >> c;
	int s=a-b;
	if(c<s)
		cout << 0 << endl;
	else
		cout << (c-s) << endl;
	return 0;
 } 

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

int main() {
  int N;
  cin >> N;
  
  vector<int> vec(N);
  
  for(int i= 0; i < N; i++) {
    cin >> vec.at(i);
  }
  
  sort(vec.begin() , vec.end());
  reverse(vec.begin() , vec.end());
  
  int Alice = 0, Bob = 0;
  
  for(int i = 0; i < N; i++) {
  	if(i % 2 == 0) {
      Alice += vec.at(i);
    }else {
      Bob += vec.at(i);
  	}
  }

	cout << Alice - Bob << endl;
  
}


Measured memory_bytes: 256
# define _CRT_SECURE_NO_WARNINGS 1
# include <iostream>
# include <string>
# include <bitset>
# include <vector>
# include <algorithm>
# include <cstdlib>
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iomanip>
# include <queue>
# include <sstream>
# include <climits>
# include <cmath>
# include <list>
# include <functional>
# include <string>
# include <ctime>
# include <set>
# include <map>
# include <stack>
using namespace std;
//# define M_PI 3.141592
# define INF ((int)(1<<30))
# define FOR(i,n) for(int i=0;i<(int)n;i++)
# define FORI(i,k,n) for(int i=k;i<(int)n;i++)
# define toRad 2.0*M_PI/360.0
# define inin(x) int x;cin>>x;
# define all(x) x.begin(),x.end()
# define debug(x) cout<<#x<<" :"<<x<<endl;
# define rep(i,n) for(int i=0;i<(int)n;i++)
# define EPS 1e-12
# define CHECK(i,a) FOR(i,a.size())cout<<#a<<"["<<i<<"] : "<<a[i]<<endl; 

vector<double>a;
double memo[1 << 12][13];
double calc(int a1,int a2)
{
	double t = a[a1] + a[a2];
	double s = a[a1] - a[a2];
	return sqrt(t*t - s*s);
}



double dp(int bit,int s)
{
	if (memo[bit][s]>=0)return memo[bit][s];
	double ans = 9999999999999.0;
	bool ok = true;
	for (int i = 0; i < a.size(); i++)
	{
		if (!(bit & (1 << i)))
		{
			ok = false;
			double x = (bit ? 0.0 : a[i]);
			ans = min(ans, dp(bit | (1 << i), i) + calc(i, s)+x);
		}
	}
	if (ok)return a[s];
	return memo[bit][s] = ans;
}
int main()
{
	string s;
	while (getline(cin,s))
	{
		for (auto &x : memo)for(auto &y:x)y= -1.0;
		a.clear();
		stringstream ss(s);
		double n;
		ss >> n;
		double temp;
		while (ss >> temp)
		{
			a.push_back(temp);
		}
		bool ok = false;
		double ans = 99999999999999999;
		for (int i = 0; i < a.size(); i++)
		{
			ans = min(ans, dp(1 << i, i)+a[i]);
		}
		ok = (ans <= n);
		if (ok)cout << "OK" << endl;
		else cout << "NA" << endl;

	}
}

Measured memory_bytes: 3588
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int INF=1e9;

int c[2001][2001];

int main(){
    c[0][0]=1;
    for(int i=1;i<=2000;i++){
        for(int j=0;j<=i;j++){
            if(j==0)c[i][j]=1;
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%MOD;
        }
    }
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=k;i++){
        if(n-k<i-1)cout<<0<<endl;
        else cout<<((ll)c[k-1][i-1]*c[n-k+1][i])%MOD<<endl;
    }
}


Measured memory_bytes: 15104
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0);
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define endl '\n'

using namespace std;

main()
{
    fast;
    int a[3];
    cin>>a[0]>>a[1]>>a[2];
    sort(a,a+3);
    cout<<a[1]-a[0]+a[2]-a[1]<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

using namespace std;
typedef long long int lli;

int main(){
	string S;
	cin>>S;
	
	int l=(int)S.length();
	
	//長いほうから検索
	int ans;
	for(int i=l-2;i>=2;i-=2){
		bool even=true;
		rep(j,i/2)if(S[j]!=S[j+(i/2)])even=false;
		if(even){
			ans=i;
			break;
		}
	}
	cout<<ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <string>
using namespace std;
typedef double  dbl;
typedef long long int lld;
#define PI 3.14159265358979323
#define foi(i,n) for(i = 0; i < n; i+=1)
#define fod(i,n) for(i=n-1; i >=0; i-=1)
#define MAX std::numeric_limits<lld>::max()
#define MIN std::numeric_limits<lld>::min()
#define FastIO  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int main ()
{
	FastIO
	lld a, b;
	cin >> a;
	cin >> b;
	if (a >= (2*b))
		cout << (a-(2*b));
	else
		cout << "0";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
long long int gcd(long long int a, long long int b){
	return (b > 0)? gcd(b, a % b) : a ;
}
long long int lcm(long long int a, long long int b){
	return a / gcd(a, b) * b;
}
int main(){
long long int N, M; 
string S, T; 
cin >> N >> M >> S >> T; 
long long int G, L; 
G = gcd(N, M); 
L = lcm(N, M); 
string ans = "Yes"; 
for(long long int i = 0; i < G; i++){
if(S.at(i * N/G) != T.at(i * M/G)){
ans = "No"; 
break; 
}
}
if(ans == "No"){
cout << -1 << endl; 
}
else if(ans == "Yes"){
cout << L << endl; 
}
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int INF = 1e9+7;
int mod = 1e9+7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
signed main() {
    int N,M;
    cin >> N >> M;
    vector<vector<int>>A(N,vector<int>(M));
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> A[i][j];
            A[i][j]--;
        }
    }
    vector<bool>ok(M,true);
    int ans = INF;
    int X = M;
    while(X--) {
        vector<P>cnt = {{0,0}};
        map<int,int>Mp;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if(ok[A[i][j]]) {
                    Mp[A[i][j]]++;
                    goto home;//gotoキャンペーン！！
                }
            }
        home:;
        }
        for(P x:Mp) {
            cnt.push_back({x.second,x.first});
        }
        sort(cnt.rbegin(),cnt.rend());
        ans = min(ans,cnt[0].first);
        ok[cnt[0].second] = false;
    }
    cout << ans << endl;
}


Measured memory_bytes: 4300
n = int(input())
h = list(map(int, input().split()))

ans = abs(h[1] - h[0])
l, ll = ans, 0

for i in range(2,n):
    ans = min(l + abs(h[i] - h[i-1]), ll + abs(h[i] - h[i-2]))
    l, ll = ans, l

print(ans)

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

using namespace std;

const int MAX_H = 8, MAX_W = 8;

int h, w;

char a[MAX_H + 1][MAX_W + 1];

bool canRight(int i, int j) {
    return j < w && a[i][j + 1] == '#';
}

bool canDown(int i, int j) {
    return i < h && a[i + 1][j] == '#';
}

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

    cin >> h >> w;

    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> a[i][j];
        }
    }

    int counter = 0;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            if (a[i][j] == '#') {
                counter++;
            }
        }
    }

    if (counter != h + w - 1) {
        cout << "Impossible" << endl;

        return 0;
    }

    int i = 1, j = 1;
    while (i < h && j < w) {
        if (canRight(i, j) && canDown(i, j)) {
            cout << "Impossible" << endl;

            return 0;
        }

        if (!canRight(i, j) && !canDown(i, j)) {
            cout << "Impossible" << endl;

            return 0;
        }

        if (canRight(i, j)) {
            j++;

            continue;
        }

        if (canDown(i, j)) {
            i++;

            continue;
        }
    }

    cout << "Possible" << endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.*;

class Main{
    public static void main(String[] args){
        int n, j, sum = 0, min = 0;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for(int i = 1; i < n; i++){
            j = n - i;
            //System.out.println(i + ", " + j + ", ");
            sum = sumDigits(i) + sumDigits(j);
            if(i == 1){
                min = sum;
            }
            if(min > sum){
                min = sum;
            }

        }
        System.out.println(min);
    }
    static public int sumDigits(int n){
        int sum = 0;
        while(n != 0){
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }
}

Measured memory_bytes: 21844
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int cycle, number_of_biscuits, time;
    cycle = Integer.parseInt(sc.next());
    number_of_biscuits = Integer.parseInt(sc.next());
    time = Integer.parseInt(sc.next());
    System.out.println(time / cycle * number_of_biscuits);
  }
}


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

#define endl "\n"

#define ll long long


int main(){
    //enable fast I/O
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int arr[5];
    for(int i=0; i<5; i++)
        cin >> arr[i];

    int result = 0;
    for(int i=0; i<5; i++)
        if(arr[i] == 0)
            result = i+1;
    
    cout << result << endl;
    

    return 0;
}

Measured memory_bytes: 3644
<?php
  
$ab = explode(' ', trim(fgets(STDIN)));
$a = $ab[0];
$b = $ab[1];
 
$c = 0;
$p = 1;
while($p<$b){
  $p--;
  $p += $a;  
  $c++;
  if ($p >= $b) break;
}
 
echo $c;
  
?>

Measured memory_bytes: 4604
#include<bits/stdc++.h>
#define rep(i,n) for (ll i=0; i<(n); i++)
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;

struct UnionFind {
    //自身が親であれば、その集合に属する頂点数に-1を掛けたもの
    //そうでなければ親のid
  vector<int> r;
 
  UnionFind(int N) {
    r = vector<int>(N, -1);
  }
 
  ll root (ll x) {
    if (r[x] < 0) return x;
    return r[x] = root(r[x]);
  }
 
  void unite (ll x, ll y) {
    x = root(x);
    y = root(y);
    if (x == y) return;
    if (r[x] > r[y]) swap(x, y);
    r[x] += r[y];
    r[y] = x;
  }
 
  ll size (ll x) {
    return -r[root(x)];
  }
};

int main() {
  ll n, m;
  cin >> n >> m;
  
  UnionFind uf(n);
  
  rep(i,m) {
    ll a, b;
    cin >> a >> b;
    a--; b--;
    uf.unite(a,b);
  }
  ll ans = 0;
  rep(i,n) ans = max(uf.size(i), ans);
  cout << ans << endl;
}

Measured memory_bytes: 4052
import sys
import bisect
input = sys.stdin.readline

def cumsum(inlist):
    s = 0
    outlist = []
    for i in inlist:
        s += i
        outlist.append(s)
    return outlist
    
oneday = 86400 
time = [ 0 for i in range(oneday) ]
n = int(input())
t = 0
for i in range(n):
    a, b = [ int(v) for v in input().split() ]
    t = (t+a) % oneday
    time[t] += 1
    t = (t+b) % oneday

time = time * 2
timesum = cumsum(time)

ans_list = []
for i in range(oneday*2-20000):
    ans_list.append(timesum[i+10801] - timesum[i])
print(max(ans_list))


Measured memory_bytes: 55588