akhauriyash/Code-Regression huggingface dataset:
cnt=0
while True:
    cnt+=1
    W=int(input())
    if W==0:
        break
    n=int(input())
    dp=[0]*(W+1)
    for i in range(n):
        v,w=map(int,input().split(','))
        for j in range(W,w-1,-1):
            dp[j]=max(dp[j],dp[j-w]+v)
    wgt=0
    md=max(dp)
    for i in range(W+1):
        if md==dp[i]:
            wgt=i
            break
    print("Case {0}:".format(cnt))
    print(md)
    print(wgt)

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

using namespace std;
 
int main()
{
  int n;
  cin>>n;
  int h[n];
  for(int i=0 ; i<n ; i++)
    cin>>h[i];
  
  int dp[n+1];
  dp[0]=0;
  dp[1]=0;
  dp[2]=abs(h[0]-h[1]);
  
  for(int i=3 ; i<=n; i++)
  {
    dp[i]=min( dp[i-2]+abs(h[i-1]-h[i-3]) , dp[i-1]+abs(h[i-1]-h[i-2]) ) ;
  }
  
  cout<<dp[n];
  return 0;
}

Measured memory_bytes: 4328
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int Inf = 2000000010;
constexpr ll INF= 2000000000000000000;
constexpr ll MOD = 1000000007;
const double PI = 3.1415926535897;
typedef pair<int,int> P;

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

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

ll mod(ll val) {
    ll res = val % MOD;
    if(res < 0) {
        res += MOD;
    }
    return res;
}

// N^P mod M（ただしM == -1の時はmodを取らない）
template<typename T>
T RS(T N, T P, T M){
    if(P == 0) {
        return 1;
    }
    if(P < 0) {
        return 0;
    }
    if(P % 2 == 0){
        ll t = RS(N, P/2, M);
        if(M == -1) return t * t;
        return t * t % M;
    }
    if(M == -1) {
        return N * RS(N,P - 1,M);
    }
    return N * RS(N, P-1, M) % M;
}

int dp[5050][5050];

int main() {
    int N;
    cin >> N;
    string S;
    cin >> S;
    for(int i = 0;i <= N;i++) {
        dp[N + 1][0] = 0;
        dp[0][N + 1] = 0;
    }
    for(int i = N;i >= 1;i--) {
        for(int j = N;j >= 1;j--) {
            if(S.at(i - 1) == S.at(j - 1)) {
                dp[i][j] = dp[i + 1][j + 1] + 1;
            }
            else {
                dp[i][j] = 0;
            }
        }
    }
    int ret = 0;
    for(int i = 1;i <= N;i++) {
        for(int j = i;j <= N;j++) {
            int cnt = min(dp[i][j],j - i);
            ret = max(ret,cnt);
        }
    } 
    cout << ret << endl;
}  

Measured memory_bytes: 102252
import sys
from collections import deque
input_lines = sys.stdin.readlines()

doublyLinkedList = deque()


for x in input_lines[1:]:
    oneLine = x.split()
    if 'insert' in oneLine[0]:
        doublyLinkedList.appendleft((int)(oneLine[1]))
    elif 'delete' == oneLine[0]:
        remove_value = (int)(oneLine[1])
        if remove_value in doublyLinkedList:
            doublyLinkedList.remove(remove_value)
    elif 'deleteFirst'in oneLine[0]:
        doublyLinkedList.popleft()
    elif 'deleteLast' in oneLine[0]:
        doublyLinkedList.pop()

print(*doublyLinkedList)

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

using namespace std;

int main() {
    int a,b,c,d,e,k;
    cin>>a>>b>>c>>d>>e>>k;

    vector<int> pos;
    pos.push_back(a);
    pos.push_back(b);
    pos.push_back(c);
    pos.push_back(d);
    pos.push_back(e);

    for (int i=0;i<pos.size();i++) {
        for (int j=0;j<pos.size();j++) {
            int d = pos[j] - pos[i];
            if (d>k) {
                cout << ":(" << endl;
                return 0;
            }
        }
    }

    cout << "Yay!" << endl;

    
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        
        int X = sc.nextInt();
        int A = sc.nextInt();
        
        if(X < A)   System.out.println(0);
        else    System.out.println(10);
    }
}


Measured memory_bytes: 21716
#define _USE_MATH_DEFINES
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;

int main() {
  int n;
  scanf("%d", &n);
  vector<int> a;
  for (int i = 1; i <= n; ++i) {
    int x;
    scanf("%d", &x);
    if (x == i) a.push_back(i);
  }
  int ret = 0;
  n = a.size();
  for (int i = 0; i < n; ) {
    if (i + 1 < n && a[i] + 1 == a[i + 1]) {
      ret += 1;
      i += 2;
    } else {
      ret += 1;
      i += 1;
    }
  }
  printf("%d\n", ret);
  return 0;
}


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

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

  vector<int> a(k);
  for (auto &i : a) cin >> i;
  reverse(a.begin(), a.end());

  int64_t mina = 2, maxa = 2;
  for (int i = 0; i < k; ++i) {
    mina = (mina + a[i] - 1) / a[i] * a[i];
    maxa = maxa / a[i] * a[i] + a[i] - 1;
    if (mina > maxa) {
      cout << -1 << endl;
      return 0;
    }
  }

  cout << mina << " " << maxa << endl;
}


