akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
bool prime(int a){
  if(a==1){
    return false;
  }
  for(int i=2;i*i<=a;i++){
    if(a%i==0){
      return false;
    }
  }
  return true;
}
int main(){
  int Q,lm=0;
  cin>>Q;
  unordered_map<int,int> mp;
  for(int i=1;i<=100000;i++){
    mp[i]=mp[i-1];
    if(i%2==1 && prime(i) && prime((i+1)/2)){
      //cout<<i<<" "<<(i+1)/2<<endl;
      mp[i]++;
      lm++;
    }
  }
  for(int i=0;i<Q;i++){
    int a,b;
    cin>>a>>b;
    cout<<mp[b]-mp[a-1]<<endl;
  }
}

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

int main() {
  int N, X, Y;
  cin >> N >> X >> Y;
  Graph G(N + 1);
  queue<P> q;
  map<P, int> m;
  vector<int> cnt(N, 0);

  rep(i, N + 1) {
    if (i == 0) continue;
    if (i > 1) G.at(i).push_back(i - 1);
    if (i < N) {
      G.at(i).push_back(i + 1);
      q.push(P(i, i + 1));
      m[P(i, i + 1)] = 1;
      cnt.at(1)++;
    }
  }

  G.at(X).push_back(Y);
  G.at(Y).push_back(X);
  q.push(P(X, Y));
  m[P(X, Y)] = 1;
  cnt.at(1)++;

  while (!q.empty()) {
    auto p = q.front();
    auto d = m.at(p);
    for (auto s : G.at(p.second)) {
      if (p.first >= s) continue;
      if (m.count(P(p.first, s))) continue;
      q.push(P(p.first, s));
      m[P(p.first, s)] = d + 1;
      cnt.at(d + 1)++;
    }
    for (auto f : G.at(p.first)) {
      if (f >= p.second) continue;
      if (m.count(P(f, p.second))) continue;
      q.push(P(f, p.second));
      m[P(f, p.second)] = d + 1;
      cnt.at(d + 1)++;
    }
    q.pop();
  }

  rep(i, N) {
    if (i == 0) continue;
    cout << cnt.at(i) << endl;
  }
}


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

const int maxN = 1005;

int main() {
    int n;
    cin >> n;
    if (n < 4) {
        cout << 1 << endl;
        return 0;
    }
    rep(i,n) {
        for (int j=2; j<32; ++j) {
            int ni = n-i;
            int c = 0;
            while (ni % j == 0) {
                ni /= j;
                c++;
            }
            if (ni == 1 && c >= 2) {
                cout << n-i << endl;
                return 0;
            }
        }
    }

    return 0;
}

Measured memory_bytes: 3628
import java.util.List;
import java.util.ArrayList;

import java.util.Scanner;
class Main{
    static public void  main(String[] av){
        int sum=0;

        Scanner sc =new Scanner(System.in);
       // int n =sc.nextInt();
int ch =1;
List<Integer> intlist = new ArrayList<Integer>();
List<Integer> stack = new ArrayList<Integer>();
String ss= sc.nextLine();

String[] f = ss.split(" ", 0);
/*
for(int k =0;k<f.length ;k++) {
    System.out.println(f[k]);
}
*/

for(int k =0;k<f.length ;k++) {
    String s= f[k];
/*
    if (s==null){
        ch=0;
        break;
    }
    */
    if (s.contains("+")){
       intlist.add(-1);
       
        continue;
    }
    if (s.contains("-")){
        intlist.add(-2);
        
        continue;
    }
    if (s.contains("*")){
        intlist.add(-3);
       
        
        continue;
    }
    if (s.contains("/")){
        intlist.add(-4);
       
        continue;
    }
    intlist.add(Integer.valueOf(s));
   
    }

    for(int i=0;i<f.length;i++){
        if ( intlist.get(i)>=0){
            stack.add(intlist.get(i));
                }
        else{
            int v1= stack.get(stack.size()-1);
            stack.remove(stack.size()-1);
            int v2= stack.get(stack.size()-1);
            stack.remove(stack.size()-1);
            if (intlist.get(i)==(-1)){
                stack.add(v2+v1);
            }
            else if (intlist.get(i)==(-2)){
                stack.add(v2-v1);
            }
            else if (intlist.get(i)==(-3)){
                stack.add(v2*v1);
            }
            else if (intlist.get(i)==(-4)){
                stack.add(v2/v1);
            }
        }
    }
    System.out.println(stack.get(0));

}

}







Measured memory_bytes: 26336
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<map>

using namespace std;

template<typename A, typename B> bool chmin(A &a, const B &b){ return b < a && (a = b, true); }
template<typename A, typename B> bool chmax(A &a, const B &b){ return a < b && (a = b, true); }

int main(){
  string s,t;
  cin >> s >> t;
  if (s[0] == t[2] && s[1] == t[1] && s[2] == t[0]){
    cout << "YES\n";
  }
  else{
    cout << "NO\n";
  }
  return 0;
}

Measured memory_bytes: 256
N=int(input())
W=[input() for i in range(N)]

M=len(W)
if M!=len(set(W)):
    print("No")
    exit()
    
for i in range(N-1):
    if W[i][-1]!=W[i+1][0]:
        print("No")
        exit()

print("Yes")

Measured memory_bytes: 3060
n  = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

sum = 0
sum += b[a[0]-1]
for i in range(1,n):
    sum += b[a[i]-1]
    if a[i]-a[i-1]==1:
        sum += c[a[i-1]-1]

print(sum)

Measured memory_bytes: 3064
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <bitset>
#include <map>
#include <vector>
#include <queue>
typedef long long ll;
using namespace std;
const int maxn=(int)1e5+100;
const int inf=0x3f;
struct edge{
    int to,cost;
    edge(int a,int b){to=a;cost=b;}
};
vector<edge> G[8*maxn+5];
map<pair<int,int>,int> mp;
int n,m;
int dis[8*maxn+5];
bool vis[8*maxn+5];
int tot;

