akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
//#pragma GCC optimize("Ofast")
//#define _GLIBCXX_DEBUG
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
//#define int ll
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define floatprec(dig) fixed << setprecision(dig)
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int;
#define invar(typ, var) typ var; cin >> var;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -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;}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX / 2;
const ll LLINF = 1LL<<60;
constexpr ll MOD = 1000000007;
const double EPS = 1e-9;

vector<ll> enum_div(ll n){
  vector<ll> ret;
  for(ll i = 1 ; i*i <= n ; ++i){
      if(n%i == 0){
        ret.push_back(i);
        if(i*i != n){
          ret.push_back(n/i);
        }
      }
  }
  return ret;
}

signed main(void) {
  cin.tie(0); ios::sync_with_stdio(false);
  
  ll N;
  cin >> N;
  
  //まず割ってみる
  vll ds = enum_div(N);
  
  ll ct = 0;
  for(int i=0; i<ds.size(); i++) {
    if(ds[i] == 1) continue;
    
    ll dd = N;
    //割れるまで割る
    while(dd % ds[i] == 0) {
      dd /= ds[i];
    }
    
    if(dd % ds[i] == 1) {
      //OK
      ct ++;
    }
  }  
  
  //ずっと引く
  vll ds2 = enum_div(N - 1);
  ct += ds2.size() - 1;
  
  fin(ct);
}

Measured memory_bytes: 384
Nstr=input()
N=int(Nstr)
K=int(input())
x=len(Nstr)
dp0=[[0]*(K+1) for i in range(x+1)]
dp1=[[0]*(K+1) for i in range(x+1)]

dp1[0][0]=1

for i in range(1,x+1):
  dp0[i][0]=dp0[i-1][0]+dp1[i-1][0]
  for j in range(1,K+1):
    if Nstr[i-1]!='0':
      dp1[i][j]=dp1[i-1][j-1]
      dp0[i][j]+=(dp1[i-1][j-1]*(int(Nstr[i-1])-1)+dp1[i-1][j])
    else:
      dp1[i][j]=dp1[i-1][j]
    dp0[i][j]+=(dp0[i-1][j]+dp0[i-1][j-1]*9)

    
  '''  
  if Nstr[i-1]!='0':
    for j in range(1,K+1):
      dp1[i][j]=dp1[i-1][j-1]
      dp0[i][j]+=(dp1[i-1][j-1]*(int(Nstr[i-1])-1)+dp1[i-1][j])
  else:
    for j in range(1,K+1):
      dp1[i][j]=dp1[i-1][j]
  for j in range(1,K+1):
    dp0[i][j]+=(dp0[i-1][j]+dp0[i-1][j-1]*9)
  '''
print(dp0[x][K]+dp1[x][K])

Measured memory_bytes: 3188
N, M = map(int, input().split())
startlist = [False]
goallist = [False]
for i in range(0, N):
	startlist.append(False)
	goallist.append(False)
for i in range(0, M):
	a, b = map(int, input().split())
	if a == 1: startlist[b] = True
	if b == N: goallist[a] = True
ans = 'IMPOSSIBLE'
for i in range(0, N+1):
	if startlist[i] and goallist[i]:
		ans = 'POSSIBLE'
		break
print(ans)

Measured memory_bytes: 66672
import java.util.Scanner;
 
public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int prime[] = new int[1000000];
        int n;
        int count = 0;
 
        for (int i = 2; i <= 1000000 / 2; i++) {
            for (int j = i * 2; j < 1000000; j += i) {
                prime[j] = 1;
            }
        }
        while (sc.hasNext()) {
            n = sc.nextInt();
            count = 0;
            for (int i = 2; i <= n; i++) {
                if (prime[i] == 0) {
                    count++;
                }
            }
            System.out.println(count);
        }
    }
}

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

using namespace std;

const int maxn = 100000;
const int maxm = 100000;

class Node
{
public:
	int u;
	long long d;

	Node(void);
	Node(const int &, const long long &);

	bool operator < (const Node &) const;
};

class Edge
{
public:
	int u;
	int v;
	int w;

	Edge(void);
	Edge(const int &, const int &, const int &);
};

Node::Node(void) : u(0), d(0)
{

}

Node::Node(const int & u, const long long & d) : u(u), d(d)
{

}

bool Node::operator < (const Node & rhs) const
{
	return d > rhs.d;
}

Edge::Edge(void) : u(0), v(0), w(0)
{

}

Edge::Edge(const int & u, const int & v, const int & w) : u(u), v(v), w(w)
{

}

int n, m;
vector<Edge> E;
vector<int> Eid[maxn];
vector<Edge> Et;
vector<int> Etid[maxn];
long long d[maxn];
long long deg[maxn];
long long dt[maxn];
long long degt[maxn];

void dijkstra(const int & s, vector<Edge> & E, vector<int> Eid[], long long d[], long long deg[])
{
	Node cur, tgt;
	priority_queue<Node> que;

	memset(d, 0x3f, sizeof(d[0]) * n);
	memset(deg, 0, sizeof(deg[0]) * n);
	d[s] = 0;
	deg[s] = 1;
	for (que.push(Node(s, 0)); !que.empty(); )
	{
		cur = que.top();
		que.pop();

		if (d[cur.u] < cur.d)
			continue;

		int u = cur.u, v, w;
		for (int i = 0; i < Eid[u].size(); ++ i)
		{
			v = E[Eid[u][i]].v;
			w = E[Eid[u][i]].w;
			if (d[v] > d[u] + w)
			{
				d[v] = d[u] + w;
				deg[v] = deg[u];
				que.push(Node(v, d[v]));
			}
			else if (d[v] == d[u] + w)
				deg[v] += deg[u];
		}
	}
}