Measured memory_bytes: 640
#include <iostream>
#include <string>
using namespace std;
int main(){
        int k, s;
        int x, y, z;
        int ans = 0;
        cin >> k >> s;
        for (x = 0; x <= k; x++) {
                for (y = 0; y <= k; y++) {
                        int z = s - x - y;
                        if(z >= 0 && z <= k) {
                                ans++;
                        }
                }
        }
        cout << ans << endl;
        return 0;
}

Measured memory_bytes: 256
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
 
#include<bits/stdc++.h>
 
using namespace std;
#define ll long long
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define ull unsigned long long
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define ff first
#define ss second
#define fast ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0); 
#define nl "\n"
#define sz(a) (int)(a).size() 
#define all(a) (a).begin(),(a).end()
#define fl(a,x) memset(a,x,sizeof(a));
#define pt(a,x) cout << get<x>(a) << " " ;  
#define mt make_tuple 
#define vec vector
 
#define int long long 
 
const int mod = (int) 1e9 + 7 ;
const int MOD = (int) 998244353 ;
const int INF = (int) 1e18 ;
 
typedef vector<int> vii;
typedef pair<int,int> pii;
typedef vector<pii> vpi;
typedef vector<vector<int> > vv;
 
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
 
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}

const int N = 1e2 + 5;
const int W = 1e5 + 5; 
int dp[N][W] , a[2][N];

void solve(int test) {
	int n ,w ; cin >> n >> w ;
	rep(i,0,n) cin >> a[0][i] >> a[1][i] ;

	dp[0][a[0][0]] = a[1][0] ;

	rep(i,1,n) {
		rep(j,0,w+1) dp[i][j] = dp[i-1][j] ;
		for(int j = w-a[0][i] ; j >=0 ; --j) 
			if(dp[i][j]) {
				dp[i][j + a[0][i]] = max(dp[i][j+a[0][i]],dp[i][j] + a[1][i]);
			}
		dp[i][a[0][i]] = max(dp[i][a[0][i]], a[1][i]) ;
	}

	int ans = 0 ;
	rep(i,0,w+1) ans = max(ans, dp[n-1][i]);

	cout << ans ;
}
 
int32_t main() {


    fast;
	int t=1;
	// cin>>t;
	rep(i,1,t+1) {
		solve(i) ;
	}
 
	// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}

Measured memory_bytes: 80924
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <sstream>

using namespace std;

inline int toInt(string s) { stringstream ss(s); int x; ss >> x; return x; }

int main() {
  int n;
  string s;
  cin >> n;
  for(int i=0; i<n; i++) {
    cin >> s;
    int sh = toInt(s.substr(0, 2));
    int lg = toInt(s.substr(3));
    double argSh = sh*5*6;
    double argLg = lg*6; argSh += argLg/12;
    
    double hen = abs(argSh-argLg);
    hen = min(hen, 360.0-hen);
    if(0<=hen && hen<30) cout << "alert" << endl;
    else if(90<=hen && hen) cout << "safe" << endl;
    else cout << "warning"<< endl;
  }
  
  return 0;
}

Measured memory_bytes: 1212
#include <iostream>
#include <cstdio>
#define N 200005
using namespace std;

typedef long long ll;
ll n, k, L, ans, s1[N], s2[N], a[N];
int main()
{
	ll i, j, t1, t2, t3, s;
	cin >> L >>  n;
	for (i = 1; i <= n; i++ ) {
		scanf ("%lld", &a[i]);
		s1[i] = s1[i - 1] + a[i];
	}
	for (i = n; i >= 1; i--) s2[i] = s2[i + 1] + (L - a[i]);
	for (i = 1; i <= n; i++) {
		s = min(i - 1, n - i);
		t1 = (s1[i - 1] - s1[i - 1 - s]) * 2;
		t2 = (s2[i + 1] - s2[i + 1 + s]) * 2;
		t3 = max(a[i], L - a[i]);
		ans = max(ans, t1 + t2 + t3);
	}
	for (i = 1; i < n; i++) {
		s = min(i, n - i);
		t1 = (s1[i] - s1[i - s]) * 2;
		t2 = (s2[i + 1] - s2[i + 1 + s]) * 2;
		t3 = min(a[i], L - a[i + 1]);
		ans = max(ans, t1 + t2 - t3);
	}
	cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4992
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<unordered_map>
#include<array>
#include<map>
#include<bitset>
#include<iomanip>
#include<list>
using namespace std;
typedef unsigned long long int ulint;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define RE return 0
//ios::sync_with_stdio(false);
//std::cin.tie(0);
//<< setprecision(20)
const int mod=1e9+7;
const llint big=1e15+100;
const long double pai=3.141592653589793238462643383279502884197;
const long double ena=2.71828182845904523536;
const long double eps=1e-7;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
template <class T> void soun(T& ar)
{sort(ar.begin(),ar.end());ar.erase(unique(ar.begin(),ar.end()),ar.end());}
llint gcd(llint a,llint b){if(a%b==0){return b;}else{return gcd(b,a%b);}}
llint lcm(llint a,llint b){return a/gcd(a,b) *b;}
template<class T,class U> auto LB(T& ve,U in){return lower_bound(ve.begin(),ve.end(),in);}
template<class T,class U> auto UB(T& ve,U in){return upper_bound(ve.begin(),ve.end(),in);}
template<class T,class U> auto LBI(T& ve,U in){return LB(ve,in)-ve.begin();}
template<class T,class U> auto UBI(T& ve,U in){return UB(ve,in)-ve.begin();}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
int main(void){
	int a,b;cin>>a>>b;cout<<(a+b+1)/2<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  // AGC015A - A+...+B Problem
  // A > Bのとき0
  // N = 1のとき、A == Bであれば1、A != Bであれば0
  // それ以外のとき、(N-1)*A+B以上、A+(N-1)*B以下の数は全て作ることができる
  // A+(N-1)*B - {(N-1)*A+B} + 1
  ll N, A, B; cin >> N >> A >> B;
  if(A > B){
    cout << 0 << endl;
    return 0;
  }
  if(N == 1){
    if(A == B){
      cout << 1 << endl;
      return 0;
    }
    if(A != B){
      cout << 0 << endl;
      return 0;
    }
  }
  cout << A+(N-1)*B - ((N-1)*A+B) + 1 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int ch[100000];
deque<int> pr;
llong P1[500];
llong P2[500];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	for (int i = 2; i < 100000; ++i) {
        if (ch[i]) continue;
        pr.push_back(i);
        for (llong j = (llong)i * i; j < 100000; j += i) ch[j] = 1;
	}
        
	int n;
	cin >> n;
	if (n == 2) {
        printf("4 7\n23 10\n");
        return 0;
	}
	for (int i = 0; i <= ((n + n - 2) >> 1); ++i) {
        P1[i] = pr.front();
        pr.pop_front();
	}
	for (int i = 0; i <= ((n + n - 2) >> 1); ++i) {
        P2[i] = pr.front();
        pr.pop_front();
	}
	for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if ((i + j) & 1) {
                int x = (i + j), y = (i - j + (n - 1));
                llong ret = 1;
                if (x > 0) ret *= P1[x - 1 >> 1];
                if (x + 1 <= n + n - 2) ret *= P1[x + 1 >> 1];
                if (y > 0) ret *= P2[y - 1 >> 1];
                if (y + 1 <= n + n - 2) ret *= P2[y + 1 >> 1];
                printf("%lld", ret + 1);
                //if (ret > 1e15) { printf("%lld\n", ret); }
            }
            else {
                printf("%lld", P1[i + j >> 1] * P2[i - j + (n - 1) >> 1]);
            }
            if (j + 1 < n) printf(" ");
            else printf("\n");
        }
	}
	return 0;
}