void addedge(int a,int b,int w){
    G[a].push_back(edge(b,w));
    G[b].push_back(edge(a,w));
}

int add(int a,int b){
    if(mp.find(make_pair(a,b))!=mp.end()) return mp[make_pair(a,b)];
    return mp[make_pair(a,b)]=++tot;
}

void spfa(int st){
    memset(dis,0x3f,sizeof(dis));
    dis[st]=0;
    memset(vis,false,sizeof(vis));
    queue<int> que;
    que.push(st);
    vis[st]=true;
    while(!que.empty()){
        int u=que.front();
        que.pop();vis[u]=false;
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i].to,w=G[u][i].cost;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                if(!vis[v]){
                    vis[v]=true;
                    que.push(v);
                }
            }
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    tot=n;
    for(int i=1;i<=m;i++){
        int u,v,c;
        scanf("%d%d%d",&u,&v,&c);
        int t1=add(u,c);
        int t2=add(v,c);
        addedge(t1,t2,0);
        addedge(u,t1,1);
        addedge(v,t2,1);
    }
    spfa(1);
    if(dis[n]>2*m+100) printf("-1\n");
    else printf("%d\n",dis[n]/2);
    return 0;
}

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

using namespace std;

const int INF = 1 << 29;

template <typename T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

template <typename T>
bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  vector<int> H(N);
  for (int i = 0; i < N; i++) {
    cin >> H[i];
  }

  vector<int> dp(N, INF);
  dp[0] = 0;
  for (int i = 0; i < N; i++) {
    if (i + 1 < N) chmin(dp[i + 1], dp[i] + abs(H[i + 1] - H[i]));
    if (i + 2 < N) chmin(dp[i + 2], dp[i] + abs(H[i + 2] - H[i]));
  }

  cout << dp[N - 1] << "\n";
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define INF pow(10, 9) + 7
#define rep(i, N) for(ll i = 0; i < N; i++)
#define rep2(i, j, k) for(ll i = j; i < k; i++)
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define chmax(x, y) x = max(x, y)
#define print(x) cout << x << "\n"
#define printv(vec) rep(i, vec.size()) cout << vec[i] << " "
#define ALL(v) v.begin(), v.end()
#define SUM(v) accumulate(ALL(v), 0)
#define MAX(v) *max_element(ALL(v))
#define MIN(v) *min_element(ALL(v))
#define SORT(v) sort(ALL(v))
#define REV(v) reverse(ALL(v))
typedef long long ll;
using namespace std;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vs = vector<string>;
using vvs = vector<vector<string>>;

struct union_find{

  vl parent;

  void init(ll n) {
    rep(i, n) parent.push_back(i);
    return;
  }

  ll root(ll n){
    if(parent[n] == n) return n;
    return parent[n] = root(parent[n]);
  }

  bool is_same(ll a, ll b){
    return root(a) == root(b);
  }

  void unite(ll a, ll b){
    if(is_same(a, b)) return;
    parent[root(b)] = root(a);
    return;
  }
};

void solve(){
	
	ll N, M;
	cin >> N >> M;
	vl p(N);
	rep(i, N) cin >> p[i];
	vvl x(M, vl(2));
	rep(i, M) cin >> x[i][0] >> x[i][1];
	ll ans = 0;
	union_find uf;
	uf.init(N);
	rep(i, M) uf.unite(x[i][0] - 1, x[i][1] - 1);
	rep(i, N) ans += uf.is_same(i, p[i] - 1);
	print(ans);
}	

int main(){
    
    fastio;
	solve();
    
	return 0;
	
}


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

int main(){
	string s,t;
	cin >> s >> t;
	sort(s.begin(),s.end());
	sort(t.begin(),t.end());
	reverse(t.begin(),t.end());
	if(s<t) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
using vi = vector<int64_t>;
using vvi = vector<vi>;
using ll = int64_t;
using P = pair<ll,ll>;
int64_t INF = 1000000007;
// int64_t INF = 9223372036854775807;
// int64_t INF = 998244353;

int main() {
    // fasten cin
    cin.tie(0);
    ios::sync_with_stdio(false);
    // implement
    ll n,m;
    cin >> n >> m;
    ll res = 0;
    if(2*n>=m){
        res = m/2;
    }else{
        res = n + (m-2*n)/4;
    }
    cout << res << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

int main(int argc, const char * argv[]) {
    // insert code here...
    //int a,b,c;
    string s;
    
    cin>>s;
    
    if(s[2]==s[3] && s[4]==s[5])
    {
    cout << "Yes" << endl;
    return 0;
    }
    else
    {
        cout << "No" << endl;
        return 0;
    }
}

Measured memory_bytes: 256
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <cassert>
#include <numeric>
#include <functional>
#include <cassert>
//#include <numeric>
#pragma warning(disable:4996) 
 
typedef long long ll;
typedef unsigned long long ull;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF  9223300000000000000
#define LINF2 1223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;

using namespace std;

char str[500][505];
int  a[500][505];
int  b[500][501];

void solve()
{
    int h, w;
    scanf("%d%d", &h, &w);
    int i, j;
    for (i = 0; i < h; i++) {
        scanf("%s", str[i]);
    }

    for (i = 0; i < h; i++) {
        for (j = 0; j < w; j++) {
            if (j == 0) a[i][j] = 1;
            if (i % 2 == 0 && j < w - 1) a[i][j] = 1;
            if (j == w - 1) b[i][j] = 1;
            if (i % 2 == 1 && j > 0) b[i][j] = 1;
            if (str[i][j] == '#') {
                a[i][j] = b[i][j] = 1;
            }
        }
    }

    for (i = 0; i < h; i++) {
        for (j = 0; j < w; j++) {
            if (a[i][j]) {
                printf("#");
            }
            else {
                printf(".");
            }
        }
        printf("\n");
    }
    printf("\n");
    for (i = 0; i < h; i++) {
        for (j = 0; j < w; j++) {
            if (b[i][j]) {
                printf("#");
            }
            else {
                printf(".");
            }
        }
        printf("\n");
    }
    return;
}

int main(int argc, char* argv[])
{
#if 1
    solve();
#else
    int T;
    scanf("%d", &T);
    int t;
    for(t=0; t<T; t++) {
        //printf("Case #%d: ", t+1);
        solve();
    }
#endif
    return 0;
}



Measured memory_bytes: 2816
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int a = s.nextInt();
        List<String> list = new ArrayList<String>();
        List<String> list2 = new ArrayList<String>();
        
        for(int i = 0; i <= a; i++){
            String x = s.nextLine();
            list.add(x.toLowerCase());
        }
        Collections.sort(list);
        Collections.reverse(list);
        list2.add(list.get(0));
        for(int i = 1; i < list.size(); i++){
            if(list.get(i).length() <= 10 && list.get(i).length() >= 1 && !list.get(i).equals(" ") && !(list.get(i).equals(list2.get(list2.size()-1)))){
                list2.add(list.get(i));
            }
        }
        System.out.println(list2.size());
    }
}