inline int check_edge(const int & idx)
{
	if (d[E[idx].v] + E[idx].w + dt[E[idx].u] < d[1])
		return -1;
	else if (d[E[idx].u] + E[idx].w + dt[E[idx].v] == d[1] && deg[E[idx].u] * degt[E[idx].v] == deg[1])
		return 1;
	else
		return 0;
}

int main()
{
	ios_base::sync_with_stdio(false);

	cin >> n >> m;
	for (int i = 0; i < m; ++ i)
	{
		int u, v, w;

		cin >> u >> v >> w;
		-- u;
		-- v;
		E.push_back(Edge(u, v, w));
		Eid[u].push_back(i);
		Et.push_back(Edge(v, u, w));
		Etid[v].push_back(i);
	}

	dijkstra(0, E, Eid, d, deg);
	dijkstra(1, Et, Etid, dt, degt);

	int ans;
	for (int k = 0; k < m; ++ k)
	{
		ans = check_edge(k);

		if (ans == -1)
			cout << "HAPPY";
		else if (ans == 0)
			cout << "SOSO";
		else
			cout << "SAD";
		cout << endl;
	}

	return 0;
}


Measured memory_bytes: 19344
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;

bool prime[1000000];

int main()
{
    int i,j,k,l,m,n;
    int count;
    while(cin>>n)
    {
        memset(prime,0,sizeof(prime));
        prime[1]=1;
        prime[2]=0;

        count=0;

        for(j=2;j*j<=n;j++)
        {
            if(prime[j]==0)
            {
                for(k=2;k*j<=n;k++)
                {
                   prime[j*k]=1;
                }
            }
        }
        for(i=1;i<=n;i++)
        {
            if(prime[i]==0)
            count++;
        }
        cout << count << endl;
    }
    return 0;
}

Measured memory_bytes: 2144
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def gcd_list(num_list: list) -> int:
    return reduce(gcd, num_list)