Measured memory_bytes: 3584
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


template<typename T>
struct BIT{
  Int n;
  vector<T> bit;
  //1-indexed
  BIT():n(-1){}
  BIT(Int n_,T d):n(n_),bit(n_+1,d){}

  T sum(Int i){
    T s=bit[0];
    for(Int x=i;x>0;x-=(x&-x))
      s+=bit[x];
    return s;
  }
  void add(Int i,T a){
    if(i==0) return;
    for(Int x=i;x<=n;x+=(x&-x))
      bit[x]+=a;
  }
};


template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}

//INSERT ABOVE HERE
signed main(){
  Int n,k;
  cin>>n>>k;
  vector<Int> ps(n);
  for(Int i=0;i<n;i++) cin>>ps[i];

  if(n==k){
    vector<Int> vs;
    for(Int p:ps) vs.emplace_back(p);
    for(Int p:ps) vs.emplace_back(p);

    for(Int i=0;i<n;i++){
      if(vs[i]!=1) continue;
      Int flg=1;
      for(Int j=0;j<n;j++)
        flg&=vs[i+j]==j+1;
      cout<<(flg?"Yes":"No")<<endl;
      break;
    }
    return 0;
  }

  if(k%2==0) drop("Yes");

  BIT<Int> bit(n+10,0);
  Int sum=0;
  for(Int i=0;i<n;i++){
    sum+=i-bit.sum(ps[i]);
    sum%=2;
    bit.add(ps[i],1);
  }
  cout<<(sum?"No":"Yes")<<endl;
  return 0;
}



Measured memory_bytes: 5644
#include <stdio.h>
int main(void){
    // Your code here!
    int a,b,c;
    int i,cnt=0;
    scanf("%d%d%d",&a,&b,&c);
    if(a==5) cnt+=1;
    if(b==5) cnt+=1;
    if(c==5) cnt+=1;
    if(a+b+c==17 && cnt==2)
        printf("YES\n");
    else
        printf("NO\n");
}