Measured memory_bytes: 74440
##a = int(stdin.readline().rstrip())
##b, c = [int(x) for x in stdin.readline().rstrip().split()]
##s = stdin.readline().rstrip()
##a = list(set(b))  重複を削除
##a = list(map(int,[int(x) for x in stdin.readline().rstrip().split()])) a[0, 1, 2, ...]
##a = [[0] * 2 for _ in range(n)]  a[0,0]
##v = [s[i: i+2] for i in range(0, len(s), 2)]
##  s="12345678" を v=["12","34","56","78"] にするイメージ
##s = "".join(list)リストを文字列に変換[""]は区切り文字
##a.sort(key=itemgetter(1))リストをソートできるよ(from operator import itemgetterが必要)
##sort_p = sorted(p) 昇順ソート

# -*- coding: utf-8 -*-
from sys import stdin
from operator import itemgetter
from collections import deque, Counter
import math
import pprint
from functools import reduce
import numpy as np
import random
import bisect
import copy
# stdin = open("sample.txt")


MOD = 1000000007
INF = float('inf')
alpha = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]

def keta(kazu): # 入力されたintを桁ごとに分解，リストで出力
    kazu_str = str(kazu)
    kazu_list = [int(kazu_str[i]) for i in range(0, len(kazu_str))]
    return kazu_list

def gcd(*numbers): # 最小公倍数
    return reduce(math.gcd, numbers)

def combination(m,n): # mCn
    
    if n > m:
        return 'すまん'
    return math.factorial(m) // (math.factorial(m-n) * math.factorial(n))

def pow_k(x,n):  # (x**n)の計算の高速化
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
    return K * x