def make_divisors(n: int) -> list:
    return_list = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            return_list.append(i)
            if i != n // i:
                return_list.append(n//i)

    return return_list[2:]

def main():
    n = i_input()
    num_list = i_list()

    num_list = list(set(num_list))

    if gcd_list(num_list) != 1:
        print('not coprime')
        exit()

    num_list.sort()

    tmp_list = [0] * (num_list[0-1] + 1)

    for num in num_list:
        if tmp_list[num] == 1:
            print('setwise coprime')
            exit()

        yakusu_list = make_divisors(num)
        yakusu_list.sort()

        for yakusu in yakusu_list:
            for i in range(yakusu, num_list[-1], yakusu):
                tmp_list[i] = 1

        for i in range(num, num_list[-1], num):
            tmp_list[i] = 1

    print('pairwise coprime')

if __name__ == '__main__':
    main()


Measured memory_bytes: 243616
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int 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;


int main(){
    int n, q;
    string s;
    cin >> n;
    cin >> s;
    cin >> q;
    vector<int> data[26];
    rep(i, n) {
        int v = s[i] - 'a';
        data[v].push_back(i);
    }
    
    rep(i, q) {
        int id;
        cin >> id;
        if (id==1) {
            int iq;
            char cq;
            cin >> iq >> cq;
            iq--;
            int v = s[iq] - 'a';
            auto it = lower_bound(data[v].begin(), data[v].end(), iq);
            data[v].erase(it);
            s[iq] = cq;
            v = cq - 'a';
            it = upper_bound(data[v].begin(), data[v].end(), iq);
            data[v].insert(it, iq);
        }
        else {
            int lq, rq;
            cin >> lq >> rq;
            lq--;
            rq--;
            int cnt = 0;
            rep(j, 26) {
                auto it = lower_bound(data[j].begin(), data[j].end(), lq);
                if (it!=data[j].end()&&*it<=rq) {
                    cnt ++;
                }
            }
            cout << cnt << endl;
        }
    }
    
    
    return 0;
}


Measured memory_bytes: 3972
def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29

DIV = (10**9) + 7

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def ncr(n, r, mod=DIV):
	r = min(r, n-r)
	ret = 1
	for i in range(1, r+1):
		ret = ret * (n-i+1) % mod
		ret = ret * mod_inv(i, mod) % mod
	return ret

def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max,mod=DIV):
    fac,finv,inv = [0]*max, [0]*max, [0]*max
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod -inv[mod%i] * (mod//i)%mod
        finv[i] = finv[i-1]*inv[i]%mod
    class CONV:
        def __init__(self):
            pass
        def ncr(self,n,k):
            if(n<k):
                return 0
            if(n<0 or k<0 ):
                return 0
            return fac[n]*(finv[k]*finv[n-k]%mod)%mod
    return CONV()


def main():
    k,q = isRaw()
    ds_orig =isRaw()
    for qidx in range(q):
        n,x,m = isRaw()
        ds = [d%m for d in ds_orig]
        numPluses = [((n-1)//k)+(0 if idx >= (n-1)%k else 1) for idx in range(k)]
        totals = x%m
        numGe =0
        for idx,d in enumerate(ds):
            totals += d*numPluses[idx]
            if totals >= m:
                numGe += totals//m
                totals = totals%m
            if d==0:
                numGe += numPluses[idx]
        print(n-1-numGe)
    return n-1-numGe



if __name__ == "__main__":
    main()


Measured memory_bytes: 92508
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main (){
    vector<int> a(3);
    int ans=0;
    for(int i=0;i <a.size();i++){
        cin >> a[i];
    }
    sort(a.begin(),a.end());
    if((a[1] - a[0]) %2==1){
        ans+=1;
    }
    ans += (a[1]-a[0]+1)/2 +(a[2]-a[1]);
    cout << ans << endl;

    return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <tuple>

#define rep(i,n) for(ll i=0;i<n;i++)
#define dup(x,y) (((x)+(y)-1)/(y)) // dup * y >= x なる最小のdup.
using namespace std;
typedef long long ll;
using Graph = vector<vector<ll>>;
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;}
//	std::cout<<std::fixed<<std::setprecision(10);

int main() {
	int a, b;
	cin >> a >> b;
	if(a>b) {
		int tmp = a;
		a = b;
		b = tmp;
	}
	
	// a < b;
	rep(i, b) {
		cout << a;
	}
	cout << endl;


	return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include <functional>
#include<time.h>
#include <stack>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define ll long long
#define llint long long int
#define sort(s) sort(s.begin(),s.end())
#define reverse(v)  reverse(v.begin(), v.end());
#define Yes(ans) if(ans)cout<<"Yes"<<endl; else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define hei(a) vector<a>
#define whei(a) vector<vector<int>>
constexpr auto mod = 1000000007;


//2のn乗を求めるよ！！！
int ni(int n) {
	if (n == 0)return 1;
	int x = ni(n / 2);
	x *= x;
	if (n % 2 == 1)x *= 2;
	return x;
}

//フィボナッチ数列のx番目を求めるよ！
int f(int x,vector<int> s) {
	if (x == 0)return 0;
	if (x == 1)return 1;
	if (s[x] != 0)return s[x];
	s[x] = f(x - 1,s) + f(x - 2,s);
	return s[x];
}

//aとｂの最大公約数を求めるよ！
llint gcd(llint a, llint b) {
	if (a < b)swap(a, b);
	if (b == 0)return a;
	return gcd(b, a % b);
}



// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

// mod. m での a の逆元 a^{-1} を計算するよ！
long long modinv(long long a, long long 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;
}


//aCbをmod.mで割った余りを求める
ll int c(ll int a, ll int b,ll int m) {
	ll int ans = 1;
	for (ll int i = 0; i < b; i++) {
		ans *= a - i;
		ans %= m;
	}
	for (ll int i = 1; i <= b; i++) {
		ans *= modinv(i, m);
		ans %= m;
	}
	return ans;
}

//m進数のn桁を全列挙やで
void dfs(int m, int n) {

	stack<string> st;
	st.push("");
	while (!st.empty()) {
		string now = st.top();
		st.pop();
		if (now.size() == n) {
			cout << now << endl;
		}
		else {
			for (int i = m-1; i >= 0; i--) {
				string next = now + to_string(i);
				st.push(next);
			}
		}
	}
}

int main(){
	int n, m;
	llint ans = 0;
	cin >> n >> m;
	vector<pair<int, int>> s(n);
	rep(i, 0, n) {
		int a, b;
		cin >> a >> b;
		s[i] = make_pair(a, b);
	}
	sort(s);
	int x = 0;
	rep(i, 0, m) {
		if (s[x].second <= 0) x++;

		ans += s[x].first;
		s[x].second--;
	}
	cout << ans << endl;
	return 0;
}




  


Measured memory_bytes: 1024
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>

#define _CRT_SECURE_NO_WARNINGS
#define TLong long long
#define TBMod 1000000007

int main(int argc, char const *argv[])
{
	int n,a[100007];
	int now = 0,cnt = 0,chk[100007] = { 0 };	// 0: NoProblem, 1:self-Loop
	scanf("%d",&n);
	for (int i = 0; i < n; ++i)	scanf("%d",&a[i]);	// Loading
	do{
		++cnt;
		chk[now] = 1;
		now = a[now] - 1;
		if(chk[now]){
			puts("-1");
			return 0;
		}
	}while(now != 1);
	printf("%d\n", cnt);
	return 0;
}


Measured memory_bytes: 896
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
//#include<boost/multiprecision/cpp_int.hpp>
//#include<boost/multiprecision/cpp_dec_float.hpp>
//namespace mp=boost::multiprecision;
//#define mulint mp::cpp_int
//#define mulfloat mp::cpp_dec_float_100
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
//constexpr int MOD=1000000007;
constexpr int MOD=998244353;
#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define endl "\n"
#define rep(i,n) for(lint (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(lint (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
#define fi first
#define se second
typedef long long lint;
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
const int MAX_N=2e5+5;
//struct edge{lint to,num;};

int main(void){
    int N,K;
    cin >> N >> K;
    int R,S,P;
    cin >> R >> S >> P;
    string T;
    cin >> T;
    int ans=0;
    rep(i,N){
        if(i<K){
            if(T[i]=='r') ans+=P;
            else if(T[i]=='s') ans+=R;
            else ans+=S;
        }
        else{
            if(T[i]==T[i-K]) T[i]='x';
            else{
                if(T[i]=='r') ans+=P;
                else if(T[i]=='s') ans+=R;
                else ans+=S;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3744
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define reps(i,n) for(int i=1;i<(int)(n);i++)

typedef long long ll;
using namespace std;
int main()
{
  string s,t;
  cin>>s>>t;
  ll min=0;
  rep(i,s.length()-t.length()+1){
    ll tmp=0;
    ll num=0;
    for(int j=i;j<i+t.length();j++){
      // cout<<s[j]<<t[num]<<endl;
      if(s[j]==t[num]){
        tmp++;
      }
      num++;
    }
    if(tmp>min)min=tmp;
  }
  ll ans=t.length()-min;
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3620
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define np next_permutation
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define pi acos(-1.0)
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'0'+=16;        で大文字に
//'大文字'+=32;    で小文字に
//s[i]-'0'でchar文字→int数に;
//string s = to_string(int数);
//int n = stoi(string文字列)
//cout << fixed << setprecision (20);   小数点以下2０桁まで
//実行時間制約2秒では２×10^8回くらいまで計算できる


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

  vector<int> p(b);
  int ans=0;
  rep(i,b){
  cin>>p[i];
  ans=max(ans,p[i]);
  }
  
  cout << max(ans-(a-ans)-1,0) << endl;
  
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <cctype>
#include <bits/stdc++.h>
#include <queue>

using namespace std;
// for loop
#define F(i, L, R) for(long i = L; i < R; i++)
#define FE(i, L, R) for(long i = L; i <= R; i++)
// for (reversed)
#define FR(i, L, R) for(long i = L; i > R; i--)
#define FRE(i, L, R) for(long i = L; i >= R; i--)

// data types
#define Int long
#define ul unsigned long
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned shoft

// vectors
typedef vector<int> vi;
typedef vector<long> vl;
typedef vector<long long> vll;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> ii;
#define ALL(c) (c).begin(),(c).end()
#define last(vec) vec.size()-1
#define lastEle(vec) vec[last(vec)]
#define pb push_back
#define InputV(a, n) F(i,0,n){long l; cin >> l; a.pb(l);}

// debug
#define DBG(vari) cerr<<#vari<<" = "<<(vari)<<endl;
#define printA(a, L, R) FE(i, L, R) cout << a[i] << (i==R?'\n':' ')
#define printAF(a, L) printA(a, 0, L-1)
#define printV(a) printA(a, 0, a.size()-1)

// utils
#define char2int(c) (c-'0')
#define bit(x, i) (x&(1<<i))
#define space ' '
#define PI 3.14159265358979323

void printM(vector<vector<long> > &vec, long height, long width){
    F(i, 0, height){
        F(j, 0, width){
            cout << vec[i][j] << space;
        }
        cout << endl;
    }
}

#define TST 0
int main() {
#if TST==1
    ifstream in ("input.txt");
    cin.rdbuf(in.rdbuf());
#endif
    long n;
    cin >> n;
    long W;
    cin >> W;
    vl weight(n+1);
    vl value(n+1);
    FE(i, 1, n){
        cin >> weight[i];
        cin >> value[i];
    }
    // dp table has maximum sum of value
    // for convenience, allocate more memory than actually is
    vvl dp;
    dp.resize(110);
    F(i, 0, dp.size()){
        dp[i].resize(100100);
    }
    FE(i, 0, n){
        FE(j, 0, W+1){
            // if dont put i+1 th bag, sum stays and i ups
            dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
            // if put i+1 th bag, sum increases
            if(i == n)break;
            if(j + weight[i+1] > W)continue;
            dp[i+1][j+weight[i+1]] = max(dp[i+1][j+weight[i+1]], dp[i][j] + value[i+1]);
        }
    }
    cout << dp[n][W] << endl;

#if TST==1
    printM(dp, n+1, W+1);

#endif
}


Measured memory_bytes: 86528
from collections import defaultdict
from math import gcd
import time
import sys
from collections import Counter
import itertools
import math
# read = sys.stdin.buffer.read
# readline = sys.stdin.buffer.readline
# readlines = sys.stdin.buffer.readlines
#input = sys.stdin.readline

start = time.time()
N = int(input())
A = list(map(int, input().split(' ')))
Asum = [i+A[i] for i in range(N)]
Adif = [i-A[i] for i in range(N)]

ans = 0
d = defaultdict(int)
for i in range(N):
    ans += d[Adif[i]]
    d[Asum[i]] += 1

print(ans)


Measured memory_bytes: 66240
#include <iostream>
#include <string>
using namespace std;
int main(){
  string s;
  cin >> s;
  int cnt = 0;
  for(int i = 0;i<s.size();i++){
    if(s[i]=='+'){
      cnt++;
    }
  }
  cout << 2*cnt -  int(s.size()) << endl;
}

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

int main() {
  int N, K;
  int trH[100001];
  cin >> N >> K;
  for (int i = 0; i < N; ++i) cin >> trH[i];
  sort(trH, trH + N);
  int min_d = 1000000000;
  for (int f = 0; f < N - K + 1; ++f) {
    int d = trH[f + K - 1] - trH[f];
    if (d < min_d) min_d = d;
  }
  cout << min_d << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rng(i, a, b) for (int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define gnr(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define per(i, b) gnr(i, 0, b)
#define bg begin()
#define ed end()
#define all(x) x.bg, x.ed
#define vi vector<int>
template <class t, class u>
bool chmax(t &a, u b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class t, class u>
bool chmin(t &a, u b)
{
    if (b < a)
    {
        a = b;
        return true;
    }
    return false;
}

//ll mod = 1000000007;
ll mod = 998244353;

signed main()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    //ll ans = 0;
    vector<set<int>> vs1(n);
    vector<set<int>> vs2(n);
    rep(i, n - 1)
    {
        auto s1 = vs1[i];
        vs1[i + 1] = vs1[i];
        vs1[i + 1].insert(s[i]);
        auto s2 = vs2[n - 1 - i];
        vs2[n - 2 - i] = vs2[n - 1 - i];
        vs2[n - 2 - i].insert(s[n - 1 - i]);
    }
    set<int> pass;
    rep(i, n)
    {
        for (auto &j : vs1[i])
        {
            for (auto &k : vs2[i])
            {
                pass.insert((j - '0') * 100 + (s[i] - '0') * 10 + (k - '0'));
            }
        }
    }
    cout << pass.size() << endl;
    return 0;
}

Measured memory_bytes: 34036
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector< int > a(n - 1), b(n - 1);

    vector< queue< int > > edge(n);
    for (int i = 0; i < n - 1; i++) {
        cin >> a[i] >> b[i];
        --a[i];
        --b[i];
        edge[a[i]].push(i);
        edge[b[i]].push(i);
    }

    int ans = 0; //塗られた色の種類数

    vector< int > ANS(n - 1, 0); //各辺に塗る色，0のときは未訪問
    vector< set< int > > colors(n); //各頂点を端点とする辺に塗られた色の集合

    queue< int > st; //訪問待ちの頂点
    st.push(a[0]);
    colors[a[0]].insert(1);
    colors[b[0]].insert(1);

    while (st.size()) {
        int v = st.front();
        st.pop();
        while (edge[v].size()) {
            int i = edge[v].front();
            edge[v].pop();

            if (ANS[i] == 0 && (v == a[i] || v == b[i])) {

                //訪問待ちの頂点を追加
                if (v == a[i]) {
                    st.push(b[i]);
                } else {
                    st.push(a[i]);
                }

                //色の決定
                if (colors[a[i]].size() == ans || colors[b[i]].size() == ans) {
                    ans++;
                    ANS[i] = ans;
                    colors[a[i]].insert(ans);
                    colors[b[i]].insert(ans);
                    continue;
                }
                for (int j = 1; j <= ans; j++) {
                    if (colors[a[i]].find(j) == colors[a[i]].end() && colors[b[i]].find(j) == colors[b[i]].end()) {
                        ANS[i] = j;
                        colors[a[i]].insert(j);
                        colors[b[i]].insert(j);
                        break;
                    }
                }
                if (ANS[i] == 0) {
                    ans++;
                    ANS[i] = ans;
                    colors[a[i]].insert(ans);
                    colors[b[i]].insert(ans);
                }
            }
        }
    }

    cout << ans << endl;
    for (int i = 0; i < n - 1; i++) {
        cout << ANS[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 82816
#include<stdio.h>
#define N 100
#define WHITE 0
#define GRAY 1
#define BLACK 2
int n,M[N][N];
int color[N],d[N],f[N],tt;
void dfs_visit(int u){
  int v;
  color[u]=GRAY;
  d[u]=++tt;
  for(v=0;v<n;v++){
    if(M[u][v]==0)continue;
    if(color[v]==WHITE){
      dfs_visit(v);
    }
  }
  color[u]=BLACK;
  f[u]=++tt;
}
void dfs(){
  int u;
  for(u=0;u<n;u++)color[u]=WHITE;
  tt=0;
  for(u=0;u<n;u++){
    if(color[u]==WHITE)dfs_visit(u);
  }
  for(u=0;u<n;u++){
    printf("%d %d %d\n",u+1,d[u],f[u]);
  }
}
int main(){
  int u,v,k,i,j;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++)M[i][j]=0;
  }
  for(i=0;i<n;i++){
    scanf("%d %d",&u,&k);
    u--;
    for(j=0;j<k;j++){
      scanf("%d",&v);
      v--;
      M[u][v]=1;
    }
  }
  dfs();
  return 0;
}



Measured memory_bytes: 2104
n = int(input())

def gcd(a,b):
    while b:
        a, b = b, a % b
    return a

ans = 0
if n == 1:
    ans = 1
else:
    for i in range(n):
        i = i + 1
        #ans = ans + i #(i,i,i)
        for j in range(n):
            j = j + 1
            for k in range(n):
                k = k + 1
                ij = gcd(i,j)
                ans = ans + gcd(ij,k)

print(ans)

Measured memory_bytes: 68780
#!/usr/bin/env python3
import sys


MOD = 1000000007  # type: int

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


def solve(N: int):
    from functools import reduce
    from operator import mul

    nn = reduce(mul, range(1,N+1))
    from collections import defaultdict
    

    d = defaultdict(int)
    for i in range(2, N+1):
        t = prime_factorize(i)        

        for j in t:
            d[j] += 1

    ans = 1
    for i,v in d.items():
        if(i == 1): continue
        ans *= (v+1)

    print(ans%MOD)

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3700
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    int a[n];
    vector<int> a0(100010, 0), a1(100010, 0);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        if(i % 2 == 0) a0[a[i]]++;
        else a1[a[i]]++;
    }
    int c = max_element(a0.begin(), a0.end()) - a0.begin();
    int b = max_element(a1.begin(), a1.end()) - a1.begin();
    sort(a0.begin(), a0.end());
    sort(a1.begin(), a1.end());
    if(c == b) {
        cout << min(n - a0[100009] - a1[100008], n - a1[100009] - a0[100008]) << endl;
            return 0;
    }
    else cout << n - a0[100009] - a1[100009] << endl;
    return 0;
}


Measured memory_bytes: 1408
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long int64;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 1e4+5, P = 998244353;
int n, s, t, f[N][N];
int64 fac[N], ifac[N], ans;
char a[N], b[N];
int64 inv(int i) { return i == 1?1:P-P/i*inv(P%i)%P; }
int64 C(int n, int m) { return fac[n]*ifac[m]%P*ifac[n-m]%P; }
int main()
{
    scanf("%s", a+1), scanf("%s", b+1);
    for(int i = 1; a[i]; ++i) 
        if(a[i] == '1'&&b[i] == '1') ++s, ++n;
        else if(a[i] == '1'&&b[i] == '0') ++t, ++n;
    fac[0] = ifac[0] = 1;
    for(int i = 1; i <= n; ++i) fac[i] = fac[i-1]*i%P;
    ifac[n] = inv(fac[n]);
    for(int i = n-1; i; --i) ifac[i] = ifac[i+1]*(i+1)%P;
    for(int i = 0; i <= t; ++i) f[0][i] = fac[i]*fac[i]%P;
    for(int i = 1; i <= s; ++i)
        for(int j = 1; j <= t; ++j)
            f[i][j] = (1ll*f[i-1][j]*i%P*j%P+1ll*f[i][j-1]*j%P*j%P)%P; 
    for(int i = 0; i <= s; ++i) ans = (ans+fac[i]*fac[i]%P*C(n, i)%P*C(s, i)%P*f[s-i][t]%P)%P;
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 389632
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
	String[] inputs = scan.nextLine().split(" ");
	int[] face = new int[6];
	int SOUTH = 2;
	int NORTH = 5;
	int WEST = 4;
	int EAST = 3;
	int TOP = 1;
	int BOTTOM = 6;
	for (int i = 0; i < 6; i++) {
	    face[i] = Integer.parseInt(inputs[i]);
	}
	String commands = scan.nextLine();
	for (int i = 0; i < commands.length(); i++) {
	    String command = commands.substring(i, i+1);
	    if (command.equals("S")) {
		BOTTOM = SOUTH;
		SOUTH = TOP;
		NORTH = 7 - SOUTH;
		TOP = 7 - BOTTOM;
	    } else if (command.equals("N")) {
	        BOTTOM = NORTH;
		NORTH = TOP;
		SOUTH = 7 - NORTH;
		TOP = 7 - BOTTOM;
	    } else if (command.equals("W")) {
		BOTTOM = WEST;
		WEST = TOP;
		EAST = 7 - WEST;
		TOP = 7 - BOTTOM;
	    } else if (command.equals("E")) {
		BOTTOM = EAST;
	        EAST = TOP;
		WEST = 7 - EAST;
	        TOP = 7 - BOTTOM;
	    }
	}
	System.out.println(face[TOP-1]);
    }
    
}

Measured memory_bytes: 26336
#include<bits/stdc++.h>
using namespace std;
set<long long> s;
void Factors(long long  n)
{
    //long long cnt=0;
    for(int i=2; i<=sqrt(n); i++)
    {
        long long x = n;
        while(x%i==0)
        {
            x/=i;
        }
        if(x%i==1)
            {s.insert(i);
            //cout<<i<<" ";
            }
    }
    //cout<<"\n";
    //return cnt;
}

void countDivisors(long long n)
{
    long long cnt = 0;
    for (int i = 1; i <= sqrt(n); i++) {
        if (n % i == 0) {
            // If divisors are equal,
            // count only one
            if (n / i == i)
               {
                //cout<<i<<" ";
                s.insert(i); }

            else // Otherwise count both
                {
                    //cout<<n/i<<" "<<i<<" ";
                    s.insert(n/i);
                    s.insert(i);
                }
        }
    }
    //cout<<"\n";
}
int main()
{
    long long n;
    cin>>n;
    countDivisors(n-1);
     Factors(n);
    cout<<s.size();
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   

using namespace std;
#define i64  long long

#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807



string shuffle_str(string & str, int num)
{
  string S1 (num,0);
  string S2 (str.size() - num,0);
  string out;
  for(int i = 0; i < str.size(); i ++)
  {
    if(i < num) 
    {
      S1[i] = str[i];
  }
  else
  {
    S2[i - num] = str[i];
  }
  }
  out = S2 + S1;
  
  return out;
}

void solve(void)
{

  vector<string> str_data;
  vector<vector<int> > num_data;

  while(true){
    string str;
    vector<int> vec;

    int m;
    int h;
    cin>>str;

    if(str == "-") break;

    cin>>m;

    for (int i = 0; i < m; i++)
    {
      cin>>h;
      str = shuffle_str(str,h);
    }

    cout<<str<<endl;

  }
  return;
}

int main(int argc, const char *argv[])
{

  solve();

  return 0;
}



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

using ll=long long;
const ll MOD=1000000007;

int main() {
  int n;
  string s;
  cin >> n >> s;
  if(n%2==0){
    bool a=true;
    for(int i=0;i<n/2;i++){
      if(s[i]!=s[i+n/2]){
        a=false;
      }
    }
    if(a)
      cout << "Yes" << endl;
    else
      cout << "No" << endl;
  }
  else
    cout << "No" << endl;
}


Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cmath> // sqrt
#define _GLIBCXX_DEBUG // check []
#define DIVISOR 1000000007

using namespace std;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<int64_t, int64_t> pII;

template<typename T>
void cins(vector<T>& arr) { for(T& e: arr) cin >> e; }

#ifdef DEBUG
#define debug(fmt, ...) \
    printf("[debug: %s] " fmt, __func__, __VA_ARGS__)
#define ps(arr) \
    debug("size %ld: ", arr.size()); \
    for(auto e: arr) cout << e << " "; \
    cout << endl;
#else
#define debug(fmt, ...)
#define ps(arr)
#endif


int main(void) {
    int64_t num;
    cin >> num;

    string ans;
    while(1) {
        int64_t idx = (num-1)%26;
        debug("%d\n", idx);
        ans.push_back(idx+'a');
        num -= idx;
        num /= 26;
        if(num == 0) break;
    }

    reverse(ans.begin(), ans.end());
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3636
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
int main(){
	int x,p=4280,w;
	while (~fscanf(stdin, "%d", &x),x!=-1) {
		w = 1150;
		if (x > 30) w += (x - 30) * 160, x -= (x - 30);
		if (x > 20) w += (x - 20) * 140, x -= (x - 20);
		if (x > 10) w += (x - 10) * 125;
		fprintf(stdout, "%d\n", p - w);
	}
	return 0;
}

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

using namespace std;
#define ll long long
#define FOR(i, a, b) for (ll i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define PRINT(item) cout << (item) << endl;
#define PRINT_VEC(V)                                                           \
    for (auto v : (V))                                                         \
        cout << v << ' ';
const int MOD = 1000000007;
/* cout << fixed << setprecision(10) << decimal << endl; */

int N;
using xy = pair<int, int>;
vector<vector<xy>> Data;

bool judge(int bit) {

    // i 人目の証言を検証する
    for (int i = 0; i < N; ++i) {

        // i 人目が「不親切」だったら、証言はすべて無意味
        if (!(bit & (1 << i)))
            continue;

        // それぞれ確認
        for (auto xy : Data[i]) {
            int x = xy.first;  // x が
            int y = xy.second; // y = 1: 正直、y = 0: 不親切

            // y = 1 なのに「不親切」だったらダメ
            if (y == 1 && !(bit & (1 << x)))
                return false;

            // y = 0 なのに「正直者」だったらダメ
            if (y == 0 && (bit & (1 << x)))
                return false;
        }
    }
    return true;
}

int main() {
    /* code */
    cin >> N;
    Data.resize(N);
    REP(i, N) {
        int A;
        cin >> A;
        Data[i].resize(A);
        REP(j, A) {
            cin >> Data[i][j].first >> Data[i][j].second;
            Data[i][j].first--;
        }
    }

    int ans = 0;
    // N人のbit全探索
    for (int bit = 0; bit < (1 << N); ++bit) {
        // 矛盾がなければ正直者を数える
        if (judge(bit)) {
            int count = 0;
            for (int i = 0; i < N; ++i) {
                if (bit & (1 << i)) {
                    count++;
                }
            }
            ans = max(count, ans);
        }
    }
    cout << ans << endl;
    return 0;
}

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

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

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

    int ans = 0;
    set<int> num;
    for(int i=0; i<n; i++){
        num.insert(p[i]);
        if(*num.begin() >= p[i]) ans += 1;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 10368
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll,ll> P;
#define M 1000000007
int main(){
  ll m=M,a,n;m*=m;
  cin>>n;
  for(int i=0;i<5;i++){
    cin>>a;
    m=min(m,a);
  }
  cout<<(n-1)/m+5;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 +c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
const int MOD = 1000000007;
int N,M;
int fac[MAXN];
int inc(int a,int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
    return 1LL * a * b % MOD;
}
void Solve() {
    read(N);read(M);
    if(abs(N - M) > 1) {puts("0");return;}
    fac[0] = 1;
    for(int i = 1 ; i <= max(N,M) ; ++i) {
	fac[i] = mul(fac[i - 1],i);
    }

    int ans = mul(fac[N],fac[M]);
    if(N == M) {
	ans = mul(ans,2);
    }
    out(ans);enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
}


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

using namespace std;

#define FaSt ios::sync_with_stdio(0),cin.tie(0);
#define random uniform_int_distribution<long long>(1, 2000000000000000LL)(rng)

const int N = 1005, M = 1e9 + 7;
long long n, m, dp[N][N], ans;
char a[N][N];
bool solved[N][N];

long long calc(int i, int j)
{
    if (solved[i][j])
    {
        return dp[i][j];
    }
    
    if (i == n - 1 && j == m - 1)
    {
        return 1;
    }
    
    if (i < n - 1 && a[i + 1][j] == '.')
    {
        dp[i][j] += calc(i + 1, j);
        dp[i][j] %= M;
    }
    
    if (j < m - 1 && a[i][j + 1] == '.')
    {
        dp[i][j] += calc(i, j + 1);
        dp[i][j] %= M;
    }
    
    solved[i][j] = 1;
    return dp[i][j];
}

int main()
{
    FaSt
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> a[i][j];
        }
    }
    
    cout << calc(0, 0);
}


Measured memory_bytes: 10240
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<string>
#include<vector>
#include<tuple>
#include<stack>
#include<iomanip>
#include<map>
using namespace std;

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	if (a == 5 && b == 5 && c == 7)cout << "YES";
	else if (a == 5 && b == 7 && c == 5) cout << "YES";
	else if (a == 7 && b == 5 && c == 5) cout << "YES";
	else cout << "NO";
	return 0;
}

Measured memory_bytes: 256
N=gets.to_i
A=gets.split.map &:to_i
ans=1
inc=nil
before=A[0]
A.each do |a|
  if inc.nil?
    if before < a
      inc = true
    elsif before > a
      inc = false
    end
  elsif inc && before > a || !inc && before < a
    ans += 1
    inc = nil
  end
  before = a
end
p ans



Measured memory_bytes: 8452
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

int main(){
  int N;
  cin >> N;
  map<int,int> mp;
  for(int i=0;i<N;i++){
    int a;
    cin >> a;
    mp[a-1]++;
    mp[a]++;
    mp[a+1]++;
  }

  int mx = 0;
  for(auto itr = mp.begin() ; itr!=mp.end() ; itr++){
    mx = max(mx,itr->second);
  }

  cout << mx << endl;
  return 0;
}


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

typedef long long ll;
//loop
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//STL
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

//const
#define MOD 1000000007 //10^9+7:合同式の法

//acronym
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

void Main() {
    int ans;
    int tmp;
    REP(i,5) {
        cin >> tmp;
        if (tmp == 0) {
            ans = i + 1;
        }
    }
    cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	Main();
	return 0;
}


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


int main(){
	int h,w;
	cin >> h >> w;
	char bord[52][52];
	for (int i = 0;i < 52; ++i){
		for (int j = 0; j < 52; ++j){
			bord[i][j]='.';
		}
	}
	for (int i = 1; i <= h; ++i){
		for (int j = 1; j <= w; ++j){
			cin >> bord[i][j];
		}
	}




	int dx[8]={0,-1,0,1};
	int dy[8]={-1,0,1,0};
	int cnt=0;
	for (int i = 1; i <= h; ++i){
		for (int j = 1; j <= w; ++j){
			if(bord[i][j]=='#'){
				for (int k = 0; k < 4; ++k){
					if(bord[i+dy[k]][j+dx[k]]=='.')
						cnt++;
				}
			}
			if(cnt==4){
				cout << "No" << endl;
				return 0;
			}else
				cnt=0;
		}
	}

	cout << "Yes" <<endl;

}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define MT make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define RT return
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;

void solve() {
    int N; // N>=2
    cin >> N;
    vector<pii> C(2 * N);
    ll SA = 0, SB = 0, S = 0;
    rep(i, N) {
        int a, b;
        cin >> a >> b;
        C[i] = { a,i };
        C[i + N] = { b,i };
        SA += a;
        SB += b;
    }
    sort(all(C));

    ll ans = min(SA, SB);
    bool ok = false;
    vi cnt(N);
    rep(i, N) {
        S += C[i].first;
        if (cnt[C[i].second]++) {
            ok = true;
        }
    }
    if (ok) {
        smin(ans, S);
    } else if (C[N - 1].second != C[N].second) {
        smin(ans, S - C[N - 1].first + C[N].first);
    } else {
        ll z = min(
            S - C[N - 2].first + C[N].first,
            S - C[N - 1].first + C[N + 1].first
        );
        smin(ans, z);
    }
    cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	solve();
	return 0;
}

Measured memory_bytes: 2176
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<functional>
#include<math.h>

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

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

	int s, t;
	s = (a + d - 1) / d;
	t = (c + b - 1) / b;
	puts(s >= t ? "Yes" : "No");

	return 0;
}

Measured memory_bytes: 3620
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <limits.h>
#include <math.h>
#include <time.h>
#include <queue>
#include <stdarg.h>
#include <map>
#include <vector>
#include <algorithm>
#include <stack>
#include <iostream>
#include <numeric>
#include <set>

#define ll long long

using namespace std;

void
solve() {
  ll n;
  cin>>n;

  ll temp;
  ll value = 1;
  ll top = 1;
  top *= 1e9;
  top *= 1e9;
  bool valid = true;
  for (int i=0; i<n; i++) {
    cin>>temp;

    if (temp == 0 || value == 0) {
      value = 0;
    }
    else {
      if (temp > top / value) {
        valid = false;
        value = -1;
      }
      else {
        value *= temp;
      }
    }
  }
  cout<<value<<endl;
}

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

  int t = 1;
  //cin>>t;

  while (t > 0) {
    t--;
    solve();
  }

  return 0;
}



Measured memory_bytes: 3640