akhauriyash/Code-Regression huggingface dataset:
N, M = [int(x) for x in input().split()]
A = set()

MOD = 10 ** 9 + 7

for _ in range(M):
    A.add(int(input()))

result = {0: 1}

for i in range(1, N+1):

    # 階段が壊れている場合にはそこに行くパターンは無い
    if i in A:
        result[i] = 0

    # それ以外の場合、前の段と前の前の段まで行くパターンを加算した数になる
    else:
        if i - 1 in result:
            min_1 = result[i-1]
        else:
            min_1 = 0
        if i - 2 in result:
            min_2 = result[i-2]
        else:
            min_2 = 0
        result[i] = (min_2 + min_1) % MOD

print(result[N])


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

const int MAX = 38;

int main()
{
	int N;
	cin >> N;
	vector<ll> X(N), Y(N);
	for (int i = 0; i < N; i++) {
		cin >> X[i] >> Y[i];
	}
	bool ng = false;
	ll t = (X[0] + Y[0]) & 1LL;
	for (int i = 0; i < N; i++) {
		if (t != ((X[i] + Y[i]) & 1LL)) {
			ng = true;
		}
	}
	if (ng) {
		cout << -1 << endl;
		return 0;
	}
	vector<ll> d(MAX);
	vector<string> res(N);
	if (t) {
		for (int i = 0; i < MAX; i++) {
			d[i] = 1LL << (ll)i;
		}
		for (int i = 0; i < N; i++) {
			res[i].assign(MAX, ' ');
			ll x = X[i], y = Y[i];
			for (int b = MAX - 1; b >= 0; --b) {
				if (abs(x) > abs(y)) {
					res[i][b] = x >= 0 ? 'R' : 'L';
					x -= x >= 0 ? d[b] : -d[b];
				}
				else {
					res[i][b] = y >= 0 ? 'U' : 'D';
					y -= y >= 0 ? d[b] : -d[b];
				}
			}
			assert(x == 0 && y == 0);
		}
	}
	else {
		d[0] = 1;
		for (int i = 1; i < MAX; i++) {
			d[i] = 1LL << (ll)(i - 1);
		}
		for (int i = 0; i < N; i++) {
			res[i].assign(MAX, ' ');
			ll x = X[i], y = Y[i];
			for (int b = MAX - 1; b >= 0; --b) {
				if (abs(x) > abs(y)) {
					res[i][b] = x >= 0 ? 'R' : 'L';
					x -= x >= 0 ? d[b] : -d[b];
				}
				else {
					res[i][b] = y >= 0 ? 'U' : 'D';
					y -= y >= 0 ? d[b] : -d[b];
				}
			}
			assert(x == 0 && y == 0);
		}
	}
	int m = d.size();
	cout << m << endl;
	for (int i = 0; i < m; i++) {
		cout << d[i] << " \n"[i + 1 == m];
	}
	for (int i = 0; i < N; i++) {
		cout << res[i] << endl;
	}
	return 0;
}


Measured memory_bytes: 384
/*input
100000 100000
*/
#include <bits/stdc++.h>
using namespace std;
const long long md=1e9+7;
unordered_map<long long,long long> mp[100005];
long long fac[100005];
long long ncr(long long n, long long r){
	if(mp[n].find(r)!=mp[n].end()) return mp[n][r];
	if(r < 0 or r > n) return 0;
	if(!r) return 1;
	return mp[n][r]=(ncr(n-1,r-1)+ncr(n-1,r))%md;
}
int main(){
	ios_base::sync_with_stdio(0);
	long long n,m;
	cin>>n>>m;
	if(n<m) swap(n,m);
	if(n>m+1) return cout<<0,0;
	fac[0]=1;
	for(int i=1;i<100005;++i) fac[i]=i*fac[i-1]%md;
	long long ans=1;
	if(n==m){
		ans=fac[n]*fac[m]%md*2%md;
	}	
	else{
		ans=fac[n]*fac[m]%md;
	}
	cout<<ans;
}

Measured memory_bytes: 6528
#include<stdio.h>
int main(void)
{
	int x,y,i,z,w,p;
	scanf("%d%d",&x,&y);
	for(i=0;i<y;i++){
		scanf("%d%d",&z,&w);
		if(p%2==1){
			p=x/2+1;
		}
		else{
			
			p=x/2;
		}
		if(z>p){
			z=x-z+1;
		}
		if(w>p){
			w=x-w+1;
		}
		if(z<w){
			if(z%3==0){
				printf("3\n");
			}
			else{
				printf("%d\n",z%3);
			}
		}
		else{
			if(w%3==0){
				printf("3\n");
			}
			else{
				printf("%d\n",w%3);
			}
		}
	}
}


Measured memory_bytes: 2720
a = gets.chomp.chars
d = []

["", "+"].repeated_permutation(a.size-1).each{|i|
	x = ""
	i.size.times{|j|
		x += a[j]
		x += i[j]
	}
	x += a.last
	d.push(x)
}

p d.map {|i| eval(i)}.inject(:+)

Measured memory_bytes: 2044
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
//using System.Text;
//using System.Text.RegularExpressions;
//using System.Globalization;
//using System.Diagnostics;
using static System.Console;
//using System.Numerics;
//using static System.Math;
//using pair = Pair<int, int>;

class Program
{
    static void Main()
    {
        //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        new Program().solve();
        Out.Flush();
    }
    Scanner cin = new Scanner();
    readonly int[] dd = { 0, 1, 0, -1, 0 }; //→↓←↑
    readonly int mod = 1000000007;
    void chmax<T>(ref T a, T b) where T : IComparable<T> { a = a.CompareTo(b) < 0 ? b : a; }
    void chmin<T>(ref T a, T b) where T : IComparable<T> { a = a.CompareTo(b) < 0 ? a : b; }

    void solve()
    {
        var A = cin.nextlong;
        var B = cin.nextlong;
        var C = cin.nextlong;
        var K = cin.nextlong;

        if (K % 2 == 0)
        {
            WriteLine(A - B);
        }
        else
        {
            WriteLine(B - A);
        }
    }

}