Measured memory_bytes: 128
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m = LI()
    a = LI()
    g = 2
    s = set()
    for c in a:
        t = fractions.gcd(g, c)
        g *= c // t
        i = 0
        while c % 2 == 0:
            i += 1
            c //= 2
        s.add(i)

    if len(s) > 1:
        return 0

    g //= 2
    t = (m // g + 1) // 2

    return t


print(main())





Measured memory_bytes: 17540
def main():
    N = int(input())
    P = tuple(map(int,input().split(' ')))
    Q = tuple(map(int,input().split(' ')))
    Pnum = dictNum(P,N)
    Qnum = dictNum(Q,N)
    ans = (abs(Pnum-Qnum))
    print(ans)

def dictNum(A, N):
    ans = 0
    restNum = [1]*N
    for i in range(N):
        restNum[A[i]-1]=0
        ans += count(sum(restNum[:A[i]]),N-i)
    return ans + 1
def count(a,N):
    ans = factorial(N-1)*a
    if N == 1:
        ans = 0
    return ans
def factorial(num):
    if num == 0:
        return 1
    else:
        return num*factorial(num-1)
main()


Measured memory_bytes: 9152
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using pii=pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
#define all(c) begin(c),end(c)
#define rall(c) rbegin(c),rend(c)
#define fore(x,c) for(auto &&x:c)
#define rep(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define rrep(i, a, n) for(int i=(int)(n-1);i>=a;--i)
#define sz(c) ((int)c.size())
#define contains(c,x) (c.find(x)!=end(c))
#define inseg(l,x,r) ((l)<=(x)&&(x)<(r))
#define dump(...)
#define pb push_back
#define _ 0
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    for (auto i = begin(v); i != end(v); i++) os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    for (auto i = begin(v); i != end(v); i++) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template <class T> void psum(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(nullptr); ios::sync_with_stdio(0);
        cout << setprecision(15) << fixed;
        // #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int N, M, P;
    cin >> N >> M >> P;
    vector<tuple<int, int, int>> E(M);
    vvi G(N), rG(N);
    vector<bool> vis1(N, false), vis2(N, false);
    rep(i, 0, M) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        E[i] = make_tuple(a, b, -c + P);
        G[a].push_back(b);
        rG[b].push_back(a);
    }
    auto dfs = [](auto fun, int v, const auto &graph, auto &vis) -> void {
        vis[v] = true;
        for (auto w : graph[v]) {
            if (vis[w]) continue;
            fun(fun, w, graph, vis);
        }
    };
    dfs(dfs, 0, G, vis1);
    dfs(dfs, N - 1, rG, vis2);

    vector<int> d(N, INF);
    d[0] = 0;
    rep(i, 0, N + 1) {
        bool updated = false;
        rep(j, 0, M) {
            int a, b, c;
            tie(a, b, c) = E[j];
            if (vis1[a] && vis2[a] && vis1[b] && vis2[b]) {
                if (chmin(d[b], d[a] + c)) {
                    updated = true;
                }
            }
        }
        if (updated && i == N) {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << max(0LL, -d[N - 1]) << endl;
    return (0^_^0);
}



Measured memory_bytes: 768
#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
const int N=1e5+5;
int dp[N],h[N];
int main(){
	int n,i;
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>h[i];
	}
	dp[2]=abs(h[2]-h[1]);
	for(i=3;i<=n;i++){
		dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i-2]-h[i]));
	}
	cout<<dp[n];
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 int N,M;
  cin >> N >> M;
  vector<int> number(N,0);
  int a,b;
  for(int i=0;i<M;i++){
    cin >> a >> b;
    number.at(a-1)++;
    number.at(b-1)++;
  }
  for(int i=0;i<N;i++){
    cout << number.at(i) << endl;
}
}

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

#define PI 3.1415926535897932
#define MOD 1000000007
#define INF 2e9

#define REP(i, n) for(int i = 0; i < (n); i++)
#define REP1(i, n) for(int i = 1; i <= (n); i++)
#define FOR(i, start, end) for(int i = (start); i < (end); i++)
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef vector<bool> vb;


void solve()
{
    int N; cin >> N;
    vi a(N+1); REP1(i, N) cin >> a[i];
    vb pressed(N+1, false);

    int button = 1;
    int ans = 0;
    while(button != 2)
    {
        if(pressed[a[button]] == true)
        {
            cout << -1 << endl;
            return;
        }
        pressed[button] = true;
        button = a[button];
        ans++;
    }

    cout << ans << endl;
}

int main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();

    return 0;
}

Measured memory_bytes: 640
#pragma GCC optimize("Ofast")
#include  "bits/stdc++.h"
using namespace std;
#define I_AM_SPEED  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
#define printclock  cerr <<"Time : "<<(double)clock()/(double)CLOCKS_PER_SEC<<" sec\n";
#define mp(a , b)   make_pair(a , b)
#define eb(a)       emplace_back(a)
#define anal         '\n'
#define mod 1000000007
#define fst first
#define sec second
//const double PI = acos(-1.0);
typedef long long ll;
typedef unsigned long long ull;

//_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-
  
//_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-
    
int main(){
I_AM_SPEED;
#ifndef ONLINE_JUDGE  
      freopen("input.in", "r", stdin);
      freopen("output.in", "w", stdout);
#endif 

//_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-
    
        int n;
        cin >> n;
        string  a, b, c, d;
        a = "AC";
        b = "WA";
        c = "TLE";
        d = "RE";
        int an = 0, bn = 0, cn = 0, dn = 0;
        while(n--){
             string s;
             cin >> s;
             if(s == a){
                  an++;
             }
             else if(s == b){
                 bn++;
             }
             else if(s == c){
                 cn++;   
             }
             else if(s == d){
                 dn++;   
             }
        }
        cout << a  << " x " << an << anal;
        cout << b  << " x " << bn << anal;
        cout << c  << " x " << cn << anal;
        cout << d  << " x " << dn << anal;

//_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-
//printclock; 
return  0 ;      
}        



   

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