def fact(n): # nの素因数分解の結果を辞書で出力 fuct(24) → {2: 3, 3: 1}
    arr = {}
    temp = n
    for i in range(2,int(n**0.5)+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr[i] = cnt
    if temp != 1:
        arr[temp] = 1
    if arr == {}:
        arr[n] = 1
    return arr


    
def main():
    N = int(stdin.readline().rstrip())
    a = {i:0 for i in range(10001)}
    
    for x in range(1,100):
        for y in range(1,100):
            for z in range(1,100):
                n = x**2 + y**2 + z**2 + x*y + y*z + z*x
                if n <= 10000:
                    a[n] += 1
    for i in range(1,N+1):
        print(a[i])
                    
main()

Measured memory_bytes: 27884
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>
#include <numeric>
#include <string.h>
#include <sys/time.h>
#include <random>


#define fs first
#define sc second
#define endl "\n"

using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef pair<int, int> P;

int main(){
    int n;  cin >> n;
    vector<int> v(n+1), w(n+1);
    for(int i = 1; i <= n; i++){
        cin >> v[i] >> w[i];
    }
    if(n == 1){
        int q;  cin >> q;
        for(int i = 0; i < q; i++){
            int x, L;   cin >> x >> L;
            if(w[x] <= L)   cout << v[x] << endl;
            else    cout << 0 << endl;
        }
        return 0;
    }

    int depth = 1;
    for(int i = 1; i < 30; i++){
        if((1 << i) - 1 >= n){
            depth = i;
            break;
        }
    }

    int d2 = depth / 2;
    int num1 = (1 << d2) - 1;
    int wMax = 100000;
    vector<vector<int>> dp(num1+1, vector<int>(wMax+1, 0));

    vector<bool> state(n, true);
    for(int i = 1; i <= num1; i++){
        state[i] = false;
    }

    dp[1][w[1]] = v[1];
    for(int i = 2; i <= num1; i++){
        int bef = i / 2;
        for(int j = 0; j <= wMax; j++){
            dp[i][j] = max(dp[i][j], dp[bef][j]);
            if(j + w[i] <= wMax){
                dp[i][j+w[i]] = max(dp[i][j+w[i]], dp[bef][j] + v[i]);
            }
        }
    }

    // i番目までの頂点で、重さj以下のうち最大の価値がdp[i][j]
    for(int i = 1; i <= num1; i++){
        for(int j = 0; j < wMax; j++){
            dp[i][j+1] = max(dp[i][j+1], dp[i][j]);
        }
    }

    int q;  cin >> q;
    for(int l = 0; l < q; l++){
        int x, L;   cin >> x >> L;
        vector<P> wvList; wvList.emplace_back(P(0, 0));
        while(state[x]){
            vector<P> wvList_tmp;
            for(auto wv: wvList){
                if(wv.fs + w[x] <= L){
                    wvList_tmp.emplace_back(P(wv.fs + w[x], wv.sc + v[x]));
                }
            }
            x /= 2;
            for(auto wv: wvList_tmp){
                wvList.emplace_back(wv);
            }
        }

        int res = 0;
        for(auto wv: wvList){
            int remain = L - wv.fs;
            res = max(res, wv.sc + dp[x][remain]);
        }
        cout << res << endl;
    }



    return 0;
}


Measured memory_bytes: 206540
# -*- coding: utf-8 -*-
"""
Created on Mon Aug  6 17:15:00 2018

@author: Yuki
"""

N = int(input())

A = list(input().split())
A = [int(i) for i in A]
#
#def get_f_value(m, A):
#    mod_list = [m%i for i in A]
#    return sum(mod_list)
#
#def gcd(a, b):
#	while b:
#		a, b = b, a % b
#	return a
#def lcm(a, b):
#	return a * b // gcd (a, b)
#
#def get_lcm_from_list(A):
#    lcm_list = [lcm(A[i], A[i+1]) for i in range(len(A)-1)]
#    return max(lcm_list)
#
#lcm_value = get_lcm_from_list(A)
#res = []
#for m in range(lcm_value):
#    res.append(get_f_value(m, A))
#print(max(res))

print(sum(A) - N)


Measured memory_bytes: 3316
/*  -*- coding: utf-8 -*-
 *
 * d.cc: D - Double Landscape
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>

using namespace std;

/* constant */

const int MAX_N = 1000;
const int MAX_M = 1000;
const int MAX_K = MAX_N * MAX_M;
const int INF = 1 << 30;
const int MOD = 1000000007;

/* typedef */

typedef long long ll;

/* global variables */

int as[MAX_N + 1], bs[MAX_M + 1];

/* subroutines */

/* main */

int main() {
  int n, m;
  scanf("%d%d", &n, &m);

  for (int i = 0; i < n; i++) scanf("%d", as + i);
  for (int i = 0; i < m; i++) scanf("%d", bs + i);

  sort(as, as + n);
  sort(bs, bs + m);
  as[n] = bs[m] = INF;

  for (int i = 0; i + 1 < n; i++)
    if (as[i] == as[i + 1]) {
      puts("0");
      return 0;
    }
  for (int i = 0; i + 1 < m; i++)
    if (bs[i] == bs[i + 1]) {
      puts("0");
      return 0;
    }

  int cnt = 1, k = n * m;
  for (int x = k, i = n, j = m; x >= 1 && cnt > 0; x--) {
    while (i > 0 && as[i - 1] >= x) i--;
    while (j > 0 && bs[j - 1] >= x) j--;

    int d;
    if (as[i] == x && bs[j] == x)
      d = 1;
    else if (as[i] == x && bs[j] != x)
      d = (m - j);
    else if (as[i] != x && bs[j] == x)
      d = (n - i);
    else
      d = (n - i) * (m - j) - (k - x);
    
    cnt = (d <= 0) ? 0 : (ll)cnt * d % MOD;
  }

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
double a[55];
int n;

int main()
{	cin>>n;
	for(int i=1;i<=n;++i)
		cin>>a[i];
	sort(a+1,a+n+1);
	for(int i=2;i<=n;++i)
	{
		a[i]=(a[i-1]+a[i])/2;
		sort(a+i,a+n+1);
	}
	cout<<a[n]<<endl;
	return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import bisect

N = int(input())
L = list(map(int,input().split()))

count = 0
L.sort()
for i in range(N-2):
    for j in range(i+1,N-1):
        k = bisect.bisect_left(L,L[i]+L[j])
        count += k - j - 1 
        
print(count)

Measured memory_bytes: 3188
from operator import itemgetter
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

mod = 10 ** 9 + 7


class Combination:
    """
    SIZEが10^6程度以下の二項係数を何回も呼び出したいときに使う
    使い方:
    comb = Combination(SIZE, MOD)
    comb(10, 3) => 120
    """

    def __init__(self, N, MOD=10 ** 9 + 7):
        self.MOD = MOD
        self.fact, self.inv = self._make_factorial_list(N)

    def __call__(self, n, k):
        if k < 0 or k > n:
            return 0
        res = self.fact[n] * self.inv[k] % self.MOD
        res = res * self.inv[n - k] % self.MOD
        return res

    def _make_factorial_list(self, N):
        fact = [1] * (N + 1)
        inv = [1] * (N + 1)
        MOD = self.MOD
        for i in range(1, N + 1):
            fact[i] = (fact[i - 1] * i) % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            inv[i - 1] = (inv[i] * i) % MOD
        return fact, inv


def main():
    H, W, N = map(int, input().split())
    XY = list(tuple(map(int, input().split())) for _ in range(N))

    comb = Combination(H + W + 10, mod)
    fact = tuple(comb.fact)
    inv = tuple(comb.inv)

    edge = [[] for _ in range(N + 2)]
    indeg = {i: 0 for i in range(N + 2)}

    edge[0].append((N + 1, comb(H+W-2, H-1)))
    indeg[N + 1] += 1
    for i, (x1, y1) in enumerate(XY, 1):
        # start->i
        edge[0].append((i, comb(x1+y1-2, x1-1)))
        indeg[i] += 1
        # i->goal
        edge[i].append((N + 1, comb(H+W-x1-y1, H-x1)))
        indeg[N + 1] += 1
        for j, (x2, y2) in enumerate(XY, 1):
            if i == j:
                continue
            if x1 <= x2 and y1 <= y2:
                edge[i].append((j, comb(x2+y2-x1-y1, x2-x1)))
                indeg[j] += 1

    order = sorted(indeg.items(), key=itemgetter(1))
    dp = [0] * (N + 2)
    dp[0] = -1
    for s, _ in order:
        for t, path in edge[s]:
            dp[t] = (dp[t] - path * dp[s] + mod) % mod
    print(dp[N + 1])


if __name__ == "__main__":
    main()

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

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

using namespace std;

int main(){
	int k; scanf("%d",&k);
	int ans=0;
	for(int a=1;a<=k;a++) for(int b=1;b<=k;b++) for(int c=1;c<=k;c++) ans+=gcd(gcd(a,b),c);
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 3828
#include<iostream>
#include<queue>
#include<algorithm>
#include<utility>
#include<cmath>

using namespace std;

const int maxn = 1e2 + 5;
int n, w, b[maxn];
pair<int, int> a[maxn];

double h(int idx, long long wt) {
	long long curw = wt;
	int curv = 0;
	for(int i = idx + 1; i <= n; i++) {
		long long diff = w - curw;
		if(diff >= a[i].first) {
			curv += a[i].second;
			curw += a[i].first;
		} else {
			curv += ((double) a[i].second) / a[i].first * diff;
			break;
		}
	}
	return curv;
}

int bab() {
	priority_queue< tuple<double, int, long long, int> > pq;
	pq.push({0, 0, 0, 0});
	int ans = 0;
	while(!pq.empty()) {
		auto e = pq.top();
		pq.pop();
		int ev = get<1>(e); long long ew = get<2>(e); int ei = get<3>(e);
		for(int i = ei + 1; i <= n; i++) {
			double cv = ev + a[i].second + h(i, ew + a[i].first);
			if(ew + a[i].first <= w && cv > ans) {
				pq.push({cv, ev + a[i].second, ew + a[i].first, i});
				ans = max(ans, ev + a[i].second);
			}
		}
		ans = max(ans, ev);
	}
	return ans;
}

bool cmp(pair<int, int> &i, pair<int, int> &j) {
	return ((double) i.second) / i.first > ((double) j.second) / j.first;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> w;
	for(int i = 1; i <= n; i++) {
		cin >> a[i].first >> a[i].second;
	}
	sort(a + 1, a + 1 + n, cmp);
	cout << bab() << endl;
	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using V = vector<ll>;
#define _GLIBCXX_DEBUG
#define rep(i, a) for(int i = 0; i < a; i++)
#define ALL(v) v.begin(), v.end()

int main(){
    int s; cin>>s;
    int ans=0;
    while(s>0){
        if(s%10==1) ans++;
        s/=10;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
using System;

class _0042 {
    static readonly int N = 1000;
    static readonly int W = 1000;
    public static void Main() {
        int w, n, k = 0;
        int mc, mw;
        int[][] c = new int[N + 1][];
        int[,] dp = new int[N + 1, W + 1];

        c[0] = new int[1] { 0 };
        for (int i = 0; i <= N; i++)
            for (int j = 0; j <= W; j++)
                dp[i, j] = 0;
        while (true) {
            w = int.Parse(Console.ReadLine());
            if (w == 0) break;
            n = int.Parse(Console.ReadLine());
            for (int i = 1; i <= n; i++)
                c[i] = Array.ConvertAll(Console.ReadLine().Split(','), s => int.Parse(s));
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= w; j++)
                    if (j - c[i][1] >= 0 && dp[i - 1, j - c[i][1]] + c[i][0] > dp[i - 1, j])
                        dp[i, j] = dp[i - 1, j - c[i][1]] + c[i][0];
                    else
                        dp[i, j] = dp[i - 1, j];
            Console.WriteLine("Case {0}:", ++k);
            mc = dp[n, w]; mw = w;
            for (int i = 1; i < w; i++)
                mw = (dp[n, i] == mc && mw > i) ? i : mw;
            Console.WriteLine(mc);
            Console.WriteLine(mw);
        }
    }
}

Measured memory_bytes: 13440
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
//#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
//#define mt make_tuple
//typedef tuple<int,int,int> tp;
//typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(){
	int x,n;
	cin>>x>>n;
	vi in(n+1);
	rep(i,n)cin>>in[i+1];
	in.pb(inf);
	int q;cin>>q;
	int a=0,b=x,c=0,d=x,T=1;
	while(q--){
		int t,s;
		cin>>t>>s;
		while(in[T]<=t){
			int tt=in[T]-in[T-1];
			if(T%2){
				a=min(b,a+max(0,tt-c));
				b=b;
				c=max(c-tt,0);
				d=max(d-tt,0);
			}else{
				a=a;
				b=max(a,b-max(0,tt-(x-d)));
				c=min(c+tt,x);
				d=min(d+tt,x);
			}
			T++;
		}
		int tt=t-in[T-1];
		int out;
		if(s<=a)out=c;
		else if(b<=s)out=d;
		else out=c+s-a;
		if(T%2)out-=tt;
		else out+=tt;
		cout<<max(0,min(x,out))<<endl;
	}
}









Measured memory_bytes: 1656
#include<stdio.h>
#include<stdlib.h>
long long cmp(const void *a,const void *b){
  return *(long long*)a - *(long long*)b;
}

long long lllabs(long long a){
  if(a<0){
    return -a;
  }else{
    return a;
  }
}

int main(){
  long long n;
  long long a[500000] = {};
  long long i = 0;
  long long ft;
  long long st;
  long long fsum = 0;
  long long ssum = 0;
  scanf("%lld",&n);
  for(i=0;i<n;i++){
    scanf("%lld",&a[i]);
    a[i] = a[i] - (i+1);
  }
  qsort(a,n,sizeof(long long),cmp);
  if(n%2==1){
    ft = a[n/2];
    st = a[n/2];
  }else{
    ft = (a[n/2]+a[n/2-1])/2;
    st = (a[n/2]+a[n/2-1])/2 + 1;
  }
  for(i=0;i<n;i++){
    fsum += lllabs(a[i] - ft);
  }
  for(i=0;i<n;i++){
    ssum += lllabs(a[i] - st);
  }
  if(fsum > ssum){
    printf("%lld",ssum);
  }else{
    printf("%lld",fsum);
  }
  return 0;
}
    

Measured memory_bytes: 5628
def q2():
    N = int(input())
    V = [int(i) for i in input().split()]
    C = [int(i) for i in input().split()]

    ans = 0
    for i in range(N):
        if V[i] - C[i] > 0:
            ans += V[i] - C[i]
    return ans

if __name__ == '__main__':
    print(q2())


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

int main()
{
      int n, i;
    cin >> n;
    for (i = 1; i <= 10; i++)
    {
        if (1000 * i >= n)
            break;
    }
    cout << (1000 * i - n);
    return 0;
}

Measured memory_bytes: 3632
# 2019/04/27
# AtCoder Beginner Contest 125 - B

# Input
n = int(input())
v = list(map(int,input().split()))
c = list(map(int,input().split()))

psum = 0
# Calc
for i in range(n):
    if v[i] > c[i]:
        psum += v[i] - c[i]

# Output
print(psum)


Measured memory_bytes: 2940
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        for (int i = 0; i < 5; i++) {
            int x = in.nextInt();
            if (x == 0) {
                System.out.println(i + 1);
                return;
            }
        }
    }
}


Measured memory_bytes: 35764
from collections import Counter
from collections import OrderedDict
N, K = map(int, input().split())
cnt = Counter(map(int, input().split()))
tot = 0
if len(cnt) <= K:
    print(0)
else:
    k = []
    for i in cnt.values():
        k.append(i)
    k.sort()
    for i in range(len(cnt)-K):
        tot += k[i]
    print(tot)


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

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

int main() {
    int n;
    ll res=1;
    bool flag=false;
    bool not_zero=true;
    cin >> n;
    rep(i,n){
        ll tmp;
        cin >> tmp;
        if (res > res*tmp){
            flag = true;
        }
        res*=tmp;
        if (tmp==0){
            not_zero=false;
        }
        if (res>1000000000000000000 || res<0){
            flag=true;
        }
    }
    if(not_zero && flag){
        cout << -1 << endl;
    }else{
        cout << res << endl;
    }
    

}

Measured memory_bytes: 3636
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    A = LMIIS()
    for a in A:
        if a % 2== 0:
            if a % 3 == 0 or a % 5 == 0:
                continue
            else:
                print('DENIED')
                return
    print('APPROVED')

    

if __name__ == '__main__':
    main()

Measured memory_bytes: 38384
// includes {{{
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<random>
#include<cassert>
#include<bitset>
#include<cstdlib>
// #include<deque>
// #include<multiset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  ll a, v, b, w, t;
  cin >> a >> v >> b >> w >> t;
  if(v > w) {
    cout << (abs(a - b)  <= t * (v - w) ? "YES": "NO") << endl;
  } else {
    cout << "NO" << endl;
  }

  return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
using vi = vector<ll>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vs = vector<string>;
using vp = vector<pii>;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (ll)((x).size())
#define all(x) (x).begin(), (x).end()
#define each(a, x) for (auto&& a : (x))
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, n) for (ll i = (a); i < (n); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
#define _per(i, n) peri(i, 0, n)
#define peri(i, a, n) for (ll i = (n) - 1; i >= (a); --i)
#define per(...) _overload3(__VA_ARGS__, peri, _per)(__VA_ARGS__)
const int INF = 1e9;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
const double PI = acos(-1.0);
const int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
template<typename T> inline void chmax(T& a, const T& b) {if (a < b) a = b;}
template<typename T> inline void chmin(T& a, const T& b) {if (a > b) a = b;}
template<typename T> inline void print(const T& x) {cout << x << "\n";}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U>& p) {is >> p.fi >> p.se; return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, const pair<T, U>& p) {os << p.fi << " " << p.se; return os;}
template<typename T> istream& operator>>(istream& is, vector<T>& v) {each(in, v) is >> in; return is;}
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {rep(i, sz(v)) {os << v[i] << (i + 1 != sz(v) ? " " : "");} return os;}
struct Init {Init() {ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(10);}} init;

inline ll gcd(ll a, ll b) {
    /* aとbの最大公約数を返す */
    return b ? gcd(b, a % b) : a;
}

map<ll, ll> primeFactorize(ll n) {
    /* nの素因数分解を返す */
    map<ll, ll> prime_factors;
    ll m = n;
    for (ll i = 2; i < sqrt(n) + 1; ++i) {
        if (m < 1) break;
        while (m % i == 0) {
            ++prime_factors[i];
            m /= i;
        }
    }
    if (m != 1) ++prime_factors[m];
    return prime_factors;
}


int main() {
    ll a, b; cin >> a >> b;
    print(sz(primeFactorize(gcd(a, b)))+1);
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>

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

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

  for (int i = 1; i <= n; i++) {
    if (i % 15 == 0)
      continue;
    if (i % 5 == 0)
      continue;
    if (i % 3 == 0)
      continue;

    ans += i;
  }

  cout << ans << endl; }

Measured memory_bytes: 3636
/*
Author: Arham_doshi
@quote "Code like there's no tommorow!"
 ***************************************   UNAUTHORISED COPYING OF CODE PROHIBITED   **********************************
*/
#include <bits/stdc++.h>

#define int         long long
#define double      long double
#define pb          push_back
#define pf          push_front
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define piii           pair<int,pair<int,int> >
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(),(a).rend()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        998244353 
#define PI          3.141592653589
#define bs(v,n)     binary_search(all((v)),(n))
#define lb(v,n)     lower_bound(all((v)),(n))
#define ub(v,n)     upper_bound(all((v)),(n))
#define fo(i,l,u)   for(i=l;i<u;i++)
#define rfo(i,l,u)  for(i=l;i>=u;i--)
#define allfo(s)    for(auto it=(s).begin();it!=(s).end();it++)
#define _init(b)     memset(b,-1,sizeof(b))
#define _init0(b)     memset(b,0,sizeof(b))
#define MOD         1000000007
#define ef else if



using namespace std;

int gcd(int a, int b) {  if (a == 0)  return b; return gcd(b % a, a); }  
bool mod(double a,double b) {return a/b - floor(a/b);}

int occurs(vi v,int n){
auto it=lb(v,n);auto it1=ub(v,n);int x=it1-it;return x;}

int logb(int base, int x) {
    return (log(x) / log(base));
}



signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int i,j,x,a,b,c;
    
    cin>>a>>b>>c;
    if((a-b)>c)cout<<0;
    else cout<<c+(b-a);
    
    return 0;
}

Measured memory_bytes: 256
from collections import Counter
N,K,Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
count = Counter(A)
f_p = [K-Q]*N
for k,v in count.items():
  f_p[k-1] += v
  
for ans in f_p:
  if ans >= 1:
    print('Yes')
  else:
    print('No')

Measured memory_bytes: 13944
#include <iostream>
#include <string>

using namespace std;

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

    const int ramen = 700;
    int topping = 0;
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] == 'o')
            ++topping;
    }
    cout << ramen + topping * 100 << '\n';
}


Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <complex>
typedef long long int LL;
using namespace std;