class Scanner
{
    string[] s; int i;
    char[] cs = new char[] { ' ' };
    public Scanner() { s = new string[0]; i = 0; }
    public string[] scan { get { return ReadLine().Split(); } }
    public int[] scanint { get { return Array.ConvertAll(scan, int.Parse); } }
    public long[] scanlong { get { return Array.ConvertAll(scan, long.Parse); } }
    public double[] scandouble { get { return Array.ConvertAll(scan, double.Parse); } }
    public string next
    {
        get
        {
            if (i < s.Length) return s[i++];
            string st = ReadLine();
            while (st == "") st = ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
            return next;
        }
    }
    public int nextint { get { return int.Parse(next); } }
    public long nextlong { get { return long.Parse(next); } }
    public double nextdouble { get { return double.Parse(next); } }
}

Measured memory_bytes: 11092
#include <bits/stdc++.h>
#include <iostream>
#include<math.h>
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
int main()
{
    int64_t K;
    cin >> K;
    int64_t m = 7 % K;
    int64_t c = 1;
    while (m != 0) {
        if (c > 1 && c > 1000000) {
            c = -1;
            break;
        }

        c++;
        m *= 10;
        m += 7;
        m %= K;
    }

    cout << c << endl;
    return 0;
}

Measured memory_bytes: 3676
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;
int N,M,X,Y;