int main()
{
    vector<char> vc(4);
    for(int i = 0; i < 4; i++) cin >> vc[i];
    sort(vc.begin(),vc.end());
    if(vc[0]==vc[1] && vc[2]==vc[3] && vc[0]!=vc[2]) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
x, k , d = map(int, input().split())
y = abs(x)
count = y // d
e = y % d
f = abs(e-d)
if e > f:
    min1 = f
    min2 = e
    count += 1
else:
    min1 = e
    min2 = f
if count > k:
    print(y - d * k)
else:
    if (k - count)%2 == 0:
        print(min1)
    else:
        print(min2)

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

int main()
{
    int N, K;
    std::cin >> N >> K;

    std::vector<std::string> D(K);
    for (auto& d : D) {
        std::cin >> d;
    }

    for (int i = N; i <= 10 * N; i++) {
        bool found = false;
        for (const auto d : D) {
            if (std::to_string(i).find(d) != std::string::npos) {
                found = true;
                break;
            }
        }

        if (not found) {
            std::cout << i << '\n';
            return 0;
        }
    }

}

Measured memory_bytes: 3668
def read_int():
    return int(input())

def read_int_map():
    return map(int,input().split(' '))

def read_int_list():
    return list(map(int,input().split(' ')))

def read_s_list_loop(n):
    return [input() for _ in range(n)]


K = read_int()
A,B = read_int_map()
for i in range(A,B+1):
    if i%K == 0:
        print('OK')
        exit(0)
print('NG')

Measured memory_bytes: 61716
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<bitset>
#include<unordered_map>
#include<climits>
#include<fstream>
using namespace std;
///////////////////library zone!!!!!!!!!!!!!!!!!!!!!!!!!!!!
typedef long long ll;
typedef long double ld;
#define all(a) (a).begin(),(a).end()
const ll Mod = 1000000007;
const ll mod = 998244353;
struct H {
	ll x, y;
	bool operator<(const H &b) const {
		if (x != b.x) return x < b.x;
		return y < b.y;
	}
	bool operator>(const H &b) const {
		if (x != b.x) return x > b.x;
		return y > b.y;
	}
	bool operator==(const H &b) const { return x == b.x&&y == b.y; }
	bool operator!=(const H &b) const { return (*this) != b; }
};
struct P {
	ll pos, cost;
	bool operator<(const P &b) const { return cost < b.cost; }
	bool operator>(const P &b) const { return cost > b.cost; }
};
struct B {
	ll to, cost;
};
struct E {
	ll from, to, cost;
	bool operator<(const E &b) const { return cost < b.cost; }
	bool operator>(const E &b) const { return cost > b.cost; }
};
template<typename T, typename U>
void chmin(T &a, U b) {
	if (a > b) a = b;
}
template<typename T, typename U>
void chmax(T &a, U b) {
	if (a < b) a = b;
}
template<typename T>
T max_0(T a) {
	if (a < 0) return 0;
	return a;
}
template<typename T>
T min_0(T a) {
	if (a > 0) return 0;
	return a;
}
ll read() {
	ll u;
	scanf("%lld", &u);
	return u;
}
ll gcd(ll i, ll j) {
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcd(j%i, i);
}
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % p;
		x = x * x % p;
		n >>= 1;
	}
	return res;
}//x^n%p
const ll Inf = 3023372036854775807;
const int inf = 1500000000;
#define int long long
//----------------------------------------------------

signed main() {
	int x, y;
	cin >> x >> y;
	cout << x * y << " " << (x + y) * 2 << endl;
}


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

int main(){
    int n,ans=0;
    cin>>n;

    vector<int> v(n);
    for(int i=0; i<n; i++){ 
        cin>>v.at(i);
    }

    for(int i=0; i<n; i++){ 
        int c;
        cin>>c;
        if(v.at(i)-c>0) ans+=v.at(i)-c;
    }

    cout<<ans<<endl;
}


Measured memory_bytes: 256
N=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
anum=0
bnum=0
equalflag=0
for i in range(N):
    if a[i]>b[i]:   #bを嵩上げしないと
        bnum=bnum+(a[i]-b[i])
    elif a[i]<b[i]:#aを嵩上げしないと
        if (b[i]-a[i])%2==0:    #差が2nならaをn回嵩上げ
            anum=anum+(b[i]-a[i])//2
        else:                   #差が2n+1ならbを一回嵩上げしてからaをn+1回嵩上げ
            bnum=bnum+1
            anum=anum+((b[i]+1)-a[i])//2
if N!=1:
    if anum>=bnum:
        print("Yes")
    else:
        print("No")
else:
    if anum==bnum:
        print("Yes")
    else:
        print("No")

Measured memory_bytes: 40944
A = gets.to_i
B = gets.to_i
C = gets.to_i
X = gets.to_i

count = 0

(A + 1).times do |i|
  (B + 1).times do |j|
    (C + 1).times do |k|
      if i * 500 + j * 100 + k * 50 == X
        count += 1 
      end
    end
  end
end

puts count

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