// 插入此處

int dp[1000006][2];

int main() {
    string s;
    cin >> s;
    int len = s.size();
    dp[0][1] = 1;
    for (int i = 0; i < len; i++) {
        int x = s[i] - '0';
        dp[i + 1][0] = min(dp[i][0] + x, dp[i][1] + 10 - x);
        dp[i + 1][1] = min(dp[i][0] + x + 1, dp[i][1] + 9 - x);
    }
    cout << dp[len][0] << endl;
}


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

int main() {
	ll N,x=0,s=0;
	bool ok=1;

	cin >> N;
	vector<ll> A(N+1),m(N+1,0),r(N+1,0),p(N+1);
	rep(i,N+1)
		cin >> A.at(i);

	if(N == 0) {
		if(A.at(0) == 1)
			cout << 1;
		else
			cout << -1;
		cout << endl;
		return 0;
	}
	
	m.at(N) = A.at(N);
	rep(i,N) {
		m.at(N-i-1) = m.at(N-i)+A.at(N-i-1);
	}

	// rep(i,N+1)
	// 	cout << m.at(i) << endl;

	r.at(0) = 1;
	p.at(0) = r.at(0)-A.at(0);
	// cout << r.at(0) << " " << p.at(0) << endl;

	rep(i,N-1) {
		r.at(i+1) = min(m.at(i+1), p.at(i)*2);
		p.at(i+1) = r.at(i+1)-A.at(i+1);

		if(p.at(i+1) < 0) {
			ok = 0;
			break;
		}

		// cout << r.at(i+1) << " " << p.at(i+1) << endl;
	}

	if(p.at(N-1)*2>=A.at(N) && p.at(N-1)<=A.at(N))
		r.at(N) = A.at(N);
	else
		ok = 0;

	rep(i,N+1)
		x += r.at(i);
	cout << ((ok) ? x : -1) << endl;
}

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