int main(){
	cin>>N>>M>>X>>Y;
	REP(i,N){
		int a;
		cin>>a;
		X=max(a,X);
	}
	REP(i,M){
		int a;
		cin>>a;
		Y=min(a,Y);
	}
	if(X<Y){
		cout<<"No War"<<endl;
	}else{
		cout<<"War"<<endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(long long i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using ll = long long;
using P = pair<int, int>;
const int mod = 1000000007;

vector<ll> pos[26];

int main(){
    string s, t;
    cin >> s >> t;
    rep(i, s.size()) {
        pos[s[i]-'a'].push_back(i);
    }
    ll ans;
    ll now = -1;
    ll cir = 0;
    rep(i, t.size()) {
        ll v = t[i] - 'a';
        if (pos[v].size()==0) {
            cout << "-1" << endl;
            return 0;
        }
        auto it = lower_bound(pos[v].begin(), pos[v].end(), now+1);
        if (it-pos[v].end()==0) {
            it = pos[v].begin();
            cir++;
        }
        now = *it;
    }
    ll ss = s.size();
    
    ans = cir * ss + now + 1;
    
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1724
#include <bits/stdc++.h>
using namespace std;
#define int long long
    



signed main(){
    int a,b[4]={};
    for(int i=0;i<6;i++){
        cin >> a;
        b[a-1]++;
    }
    int c[2]={};
    for(int i=0;i<4;i++){
        if(b[i]==1)c[0]++;
        if(b[i]==2)c[1]++;
    }
    if(c[0]==2 && c[1]==2)cout << " YES ";
    else cout << " NO ";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define VPII vector<pair<int,int> >
#define F first
#define S second
#define RF(x) freopen(x,"r",stdin)
#define WF(x) freopen(x,"w",stdout)
typedef long long LL;
using namespace std;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
const LL MOD = 1e9+7;
const LL INF = 1LL<<60;
const double eps = 1e-13;

bool myquery(LL x){
	printf("? %lld\n",x);fflush(stdout);
	char c;scanf(" %c",&c);
	return c=='Y';
}

LL p[10];

int main(){
	p[0]=1;
	REPP(i,1,16)p[i]=p[i-1]*10;
	LL cur=0;
	REP(d,10){
		LL st=0,en=9;
		while(st<en){
			LL mi=(st+en+1)/2;
			LL qi=(cur*10+mi);
			while(qi<=1000000000)qi*=10;
			if(myquery(qi))en=mi-1;
			else st=mi;
		}
		cur=cur*10+st;
	}
	cur++;
	while(cur<=1000000000)cur*=10;
	while(cur/10){
		if(((cur/10)%10)!=9){
			if(!myquery(cur/10+1)){
				printf("! %lld\n",cur);return 0;
			}
		}
		else{
			if(myquery((cur/10-1)*10)){
				printf("! %lld\n",cur);return 0;
			}
		}
		cur/=10;
	}
	printf("! %lld\n",cur);return 0;
}


Measured memory_bytes: 596
import itertools

n, m, q = map(int, input().split())
li = [tuple(map(int, input().split())) for i in range(q)]

A_li = tuple(itertools.combinations_with_replacement(range(m), n))

score = 0

for A in A_li:
  tmp = 0
  for nums in li:
    ai =  nums[0]-1
    bi = nums[1]-1
    ci = nums[2]
    di = nums[3]
    
    if A[bi] - A[ai] == ci:
      tmp += di
  score = max(score, tmp)
  
print(score)

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

int a, b, c, d, used[10];
int main (){
    scanf ("%d %d %d %d", &a, &b, &c, &d);
    used[a] = 1, used[b] = 1, used[c] = 1, used[d] = 1;
    if (used[1] == 1 && used[9] == 1 && used[7] == 1 && used[4] == 1){
        printf ("YES\n");
    } else {
        printf ("NO\n");
    }
    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N, X = map(int, raw_input().split())

def func(lv, id):
    sz = 4 * 2 ** lv - 3
    num = 2 * 2 ** lv - 1
    mid = (sz + 1) / 2
    if lv == 0:
        return 1
    if id == 1:
        return 0
    if id == mid:
        return (num - 1) / 2 + 1
    if id == sz:
        return num
    if 1 < id < mid:
        return func(lv - 1, id - 1)
    if mid < id < sz:
        return func(lv - 1, id - (sz - 3) / 2 - 2) + (num - 1) / 2 + 1

print func(N, X)


Measured memory_bytes: 2936
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define pb push_back
#define fs first
#define sc second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef pair<int, int> pii;
typedef pair<ll, int> plli;
typedef vector<pii> vpii;
typedef tree<pii, null_type, less<pii>, rb_tree_tag,
    tree_order_statistics_node_update> ost;

const int N=2100;
char a[N], b[N];
int nl[N], nr[N], wl[N], wr[N];

int main() {
    int i, j, k, kl, kr, n, d, diff, ans;
    scanf("%s%s", a, b);
    n=strlen(a);
    for(i=0; i<n && a[i]=='0'; i++);
    for(j=0; j<n && b[j]=='0'; j++);
    if(j==n) {
        printf("%d\n", i==n? 0 : -1);
        return 0;
    }
    for(d=k=0; k<n; k++) {
        i=(j+k)%n;
        if(b[i]=='1') d=0;
        else d++;
        nl[i]=d;
    }
    for(d=k=0; k<n; k++) {
        i=(j+n-k)%n;
        if(b[i]=='1') d=0;
        else d++;
        nr[i]=d;
    }
    ans=2*n;
    for(d=0; d<n; d++) {
        for(i=0; i<n; i++) wl[i]=wr[i]=0;
        diff=0;
        for(i=0; i<n; i++) {
            j=(d+i)%n;
            if(b[i]==a[j]) continue;
            diff++;
            if(nl[j]>d)
                wl[nl[j]-d-1]=max(wl[nl[j]-d-1], nr[j]);
            if(nr[j]>n-d)
                wr[nr[j]-n+d-1]=max(wr[nr[j]-n+d-1], nl[j]);
        }
        ans=min(ans, diff+n+min(d, n-d));
        for(kl=kr=0, i=n-1; i>=0; i--) {
            kl=max(kl, wl[i]);
            kr=max(kr, wr[i]);
            ans=min(ans, diff+d+2*i+2*kl);
            ans=min(ans, diff+n-d+2*i+2*kr);
        }
    }
    printf("%d\n", ans);
    return 0;
}

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

int main(){
    using namespace std;
    unsigned long N;
    cin >> N;
    unsigned long M;
    vector<vector<unsigned long>> path;
    {
        vector<vector<unsigned long>> edge(N);
        vector<unsigned long> queries(N);
        --N;
        vector<unsigned long> edges(N);
        for(unsigned long i{0}, a, b; i < N; ++i){
            cin >> a >> b;
            edge[--a].push_back(i);
            edge[--b].push_back(i);
            edges[i] = a ^ b;
        }
        cin >> M;
        path.resize(M);
        for(unsigned long i{1}, u, v; i < 1UL << M; i <<= 1){
            cin >> u >> v;
            queries[--u] ^= i;
            queries[--v] ^= i;
        }
        [rec_impl = [&path, &edge, &edges, &queries, &M](auto f, unsigned long now, unsigned long prev) -> unsigned long {
            unsigned long mask{queries[now]};
            for(const auto& i : edge[now])if((edges[i] ^ now) != prev){
                    auto t = f(f, edges[i] ^ now, now);
                    for(unsigned long j{0}; j < M; ++j)if(1 & (t >> j))path[j].push_back(i);
                    mask ^= t;
                }
            return mask;
        }]{rec_impl(rec_impl, 0, 0);}();
    }
    sort(path.begin(), path.end(), [](auto& i, auto& j){return i.size() < j.size();});
    vector<unsigned long> cnt(N), used(M);
    unsigned long ans{1UL << N}, cntr{N};
    const auto& check = [&cnt, &used, &path, &cntr, &M](unsigned long i){
        if(used[i] ^= 1)for(const auto& e : path[i])cntr -= !(cnt[e]++);
        else for(const auto& e : path[i])cntr += !(--cnt[e]);
    };
    for(unsigned long i{1}; i < 1UL << M; ++i){
        check(__builtin_ctzl(i));
        ans += (i & 1 ? -1 : 1) * (1UL << cntr);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
/*
これを入れて実行
g++ code.cpp
./a.out
 */
 
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>
#include <bitset>
#include <functional>
#include <cassert>
#include <random>

#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;
 
bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}
 
ll gcd(ll a, ll b){
	if (b == 0)return a;
	return gcd(b, a % b);
}
 
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}

ll conbinationMemo[100][100];

void cmemoInit(){
    rep(i, 100){
        rep(j, 100){
            conbinationMemo[i][j] = -1;
        }
    }
}
 
ll nCr(ll n, ll r){
    if(conbinationMemo[n][r] != -1) return conbinationMemo[n][r];
    if(r == 0 || r == n){
        return 1;
    } else if(r == 1){
        return n;
    }
    return conbinationMemo[n][r] = (nCr(n - 1, r) + nCr(n - 1, r - 1));
}
 
ll nPr(ll n, ll r){
    r = n - r;
    ll ret = 1;
    for (ll i = n; i >= r + 1; i--) ret *= i;
    return ret;
}
//-----------------------ここから-----------
ll n;
ll modpow(ll a, ll b){
    ll res = 1;
    while(b > 0){
        if(b & 1){
            res *= a;
            res %= MOD;
        }
        a *= a;
        a %= MOD;
        b >>= 1;
    }
    return res;
}
ll factorial[2010000];
ll invfactorial[2010000];

ll extGCD(ll a, ll b, ll &x, ll &y){
	if (b == 0){
		x = 1;
		y = 0;
		return a;
	}
 
	ll d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

ll nCrM(ll n, ll r){
	ll ret = factorial[n];
	ret *= invfactorial[n - r];
	ret %= MOD;
	ret *= invfactorial[r];
	ret %= MOD; 
	return ret;
}
int main(void){
    cin >> n;
    factorial[0] = 1;

    for (int i = 1; i < 2010000; i++){
        factorial[i] = (factorial[i - 1] * i) % MOD;
    }
    for (int i = 0; i < 2010000; i++){
        ll x, y;
        ll g = extGCD(factorial[i], MOD, x, y);
        while (x < 0) x += MOD;
        x %= MOD;
        invfactorial[i] = x;
    }

    ll ans = modpow(10, n) - modpow(8, n);
    for(ll i = 1; i <= n; i++){
        ans -= (modpow(8, n - i) * nCrM(n, i))%MOD * 2;
    }
    while(ans < 0) ans += MOD;
    cout << ans % MOD << endl;
}


Measured memory_bytes: 35076
def bubble(A, N):
    c = 0
    flag = True
    while flag:
        flag = False
        for j in range(N-1, 0, -1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]
                c += 1
                flag = True
    return A, c

if __name__ == "__main__":
    N = int(input())
    A = [int(i) for i in input().split()]

    A, c = bubble(A, N)
    print (*A)
    print (c)

Measured memory_bytes: 7760
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);--(i))
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
#define END(a) {cout << (a) << "\n"; return 0;}
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
const long double pi = acos(-1);
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; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& input, vector<T>& v) { for (auto& elemnt : v)input >> elemnt; return input; }

int main() {
    init();

    int n; cin >> n;
    vector<VI> num(n, VI(n, -1));
    int cnt = 0;
    FOR(i, 0, n)FOR(j, 0, n) {
        if (i == j || num[i][j] != -1)continue;
        num[i][j] = cnt;
        num[j][i] = cnt;
        ++cnt;
    }
    vector<VI> a(n, VI(n - 1));
    FOR(i, 0, n)FOR(j, 0, n - 1) {
        int x = i, y; cin >> y; --y;
        if (x > y)swap(x, y);
        a[i][j] = num[x][y];
    }
    vector<VI> g(cnt);
    FOR(i, 0, n)FOR(j, 0, n - 2) {
        g[a[i][j]].push_back(a[i][j + 1]);
    }

    //入次数が0の頂点とそこからの辺を削除することを繰り返す
    //閉路がある場合それに含まれる頂点は削除されない
    //よって削除した頂点数を見れば成功か分かる
    VI in(cnt), len(cnt), tpz;
    FOR(i, 0, cnt)for (int to : g[i])++in[to];
    queue<int> q;
    FOR(i, 0, cnt)if (in[i] == 0) {
        q.push(i);
        len[i] = 1;
    }
    while (!q.empty()) {
        int now = q.front(); q.pop();
        tpz.push_back(now);
        for (int to : g[now]) {
            --in[to];
            if (in[to] == 0) {
                q.push(to);
                chmax(len[to], len[now] + 1);
            }
        }
    }

    if (tpz.size() == cnt)cout << *max_element(all(len)) << "\n";
    else cout << "-1\n";
}

Measured memory_bytes: 41588
#include<cstdio>
#include<cstring>
using namespace std;
bool x;
int main()
{
	char a[103];
	scanf("%s",a);
	int len=strlen(a);
	for(int i=0;i<len;i++)
	{
		if(a[i]=='C')
			x=1;
		if(x&&a[i]=='F')
		{
				printf("Yes");
				return 0;
		}
	}
	printf("No");
	return 0;
}

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

using namespace std;

#define int long long int
#define cont continue;
#define ff first
#define ss second
#define pb push_back
#define ins insert
#define mp make_pair
#define endl '\n'


typedef vector<int> vi;
typedef set<int> si;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef map<int, int> mi;

//const
#define EPS 1e-9
#define INF LLONG_MAX
const int mod = 1000 * 1000 * 1000 + 7; //1e9+7
const double PI = 3.14159265358979323846264;
const pi steps[] = {{1, 0}, {0, 1}, { -1, 0}, {0, -1}, {1, -1}, {1, 1}, { -1, -1}, { -1, 1}}; //for (auto [dx,dy] : steps)
//const int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};

// inputs & output & debug
#define w(t) int t; cin>> t; while(t--)

#define deb(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...);
}

//useful functions
//#define deb(x) cout<<#x<<": "<<x<<endl;
#define isPowOfTwo(x) return (x && (!(x&(x-1))));
#define sz(a) (int)((a).size())
#define present(c,x) ((c).find(x) != (c).end())
#define ip_arr(a,n)   for(int i=0;i<n;i++) cin>>a[i];
#define op_arr(arr,n) for(int i=0;i<n;i++) cout<<arr[i]<<"\n"; cout<<endl;
#define fill_arr(arr,n,i) fill(arr,arr+n,i)
#define fill_vec(v,n,i) fill(v.begin(),v.begin()+n,i);
#define sortv(a) sort(a.begin(),a.end())

void fio()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
}
void setUpLocal()
{
#ifndef ONLINE_JUDGE
	freopen("/Users/asuryana/Documents/CP/input.txt", "r", stdin);
	freopen("/Users/asuryana/Documents/CP/output.txt", "w", stdout);
#else
#define cerr if(0) cerr
#endif
}

const int maxN = 107;
// vi gp[gp_size];
// int vis[gp_size];
// int cnt[gp_size];

int w[maxN], v[maxN];
int dp[maxN][100005];
int knap(int i, int W)
{
	if (i == 0 or W == 0)
	{
		return 0;
	}

	if (dp[i][W] != -1)
	{
		return dp[i][W];
	}
	if (w[i - 1] <= W)
	{
		return dp[i][W] = max(v[i - 1] + knap(i - 1, W - w[i - 1]),
		                      knap(i - 1, W));
	}

	return dp[i][W] = knap(i - 1, W);
}

void solve()
{
	int n, W; cin >> n >> W;

	for (int i = 0; i < n; i++)
	{
		cin >> w[i] >> v[i];
	}

	memset(dp, -1, sizeof(dp));

	cout << knap(n, W);

}

int32_t main()
{
	fio();
	//setUpLocal();
	return solve(), 0;
}


Measured memory_bytes: 87224
package main

import "fmt"

func main() {

	var n, x int

	for {
		fmt.Scan(&n, &x)
		if n==0 && x==0 {
			break
		}
		tot := 0
		for a:=1; a<=n-2; a++ {
			for b:=a+1; b<=n-1; b++ {
				for c:=b+1; c<=n; c++ {
					if a+b+c == x {
						tot++
					}
				}
			}
		}
		fmt.Println(tot)
	}
}


Measured memory_bytes: 1160
import math

count = 0
a = 0

N, D = [int (x) for x in input().split()]
for i in range(N):
    X, Y = [int (x) for x in input().split()]
    a = X**2 + Y**2
    p =  math.sqrt(abs(a))
    if(p <= D):
        count = count + 1

print(str(count))

Measured memory_bytes: 9200
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
from itertools import accumulate #list(accumulate(A))

'''
def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    #table = [ i for i in range(1, n+1) if is_prime[i-1]]
    #return is_prime, table
    return is_prime
'''

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False

    for i in range(2, n+1):
        if is_prime[i]:
            j = 2 * i
            while j <= n:
                is_prime[j] = False
                j += i
    #table = [ i for i in range(1, n+1) if is_prime[i-1]]
    #return is_prime, table
    return is_prime


Q = ii()
lr = li2(Q)

prime = sieve(10**5)
flag = [0]*(10**5+1)

for i in range(3, 10**5+1, 2):
    if prime[i] and prime[(i+1)//2]:
        flag[i] = 1

ans = list(accumulate(flag))

for i in range(Q):
    print(ans[lr[i][1]] - ans[lr[i][0]-1])

Measured memory_bytes: 32840
import * as fs from 'fs';

function main(input: string) {
  let lines = input.split('\n');
  let tmp = lines[0].split(' ');

  let N = Number(tmp[0]);
  let A = Number(tmp[1]);

  let x = [0];
  x = x.concat(lines[1].split(' ').map(Number));

  let dp = new Array(N + 1);
  for (let i = 0; i <= N; ++i) {
    dp[i] = new Array(N + 1);
    for (let j = 0; j <= N; ++j) {
      dp[i][j] = new Array(A * N + 1).fill(0);
    }
  }

  for (let i = 0; i < N; ++i) dp[i][0][0] = 1;

  for (let i = 1; i <= N; ++i) {
    for (let j = 1; j <= i; ++j) {
      for (let k = 1; k <= A * N; ++k) {
        if (k < x[i]) {
          dp[i][j][k] = dp[i - 1][j][k];
        } else {
          dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - 1][k - x[i]];
        }
      }
    }
  }

  let ans = 0;
  for (let j = 1; j <= N; ++j) {
    ans += dp[N][j][j * A];
  }

  console.log(ans);
}

main(fs.readFileSync('/dev/stdin', 'utf8'));


Measured memory_bytes: 98352
n = int(input())
a = list(map(int, input().split()))

mod = 10**9 + 7

pows = [pow(2, i, mod) for i in range(60)]
count = [0]*60

for i in range(n):
    bit = a[i]
    for g in range(60):
        count[g] += bit%2
        bit //= 2
        if bit == 0:
            break

ans = 0
num = [0]*60

for i in range(n):
    bit = a[i]
    for g in range(60):
        if bit % 2 == 1:
            num[g] += n - count[g]
        else:
            num[g] += count[g]
        bit //= 2

for i in range(60):
    ans += num[i]*pows[i]

print(ans//2 % mod)
    

Measured memory_bytes: 124528
#include <bits/stdc++.h>
using namespace std;
long long n, cnt = 0;
bool good(long long number)
{
	unordered_map<int,bool>um;
	while(number > 0)
	{
		int last = number % 10;
		number/=10;
		if(last == 3 || last == 5 || last == 7)
			um[last] = true;
			
		if(um.size() == 3)
			return true;
	}
	if(um.size() == 3)
		return true;
	return false;
}
void f(long long number)
{
	if(number > n)
		return;	
	else{
		if(good(number))
			cnt++;
	//cout<<number<<endl;
	number *= 10;
	f(number + 3);
	f(number + 5);
	f(number + 7);
	}
}
int main()
{
	cin>>n;
	f(0);
	cout<<cnt<<endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<queue>

using namespace std;

int h, w;
char F[1024][1024];

int dist(int x1, int y1, int x2, int y2)
{
  int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
  char vis[1024][1024] = {{0}};
  queue<pair<int, int> > q;
  q.push(make_pair(y1*1000+x1, 0)); vis[y1][x1]=1;
  while(!q.empty()) {
    int x=q.front().first%1000, y=q.front().first/1000, s=q.front().second; q.pop();
    if(x==x2 && y==y2) return s;
    for(int i=0; i<4; ++i) {
      int nx=x+dx[i], ny=y+dy[i];
      if(nx<0||ny<0) continue; if(nx>=w||ny>=h) continue;
      if(F[ny][nx]=='X'||vis[ny][nx]) continue;
      vis[ny][nx]=1; q.push(make_pair(ny*1000+nx,s+1));
    }
  }
  return 100000000;
}

int main()
{
  int n, x[10], y[10];
  scanf("%d%d%d", &h, &w, &n);
  for(int i=0; i<h; ++i) {
    scanf("%s", F[i]);
    for(int j=0; j<w; ++j) {
      if(F[i][j]=='S') { x[0]=j; y[0]=i; F[i][j]='.'; }
      else if('0'<=F[i][j]&&F[i][j]<='9') {
	x[F[i][j]-'0']=j; y[F[i][j]-'0']=i; F[i][j]='.';
      }
    }
  }
  int sol=0;
  for(int i=0; i<n; ++i) sol+=dist(x[i],y[i],x[i+1],y[i+1]);
  printf("%d\n", sol);
  return 0;
}

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

#define NREP() for(ll i = 0; i < n; i++)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define ALL(x) (x).begin(),(x).end()
#define MSG(x) cout << x << endl;
#define YN(x) x ? cout << "YES" << endl : cout << "NO" << endl;
#define Yn(x) x ? cout << "Yes" << endl : cout << "No" << endl;
#define yn(x) x ? cout << "yes" << endl : cout << "no" << endl;

using namespace std;
using ll = long long;
const static ll MOD = 1e9 + 7;

int main() {
    ll n, m;
    cin >> n >> m;

    if (n == 1 && m == 1) {
        MSG(1)
    } else if ((n == 1 && m >= 2)) {
        MSG(m - 2)
    } else if ((n >= 2 && m == 1)) {
        MSG(n - 2)
    } else {
        MSG((n - 2) * (m - 2))
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
int main(void){
	int i,j,k=0,l=0,h,w;
	cin>>h>>w;
	string s[h];
	vector<int> x,y;
	for(i=0;i<h;i++)cin>>s[i];
	for(i=0;i<h;i++){
		int f=1;
		for(j=0;j<w;j++){
			if(s[i][j]=='#')f=0;
		}
		if(f)x.push_back(i);
	}
	for(j=0;j<w;j++){
		int f=1;
		for(i=0;i<h;i++){
			if(s[i][j]=='#')f=0;
		}
		if(f)y.push_back(j);
	}
	x.push_back(100);
	y.push_back(100);
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			if(x[k]!=i&&y[l]!=j)cout<<s[i][j];
			if(y[l]==j&&l<y.size()-1)l++;
		}
		if(x[k]==i&&k<x.size()-1)k++;
		else cout<<endl;
		l=0;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>

// Remove GCC optimizer for codechef
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;
using namespace __gnu_pbds;

  #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define int long long
  #define endl "\n"
  #define all(v) v.begin(),v.end()
  #define double long double
  #define trace1(x)                cerr<<#x<<": "<<x<<endl
  #define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
  #define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
  #define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
  #define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<< ": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
  #define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
  #define cases int testcases;cin>>testcases; while(testcases--)
  const int N = 200005;



int32_t main()
{



    IOS



    int arr[5];

    for(int i = 0; i < 5; i++)
    {
    	cin >> arr[i];
    	if(arr[i] == 0)
    	{
    		cout << i + 1;
    		return 0;
    	}
    }





    return 0;
}


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

int main(){
  int n,q,a[10000+1],key,cnt=0;
  cin >> n;
  for(int i=0;i<n;i++) cin >> a[i];
  cin >> q;
  for(int j=0;j<q;j++){
    cin >> key;
    for(int i=0;i<n;i++){
      if(a[i]==key){
        cnt++;
        break;
      }
    }
  }
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 1200
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
using namespace std;
const long long int INF = 1e18;
const long long int mod = 1e9+7;

typedef pair<ll, ll> pairs;
typedef vector<pairs> p;

struct Edge{
    ll to, weight;
    Edge(ll t, ll w) : to(t), weight(w){}
};
using graph = vector<vector<ll>>;
using Graph = vector<vector<Edge>>;


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

ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}

ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}

// 回文
bool kai(string S){
    bool flag = true;
    for(ll i=0;i<S.size()/2;++i){
        if(S[i] != S[S.size()-i-1]){
            flag = false;
            break;
        }
    }
    return flag;
}
// ---------------------------------------------

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

    ll ans = a - b;
    if(k % 2 == 1){
        ans *= -1;
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 3560
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1000000007;

int N, H[200200], A[200200];

int dat[2002000], n;

void init()
{
    n = 1;
    while(n < N){
        n *= 2;
    }
}

void update(int k, int x)
{
    k += n - 1;
    dat[k] = x;
    while(k > 0){
        k = (k - 1) / 2;
        dat[k] = max(dat[2 * k + 1], dat[2 * k + 2]);
    }
}

int query(int a, int b, int k = 0, int l = 0, int r = -1)
{
    if(r < 0)r = n;
    if(r <= a || b <= l)return 0;
    if(a <= l && r <= b)return dat[k];
    int vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
    int vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
    return max(vl, vr);
}

signed main()
{
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> H[i];
        H[i]--;
    }
    for(int i = 0; i < N; i++){
        cin >> A[i];
    }
    init();
    for(int i = 0; i < N; i++){
        int res = query(0, H[i] + 1);
        //printf("%lld\n", res);
        update(H[i], res + A[i]);
    }
    cout << query(0, N) << endl;


    return 0;
}


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

int main(){
  int H,W;
  cin >>   H >> W;
  
  vector<char> stock(W);
  
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      cin >> stock[j];
    }
    for(int j = 0; j < W; j++){
      cout << stock[j];
    }
    cout << endl;
    for(int j = 0; j < W; j++){
      cout << stock[j];
    }
    cout << endl;
  }
}

    

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

  int main() {
    double A,B;
    int C;
    int D;
    cin >> A >> B;
    
    if(10*B<=25*A/2){
      if(10*(B+1)>25*A/2){
        C=25*A/2;
        D=A;
        if(D%2==0)
          cout << C;
        
        else
          cout << 25*D/2+1;
      }

      else
        cout << -1;
      
    }

    if(25*A/2<10*B){
      if(25*(A+1)/2>10*B)
        cout << 10*B;

      else
        cout << -1;
      
    }
  }

Measured memory_bytes: 256
#include <iostream>
#include <cstdint>
#include <queue>

using namespace std;

int main() {
  int64_t N, K;
  cin >> N >> K;
  
  priority_queue<int64_t> q;
  for (size_t n = 0; n < N; ++n) {
    int64_t H;
    cin >> H;
    q.push(H);
  }
  if (q.size() <= K) {
    cout << 0 << endl;
    return 0;
  }
  for (size_t i = 0; i < K; ++i) {
    q.pop();
  }
  int64_t total = 0;
  while (!q.empty()) {
    total += q.top();
    q.pop();
  }
  cout << total << endl;
  
  return 0;
}


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

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;

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

#define M (1000000007)

// n^k mod m in O(log k)
ll powmod_r(ll n, ll k, ll m) {
    if (k == 0)
        return 1;
    if (k % 2 == 0) {
        ll tmp = powmod_r(n, k / 2, m);
        return tmp * tmp % m;
    } else {
        return powmod_r(n, k - 1, m) * n % m;
    }
}

// loop version
// n^k mod m
ll powmod(ll n, ll k, ll m) {
    ll ans = 1;
    while (k > 0) {
        if (k & 1) {
            ans = (n * ans) % m;
        }
        n = (n * n) % m;
        k >>= 1;
    }
    return ans;
}

// inverse (gyakugen)
ll modinv(ll a, ll m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= m;
    if (u < 0)
        u += m;
    return u;
}

// a/b mod m
ll moddiv(ll a, ll b, ll m) {
    a %= M;
    return a * modinv(b, m) % m;
}

// nCr mod m
ll modncr(ll n, ll r, ll m) {
    ll numerator = n;
    for (ll i = n - 1; i >= n - r + 1; i--) {
        numerator = numerator * i % m;
    }

    ll denominator = r;
    for (ll i = r - 1; i >= 2; i--) {
        denominator = denominator * i % m;
    }

    return moddiv(numerator, denominator, M);
}

int main() {
    ios::sync_with_stdio(false);
    ll n, a, b;
    cin >> n >> a >> b;
    ll ans = powmod(2, n, M) - 1 - modncr(n, a, M) - modncr(n, b, M);
    while (ans < 0)
        ans += M;

    cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<time.h>
#define rep(i,n)for(int i=0;i<n;i++)
#define int long long
#define ggr getchar();getchar();return 0;
#define prique priority_queue
#define mod 1000000007
#define inf 1e15
#define key 1e9
using namespace std;
typedef pair<int, int>P;
void yes() { cout << "Yay!" << endl; }
void no() { cout << ":(" << endl; }
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y)* mod_pow(kai(y, y), mod - 2, mod) % mod;
}
struct edge { int to, cost; };
int n, q;
int t[114514];
double a[114514];
int l[114514], r[114514];
pair<int, double>memo[114514];
signed main() {
	cin >> n;
	rep(i, n)cin >> t[i] >> a[i];
	cin >> q;
	rep(i, q)cin >> l[i] >> r[i];
	memo[0].first = t[0], memo[0].second = double(1 - a[0] / 10.0);
	for (int i = 1; i < n; i++) {
		memo[i].first = t[i];
		memo[i].second = double(memo[i - 1].second * (double(1 - a[i] / 10.0)));
	}
	rep(i, q) {
		int x = lower_bound(t, t + n, l[i]) - t - 1;
		int y = upper_bound(t, t + n, r[i]) - t - 1;
		double pp = 10000, qq = 10000;
		if (x >= 0)pp = memo[x].second;
		if (y >= 0)qq = memo[y].second;
		pp = min(pp, (double)1), qq = min(qq, (double)1);
		cout << setprecision(15) << double(qq / pp) * key << endl;
	}
	ggr
}




Measured memory_bytes: 7952
# -*- coding: utf-8 -*-


def calc_dist(s, start_i, start_j, h, w):
    from collections import deque

    result = 0
    # 待ち行列に相当する部分をキューで管理
    d = deque()
    # キューの初期化
    d.append((start_i, start_j))
    # 仮決めした始点からの距離を計算
    dist = [[0 for _ in range(w)] for _ in range(h)]
    # 迷路のマスを通ったかどうかを管理
    visited = [[False for _ in range(w)] for _ in range(h)]
    visited[start_i][start_j] = True
    # 4方向を移動する部分を配列でスマートに管理する
    dxy = [(1, 0), (-1, 0), (0, -1), (0, 1)]

    while d:
        hd, wd = d.popleft()

        # 上下左右の4方向に移動
        for dx, dy in dxy:
            nx = wd + dx
            ny = hd + dy

            # 迷路の範囲外
            if nx < 0 or nx >= w or ny < 0 or ny >= h:
                continue

            # 壁
            if s[ny][nx] == '#':
                continue

            # 既に通過した
            # DEBUG: 本番では、ここがなくて計算量が爆発していた
            if visited[ny][nx]:
                continue

            visited[ny][nx] = True
            dist[ny][nx] = dist[hd][wd] + 1
            d.append((ny, nx))
            result = max(result, dist[ny][nx])

    return result


def main():
    h, w = map(int, input().split())
    s = [list(input()) for _ in range(h)]
    ans = 0

    # KeyInsight
    # 始点のみを全探索(終点は全探索する必要はない．終点の位置は、移動距離の最大値に相当)
    # 距離は幅優先探索BFSで計算
    # DEBUG: 終点を全探索するループさえなければACしていた
    for start_i in range(h):
        for start_j in range(w):
            # 始点が壁のときは、距離を計算しない
            if s[start_i][start_j] == '#':
                continue

            ans = max(ans, calc_dist(s, start_i, start_j, h, w))

    print(ans)


if __name__ == '__main__':
    main()


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

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

    bool ok = false;
    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++){
            if(i*j==N) ok = true;
        }
    }
    
    if(ok) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stack>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <cstring>