int main() {
  for(int N; cin >> N && N; ) {
    int res = 0;
    for(int i = 1; i <= N; ++i) {
      int sum = i + i + 1;
      for(int j = i + 1; sum < N; sum += ++j);
      res += sum == N;
    }
    cout << res << endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
 //Compiler version g++ 6.3.0

 int main()
 {
 	int n,m;
 	cin >> n>>m;
 	cout << n*n-m << endl;
 }

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;
 
int main() {
    ll n, m, L;
    cin >> n >> m >> L;    
    
    vector<vector<P>> G(n);  // 辺の重みがすべて0以上のグラフ
    rep(i, m) {
        ll a, b, c;
        cin >> a >> b >> c;
        a--;  b--;
        G[a].pb(make_pair(b, c));
        G[b].pb(make_pair(a, c));
    }
    
    // 拡張ダイクストラ法。計算量はO((V+E)*log(V))
    vector<vector<P>> dp(n, vector<P>(n, make_pair(INF, INF)));  // dp[sv][v] : (頂点svから頂点vへの補給回数の最小値, そのとき満タンの状態から使用した燃料量)
    rep(sv, n) {
        dp[sv][sv] = make_pair(0, 0);
        priority_queue<pair<P, ll>, vector<pair<P, ll>>, greater<pair<P, ll>>> prQ;
        prQ.push(make_pair(make_pair(0, 0), sv));  // ((補給回数kaisuu, 満タンの状態から使用した燃料量used), いまいる頂点v)
        while(!prQ.empty()) {
            auto p1 = prQ.top();
            prQ.pop();
            ll v = p1.second;
            ll kaisuu = p1.first.first;
            ll used = p1.first.second;
            if(dp[sv][v] < p1.first) {
                continue;
            }
            for(auto p2 : G[v]) {
                ll u = p2.first;
                ll cost = p2.second;
                if(cost > L) {
                    continue;
                }
                P np;
                if(used + cost > L) {
                    np = make_pair(kaisuu + 1, cost);
                }
                else {
                    np = make_pair(kaisuu, used + cost);
                }
                if(dp[sv][u] > np) {
                    dp[sv][u] = np;
                    prQ.push(make_pair(np, u));
                }
            }
        }
    }
    
    ll q;
    cin >> q;
    vl ans(q);
    rep(i, q) {
        ll sv, gv;
        cin >> sv >> gv;
        sv--;  gv--;
        if(dp[sv][gv].first == INF) {
            ans[i] = -1;
        }
        else {
            ans[i] = dp[sv][gv].first;
        }
    }
 
    rep(i, q) {
        out(ans[i]);
    }
 
    re0;
}

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

const ll INF = 1001001001;

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

ll f(ll x){
  if(x==0) return 0;
  else if(x==1) return 1;
  return x*f(x-1);
}

int zetai(int y,int z ){
  if(y>=z) return y-z;
  else return z-y;
}

//再起関数でとく

int main(){
  ll n,m;
  cin>>n>>m;
  vector<ll>h(n);
  rep(i,n){
    cin>>h[i];
  }
  vector<ll>a(m);
  vector<ll>b(m);
  rep(i,m){
    cin>>a[i]>>b[i];
  }
  vector<ll>vec(n,1);
  rep(i,m){
    if(h[a[i]-1]==h[b[i]-1]){
      vec[a[i]-1]=0;
      vec[b[i]-1]=0;
    }else if(h[a[i]-1]>h[b[i]-1]){
      if(vec[a[i]-1]!=0){
        vec[a[i]-1]=2;
      }
      vec[b[i]-1]=0;
    }else{
      if(vec[b[i]-1]!=0){
        vec[b[i]-1]=2;
      }
      vec[a[i]-1]=0;
    }
    



    
  }
  ll count=0;
  rep(i,n){
    if(vec[i]==2 || vec[i]==1){
      count++;
    }
  }
  cout<<count<<endl;

  
  
  return 0;
}



Measured memory_bytes: 6428
N = int(input())
P = list(map(int,input().split()))
Q = list(map(int,input().split()))

def kaijou(n):
    ans = 1
    while n > 0:
        ans *= n
        n -= 1
    return ans

def calc(misiyou, num, cnt, x):
    if cnt == len(num):
        return x
    else:
        siyou = num[cnt]
        ind = misiyou.index(siyou)
        misiyou.remove(siyou)
        misiyou2 = misiyou.copy()
        x2 = x + (kaijou(len(misiyou2)-1))*(ind-1)
        return calc(misiyou2, num, cnt+1, x2)

lis1 = [i for i in range(N+1)]
a = calc(lis1, P, 0, 1)
lis2 = [i for i in range(N+1)]
b = calc(lis2, Q, 0, 1)
print(abs(a-b))


Measured memory_bytes: 9024
n,m = map(int,input().split())
ans = ['Yes'] * m
for i in range(n):
    k = list(map(int,input().split()))
    k.pop(0)
    for i in range(m):
        if not i + 1 in k:
            ans[i] = 'No'
print(ans.count('Yes'))

Measured memory_bytes: 9104
(* O(n) *)
let n = Scanf.scanf " %d" @@ (+) 0
let a1s = Array.init n @@ fun _ -> Scanf.scanf " %d" @@ (+) 0
let a2s = Array.init n @@ fun _ -> Scanf.scanf " %d" @@ (+) 0
let c1, c2 = ref 0, ref 0
let acc1 = Array.make (n + 1) 0
let acc2 = Array.make (n + 1) 0
let ans = ref 0
let _ =
  for i = 0 to n - 1 do
    c1 := !c1 + a1s.(i); acc1.(i + 1) <- !c1;
    c2 := !c2 + a2s.(i); acc2.(i + 1) <- !c2
  done;
  for i = 0 to n - 1 do
    ans := max !ans @@ acc1.(i + 1) - acc1.(0) + acc2.(n) - acc2.(i)
  done;
  Printf.printf "%d\n" !ans

Measured memory_bytes: 512
#include <cstdio>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
#include <functional>
#include <complex>

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

const long long MAX = 5100000;
const long long INF = 1LL << 60;
const long long mod = 1000000007LL;
//const long long mod = 998244353LL;

using namespace std;
typedef unsigned long long ull;
typedef long long ll;

vector<vector<ll>> nextchar(string& s) {
	vector<vector<ll>> next(s.size() + 1, vector<ll>(26, INF));
	for (ll i = (ll)s.size() - 1; i >= 0; i--) {
		for (ll j = 0; j < 26; j++) next[i][j] = next[i + 1][j];
		next[i][s[i] - 'a'] = i;
	}
	return next;
}

struct mint {
	ll x; // typedef long long ll;
	mint(ll x = 0) :x((x% mod + mod) % mod) {}
	mint& operator+=(const mint a) {
		if ((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator-=(const mint a) {
		if ((x += mod - a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator*=(const mint a) {
		(x *= a.x) %= mod;
		return *this;
	}
	mint operator+(const mint a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint a) const {
		mint res(*this);
		return res *= a;
	}
	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	// for prime mod
	mint inv() const {
		return pow(mod - 2);
	}
	mint& operator/=(const mint a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint a) const {
		mint res(*this);
		return res /= a;
	}
};

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

	string s; cin >> s;
	string t = s;
	ll n = s.size();
	reverse(t.begin(), t.end());

	vector<vector<mint>> dp(n + 1, vector<mint>(n + 1));
	dp[0][0] = 1;
	vector<vector<ll>> ns = nextchar(s);
	vector<vector<ll>> nt = nextchar(t);
	for (ll i = 0; i < n; i++) {
		for (ll j = 0; j < n; j++) {
			for (ll k = 0; k < 26; k++) {
				ll ni = ns[i][k];
				ll nj = nt[j][k];
				//cout << ni << " " << nj << endl;
				if (ni + nj + 2 > n) continue;
				dp[ni + 1][nj + 1] += dp[i][j];
			}
		}
	}

	mint res = 0;
	for (ll i = 0; i <= n; i++) {
		for (ll j = 0; j <= n; j++) {
			mint cnt = 1;
			for (ll k = 0; k < 26; k++) {
				ll ni = ns[i][k];
				if (ni + j + 1 > n) continue;
				cnt += 1;
			}
			//cout << i << " " << j << " " << dp[i][j].x << " " << cnt.x << endl;
			res += dp[i][j] * cnt;
		}
	}
	res.x -= 1;
	cout << res.x << endl;
	return 0;
}


Measured memory_bytes: 35160
import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int w = Integer.parseInt(st.nextToken());
        int h = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        int xmax = 0;
        int xmin = w;
        int ymax = 0;
        int ymin = h;
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            if (a == 1) {
                xmax = Math.max(xmax, x);
            }
            if (a == 2) {
                xmin = Math.min(xmin, x);
            }
            if (a == 3) {
                ymax = Math.max(ymax, y);
            }
            if (a == 4) {
                ymin = Math.min(ymin, y);
            }
        }
        if(xmin <= xmax || ymin <= ymax)
            System.out.print("0");
       else  System.out.println((xmin - xmax)*(ymin - ymax));
    }
}

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

int main()
{
	int a, b;
	cin >> a >> b;

	int c = min(a, b);
	int d = max(a, b);

	for (int i = 0; i < d; ++i) {
		cout << c;
	}
	cout << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
typedef vector <bool> vb;
typedef vector <long long> vll;
typedef vector <vi> vvi;
typedef vector <vll> vvll;
 
#define all(v) v.begin(),v.end()
#define nl endl
#define bs(v,n) binary_search(v.begin(),v.end(),n)
#define sz() size()
#define pb push_back
#define mp make_pair
 
ll mod=1e9+7;
const int MAX_CHAR = 26; 

void sortString(string &str){
    int charCount[MAX_CHAR] = {0};
    string newstr="";
    for (int i=0;i<str.length();i++)
        charCount[str[i]-'a']++;
    int k=0;
    for (int i=0;i<MAX_CHAR;i++){
        for (int j=0;j<charCount[i];j++){
        	str[k]=(char)('a'+i);
        	k++;
        }
    }
} 

int main() {
	int n;
	cin>>n;
	ll c=0;
	map<string,int> anagram;
	for(int i=0;i<n;i++){
		string S;
		cin>>S;
		sort(all(S));
		c+=anagram[S];
		anagram[S]++;
	}
	cout<<c<<nl;
	return 0;
}

Measured memory_bytes: 11136
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

long long x;

int main() {
    cin >> x;
    long long xx = 100;
    long long cnt = 0;
    while(xx < x) {
        cnt++;
        xx = xx * 1.01;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 3636
#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include <cmath>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#define debug(x) cerr << #x << ':' << x << endl
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define ALL(c) (c).begin(), (c).end()
using namespace std;
typedef long long ll;

const ll M = 1000000007;

vector<ll> fac(300001); //n!(mod M)
vector<ll> ifac(300001); //k!^{M-2} (mod M)
ll mpow(ll x, ll n){ //x^n(mod M) ←普通にpow(x,n)では溢れてしまうため，随時mod計算
    ll ans = 1;
    while(n != 0){
        if(n&1) ans = ans*x % M;
        x = x*x % M;
        n = n >> 1;
    }
    return ans;
}

ll comb(ll a, ll b){ //aCbをmod計算
    if(a == 0 && b == 0)return 1;
    if(a < b || a < 0)return 0;
    ll tmp = ifac[a-b]* ifac[b] % M;
    return tmp * fac[a] % M;
}


ll cnt = 0LL;
void dfs(int ball, int b, int end){
    // cout << ball << " " << end << " " << b<< endl;
    if(b==end){
        if(ball==0)
            cnt++;
        return;
    }

    for(int take=0; take<=ball; take++){
        dfs(ball-take, b+1, end);
    }
}

int main(){
    ll n,blue;
    cin >> n >> blue;
    ll red = n-blue;
    fac[0] = 1LL;
    ifac[0] = 1LL;
    for(ll i = 0LL; i<300000LL; i++){
        fac[i+1] = fac[i]*(i+1) % M; // n!(mod M)
        ifac[i+1] = ifac[i]*mpow(i+1, M-2) % M; // k!^{M-2} (mod M) ←累乗にmpowを採用
    }

    for(ll i=1LL; i<=blue; i++){
        // 青いボールを入れる位置を決定し一個ずつ入れる
        ll p = comb(red+1LL,i) % M;
        ll q = comb(blue-1,i-1) % M;
        cout << (p*q)%M << endl;

        // ll r_blue = blue - i;
        // // r_blue個のボールをi個のグループに分けたい
        // // cout << "a"  << r_blue+1 << "b" << i-1 << endl;

        // ll t = pow(r_blue+1, i-1);
        // t%=M;

        
        // ll fac = 1LL;
        // for(ll a=1; a<=i-1; a++){
        //     fac = (fac*a) % M;
        // }
        // cout << "fac" << fac << " " << t << endl;
        // if(fac!=0){
        //     t/=fac;
        // }
        // // cout << p << "*" << fac << endl;
        // // cout << "p==" << p << "t== " << t << endl;
        // ll ans = (p*t);
        // ans %= M;
        // cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 5624
#include <bits/stdc++.h>
#include <sys/types.h>
#include <unistd.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

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

using ll=long long;
using R=long double;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

template<typename T> vector<T> make_vector(size_t sz){
	return vector<T>(sz);
}

template<typename T,typename... Ts> 
auto make_vector(size_t sz, Ts... ts){
	return vector<decltype(make_vector<T>(ts...))>(sz, make_vector<T>(ts...));
}

template<typename T,typename U,typename... V> 
typename enable_if<is_same<T, U>::value!=0>::type 
fill_value(U &u, const V... v){
	u=U(v...);
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_value(U &u, const V... v){
	for(auto &e:u){
		fill_value<T>(e,v...);
	}
}

const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};

const pid_t pid = getpid();
// Problem Specific Parameter:

map<int, int> memo;

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

	ll ans = 0LL;
	rep(i, n) {
		ans += memo[i - a[i]];
		memo[a[i] + i]++;
	}

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

Measured memory_bytes: 21180
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int main(){
  double xa, ya, ra, xb, yb, rb;
  int n, ans;
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> xa >> ya >> ra >> xb >> yb >> rb;
    double d = sqrt((xb-xa)*(xb-xa)+(yb-ya)*(yb-ya));
    double r = ra + rb;
    
    if(d > r){
      ans = 0;
    }
    else if(d <= r && d >= fabs(ra - rb)){
      ans = 1;
    }else{
      if(max(ra,rb) == ra) ans = 2;
      else ans = -2;
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 3200
// This file is a "Hello, world!" in C++ language by GCC for wandbox.
#include <iostream>
#include <cstdlib>

using namespace std;

int main()
{
    
    int N,K,X,Y;
    // 入力
    cin >> N >> K >> X >> Y;
    
    if (N < K) K = N;
        
    int answer = K*X+(N-K)*Y;
    
    //　出力
    cout << answer << endl;
}

// GCC reference:
//   https://gcc.gnu.org/

// C++ language references:
//   https://cppreference.com/
//   https://isocpp.org/
//   http://www.open-std.org/jtc1/sc22/wg21/

// Boost libraries references:
//   https://www.boost.org/doc/


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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()

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

  string s;
  cin>>s;
  int n=s.size();
  ll answ=0;
  int dw=0;
  for(int i=0;i<n;i++){
    if(s[i]=='W')answ+=i-dw,dw++;
  }
  cout<<answ<<endl;
  return 0;
}


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

using namespace std;

#define ll long long
#define ini(arr, val) memset(arr, (val), sizeof(arr))
#define loop(i,n)  for(ll i=0; i<n; i++)

#define all(a)      (a).begin(),(a).end()
#define exist(s,e)  (s.find(e)!=s.end())
#define dbg(x)  cerr << #x << " is " << x << endl;
#define pt(x) cout<<x<<"\n";

#define mp make_pair
#define pb push_back
#define f first
#define s second


#define inf (int)1e9
#define eps 1e-9
#define PI 3.1415926535897932384626433832795
#define mod 1000000007


#define fast    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define test   int t; cin>>t; while(t--)

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef map<int,int> mii;
typedef set<int> si;

typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<pll> vpll;
typedef vector<vl> vvl;
typedef map<ll,ll> mll;
typedef set<ll> sl;


//////////////////////////////////////////////////////////////////////////////////////////
//                      main starts
//////////////////////////////////////////////////////////////////////////////////////////
int const lmt=1e5+5;



int main(){
    fast
    string s;
	cin>>s;
	ll n = s.length();
	ll  ans=0,prev=0;
	bool flag=0;
	for(int i=0; i<n;){
		if(s[i]=='A' || flag){
			flag=0;
			ll cnt=prev;
			while(i<n && s[i]=='A')cnt++,i++;
			if(i<n-1 && s[i]=='B' && s[i+1]=='C'){
				// dbg(cnt);
				ans+=cnt;
				i+=2;
				if(i<n && s[i]=='A')prev = cnt;
				else if(i+1<n && s[i]=='B' && s[i+1]=='C'){prev=cnt, flag=1;continue;}
				else prev=0;
			}else prev=0;
		}else prev=0,i++;
	}
	cout<<ans<<"\n";
}


/*



*/

Measured memory_bytes: 720
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define vpii vector< pair<int,int> >
#define mii map<int,int>
#define MOD 1000000007
#define fr(i,k,n) for(int i=k;i<n;i++)
#define fl(i,k,n) for(int i=k;i>=n;i--)
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a,b;
  cin>>a>>b;
  cout<<a*b;
return 0;
}
// Problem : A - Multiplication 1
// Contest : AtCoder - AtCoder Beginner Contest 169
// URL : https://atcoder.jp/contests/abc169/tasks/abc169_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)



Measured memory_bytes: 3652