#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
using ll = long long;
using ull = unsigned long long;
constexpr int MOD = 1000000007;
using us = unsigned short;

int mod(int x){
	return x % MOD;
}

int main(void)
{
    IOS
    constexpr int N = 50 + 1;
    constexpr int X = 50;
    // dp[rep][平均]=組み合わせ数
    int n,a; cin >> n >> a;
    vector<map<ll,ll>> dp(n+1);
    REP(i,n+1) {
        FOR(j,-N*X,N*X+1) dp[i][j]=0;
    }

    vector<int> v(n+1);
    FOR(i,1,n+1) {
        cin >> v[i];
        v[i] -=a;
    }

    dp[1][v[1]] = 1;
    FOR(i,2,n+1) {
        //cerr << v[i] << endl;
        FOR(j,-X*i,X*i+1) {
            dp[i][j+v[i]] = dp[i-1][j] + dp[i-1][j+v[i]];
        }
        //cerr << dp[i][0] << endl;
        dp[i][v[i]]++;
    }
    
    cout << dp[n][0] << endl;

    return 0;
}


Measured memory_bytes: 16512
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 1010;
const int MOD = 1e9 + 7;
int a, bx, cx, by, cy;
char s[N][N];
int h, w;
LL k;
struct mat {int d[2][2];};
mat operator * (mat a, mat b)
{
    mat c = (mat){{{0, 0}, {0, 0}}};
    for (int i = 0; i < 2; ++ i)
        for (int j = 0; j < 2; ++ j)
            for (int k = 0; k < 2; ++ k)
                c.d[i][j] = (c.d[i][j] + 1ll * a.d[i][k] * b.d[k][j]) % MOD;
    return c;
}
mat operator ^ (mat a, LL b)
{
    mat c = (mat){{{1, 0}, {0, 1}}};
    for (; b; b >>= 1, a = a * a)
        if (b & 1) c = c * a;
    return c;
}
int main()
{
    scanf("%d%d%lld", &h, &w, &k);
    for (int i = 0; i < h; ++ i)
        scanf("%s", s[i]);
    for (int i = 0; i < h; ++ i)
        if (s[i][0] == s[i][w - 1] && s[i][0] == '#')
            cx ++;
    for (int i = 0; i < w; ++ i)
        if (s[0][i] == s[h - 1][i] && s[0][i] == '#')
            cy ++;
    for (int i = 0; i < h; ++ i)
        for (int j = 0; j < w - 1; ++ j)
            if (s[i][j] == s[i][j + 1] && s[i][j] == '#')
                bx ++;
    for (int i = 0; i < h - 1; ++ i)
        for (int j = 0; j < w; ++ j)
            if (s[i][j] == s[i + 1][j] && s[i][j] == '#')
                by ++;
    for (int i = 0; i < h; ++ i)
        for (int j = 0; j < w; ++ j)
            if (s[i][j] == '#')
                a ++;
        mat G;
    if (!k) return puts("1"), 0;
    else if (cx && cy) return puts("1"), 0;
    else if (cx) G = (mat){{{a, bx}, {0, cx}}};
    else if (cy) G = (mat){{{a, by}, {0, cy}}};
    else G = (mat){{{a, 0}, {0, 0}}};
    G = G ^ (k - 1);
    printf("%d\n", (G.d[0][0] - G.d[0][1] + MOD) % MOD);
}