#include <vector>
#include <cmath>
#include <stdlib.h>
#include <unordered_map>
#define ll long long
using namespace std;
int a[100010];
int main()
{
    int n,k;
    int mi=2e9;
    cin>>n>>k;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n-k+1;i++){
        if(a[i]>=0&&a[i+k-1]>0)
            mi=min(mi,a[i+k-1]);
        else if(a[i]<0&&a[i+k-1]<0)
            mi=min(mi,-a[i]);
        else{
            mi=min(mi,-2*a[i]+a[i+k-1]);
            mi=min(mi,-a[i]+2*a[i+k-1]);
        }
    }
    cout<<mi;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
//#define INF 810114514
//#define PI 3.141592653589
typedef pair<int,int> PP;
typedef long long ll;
#define int ll
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE do { cout << "0" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl

int roundup(int a,int b){
    return (a+b-1)/b;
}

signed main(void){
    int K,X,Y;
    cin >> K >> X >> Y;
    
    if(abs(X)+abs(Y)==K){
        cout << 1 << endl;
        cout << X << " " << Y << endl;
        return 0;
    }
    
    
    bool Xnega=false,Ynega=false,XYswap=false;
    if(X<0){
        Xnega=true;
        X*=-1;
    }
    if(Y<0){
        Ynega=true;
        Y*=-1;
    }
    if(X<Y){
        XYswap=true;
        swap(X,Y);
    }
    //0<=Y<=X
    vector<pair<int,int>> Ans;
    
    int n,m;
    n=roundup(X+Y,K);m=n;
    if(n==1)n++;
    if((n*K+(X+Y))%2==1){
        if(K%2==1){
            n++;
        }else{
            cout << -1 << endl;
            return 0;
        }
    }
    
    if(m!=1 || n!=3){
        int a = (n*K-X-Y)/2;
        REP(i,n){
            int p = (i+1)*K;
            if(p<a+Y){
                Ans.push_back({0,p});
            }else if(p<a+Y+X){
                Ans.push_back({p-a-Y,a+Y});
            }else{
                Ans.push_back({X,2*(a+Y)+X-p});
            }
        }
    }else{
        int c=(n*K-X-Y)/2;
        int b=c/2;
        int a=c-b;
        
        REP(i,n){
            int p = (i+1)*K;
            if(p<a){
                Ans.push_back({-p,0});
            }else if(p<a+b+Y){
                Ans.push_back({-a,p-a});
            }else if(p<a+b+Y+a+X){
                int s = a+b+Y;
                Ans.push_back({-a+p-s,b+Y});
            }else{
                int s = a+b+Y+a+X;
                Ans.push_back({X,b+Y-(p-s)});
            }
        }
    }
    
    
    if(XYswap){
        REP(i,Ans.size()){
            swap(Ans[i].first,Ans[i].second);
        }
    }
    if(Ynega){
        REP(i,Ans.size()){
            Ans[i].second*=-1;
        }
    }
    if(Xnega){
        REP(i,Ans.size()){
            Ans[i].first*=-1;
        }
    }
    
    cout << Ans.size() << endl;
    REP(i,Ans.size()){
        cout << Ans[i].first << " " << Ans[i].second << endl;
    }
    
    return 0;
}



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

int main() {
    int N, i;
    double mixed;
    cin >> N;
    vector<int> value(N);
    for (i = 0; i < N; i++) {
        cin >> value.at(i);
    }
    sort(value.begin(), value.end());
    mixed = (value.at(0) + value.at(1)) / 2.0;
    for (i = 2; i < N; i++) {
        mixed = (mixed + value.at(i)) / 2.0;
    }
    cout << mixed << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

typedef long long ll;

const int N = 100100;
int n, k;
ll a[N];
ll sum[N];
ll pref[N], suf[N];

int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++)
		scanf("%lld", &a[i]);
	sum[0] = 0;
	for (int i = 0; i < n; i++)
		sum[i + 1] = sum[i] + a[i];
	pref[0] = 0;
	for (int i = 0; i < n; i++)
		pref[i + 1] = pref[i] + max(0LL, a[i]);
	suf[n] = 0;
	for (int i = n - 1; i >= 0; i--)
		suf[i] = suf[i + 1] + max(0LL, a[i]);
	ll ans = 0;
	for (int i = 0; i + k <= n; i++)
		ans = max(ans, pref[i] + suf[i + k] + max(0LL, sum[i + k] - sum[i]));
	printf("%lld\n", ans);

	return 0;
}


Measured memory_bytes: 3328
#include <iostream>
#include <vector>
#include <fstream>

#define INPUT_FROM_FILE (0)

int main(int argc, char **argv){
#if INPUT_FROM_FILE
	std::ifstream ifs("test.txt");
#endif // INPUT_FROM_FILE
	std::vector<std::vector<bool> > is_exists_card;
	std::vector<char> c_vec(4);
	int n = 0;

	is_exists_card.resize(4);
	for(unsigned int i = 0; i < 4; i++){
		is_exists_card[i].resize(14, false);
	}
	c_vec[0] = 'S';
	c_vec[1] = 'H';
	c_vec[2] = 'C';
	c_vec[3] = 'D';

#if INPUT_FROM_FILE
	ifs >> n;
#else
	std::cin >> n;
#endif // INPUT_FROM_FILE


	for(int i = 0; i < n; i++){
		char c = 0;
		int num = 0;
		char idx_c = 0;

#if INPUT_FROM_FILE
		ifs >> c >> num;
#else
		std::cin >> c >> num;
#endif // INPUT_FROM_FILE

		switch(c){
		case 'S':
			idx_c = 0;
			break;
		case 'H':
			idx_c = 1;
			break;
		case 'C':
			idx_c = 2;
			break;
		case 'D':
			idx_c = 3;
			break;
		default:
			break;
		}
		is_exists_card[idx_c][num] = true;
	}
	for(int j = 0; j < 4; j++){
		for(int i = 1; i < 14; i++){
			if(!is_exists_card[j][i]){
				std::cout << c_vec[j] << " " << i << std::endl;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 3080
#include<bits/stdc++.h>
#define ll long long 
#define MM(arr,x) memset(arr,x,sizeof(arr))
#define INF 0x3f3f3f3f
#define Maxn 1e5+10;
using namespace std;
int main()
{
	ios::sync_with_stdio(0);
	int n;
	cin>>n;
	if(n>=30) cout<<"Yes";
	else cout<<"No"; 
	return 0;
} 

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

int main() {
	int N; cin >> N;
	int S[1000010][3];
	cin >> S[0][0] >> S[0][1] >> S[0][2];
	for(int i=1; i<N; ++i){
	    cin >> S[i][0] >> S[i][1] >> S[i][2];
	    for(int j=0; j<3; ++j) S[i][j] += max(S[i-1][(j+1)%3], S[i-1][(j+2)%3]);
	}
	cout << max(S[N-1][0], max(S[N-1][1], S[N-1][2])) << endl;
	return 0;
}


Measured memory_bytes: 3200
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

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

constexpr int dx[]={1,0,-1,0};
constexpr int dy[]={0,1,0,-1};
constexpr int INF = 1<<28;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int H,W,C_h,C_w,D_h,D_w;
  cin>>H>>W>>C_h>>C_w>>D_h>>D_w;
  C_h--,C_w--,D_h--,D_w--;
  vector<string> S(H);
  rep(i,H)cin>>S[i];

  vector dist(H,vector(W,INF));
  dist[C_h][C_w] = 0;
  deque<int> deq;
  deq.emplace_front(C_h*W+C_w);
  while(!deq.empty()){
    int cur = deq.front();
    deq.pop_front();
    int y = cur/W;
    int x = cur%W;
    rep(i,4){
      int ny = y+dy[i];
      int nx = x+dx[i];
      if(ny<0||nx<0||ny>=H||nx>=W)continue;
      if(S[ny][nx]=='#')continue;
      if(dist[ny][nx]>dist[y][x]){
        dist[ny][nx] = dist[y][x];
        deq.emplace_front(ny*W+nx);
      }
    }
    for(int ddy=-2;ddy<=2;++ddy)for(int ddx=-2;ddx<=2;++ddx){
      if(abs(ddy)+abs(ddx)<=1)continue;
      int ny = y+ddy;
      int nx = x+ddx;
      if(ny<0||nx<0||ny>=H||nx>=W||S[ny][nx]=='#')continue;
      if(dist[ny][nx]>dist[y][x]+1){
        dist[ny][nx] = dist[y][x]+1;
        deq.emplace_back(ny*W+nx);
      }
    }
  }
  int ans = dist[D_h][D_w];
  cout<<(ans==INF?-1:ans)<<endl;
}


Measured memory_bytes: 8672