Measured memory_bytes: 1280
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String text = in.next();
        in.close();
        boolean u = text.contains("N");
        boolean d = text.contains("S");
        boolean r = text.contains("E");
        boolean l = text.contains("W");
        String dis = !(u ^ d) && !(r ^ l) ? "Yes" : "No";
        System.out.println(dis);
    }
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repv(i,a,b) for(ll i=b-1;i>=a;i--)
#define MAXN 300005
#define endl "\n"

ll power(ll x,ll y){ll res=1; while(y>0){if(y&1) res=res*x;y=y>>1;x=x*x;}return res;}

ll n,w,dp[105][100005],a,b;
ll wt[105],v[105];

int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>w;
    for(ll i=1;i<=n;i++) cin>>wt[i]>>v[i];
    for(ll i=1;i<=n;i++)
    {
        for(ll j=1;j<=w;j++)
        {
            if(j-wt[i]>=0)
            {
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-wt[i]]+v[i]);
            }
            else dp[i][j]=dp[i-1][j];
        }
    }
    cout<<dp[n][w]<<endl;
}

Measured memory_bytes: 79360
"use strict";

function main(input) {
  input = input.trim().split(" ");
  const K = parseInt(input[0]);
  const X = parseInt(input[1]);
  const coin = 500;
  if (coin * K >= X) {
    console.log("Yes");
  } else {
    console.log("No");
  }
}

main(require("fs").readFileSync("/dev/stdin", "utf-8"));


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

typedef long long ll;
const ll MOD = 1e9 + 7;
const long long INF = 1LL<<60;
const double PI=3.14159265358979323846;
const int NMAX=100005;
using namespace std;


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

    string ans = "";
    while(n > 0){
        n -= 1;
        char p = 'a'+(n%26);
        ans = p+ans;
        n/=26;
    }

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

Measured memory_bytes: 3624
#pragma once
#include <stdio.h>
#include <sstream>
#include <string>
#include <string.h>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <limits>
#include <iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define bit(x,v) ((ll)x << v)

const ll INF = 1000000007;
const int MAX = 210000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
int pr[100010];
void uini(int n) {
	for (size_t i = 0; i <= n; i++)
	{
		pr[i] = i;
	}
}

int parent(int x) {
	if (x == pr[x]) return x;
	return pr[x] = parent(pr[x]);
}

bool unit(int x, int y) {
	int px = parent(x);
	int py = parent(y);

	if (px == py) return false;
	if (px < py) {
		pr[py] = px;
	}
	else {
		pr[px] = py;
	}
	return true;
}

// res[i][c] := i 文字目以降で最初に文字 c が登場する index (存在しないときは n)
vector<vector<int> > calcNext(const string& S) {
	int n = (int)S.size();
	vector<vector<int> > res(n + 1, vector<int>(26, n));
	for (int i = n - 1; i >= 0; --i) {
		for (int j = 0; j < 26; ++j) res[i][j] = res[i + 1][j];
		res[i][S[i] - 'a'] = i;
	}
	return res;
}

void solv() {
	
	ll k, s;
	cin >> k >> s;
	s /= 1000;
	for (ll x = 0; x <= k; x++)
	{
		for (ll y = 0; y <= k; y++)
		{
			ll v = s - x * 10 - y * 5;
			if (v >= 0 && v + x + y == k) {
				cout << x << " " << y << " " << v << endl;
				return;
			}
		}
	}
	cout << -1 << " " << -1 << " " << -1 << endl;

}

int main() {
	COMinit();
	solv();

	return 0;
}
 

Measured memory_bytes: 5120
#include <stdio.h>
int main(){
    int a,b,c;
    scanf("%d %d %d",&a,&b,&c);
    if(a<=b && b<=c){
        printf("%d %d %d\n",a,b,c);
    }else if(a<=c && c<=b){
        printf("%d %d %d\n",a,c,b);
    }else if(b<=a && a<=c){
        printf("%d %d %d\n",b,a,c);
    }else if(b<=c && c<=a){
        printf("%d %d %d\n",b,c,a);
    }else if(c<=a && a<=b){
        printf("%d %d %d\n",c,a,b);
    }else if(c<=b && b<=a){
        printf("%d %d %d\n",c,b,a);
    }
}


Measured memory_bytes: 2708
import java.util.Scanner;

public class Main {


    public static void main(String[] args) {
        int W, H, x, y, r, xr, yr;
      Scanner sc = new Scanner(System.in);
       W = sc.nextInt();
       H = sc.nextInt();
       x = sc.nextInt();
       y = sc.nextInt();
       r = sc.nextInt();
      xr = x + r;
      yr = y + r;
     
      if (x<=-1|| y<=-1||xr>W || yr>W|| xr>H||yr>H){
      System.out.println("No");
      }
      else System.out.println("Yes");
    }
    }
    


Measured memory_bytes: 26236
#include <stdio.h>

int main(void)
{
	int w, n;
	int tate[30];
	int i, j, temp;
	int a, b;
	
	scanf("%d", &w);
	scanf("%d", &n);
	
	for (i = 1; i <= 30; i++){
		tate[i - 1] = i;
	}
	
	for (i = 0; i < n; i++){
		scanf("%d,%d", &a, &b);
		
		temp = tate[a - 1];
		tate[a - 1] = tate[b - 1];
		tate[b - 1] = temp;
	}
	
	for (i = 0; i < w; i++){
		printf("%d\n", tate[i]);
	}
	
	return (0);
}

Measured memory_bytes: 0
#include <algorithm>
#include <complex>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::endl;

using std::string;
using std::to_string;
using std::vector;
using std::set;
using std::queue;
using std::priority_queue;

using std::min;
using std::max;
using std::sort;
using std::abs;

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define ll long long 
int ctoi(char c) {return c-'0';}/*char to int*/
int gcd(ll a,ll b){return b?gcd(b,a%b):a;}/*MAX*/
int lcm(ll a,ll b){return a*b/gcd(a,b);}/*MIN*/
bool primecheck(ll n){/*sosuu*/if(n < 2) return false;else{for(int i = 2; i * i <= n; i++){if(n % i == 0) return false;}return true;}}
string  reverserange(string s,ll a,ll b){reverse(s.begin()+a-1,s.begin()+b); return s;}
int  main(){
int n;
cin >> n;
map<int,int>ma;
for(int i=0;i<n;i++){
  int z;
  cin >> z;
  if(ma.count(z))ma.at(z)++;
  else ma[z]=1;
}
int  ans = 0;
for(auto p:ma){
    int x=p.first;
    int n = p.second;
    if(n<x)ans+=n;
    else ans+=n-x;
}
cout << ans << endl;
}





Measured memory_bytes: 4736